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.
Citation
AT&T Labs Research Technical Report, Shannon Laboratory, 180 Park Avenue, Florham Park, NJ 07932 USA February 2001