On the Undirected Rural Postman Problem: Tight Bounds Based on a New Formulation

Elena Fernández (), Oscar Meza (), Robert Garfinkel () and Maruja Ortega ()
Additional contact information
Elena Fernández: Statistics and Operations Research Department, Technical University of Catalonia, Barcelona, Spain
Oscar Meza: Computer Science and Information Technology Department, Simón Bolívar University, Baruta, Venezuela
Robert Garfinkel: School of Business Administration, University of Connecticut, Storrs, Connecticut 06269
Maruja Ortega: Computer Science and Information Technology Department, Simón Bolívar University, Baruta, Venezuela

Operations Research, 2003, vol. 51, issue 2, 281-291

Abstract: The Rural Postman Problem (RPP) is a classic “edge-routing” problem. A mathematical programming formulation of the RPP that differs fundamentally from those in the literature was introduced, but not tested computationally, by Garfinkel and Webb (1999). A rudimentary algorithm that yields lower bounds via cutting planes and upper bounds via heuristics is developed and tested for a variation of that formulation. Computational results are encouraging, especially in terms of the relatively small number of added inequalities needed to get good lower bounds, and the fact that the vast majority of these have efficient, exact separation procedures. Note that a first algorithm based on this new formulation is computationally competitive, allowing the possibility of far more efficient and complex future realizations.

Keywords: Networks; applications: The Rural Postman Problem; Networks; distance algorithms: tight upper and lower bounds (search for similar items in EconPapers)
Date: 2003
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (7)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.51.2.281.12790 (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:oropre:v:51:y:2003:i:2:p:281-291

Access Statistics for this article

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