Machine Learning-Guided Matheuristics for the Covering Tour Problem with Path Upgrades

D. Amitrano, M. Baldomero Naranjo, M. Boccia, A. Mancuso, A. Masone, A. M. Rodríguez Chía, C. Sterle

The Covering Tour Problem (CTP) consists of finding a minimum-cost tour over a subset of nodes such that all nodes not in the tour are covered (i.e., within a fixed distance of a tour stop). This work addresses the Covering Tour Problem with Path Upgrades (CTP-PU), which introduces the option to upgrade network arcs within a budget. Moreover, these upgrades allow multiple non-tour nodes to share improved infrastructure.

To solve this NP-hard problem, we propose a matheuristic guided by supervised machine learning. We use classification models to predict node roles, identifying whether a node should be part of the tour or remain covered. Using these predictions, our algorithm finds high-quality solutions significantly faster than exact methods.

Palabras clave: Covering Tour Problem, Upgrading, Matheuristic

GT GELOCA 3: Covering models and clustering approaches in location
4 de septiembre de 2026  11:10
Aula B

A. MANCUSO, A. M. Rodríguez Chía, F. Saldanha-da-Gama, C. Sterle

C. Domínguez-Bravo, E. Fernández, A. Lüer Villagra

L. Nácher, M. Baldomero Naranjo, M. Landete, M. Leal

C. Valverde Martín, J. Puerto Albandoz, L. Amorosi, P. Dell'Olmo