Upgrading arcs in the covering tour problem.
- Marta Baldomero-Naranjo
- Andrea Mancuso
- Adriano Masone
- Antonio Manuel Rodriguez-Chia
- Claudio Sterle
Éditorial: Technical University of Denmark (DTU),
ISBN: 978-87-93458-26-0
Année de publication: 2024
Pages: 329
Type: Communication dans un congrès
Résumé
In this study, we present the Covering Tour Problem with Arcs Upgrade (CTPAU). This problem is an extension of the Covering Tour Problem (CTP) that considers the possibility of enhancing the network by reducing the length of some arcs, i.e., upgrading them. Hence, upgrading an arc means reducing its length, usually within certain limits, at a given cost that is proportional to the extent of the upgrade. The CTPAU is formulated with three different sets of nodes, V, W, and, T that is a subset of V. Two decisions have to be made simultaneously: i) identify the tour of minimum length that passes through a subset of V, ensuring that all nodes of set T are included in the tour, and that each node in W is within a given coverage distance from a node on the tour, ii) decide with connections to upgrade. Therefore, the CTPAU seeks to identify the minimum length tour while integrating arc upgrading and a budget constraint. In this context, we present some MILP formulation and compare them to illustrate the potential and limitations of each one.