Á. Corberán, I. Plana, J. M. Sanchis Llopis

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, in order 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.


F4 Routing 3
October 2, 2015  5:00 PM
Salón de actos

Other papers in the same session

On the Hierarchical Mixed Rural Postman Problem

M. Colombi, Á. Corberán, R. Mansini, I. Plana, J. M. Sanchis Llopis

The Multi-Depot Rural Postman Problem

J. Rodríguez Pereira, E. Fernández

Cookie policy

We use cookies in order to be able to identify and authenticate you on the website. They are necessary for the correct functioning of it, and therefore they can not be disabled. If you continue browsing the website, you are agreeing with their acceptance, as well as our Privacy Policy.

Additionally, we use Google Analytics in order to analyze the website traffic. They also use cookies and you can accept or refuse them with the buttons below.

You can read more details about our Cookie Policy and our Privacy Policy.