Greedy randomized adaptive search procedures

Mauricio G.C. Resende (mgcrresearch.att.com)
Celso C. Ribeiro (celsoinf.puc-rio.br)

Abstract: GRASP is a multi-start metaheuristic for combinatorial 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 and parameter tuning strategies 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: Reactive GRASP, cost perturbations, bias functions, memory and learning, local search on partially constructed solutions, hashing, and filtering. We also discuss in detail implementation strategies of memory-based intensification and post-optimization techniques using path-relinking. Hybridizations with other metaheuristics, parallelization strategies, and applications are also reviewed.

Keywords: GRASP, metaheuristic, combinatorial optimization

Category 1: Combinatorial Optimization (Meta Heuristics )

Citation: AT&T Labs Research Technical Report, Sept. 2001. Revision 2, Aug. 29, 2002. To appear in "State of the Art Handbook in Metaheuristics", F. Glover and G. Kochenberger, eds., Kluwer, 2002.

Download: [PDF]

Entry Submitted: 09/13/2001
Entry Accepted: 09/13/2001
Entry Last Modified: 08/29/2002

Modify/Update this entry