20 years of GRASP with Path Relinking

A. Martinez Gavara, R. Marti, S. Pérez Peló, M. Laguna, M. Resende

In this talk, we present a thorough examination of the hybridization of two metaheuristic optimization methods: Greedy Randomized Adaptive Search Procedure and Path Relinking (PR). This hybrid methodology has gained the interest of researchers as a highly effective and versatile approach for tackling hard optimization problems. The talk covers the historical development of GRASP with PR over the last two decades, its underlying theoretical foundations, as well as recent advancements in its implementations. Our main contribution is to provide a critical analysis of the different PR variants and search strategies, including forward and backward, neighborhood selection, truncated, internal and external, and greedy randomized PR; shedding light on their distinct characteristics and performance. The empirical analysis of these elements and strategies with two different optimization problems, allows us to establish the most appropriate hybridizations according to the optimization problem.

Keywords: metaheuristics, combinatorial optimization, GRASP, Path Relinking

GT10.HEUR3 Invited Session
November 8, 2023  5:20 PM
CC3: Room 1

D. Valero Carreras, J. Alcaraz Soria, M. Landete

J. M. Carretero Ávila

M. Robles Rodríguez, S. Cavero Díaz, E. G. Pardo

S. Pérez Peló, J. Sánchez-Oro, A. Martínez-Gavara, R. Marti, A. Duarte