Abstract
In this paper we describe a cutting plane algorithm for the (NP-hard) windy postman problem. This algorithm can also be applied to the mixed, directed, and undirected postman problems. It is based on a partial linear description of the windy postman polyhedron and on the simplex method. The partial linear description (together with cutting plane recognition strategies) provides new cutting planes and hence generates better and better linear programming relaxations of the windy postman polyhedron, and the simplex method solves these linear programs. We have investigated the performance of our algorithm with several test problems defined on graphs of up to 264 nodes. For most of these problems, we obtained optimal solutions in reasonable computation times.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
K. Alewell,Standort und Distribution: Entscheidungsfälle (Gabler, Wiesbaden, 1980).
A. Bachem and M. Grötschel, “New aspects of polyhedral theory,” in: B. Korte, ed.,Modern Applied Mathematics: Optimization and Operations Research (North-Holland, Amsterdam, 1982) pp. 51–106.
J.A. Bondy and U.S.R. Murty,Graph Theory with Applications (American Elsevier, New York, and Macmillan, London, 1976).
R. Burkard and U. Derigs,Assignment and Matching Problems: Solutions Methods with FORTRAN Programs, Lecture Notes in Economics and Mathematical Systems No. 184 (Springer, Berlin, 1980).
N. Christofides, E. Benavent, V. Campos, A. Corberan and E. Mota, “An optimal method for the mixed postman problem,” in: P. Thoft-Christensen, ed.,System Modelling and Optimization, Lecture Notes in Control and Information Sciences No. 59 (Springer, Berlin, 1984).
J. Edmonds, “The Chinese postman problem,”Operations Research 13, Supplement 1 (1965) B-73.
J. Edmonds and E.L. Johnson, “Matching, Euler tours and the Chinese postman,”Mathematical Programming 5 (1973) 88–124.
A.V. Goldberg and R.E. Tarjan, “A new approach to the maximum flow problem,”Proceedings of the 18th ACM Symposium on Theory of Computing (1986) pp. 136–146.
M. Grötschel and O. Holland, “Solving matching problems with linear programming,”Mathematical Programming 33 (1985) 243–259.
M. Grötschel and O. Holland, “Solution of large-scale symmetric travelling salesman problems,”Mathematical Programming 51 (1991) 141–202.
M. Grötschel, M. Jünger and G. Reinelt, “A cutting plane algorithm for the linear ordering problem,”Operations Research 32 (1984) 1195–1220.
M. Grötschel, L. Lovász and A. Schrijver, “The ellipsoid method and its consequences in combinatorial optimization,”Combinatorica 1 (1981) 169–197.
M. Grötschel and Y. Wakabayashi, “A cutting plane algorithm for a clustering problem,”Mathematical Programming (Series B) 45 (1989) 59–96.
M. Grötschel and Z. Win (1992), “On the windy postman polyhedron,” to appear.
M. Guan, “Graphic programming using odd or even points,”Chinese Mathematics 1 (1962) 273–277.
M. Guan, “On the windy postman problem,”Discrete Applied Mathematics 9 (1984) 41–46.
T.M. Liebling,Graphentheorie in Planungs- und Tourenproblemen, Lecture Notes in Operations Research and Mathematical Systems No. 21, (Springer, Berlin, 1970).
R. Marsten, “The design of the XMP linear programming library,”ACM Transactions on Mathematical Software 7 (1981) 481–497.
M.W. Padberg and M. Grötschel, “Polyhedral computations,” in: E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan and D. Shmoys eds.,The Traveling Salesman Problem (Wiley, Chichester, 1985) pp. 307–360.
M.W. Padberg and M.R. Rao, “Odd minimum cut-sets andb-matchings,”Mathematics of Operations Research 7 (1982) 67–80.
M. Padberg and G. Rinaldi, “A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems,”SIAM Review 33 (1991) 60–100.
H. Paessens, “Tourenplanung bei der regionalen Hausmüllentsorgung,” Institut für Siedlungswasserwirtschaft, Universität Karlsruhe (Karlsruhe, 1981).
C.H. Papadimitriou, “On the complexity of edge traversing,”Journal of the Association for Computing Machinery 23 (1976) 544–554.
Z. Win, “Contributions to routing problems,” Ph.D. Thesis, Universität Augsburg (Augsburg, 1987).
Z. Win, “On the windy postman problem on Eulerian graphs,”Mathematical Programming 44 (1989) 97–112.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Grötschel, M., Win, Z. A cutting plane algorithm for the windy postman problem. Mathematical Programming 55, 339–358 (1992). https://doi.org/10.1007/BF01581206
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01581206