An Empirical Study of Extended Guided Local Search on the Quadratic Assignment Problem

Abstract. In this paper, we show how an Extended Guided Local Search can be applied to the Quadratic Assignment Problem and show the extensions can improve its performance. GLS is a general, penalty-based meta-heuristic, which sits on top of local search algorithms, to help guide them out of local minima. GLS has been shown to be successful in solving a number of practical real life problems, such as the travelling salesman problem, BT’s workforce scheduling problem, the radio link frequency assignment problem, the SAT problem, the weighted MAX-SAT problems, and the vehicle routing problem. We present empirical results of applying several extended versions of Guided Local Search to the Quadratic Assignment Problem, and show that these extensions can improve the range of parameter setting within which Guided Local Search performs well. Finally, we compare the results of running our Extended Guided Local Search with some state of the art algorithms for the QAP.