Hybrid Metaheuristics for Solving the Quadratic Assignment Problem and the Generalized Quadratic Assignment Problem

• Main Authors: GUNAWAN, Aldy, Ng, Kien Ming, Poh, Kim Leng, LAU, Hoong Chuin
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2014
• Subjects: Artificial Intelligence and Robotics; Operations Research, Systems Engineering and Industrial Engineering
• Online Access: https://ink.library.smu.edu.sg/sis_research/2668; https://ink.library.smu.edu.sg/context/sis_research/article/3668/viewcontent/C112___Hybrid_Metahuristics_for_Solving_the_Quadratic_Assignment_Problem_and_the_Generalized_Quadratic_Assignment_Problem__CASE2014_.pdf
• Institution: Singapore Management University

This paper presents a hybrid metaheuristic for solving the Quadratic Assignment Problem (QAP). The proposed algorithm involves using the Greedy Randomized Adaptive Search Procedure (GRASP) to construct an initial solution, and then using a hybrid Simulated Annealing and Tabu Search (SA-TS) algorithm to further improve the solution. Experimental results show that the hybrid metaheuristic is able to obtain good quality solutions for QAPLIB test problems within reasonable computation time. The proposed algorithm is extended to solve the Generalized Quadratic Assignment Problem (GQAP), with an emphasis on modelling and solving a practical problem, namely an examination timetabling problem. We found that the proposed algorithm is able to perform better than the standard SA algorithm does.