The Covering Tour Problem with Edge Upgrade

  1. Marta Baldomero-Naranjo 2
  2. Andrea Mancuso 1
  3. Antonio Manuel Rodriguez-Chia 2
  4. Claudio Sterle 1
  1. 1 Department of Electrical Engineering and Information Technology, University of Naples Federico II, Naples, 80125, Italy
  2. 2 Departamento de Estadística e Investigación Operativa, Universidad de Cádiz, Facultad de Ciencias, Puerto Real (Cádiz), 11510, Spain
Proceedings:
8th AIROYoung Workshop

Publisher: -

Year of publication: 2024

Pages: 62

Type: Conference paper

GOOGLE SCHOLAR

Abstract

In this study, we present the Covering Tour Problem with Edge Upgrade(CTPEU). The CTPEU is an extension of the Covering Tour Problem (CTP) thatexploits the potential of enhancing the network by upgrading edges. The CoveringTour Problem (CTP) is formulated with three distinct nodes sets, V, W, and, T ⊆ V.Its objective is to identify the minimum length tour passing through a subset of V,ensuring that all nodes in the set T are included in the tour, and each node in W iswithin a given coverage distance from a node on the tour. Upgrading an edge herebymeans reducing its length, usually within certain limits, at a given cost which is proportional to the extent of the upgrade. Therefore, the CTPEU seeks to identify theminimum length tour while integrating edge upgrading and budgetary constraints.In this context, we present three MILP formulations for the CTPEU differing in theway subtours are tackled. The proposed formulations have been experienced andcompared on TSPLib instances in terms of optimality gap and computation time.