Greedy Randomized Adaptive Search Procedures with Path Relinking. An analytical review of designs and implementations

Manuel Laguna, Rafael Martí, Anna Martínez-Gavara, Sergio Pérez-Peló and Mauricio G.C. Resende

European Journal of Operational Research, 2025, vol. 327, issue 3, 717-734

Abstract: This is a comprehensive review of the Greedy Randomized Adaptive Search Procedure (GRASP) metaheuristic and its hybridization with Path Relinking (PR). GRASP with PR has become a widely adopted approach for solving hard optimization problems since its proposal in 1999. The paper covers the historical development of GRASP with PR and its theoretical foundations, as well as recent advances in its implementation and application. The review includes a careful analysis of PR variants, paying special attention to memory-based and randomized designs, with a total of ten different implementations. It identifies the design questions that are still open in the scientific literature. The experimental section applies advanced PR implementations on two well-known combinatorial optimization problems, linear ordering and max-cut, in an effort to answer these open questions. The paper also explores the hybridization of PR and other metaheuristics, such as tabu search, scatter search, and random-keys genetic algorithms. Overall, this review provides valuable insights for researchers and practitioners seeking to implement GRASP with PR for solving optimization problems.

Keywords: Hybrid heuristics; GRASP; Path Relinking; Review (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725001456
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:327:y:2025:i:3:p:717-734

DOI: 10.1016/j.ejor.2025.02.022

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().