A branch-and-cut algorithm for the Undirected Rural Postman Problem

Abstract.

The well-known Undirected Rural Postman Problem is considered and a binary linear problem using new dominance relations is presented. Polyhedral properties are investigated and a branch-and-cut algorithm is developed. Extensive computational results indicate that the algorithm is capable of solving much larger instances than previously reported.

Similar content being viewed by others

A branch-and-cut algorithm for the windy profitable location rural postman problem

Article 02 August 2024

A branch-cut-and-price algorithm for the generalized vehicle routing problem

Article 12 April 2017

Mixed-integer programming techniques for the connected max-k-cut problem

Article Open access 30 April 2020

Author information

Authors and Affiliations

1. GERAD, École des Hautes Études Commerciales, 3000 chemin de la Côte-Sainte-Catherine, Montréal, Canada H3T 2A7, e-mail: {ghiani,gilbert}@crt.umontreal.ca, , , , , , CA

   Gianpaolo Ghiani & Gilbert Laporte

Authors

1. Gianpaolo Ghiani
   View author publications

   You can also search for this author in PubMed Google Scholar

2. Gilbert Laporte
   View author publications

   You can also search for this author in PubMed Google Scholar

Additional information

Received: December 1, 1997 / Accepted: October 13, 1999¶Published online January 27, 2000

Rights and permissions

Reprints and permissions

About this article

Cite this article

Ghiani, G., Laporte, G. A branch-and-cut algorithm for the Undirected Rural Postman Problem. Math. Program. 87, 467–481 (2000). https://doi.org/10.1007/s101070050007

Download citation

• Issue Date: May 2000

• DOI: https://doi.org/10.1007/s101070050007

• Key words: Arc Routing Problems – Undirected Rural Postman Problem – branch-and-cut – polyhedral analysis – facets

• Mathematics Subject Classification (1991): 05c45