Solving quadratic assignment problems by a tabu based simulated annealing algorithm

The quadratic assignment problem (QAP) is a hard and classical combinatorial optimization problem. In this paper a hybrid algorithm that combines the simulated annealing (SA) and tabu search (TS) is proposed to solve the QAP. The search of simulated annealing may stuck at a local optimum due to the low acceptable moves, particularly as the barrier is high and the temperature is low. A guided restart strategy is incorporated into SA to escape from a local optimum and re-annealing from a promising point more efficiently. The tabu list, as a short-term memory, is used in the move generation procedure to prohibit the highly frequent moves and diversify the search. Performance evaluation has been carried out on several problem instances in the QAPLIB. Experimental results indicate that these two strategies significantly improve the performance of simulated annealing algorithm.