Optimization Online


GRASP and path-relinking: Recent advances and applications

Maurício Resende (mgcr***at***research.att.com)
Celso Ribeiro (celso***at***inf.puc-rio.br)

Abstract: 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.

Keywords: GRASP, path relinking, metaheuristics

Category 1: Combinatorial Optimization (Meta Heuristics )

Citation: Tutorial presented at the V Metaheuristics International Conference, Kyoto, Japan, August 2003.

Download: [Postscript]

Entry Submitted: 10/12/2003
Entry Accepted: 10/12/2003
Entry Last Modified: 10/12/2003

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society