INFORMS J. on Computing, vol. 17, no. 2, pp. 224-247, 2005
ABSTRACT
This paper describes variants
of GRASP (greedy randomized adaptive search procedure) with path
relinking for the three index assignment problem (AP3). GRASP is
a
multi-start 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 and Saltzman (1991),
Burkard, Rudolf, and Woeginger (1996), and Crama and Spieksma (1992) 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.
PDF file of
full paper