- -

New results on the Windy Postman Problem

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

New results on the Windy Postman Problem

Show full item record

Corberán, A.; Oswald, M.; Plana, I.; Reinelt, G.; Sanchís Llopis, JM. (2012). New results on the Windy Postman Problem. Mathematical Programming. 132(1-2):309-332. https://doi.org/10.1007/s10107-010-0399-x

Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10251/150344

Files in this item

Thumbnail
Name: Corberán;Oswald;Plana ...
Size: 312.2Kb
Format: PDF
Description: Versión del Autor.
Open/Preview
[Cerrado]
Name: MathProgWPPReinel ...
Size: 625.8Kb
Format: PDF
Description: Versión editorial
Request a copy of the document

Item Metadata

Title: New results on the Windy Postman Problem
Author: Corberán, Angel Oswald, Marcus Plana, Isaac Reinelt, Gerhard Sanchís Llopis, José María
UPV Unit: Universitat Politècnica de València. Departamento de Matemática Aplicada - Departament de Matemàtica Aplicada
Issued date:
Abstract:
[EN] In this paper, we study the Windy Postman Problem (WPP). This is a well-known Arc Routing Problem that contains the Mixed Chinese Postman Problem (MCPP) as a special case. We extend to arbitrary dimension some new ...[+]
Subjects: Arc routing , Facets , Mixed Chinese Postman Problem , Polyhedral combinatorics , Windy Postman Problem , Chinese postman problem , Postman problems , Heuristic methods , Algorithms
Copyrigths: Reserva de todos los derechos
Source:
Mathematical Programming. (issn: 0025-5610 )
DOI: 10.1007/s10107-010-0399-x
Publisher:
Springer-Verlag
Publisher version: https://doi.org/10.1007/s10107-010-0399-x
Project ID:
info:eu-repo/grantAgreement/MICINN//MTM2009-14039-C06-02/ES/Modelos Y Metodos De Programacion Matematica Y Sus Aplicaciones (Optimos2)/
info:eu-repo/grantAgreement/MEC//MTM2006-14961-C05-02/ES/OPTIMOS: OPTIMIZACION PARA LA MOVILIDAD SOSTENIBLE/
Thanks:
The authors want to thank the three referees for their careful reading of the manuscript and for their many comments and suggestions that have contributed to improve the paper content and readability. In particular, several ...[+]
Type: Artículo

References

Benavent E., Carrotta A., Corberán A., Sanchis J.M., Vigo D.: Lower bounds and heuristics for the windy rural postman problem. Eur. J. Oper. Res. 176, 855–869 (2007)

Brucker P. The Chinese postman problem for mixed graphs. In Proceedings of international workshop. Lecture Notes in Computer Science 100, 354–366 (1981)

Caprara A., Fischetti M.: $${\{0,\frac{1}{2}\}}$$ -Chvátal-Gomory cuts. Math. Program. 74, 221–235 (1996) [+]
Benavent E., Carrotta A., Corberán A., Sanchis J.M., Vigo D.: Lower bounds and heuristics for the windy rural postman problem. Eur. J. Oper. Res. 176, 855–869 (2007)

Brucker P. The Chinese postman problem for mixed graphs. In Proceedings of international workshop. Lecture Notes in Computer Science 100, 354–366 (1981)

Caprara A., Fischetti M.: $${\{0,\frac{1}{2}\}}$$ -Chvátal-Gomory cuts. Math. Program. 74, 221–235 (1996)

Caprara A., Fischetti M., Letchford A.N.: On the separation of maximally violated mod-k cuts. Math. Program. 87, 37–56 (2000)

Christof, T., Loebel, A.: PORTA—a polyhedron representation algorithm www.informatik.uni-heidelberg.de/groups/comopt/software/PORTA/ (1998)

Christofides, N., Benavent, E., Campos, V., Corberán, A., Mota, E.: An optimal method for the mixed postman problem. In Thoft-Christensen, P. (ed.) System Modelling and Optimization. Lecture Notes in Control and Information Sciences 59, Springer (1984)

Corberán A., Plana I., Sanchis J.M.: Zigzag inequalities: a new class of facet-inducing inequalities for arc routing problems. Math. Program. 108, 79–96 (2006)

Corberán A., Plana I., Sanchis J.M.: A branch & cut algorithm for the windy general routing problem and special cases. Networks 49, 245–257 (2007)

Corberán, A., Plana I., Sanchis, J.M.: Arc routing problems: data instances. www.uv.es/corberan/instancias.htm (2007)

Corberán A., Plana I., Sanchis J.M.: The windy general routing polyhedron: a global view of many known arc routing polyhedra. SIAM J. Discrete Math. 22, 606–628 (2008)

Grötschel, M., Win, Z.: On the windy postman polyhedron. Report No. 75, Schwerpunktprogram der Deutschen Forschungsgemeinschaft, Universität Augsburg, Germany (1988)

Grötschel M., Win Z.: A cutting plane algorithm for the Windy Postman Problem. Math. Program. 55, 339–358 (1992)

Guan M.: On the Windy Postman Problem. Discrete Appl. Math. 9, 41–46 (1984)

Minieka E.: The Chinese postman problem for mixed networks. Manage. Sci. 25, 643–648 (1979)

Naddef D., Rinaldi G.: The symmetric traveling salesman polytope and its graphical relaxation: composition of valid inequalities. Math. Program. 51, 359–400 (1991)

Oswald M., Reinelt G., Seitz H.: Applying mod-k cuts for solving linear ordering problems. TOP 17, 158–170 (2009)

Papadimitriou C.H.: On the complexity of edge traversing. J. Assoc. Comput. Mach. 23, 544–554 (1976)

Ralphs T.K.: On the mixed Chinese postman problem. Oper. Res. Lett. 14, 123–127 (1993)

Wenger, K.: Generic Cut Generation Methods for Routing Problems. PhD Dissertation, University of Heidelberg, Germany (2004)

Win, Z.: Contributions to Routing Problems. PhD Dissertation, University of Augsburg, Germany (1987)

Win Z.: On the Windy Postman Problem on eulerian graphs. Math. Program. 44, 97–112 (1989)

Zaragoza Martínez F.J.: Series-parallel graphs are windy postman perfect. Discrete Math. 308, 1366–1374 (2008)

[-]

recommendations

 

This item appears in the following Collection(s)

Show full item record