A matheuristic for the Distance-Constrained Close-Enough Arc Routing Problem
- Ángel Corberán 1
- Isaac Plana 1
- Miguel Reula 1
- José M. Sanchis 2
- 1 Universitat de València, España
- 2 Universidad Politécnica de Valencia, España
ISSN: 1863-8279, 1134-5764
Año de publicación: 2019
Volumen: 27
Número: 2
Páginas: 312-326
Tipo: Artículo
Otras publicaciones en: Top
Resumen
The Close-Enough Arc Routing Problem, also called Generalized Directed Rural Postman Problem, is an arc routing problem with interesting real-life applications, such as routing for meter reading. In this application, a vehicle with a receiver travels through a series of neighborhoods. If the vehicle gets within a certain distance of a meter, the receiver is able to record the gas, water, or electricity consumption. Therefore, the vehicle does not need to traverse every street, but only a few, in order to be close enough to each meter. In this paper we deal with an extension of this problem, the Distance-Constrained Generalized Directed Rural Postman Problem or Distance-Constrained Close Enough Arc Routing Problem, in which a fleet of vehicles is available. The vehicles have to leave from and return to a common vertex, the depot, and the length of their routes must not exceed a maximum distance (or time). For solving this problem we propose a matheuristic that incorporates an effective exact procedure to optimize the routes obtained. Extensive computational experiments have been performed on a set of benchmark instances and the results are compared with those obtained with an exact procedure proposed in the literature.