A hybrid algorithm for the quadratic assignment problem

Abstract

The quadratic assignment problem is known to be NP-hard and we propose a new hybrid algorithm to solve this problem. The proposed algorithm involves using the Greedy Randomized Adaptive Search Procedure (GRASP) to obtain an initial solution, and then using a combined Simulated Annealing (SA) and Tabu Search (TS) algorithm to improve the solution. Computational results on applying the proposed hybrid algorithm to QAPLIB test problems indicate that this algorithm can obtain good quality solutions for the quadratic assignment problem within reasonable computation time.