RT journal article
T1 The covering tour problem with path upgrades
A1 Baldomero Naranjo, Marta
A1 Mancuso, A.
A1 Masone, A.
A1 Rodríguez Chía, Antonio Manuel
A2 Estadística e Investigación Operativa
K1 Covering tour problem
K1 Mixed-integer linear programming
K1 Routing
K1 Upgrading
AB 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.
PB Elsevier Ltd
SN 1873-765X
YR 2026
FD 2026
LK http://hdl.handle.net/10498/40569
UL http://hdl.handle.net/10498/40569
LA eng
DS Repositorio Institucional de la Universidad de Cádiz
RD 15-nov-2026