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

Elena Fernández, Gilbert Laporte, Jessica Rodríguez-Pereira

Research output: Contribution to journalArticlepeer-review

14 Citations (SciVal)


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.

Original languageEnglish
Pages (from-to)353-369
Number of pages17
JournalTransportation Science
Issue number2
Publication statusPublished - 1 Mar 2018


  • Arc routing
  • Branch-And-cut
  • Multi-depot rural postman problem
  • Polyhedral analysis
  • Worst-case analysis

ASJC Scopus subject areas

  • Civil and Structural Engineering
  • Transportation


Dive into the research topics of 'A branch-And-cut algorithm for the multidepot rural postman problem'. Together they form a unique fingerprint.

Cite this