Hybridizations of GRASP with path-relinking

P. Festa and M. G. C. Resende

in Hybrid Metaheuristics, E-G. Talbi, Editor, Studies in Computational Intelligence, vol. 434, pp. 135-155, 2013, Springer.


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

PDF file of full paper

DjVu file of full paper
Mauricio G.C. Resende's Home Page
Last modified:  5 August 2013

Copyright Notice