A Multistart Simulated Annealing Algorithm for the Quadratic Assignment Problem

Quadratic assignment problem (QAP) is a hard and classical combinatorial optimization problem. Simulated annealing algorithm has been successfully applied to solve QAP. However, the search of simulated annealing algorithm might usually get stuck with local optima due to the low acceptable moves, particularly when the barrier is high and the temperature is low. In this paper, we propose a tabu-based simulated annealing algorithm with a new restart strategy for solving the quadratic assignment problem. By using the controlling diversification mechanism, a search might be easily escaped from local optima and then can be restarted with a new diversified point. Performance evaluation has been carried on comparing the new strategy with two different restart strategies. Experimental results show that our new restart strategy is a promising approach for diversifying the search of simulated annealing heuristics.