An Intensive Search Algorithm for the Quadratic Assignment Problem

Article type: Research Article

Authors: Misevičius, Alfonsas

Affiliations: Kaunas University of Technology, Studentų St. 50-416D, LT-3031 Kaunas, Lithuania. E-mail: misevi@soften.ktu.lt

Abstract: Many heuristics, such as simulated annealing, genetic algorithms, greedy randomized adaptive search procedures are stochastic. In this paper, we propose a deterministic heuristic algorithm, which is applied to the quadratic assignment problem. We refer this algorithm to as intensive search algorithm (or briefly intensive search). We tested our algorithm on the various instances from the library of the QAP instances – QAPLIB. The results obtained from the experiments show that the proposed algorithm appears superior, in many cases, to the well-known algorithm – simulated annealing.

Keywords: heuristics, intensive search, quadratic assignment problem

DOI: 10.3233/INF-2000-11204

Journal: Informatica, vol. 11, no. 2, pp. 145-162, 2000