A Modified Simulated Annealing Algorithm for the Quadratic Assignment Problem

Article type: Research Article

Authors: Misevičius, Alfonsas

Affiliations: Department of Practical Informatics, Kaunas University of Technology, Studentų 50–400a, LT‐3031 Kaunas, Lithuania, e‐mail: misevi@soften.ktu.lt

Abstract: The quadratic assignment problem (QAP) is one of the well‐known combinatorial optimization problems and is known for its various applications. In this paper, we propose a modified simulated annealing algorithm for the QAP – M‐SA‐QAP. The novelty of the proposed algorithm is an advanced formula of calculation of the initial and final temperatures, as well as an original cooling schedule with oscillation, i.e., periodical decreasing and increasing of the temperature. In addition, in order to improve the results obtained, the simulated annealing algorithm is combined with a tabu search approach based algorithm. We tested our algorithm on a number of instances from the library of the QAP instances – QAPLIB. The results obtained from the experiments show that the proposed algorithm appears to be superior to earlier versions of the simulated annealing for the QAP. The power of M‐SA‐QAP is also corroborated by the fact that the new best known solution was found for the one of the largest QAP instances – THO150.

Keywords: heuristics, local search, simulated annealing, quadratic assignment problem

Journal: Informatica, vol. 14, no. 4, pp. 497-514, 2003