Reula

Menú

Aumentar Tamaño del texto Disminuir Tamaño del texto

Miguel Reula, Universidad Carlos III de Madrid

13-05-2022

Generalizations of the Close-Enough Arc Routing Problem

 

Abstract:


Relevant technological innovations, such as new types of devices, radio frequency identification technology (RFID), and the availability of real-time data through geolocation, traffic flows or communication between customers and drivers, have led to numerous changes in the logistics business. At the same time, Operations Research has continued to evolve and this has required the definition and study of new problems, as well as the incorporation of new features to existing ones. In particular, the development of new technologies has given rise to scenarios in which the vehicle is not required to arrive at the customer's location in order to perform the service, but rather that it is sufficient to approach it. In routing problems this feature is called "close enough", since the vehicle only needs to pass close enough to the customer's position to perform the service. If, in the problem under study, customer service is modeled or performed on the arcs of a graph, we obtain what is known as the Close Enough Arc Routing Problem (CEARP).  This problem consists of finding a minimum cost route that starts and ends at a depot and traverses some of the streets of a road network in such a way that all customers are serviced.

One of the most direct applications of CEARP is in the automatic meter reading, since nowadays the operators of gas, water and electricity companies do not need to traverse all the streets of their customers to read the consumption of their meters. Other relevant applications of CEARP are, for example, inventory management in department stores, where drones are being used that only need to pass close enough to the products to inventory them, in network surveillance and maintenance tasks, as well as in robotic monitoring of wireless sensor networks.

On the basis of the CEARP that already existed in the literature, we have studied three different extensions of it: the Profitable CEARP, for a single vehicle, and the Distance-Constrained CEARP and the Min-Max CEARP, for multiple vehicles. In the first problem, the Profitable CEARP, each customer has associated a profit that is collected if the customer is serviced. In this problem not all customers have to be serviced, but only those more interesting from the point of view of the profit provided. In the second problem, the Distance-Constrained CEARP, the service is done by a fleet of vehicles with the maximum length or time for their routes, and the objective is to minimize the total traversed length. Finally, the Min-Max CEARP also considers a fleet of vehicles to service all the customers but in this case the length of the longest route is minimized in order to balance the length of the planned routes. For each of these extensions, a detailed study of the problem has been carried out, and different heuristic and exact algorithms have been designed and implemented to solve them.