To appear in "Metaheuristics: Progress as Real Problem Solvers," T. Ibaraki, K. Nonobe and M. Yagiura, (Eds.), Kluwer Academic Publishers, 2005.
ABSTRACT
Path-relinking is a major enhancement to the basic
greedy randomized adaptive search procedure (GRASP), leading to
significant improvements in solution time and quality. Path-relinking
adds a memory mechanism to GRASP by providing an intensification
strategy that explores trajectories connecting GRASP solutions and the
best elite solutions previously produced during the search. This
paper reviews recent advances and applications of GRASP with
path-relinking. A brief review of GRASP is given. This is
followed by a description of path-relinking and how it is incorporated
into GRASP. Several recent applications of GRASP with
path-relinking are reviewed. The paper concludes with a
discussion of extensions to this strategy, concerning in particular
parallel implementations and applications of path-relinking with other
metaheuristics.
PDF file of full paper