Hybrid Metaheuristics for Solving the Quadratic Assignment Problem and the Generalized Quadratic Assignment Problem
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...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | text |
| Language: | English |
| Published: |
Institutional Knowledge at Singapore Management University
2014
|
| Subjects: | |
| 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 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Singapore Management University |
| Language: | English |
| Summary: | 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. |
|---|