EXPERIMENTS WITH TABU SEARCH FOR RANDOM QUADRATIC ASSIGNMENT PROBLEMS

Abstract

Tabu search (TS) is a modern highly effective meta-heuristic for solving various optimization problems. In this paper, we discuss some enhancements of TS for one of the difficult combinatorial optimization problems − the quadratic assignment problem (QAP). We implemented five variants (modifications) of TS for the random QAP instances from the library of the QAP instances QAPLIB. These random QAPs pose a real challenge for the researchers. A number of the experiments were carried out on these instances. The results obtained from the experiments demonstrate the outstanding efficiency of the modifications proposed. These modifications seem to be superior to the earlier TS algorithms for the QAP. In addition, the new best known solution has been achieved for the instance tai100a.