- -

The Windy General Routing Polyhedron: A global view of many known Arc Routing Polyhedra

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

The Windy General Routing Polyhedron: A global view of many known Arc Routing Polyhedra

Show simple item record

Files in this item

dc.contributor.author Corberán, Angel es_ES
dc.contributor.author Plana, Isaac es_ES
dc.contributor.author Sanchís Llopis, José María es_ES
dc.date.accessioned 2020-07-04T03:32:16Z
dc.date.available 2020-07-04T03:32:16Z
dc.date.issued 2008-03-21 es_ES
dc.identifier.issn 0895-4801 es_ES
dc.identifier.uri http://hdl.handle.net/10251/147434
dc.description.abstract [EN] The windy postman problem consists of finding a minimum cost traversal of all of the edges of an undirected graph with two costs associated with each edge, representing the costs of traversing it in each direction. In this paper we deal with the windy general routing problem (WGRP), in which only a subset of edges must be traversed and a subset of vertices must be visited. This is also an NP-hard problem that generalizes many important arc routing problems (ARPs) and has some interesting real-life applications. Here we study the description of the WGRP polyhedron, for which some general properties and some large families of facet-inducing inequalities are presented. Moreover, since the WGRP contains many well-known routing problems as special cases, this paper also provides a global view of their associated polyhedra. Finally, for the first time, some polyhedral results for several ARPs defined on mixed graphs formulated by using two variables per edge are presented. es_ES
dc.description.sponsorship This work was supported by the Ministerio de Educación y Ciencia of Spain (project MTM2006-14961-C05-02). es_ES
dc.language Inglés es_ES
dc.publisher Society for Industrial and Applied Mathematics es_ES
dc.relation MEC/MTM2006-14961-C05-02 es_ES
dc.relation.ispartof SIAM Journal on Discrete Mathematics es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Arc routing problems es_ES
dc.subject Windy general routing problem es_ES
dc.subject Polyhedra es_ES
dc.subject Facets es_ES
dc.subject.classification MATEMATICA APLICADA es_ES
dc.title The Windy General Routing Polyhedron: A global view of many known Arc Routing Polyhedra es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1137/050640886 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.; Plana, I.; Sanchís Llopis, JM. (2008). The Windy General Routing Polyhedron: A global view of many known Arc Routing Polyhedra. SIAM Journal on Discrete Mathematics. 22(2):606-628. https://doi.org/10.1137/050640886 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1137/050640886 es_ES
dc.description.upvformatpinicio 606 es_ES
dc.description.upvformatpfin 628 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 22 es_ES
dc.description.issue 2 es_ES
dc.relation.pasarela S\33691 es_ES
dc.contributor.funder Ministerio de Educación y Ciencia es_ES


This item appears in the following Collection(s)

Show simple item record