- -

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 sencillo del ítem

Ficheros en el ítem

Thumbnail
Nombre: Corberán;Oswald;Plana ...
Tamaño: 312.2Kb
Formato: PDF
Descripción: Versión del Autor.
Abrir
[Cerrado]
Nombre: MathProgWPPReinel ...
Tamaño: 625.8Kb
Formato: PDF
Descripción: Versión editorial
Solicitar una copia al autor
dc.contributor.author Corberán, Angel es_ES
dc.contributor.author Oswald, Marcus es_ES
dc.contributor.author Plana, Isaac es_ES
dc.contributor.author Reinelt, Gerhard es_ES
dc.contributor.author Sanchís Llopis, José María es_ES
dc.date.accessioned 2020-09-18T03:35:51Z
dc.date.available 2020-09-18T03:35:51Z
dc.date.issued 2012-04 es_ES
dc.identifier.issn 0025-5610 es_ES
dc.identifier.uri http://hdl.handle.net/10251/150344
dc.description.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 inequalities that complete the description of the polyhedron associated with the Windy Postman Problem over graphs with up to four vertices and ten edges. We introduce two new families of facet-inducing inequalities and prove that these inequalities, along with the already known odd zigzag inequalities, are Chvátal-Gomory inequalities of rank at most 2. Moreover, a branch-and-cut algorithm that incorporates two new separation algorithms for all the previously mentioned inequalities and a new heuristic procedure to obtain upper bounds are presented. Finally, the performance of a branch-and-cut algorithm over several sets of large WPP and MCPP instances, with up to 3,000 nodes and 9,000 edges (and arcs in the MCPP case), shows that, to our knowledge, this is the best algorithm to date for the exact resolution of the WPP and the MCPP. © 2010 Springer and Mathematical Optimization Society. es_ES
dc.description.sponsorship 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 remarks regarding the discussion of C-G and mod-k inequalities were pointed out by one of the referees. A. Corberan, I. Plana and J.M. Sanchis wish to thank the Ministerio de Educacion y Ciencia of Spain (projects MTM2006-14961-C05-02 and MTM2009-14039-C06-02) for its support. es_ES
dc.language Inglés es_ES
dc.publisher Springer-Verlag es_ES
dc.relation.ispartof Mathematical Programming es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Arc routing es_ES
dc.subject Facets es_ES
dc.subject Mixed Chinese Postman Problem es_ES
dc.subject Polyhedral combinatorics es_ES
dc.subject Windy Postman Problem es_ES
dc.subject Chinese postman problem es_ES
dc.subject Postman problems es_ES
dc.subject Heuristic methods es_ES
dc.subject Algorithms es_ES
dc.subject.classification MATEMATICA APLICADA es_ES
dc.title New results on the Windy Postman Problem es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1007/s10107-010-0399-x es_ES
dc.relation.projectID info:eu-repo/grantAgreement/MICINN//MTM2009-14039-C06-02/ES/Modelos Y Metodos De Programacion Matematica Y Sus Aplicaciones (Optimos2)/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/MEC//MTM2006-14961-C05-02/ES/OPTIMOS: OPTIMIZACION PARA LA MOVILIDAD SOSTENIBLE/ es_ES
dc.rights.accessRights Abierto es_ES
dc.contributor.affiliation Universitat Politècnica de València. Departamento de Matemática Aplicada - Departament de Matemàtica Aplicada es_ES
dc.description.bibliographicCitation 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 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1007/s10107-010-0399-x es_ES
dc.description.upvformatpinicio 309 es_ES
dc.description.upvformatpfin 332 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 132 es_ES
dc.description.issue 1-2 es_ES
dc.relation.pasarela S\221719 es_ES
dc.contributor.funder Ministerio de Educación y Ciencia es_ES
dc.contributor.funder Ministerio de Ciencia e Innovación es_ES
dc.description.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) es_ES
dc.description.references Brucker P. The Chinese postman problem for mixed graphs. In Proceedings of international workshop. Lecture Notes in Computer Science 100, 354–366 (1981) es_ES
dc.description.references Caprara A., Fischetti M.: $${\{0,\frac{1}{2}\}}$$ -Chvátal-Gomory cuts. Math. Program. 74, 221–235 (1996) es_ES
dc.description.references Caprara A., Fischetti M., Letchford A.N.: On the separation of maximally violated mod-k cuts. Math. Program. 87, 37–56 (2000) es_ES
dc.description.references Christof, T., Loebel, A.: PORTA—a polyhedron representation algorithm www.informatik.uni-heidelberg.de/groups/comopt/software/PORTA/ (1998) es_ES
dc.description.references 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) es_ES
dc.description.references 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) es_ES
dc.description.references 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) es_ES
dc.description.references Corberán, A., Plana I., Sanchis, J.M.: Arc routing problems: data instances. www.uv.es/corberan/instancias.htm (2007) es_ES
dc.description.references 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) es_ES
dc.description.references Grötschel, M., Win, Z.: On the windy postman polyhedron. Report No. 75, Schwerpunktprogram der Deutschen Forschungsgemeinschaft, Universität Augsburg, Germany (1988) es_ES
dc.description.references Grötschel M., Win Z.: A cutting plane algorithm for the Windy Postman Problem. Math. Program. 55, 339–358 (1992) es_ES
dc.description.references Guan M.: On the Windy Postman Problem. Discrete Appl. Math. 9, 41–46 (1984) es_ES
dc.description.references Minieka E.: The Chinese postman problem for mixed networks. Manage. Sci. 25, 643–648 (1979) es_ES
dc.description.references Naddef D., Rinaldi G.: The symmetric traveling salesman polytope and its graphical relaxation: composition of valid inequalities. Math. Program. 51, 359–400 (1991) es_ES
dc.description.references Oswald M., Reinelt G., Seitz H.: Applying mod-k cuts for solving linear ordering problems. TOP 17, 158–170 (2009) es_ES
dc.description.references Papadimitriou C.H.: On the complexity of edge traversing. J. Assoc. Comput. Mach. 23, 544–554 (1976) es_ES
dc.description.references Ralphs T.K.: On the mixed Chinese postman problem. Oper. Res. Lett. 14, 123–127 (1993) es_ES
dc.description.references Wenger, K.: Generic Cut Generation Methods for Routing Problems. PhD Dissertation, University of Heidelberg, Germany (2004) es_ES
dc.description.references Win, Z.: Contributions to Routing Problems. PhD Dissertation, University of Augsburg, Germany (1987) es_ES
dc.description.references Win Z.: On the Windy Postman Problem on eulerian graphs. Math. Program. 44, 97–112 (1989) es_ES
dc.description.references Zaragoza Martínez F.J.: Series-parallel graphs are windy postman perfect. Discrete Math. 308, 1366–1374 (2008) es_ES


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

Mostrar el registro sencillo del ítem