Abstract
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.
Similar content being viewed by others
References
Aráoz J, Fernández E, Franquesa C (2017) The generalized arc routing problem. TOP 25:497–525
Ávila T, Corberán Á, Plana I, Sanchis JM (2016) A new branch-and-cut algorithm for the generalized directed rural postman problem. Transportation Science 50:750–761
Ávila T, Corberán Á, Plana I, Sanchis JM (2017) Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem. EURO Journal on Computational Optimization 5:339–365
Cerrone C, Cerulli R, Golden B, Pentangelo R (2017) A flow formulation for the close-enough arc routing problem. In Sforza A. and Sterle C., editors, Optimization and Decision Science: Methodologies and Applications. ODS 2017., volume 217 of Springer Proceedings in Mathematics & Statistics, pages 539–546
Corberán Á, Laporte G (editors) (2014) Arc Routing: Problems,Methods, and Applications. MOS-SIAM Series on Optimization,Philadelphia
Corberán Á, Plana I, Sanchis J.M (2007) Arc routing problems: data instances. http://www.uv.es/~corberan/instancias.htm
Drexl M (2007) On some generalized routing problems. PhD thesis, Rheinisch-Westfälische Technische Hochschule, Aachen University
Drexl M (2014) On the generalized directed rural postman problem. Journal of the Operational Research Society 65:1143–1154
Gendreau M, Laporte G, Semet F (1997) The covering tour problem. Operations Research 45:568–576
Hà M-H, Bostel N, Langevin A, Rousseau L-M (2014) Solving the close enough arc routing problem. Networks 63:107–118
Mourão MC, Pinto LS (2017) An updated annotated bibliography on arc routing problems. Networks 70:144–194
Renaud A, Absi N, Feillet D (2017) The stochastic close-enough arc routing problem. Networks 69:205–221
Shuttleworth R, Golden BL, Smith S, Wasil EA (2008) Advances in meter reading: Heuristic solution of the close enough traveling salesman problem over a street network. In: Golden BL, Raghavan S, Wasil EA (eds) The Vehicle Routing Problem: Lastest Advances and New Challenges. Springer, pp 487–501
Acknowledgements
This work was supported by the Spanish Ministerio de Economía y Competitividad and Fondo Europeo de Desarrollo Regional (FEDER) through Project MTM2015-68097-P (MINECO/FEDER). Authors want to thank two anonymous referees for their suggestions and comments that have contributed to improve the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Corberán, Á., Plana, I., Reula, M. et al. A matheuristic for the Distance-Constrained Close-Enough Arc Routing Problem. TOP 27, 312–326 (2019). https://doi.org/10.1007/s11750-019-00507-3
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11750-019-00507-3