EURO 2025 Leeds
Abstract Submission

1323. GRASP WITH PATH RELINKING. An analytical review

Invited abstract in session TA-15: Heuristic Search 1, stream Combinatorial Optimization.

Tuesday, 8:30-10:00
Room: Esther Simpson 1.08

Authors (first author is the speaker)

1. Rafael Marti
Departamento de Estadística e Investigación Operativa, Universitat de València
2. Manuel Laguna
Leeds School of Business, University of Colorado Boulder
3. Anna Martínez-Gavara
Estadística i Investigació Operativa, Universitat de València
4. Sergio Pérez-Peló
Informática y Estadística, Universidad Rey Juan Carlos
5. Mauricio Resende
Industrial and Systems Engineering, University of Washington

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 talk covers the historical development of GRASP with PR and its theoretical foundations, as well as recent advances in its implementation and application. It identifies the design questions that are still open in the scientific literature. The experimental part 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 talk also explores the hybridization of PR and other metaheuristics, such as tabu search, scatter search, and random-keys genetic algorithms.

Keywords

Status: accepted

Back to the list of papers