GRASP with path-relinking: Recent advances and applications

M.G.C. Resende and C.C. Ribeiro

To appear in "Metaheuristics: Progress as Real Problem Solvers,"  T. Ibaraki, K. Nonobe and M. Yagiura, (Eds.), Kluwer Academic Publishers,  2005.


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

DjVu file of full paper

Go back

Mauricio G.C. Resende's Home Page

Last modified: 12 October 2004