M. G. C. Resende and C.C. Ribeiro
To appear in Handbook of Metaheuristics, 2nd Edition, Springer.
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. In this chapter, we first describe the basic components of
GRASP. Successful implementation techniques are discussed and
illustrated by numerical results obtained for different applications.
Enhanced or alternative solution construction mechanisms and techniques
to speed up the search are also described: alternative randomized
greedy construction schemes, Reactive GRASP, cost perturbations, bias
functions, memory and learning, local search on partially constructed
solutions, hashing, and filtering. We also discuss implementation
strategies of memory-based intensification and post-optimization
techniques using path-relinking. Hybridizations with other
metaheuristics, parallelization strategies, and applications are also
reviewed.
PDF file
of full paper
Mauricio G.C. Resende's Home Page
Last modified: 20 August 2009