-

 

 

 




Optimization Online





 

GRASP: Advances and applications

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. 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.

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

 

Submit
Update
Policies
Coordinator's Board
Classification Scheme
Credits
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society