Article ID: | iaor2007392 |
Country: | United States |
Volume: | 17 |
Issue: | 2 |
Start Page Number: | 224 |
End Page Number: | 247 |
Publication Date: | Mar 2005 |
Journal: | INFORMS Journal On Computing |
Authors: | Resende Mauricio G.C., Toraldo Gerardo, Pardalos Panos M., Aiex Renata M. |
Keywords: | heuristics, computational analysis: parallel computers |
This paper proposes and tests variants of GRASP (greedy randomized adaptive search procedure) with path relinking for the three-index assignment problem (AP3). GRASP is a multistart metaheuristic for combinatorial optimization. It usually consists of a construction procedure based on a greedy randomized algorithm and of a local search. Path relinking is an intensification strategy that explores trajectories that connect high-quality solutions. Several variants of the heuristic are proposed and tested. Computational results show clearly that this GRASP for AP3 benefits from path relinking and that the variants considered in this paper compare well with previously proposed heuristics for this problem. GRASP with path relinking was able to improve the solution quality of heuristics proposed by Balas & Saltzman, Burkard