- -

New results on the Windy Postman Problem

RiuNet: Repositorio Institucional de la Universidad Politécnica de Valencia

Compartir/Enviar a

Citas

Estadísticas

  • Estadisticas de Uso

New results on the Windy Postman Problem

Mostrar el registro completo del ítem

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

Ficheros en el ítem

Thumbnail
Nombre: Corberán;Oswald;Plana ...
Tamaño: 312.2Kb
Formato: PDF
Descripción: Versión del Autor.
Abrir/Preview
[Cerrado]
Nombre: MathProgWPPReinel ...
Tamaño: 625.8Kb
Formato: PDF
Descripción: Versión editorial
Solicitar una copia al autor

Metadatos del ítem

Título: New results on the Windy Postman Problem
Autor: Corberán, Angel Oswald, Marcus Plana, Isaac Reinelt, Gerhard Sanchís Llopis, José María
Entidad UPV: Universitat Politècnica de València. Departamento de Matemática Aplicada - Departament de Matemàtica Aplicada
Fecha difusión:
Resumen:
[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 ...[+]
Palabras clave: Arc routing , Facets , Mixed Chinese Postman Problem , Polyhedral combinatorics , Windy Postman Problem , Chinese postman problem , Postman problems , Heuristic methods , Algorithms
Derechos de uso: Reserva de todos los derechos
Fuente:
Mathematical Programming. (issn: 0025-5610 )
DOI: 10.1007/s10107-010-0399-x
Editorial:
Springer-Verlag
Versión del editor: https://doi.org/10.1007/s10107-010-0399-x
Código del Proyecto:
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/
Agradecimientos:
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 ...[+]
Tipo: 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

 

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro completo del ítem