The Covering Tour Problem with Arc Upgrades

In this study, we introduce the Covering Tour Problem with Arc Upgrade (CTPAU), an extension of the Covering Tour Problem (CTP) that exploits the possibility of enhancing the network by upgrading arcs. The CTP is defined on a graph consisting of three sets of nodes: those requiring coverage, those eligible to provide coverage, and a subset of the latter which must be visited. The objective is to determine the minimum cost tour that complies with both visiting and covering requirements. We introduce a further aspect on the problem given by the possibility of arc upgrades. Such upgrades decrease the length of an arc, usually within specific limits, incurring a cost directly proportional to the degree of reduction. Thus, the CTPAU aims to determine the minimum cost tour that meets the CTP requirements and incorporates the possibility of upgrading arcs, satisfying a budget constraint. To address this problem, we developed a Mixed Integer Linear Programming formulation and conducted experiments on benchmark instances from TSPLIB to assess our approach.