A Branch-and-Cut Algorithm for the Multidepot Rural Postman Problem

Elena Fernández (), Gilbert Laporte () and Jessica Rodríguez-Pereira ()
Additional contact information
Elena Fernández: Department of Statistics and Operations Research, Universitat Politècnica de Catalunya–BarcelonaTech, 08034 Barcelona, Spain; Barcelona Graduate School of Mathematics, Universitat de Barcelona, 08007 Barcelona, Spain
Gilbert Laporte: HEC Montréal, Montréal, Québec H3T 2A7, Canada
Jessica Rodríguez-Pereira: Department of Statistics and Operations Research, Universitat Politècnica de Catalunya–BarcelonaTech, 08034 Barcelona, Spain

Transportation Science, 2018, vol. 52, issue 2, 353-369

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 programming formulation containing only binary variables, as well as a polyhedral analysis; (iii) It develops a branch-and-cut algorithm that includes several new exact and heuristic separation procedures. Instances involving up to four depots, 744 vertices, and 1,315 edges are solved to optimality. These instances contain up to 140 required components and 1,000 required edges.

Keywords: arc routing; multi-depot rural postman problem; worst-case analysis; polyhedral analysis; branch-and-cut (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://doi.org/10.1287/trsc.2017.0783 (application/pdf)

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:inm:ortrsc:v:52:y:2018:i:2:p:353-369

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().