×

Tabu search applied to the quadratic assignment problem. (English) Zbl 0752.90054

Summary: 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 problem 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.

MSC:

90C20 Quadratic programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C10 Integer programming
90C09 Boolean programming
90B10 Deterministic network models in operations research
PDFBibTeX XMLCite
Full Text: DOI