Optimization Online


Hybridizations of GRASP with path-relinking

Paola Festa(paola.festa***at***unina.it)
Mauricio G. C. Resende(mgcr***at***research.att.com)

Abstract: A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. GRASP heuristics are multistart procedures which apply local search to a set of starting solutions generated with a randomized greedy algorithm or semi-greedy method. The best local optimum found over the iterations is returned as the heuristic solution. Path-relinking is a search intensification procedure that explores paths in the neighborhood solution space connecting two good-quality solutions. A local search procedure is applied to the best solution found in the path and the local optimum found is returned as the solution of path-relinking. The hybridization of path-relinking and GRASP adds memory mechanisms to GRASP. This paper describes basic concepts of GRASP, path-relinking, and the hybridization of GRASP with path-relinking.

Keywords: GRASP, path-relinking, GRASP with path-relinking, metaheuristic, local search, parallel computing, combinatorial optimization, discrete mathematics

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Meta Heuristics )

Citation: AT&T Labs Research Technical Report, Florham Park, NJ 07733 USA, October 2011.

Download: [PDF]

Entry Submitted: 11/18/2011
Entry Accepted: 11/18/2011
Entry Last Modified: 11/18/2011

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society