New results in the covering tour problem with edge upgrades

Résumé

This talk addresses a version of the Covering Tour Problem, a covering problem within the context of location decision problems combined with a routing problem. This version considers that the edges can be upgraded subject to a budget constraint. Therefore, the goal is to find a minimum length tour that cover all the nodes of a graph taking into account that some edges can be upgraded. Introduction. Routing problems are a class of problems focused on finding the most effective way to move goods, people, or information from one point to another. The primary objective is often to minimize travel time, distance, or operational costs while adhering to various constraints and requirements. These problems are central to many industries, including logistics, supply chain management, and transportation. Among these routing problems, one of the most fundamental is the Traveling Salesman Problem (TSP). The TSP involves finding the shortestpossible route that allows a salesman to visit each city in a given list exactly once and return to the origin city, see.Coverage problems arise when it is necessary to determine the optimal location of one or morefacilities for the production of goods or the provision of services, with the goal of meetingthe demand for goods or services at various nodes. The main objective is to minimize theplacement costs of facilities or maximize the coverage of demand points. For each facility, acoverage radius is defined, representing the distance within which the demand for goods orservices can be satisfied.Combining TSP and convering problems is obtained the covering tour problem (CTP). Thisproblem aims to determine a minimum lengh tour over a subset of nodes that can be visited,in such a way that the tour contains all these nodes, and every node is covered by the tour, see.The goal of this talk is to analyze the covering tour problem with edge upgrading (CTPEU).This problem is an extension of the CTP where we consider the possibility of upgrading edges.It combines the routing aspect seen in the TSP, the covering part of the CTP, and additionally allows for the possibility of updating edges, similar to the Maximal Covering Problem with Edge Upgrade, see. Edge upgrading consists in reducing their length (travel time), typically within certain limits, at a given cost that is proportional to the upgrade. The total cost of all upgrades is subject to a budget constraint. On this basis, the CTPEU involves finding a tour of minimum length subject to covering and budget constraints.