M. G. C. Resende and C.C. Ribeiro
Submitted to Search Methodologies, 2nd Edition, 2008.
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.
PDF file
of full paper
Mauricio G.C. Resende's Home Page
Last modified: 7 July 2008