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

References

• Barahona F., Grötschel M. On the cycle polytope of a binary matroid. J. Combin. Theory, Series B (1986) 40:40–62Crossref, Google Scholar
• Christofides N. Worst-case analysis of a new heuristic for the traveling salesman problem. (1976) . Report No. 388 Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PAGoogle Scholar
• Christofides N., Campos V., Corberán A., Mota E. An algorithm for the rural postman problem. (1981) . Imperial College Report I.C.O.R.81.5., London, U.KGoogle Scholar
• Corberán A., Sanchis J. M. A polyhedral approach to the rural postman problem. Eur. J. Oper. Res. (1994) 79:95–114Crossref, Google Scholar
• Corberán A., Sanchis J. M. The general routing problem: Facets from the RPP and GTSP polyhedra. Eur. J. Oper. Res. (1998) 108:538–550Crossref, Google Scholar
• Corberán A., Letchford A., Sanchis J. M. A cutting plane algorithm for the general routing problem. Math. Programming (2001) 90:291–316Crossref, Google Scholar
• Dantzig G. B., Fulkerson D. R., Johnson S. M. Solution of a large scale travelling salesman problem. Oper. Res. (1954) 2:393–410Link, Google Scholar
• Edmonds J. Maximum matching and a polyhedron with 0,1-vertices. J. Res. National Bureau of Standards (1965) 69B:125–130Crossref, Google Scholar
• Eiselt H. A., Gendreau M., Laporte G. Arc routing problems, part I: The Chinese postman problem. Oper. Res. (1995a) 43:231–242Link, Google Scholar
• Eiselt H. A., Gendreau M., Laporte G. Arc fouting problems, part II: The rural postman problem. Oper. Res. (1995b) 43:399–414Link, Google Scholar
• Finke G., Claus A., Gunn E. A. A two-commodity network flow approach to the travelling salesman problem. Congressus Numerantium (1984) 41:167–178Google Scholar
• Fischetti M., Laporte G., Martello S. The delivery man problem and cumulative matroids. Oper. Res. (1993) 41:1055–1064Link, Google Scholar
• Frederickson G. N. Approximation algorithms for some postman problems. J. Assoc. Comput. Machinery (1979) 7:178–193Google Scholar
• Garfinkel R., Webb I. On crossings, the crossing postman problem, and the rural postman problem. Networks (1999) 34:173–180Crossref, Google Scholar
• Ghiani G., Laporte G. A branch-and-cut algorithm for the undirected rural postman problem. Math. Programming (2000) 87:467–481Crossref, Google Scholar
• Grötschel M., Holland O. Solving matching problems with linear programming. Math. Programming (1985) 33:243–259Crossref, Google Scholar
• Hertz A., Laporte G., Nanchen-Hugo P. Improvement procedures for the undirected rural postman problem. INFORMS J. Comput. (1999) 1:53–62Link, Google Scholar
• Lenstra J. K., Rinnooy Kan A. H. G. On general routing problems. Networks (1976) 6:273–280Crossref, Google Scholar
• Letchford A. N. New inequalities for the general routing problem. Eur. J. Oper. Res. (1997) 96:317–332Crossref, Google Scholar
• Letchford A. N. The general routing polyhedron: A unifying framework. Eur. J. Oper. Res. (1999) 112:122–133Crossref, Google Scholar
• Lin S. Computer solutions of the traveling salesman problem. Bell System Tech. J. (1965) 44:2245–2269Crossref, Google Scholar
• Padberg M. W., Rao M. R. Odd minimum cut-sets and b-matchings. Math. Oper. Res. (1982) 7:67–80Link, Google Scholar
• Pearn W. L., Wu T. C. Algorithms for the rural postman problem. Comput. Oper. Res. (1995) 22:819–828Crossref, Google Scholar