A matheuristic approach for the Set Orienteering Problem

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

The Set Orienteering Problem (SOP) is a generalization of the well-known Orienteering Problem (OP). The OP consists of determining the tour from an origin to a destination in a graph, visiting some of them in a way that the total travel cost does not exceed a pre-established limit, and in order to maximize the profit of the visited locations. In the SOP, the customers are grouped in clusters/sets, and the profit of all the customers of the set are collected by visiting at least one of the customers in the respective cluster. In addition, the point of origin and destination are the same one. In this problem, Construct, Merge, Solve and Adapt (CMSA) methodology combined with a Greedy Randomized Adaptive Search Procedure (GRASP) constructive procedure for solving the SOP.

Keywords: GRASP, CMSA, Matheuristics

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

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