The covering tour problem with path upgrades

Abstract

This work introduces the Covering Tour Problem with Path Upgrades (CTP-PU) where for a given graph and a cost associated with each arc, the objective is to find a minimum-cost tour that ensures coverage of all non-tour nodes. Unlike the classical Covering Tour Problem, the CTP-PU enables the upgrading of arcs within a budget. These upgraded arcs can be shared by multiple paths from non-tour nodes to the tour. As a result, more than one of these nodes can benefit from each upgrade, thereby extending coverage to previously unreachable nodes. This approach provides a more practical and cost-effective solution, particularly beneficial in scenarios like humanitarian aid and medical supply distribution where optimizing shared infrastructure enhances overall efficiency. To address the CTP-PU, we propose several Mixed-Integer Linear Programming formulations based on a different rationale for preventing subtours. We also introduce different families of valid inequalities to tighten these formulations and improve computational efficiency. In the case of formulations with an exponential number of constraints, we develop alternative variants of a Branch-and-Cut (B&C) procedure specifically designed for this type of problem. We perform extensive computational experiments using benchmark instances from the literature to evaluate the effectiveness of the proposed method. Our results demonstrate their efficiency and highlight the significant impact of the valid inequalities and B&C procedure on solution quality and computational time.