Optimization Online



Mauricio G. C. Resende(mgcr***at***research.att.com)
Celso C. Ribeiro(celso***at***ic.uff.br)

Abstract: GRASP is a multi-start metaheuristic for combinatorial optimization problems, in which each iteration consists basically of two phases: construction and local search. The construction phase builds a feasible solution, whose neighborhood is investigated until a local minimum is found during the local search phase. The best overall solution is kept as the result. An intensification strategy based on path-relinking is frequently used to improve solution quality and to reduce computation times by exploring elite solutions previously found along the search. This chapter describes the basic components of GRASP, successful implementation strategies, and effective hybridizations with path-relinking and other metaheuristics. We also list some tricks to be used in the quest for good implementations. The bibliography is enriched by an account of relevant applications and by links to surveys, software, and additional sources of material.

Keywords: GRASP, metaheuristics, hybrid heuristics, heuristics

Category 1: Combinatorial Optimization (Meta Heuristics )

Citation: AT&T Labs Research Technical Report, AT&T Labs Research, Florham Park, NJ 07932 USA, July 2008.

Download: [PDF]

Entry Submitted: 07/08/2008
Entry Accepted: 07/11/2008
Entry Last Modified: 07/08/2008

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