Á. 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

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

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