Formulations and exact algorithms for the distance-constrained generalized directed rural postman problem

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

EURO Journal on Computational Optimization, 2017, vol. 5, issue 3, No 2, 339-365

Abstract: Abstract The generalized directed rural postman problem is an arc routing problem with many 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 closer than a certain distance to 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, to get close enough to each meter. We study an extension of this problem in which a fleet of vehicles is available. Given the characteristics of the mentioned application, the vehicles have no capacities but there is a maximum distance (or time) constraint all of them have to satisfy. We introduce four formulations for this problem, propose some families of valid inequalities, and present four branch-and-cut algorithms for its solution. The formulations and the algorithms are compared on a large set of instances.

Keywords: Distance constrained; Multivehicle; Generalized directed rural postman problem; Close-enough arc routing problem; Branch-and-cut; 90C10; 90C27; 90C57; 90B99 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1007/s13675-015-0053-8 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:eurjco:v:5:y:2017:i:3:d:10.1007_s13675-015-0053-8

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/13675

DOI: 10.1007/s13675-015-0053-8

Access Statistics for this article

EURO Journal on Computational Optimization is currently edited by Martine C. Labbé

More articles in EURO Journal on Computational Optimization from Springer, EURO - The Association of European Operational Research Societies
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().