GRASP with path relinking for three-index assignment

GRASP with path relinking for three-index assignment

0.00 Avg rating0 Votes
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: , , ,
Keywords: heuristics, computational analysis: parallel computers
Abstract:

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 et al., and Crama & Spieksma on all instances proposed in those papers. We show that the random variable ‘time to target solution,’ for all proposed GRASP with path-relinking variants, fits a two-parameter exponential distribution. To illustrate the consequence of this, one of the variants of GRASP with path relinking is shown to benefit from parallelization.

Reviews

Required fields are marked *. Your email address will not be published.