GRASP: Greedy Randomized Adaptive Search Procedures

M. G. C. Resende and C.C. Ribeiro 

Search Methodologies, 2nd Edition, E.K. Burke and G. Kendall (Eds.), Springer, Chapter 11, pp. 287-312, 2014.


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

Go back

Mauricio G.C. Resende's Home Page

Last modified: 3 December 2013

Copyright Notice