Loading...
Loading...

Go to the content (press return)

A branch-and-cut algorithm for the multidepot rural postman problem

Author
Fernandez, E.; Gilbert, L.; Rodríguez-Pereira, J.
Type of activity
Journal article
Journal
Transportation science
Date of publication
2018-03
Volume
52
Number
2
First page
353
Last page
369
DOI
https://doi.org/10.1287/trsc.2017.0783 Open in new window
Project funding
Discrete Optimization for Integrated Logistic and Transportation Problems
Models and methods of mathematical programming and applications
Repository
http://hdl.handle.net/2117/126907 Open in new window
URL
https://pubsonline.informs.org/doi/abs/10.1287/trsc.2017.0783?journalCode=trsc Open in new window
Abstract
This paper considers the Multidepot Rural Postman Problem, an extension of the classical Rural Postman Problem in which there are several depots instead of only one. The aim is to construct a minimum cost set of routes traversing each required edge of the graph, where each route starts and ends at the same depot. The paper makes the following scientific contributions: (i) It presents optimality conditions and a worst case analysis for the problem; (ii) It proposes a compact integer linear progra...
Citation
Fernandez, E., Gilbert, L., Rodríguez-Pereira, J. A branch-and-cut algorithm for the multidepot rural postman problem. "Transportation science", Març 2018, vol. 52, núm. 2, p. 353-369.
Keywords
arc routing, branch-and-cut, multi-depot rural postman problem, polyhedral analysis, worst-case analysis
Group of research
GNOM - Mathematical Optimization Group

Participants

Attachments