Machine Learning-Guided Matheuristics for the Covering Tour Problem with Path Upgrades
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