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

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.