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.
Keywords: Covering Tour Problem, Upgrading, Matheuristic
Scheduled
GT GELOCA 3: Covering models and clustering approaches in location
September 4, 2026 11:10 AM
Aula B
Other papers in the same session
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