A greedy randomized adaptive search procedure (GRASP) is a multi-start metaheuristic which applies local search to starting solutions generated by a greedy randomized construction procedure. Until recently, most implementations of GRASP assumed independence of its iterations, thus making no use of memory structures. Path-relinking is an intensification strategy which explores trajectories between elite solutions. Using one or more elite solutions, paths in the solution space leading to other elite solutions are explored in the search for better solutions. To generate paths, moves are selected to introduce attributes in the current solution that appear in the elite guiding solution. We present recent advances and applications of GRASP with path-relinking. Starting from a basic template for implementing path-relinking in a GRASP, we discuss some extensions and enhancements. Applications to the Steiner problem in graphs, to the max-cut problem, to the three-index asignment problem, to private virtual circuit routing, to the 2-path network design problem, and to the job shop scheduling problem, among others, are discussed. Strategies for the implementation of parallel cooperative strategies combining GRASP and path-relinking are also illustrated. We conclude with some computational results, showing the benefits reaped with path-relinking.
Citation
Tutorial presented at the V Metaheuristics International Conference, Kyoto, Japan, August 2003.