A matheuristic for the Distance-Constrained Close-Enough Arc Routing Problem

Ángel Corberán, Isaac Plana, Miguel Reula () and José M. Sanchis
Additional contact information
Ángel Corberán: Universitat de València
Isaac Plana: Universitat de València
Miguel Reula: Universitat de València
José M. Sanchis: Universidad Politécnica de Valencia

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, 2019, vol. 27, issue 2, No 11, 312-326

Abstract: 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.

Keywords: Close-Enough Arc Routing Problem; Generalized directed Rural Postman Problem; Distance constraints; Matheuristic; multi-start (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s11750-019-00507-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:topjnl:v:27:y:2019:i:2:d:10.1007_s11750-019-00507-3

Ordering information: This journal article can be ordered from
http://link.springer.de/orders.htm

DOI: 10.1007/s11750-019-00507-3

Access Statistics for this article

TOP: An Official Journal of the Spanish Society of Statistics and Operations Research is currently edited by Juan José Salazar González and Gustavo Bergantiños

More articles in TOP: An Official Journal of the Spanish Society of Statistics and Operations Research from Springer, Sociedad de Estadística e Investigación Operativa
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().