Tabu Search Applied to the Quadratic Assignment Problem

This paper describes an adaptation of Tabu Search, a recent technique to overcome local optimality, to the Quadratic Assignment Problem (QAP). Computational experiments with different parameter values and different strategies have been performed for some QAPs from the literature and some randomly generated QAPs of dimensions varying between 42 and 90. The method is implemented in a flexible form which allows the user to interact and change the parameters (tabu list size, the iteration limit, a search diversification parameter and the number of new starting solutions) during the run. The results suggest that good tabu list sizes increase with dimension of the problem. The algorithm appears to be a very efficient method for QAPs: for the standard problems tested, the best known solutions were obtained using less CPU time than previously reported in the literature. For Steinberg's problem (n = 36) with rectangular distances, a better solution than previously known in the literature was obtained. In addition, in comparison with simulated annealing, tabu search appears to be superior with respect to the solution quality. INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.