Article ID: | iaor20022554 |
Country: | Brazil |
Volume: | 20 |
Issue: | 1 |
Start Page Number: | 45 |
End Page Number: | 58 |
Publication Date: | Jun 2000 |
Journal: | Pesquisa Operacional |
Authors: | Rangel M.C., Abreu N.M.M., Netto P.O. Boaventura |
Keywords: | heuristics, programming: assignment |
The Quadratic Assignment Problem (QAP) is an NP-hard problem which has been defying researchers both in theoretical aspects and in what concerns computational results. Owing to its high complexity, several heuristics have been developed trying to approximate its solution. The GRASP metaheuristic (greedy randomized adaptive search procedures) shows a good efficiency with it. In this work a proposal to discard initial supposedly bad initial solutions based on cost normalization is presented. A reduction of computational time to find optimal or near-optimal solutions was observed with this GRASP, when compared with the original version.