STAGNATION-PROTECTED TABU SEARCH VARIANTS FOR UNSTRUCTURED QUADRATIC ASSIGNMENT PROBLEMS

Abstract

Tabu search (TS) algorithms have been proven to be extremely efficient for solving combinatorial optimization problems. In this paper, we discuss new variants of the tabu search for the well-known combinatorial problem, the quadratic assignment problem (QAP). In particular, a so-called stagnation-protected tabu search (SPTS) strategy is proposed. The goal is to fight against the chaotic behaviour and stagnation phenomenon, especially at long runs of TS. SPTS seems to be quite useful for the unstructured (random) quadratic assignment problems. These problems, which resemble a "needle-in-a-haystack" problem, are hardly solvable by the ordinary heuristic algorithms and still remain a challenge for the QAP community. The results obtained from the experiments with SPTS on the unstructured QAPs taken from the QAP library QAPLIB demonstrate that this new strategy is superior to other tabu search algorithms.