- -

A branch-and-cut algorithm for the Profitable Windy Rural Postman Problem

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

A branch-and-cut algorithm for the Profitable Windy Rural Postman Problem

Show simple item record

Files in this item

dc.contributor.author Ávila, T. es_ES
dc.contributor.author Corberán, A. es_ES
dc.contributor.author Plana, I. es_ES
dc.contributor.author Sanchís Llopis, José María es_ES
dc.date.accessioned 2020-03-23T08:46:16Z
dc.date.available 2020-03-23T08:46:16Z
dc.date.issued 2016-03-16 es_ES
dc.identifier.issn 0377-2217 es_ES
dc.identifier.uri http://hdl.handle.net/10251/139158
dc.description.abstract [EN] In this paper we study the profitable windy rural postman problem. This is an arc routing problem with profits defined on a windy graph in which there is a profit associated with some of the edges of the graph, consisting of finding a route maximizing the difference between the total profit collected and the total cost. This problem generalizes the rural postman problem and other well-known arc routing problems and has real-life applications, mainly in snow removal operations. We propose here a formulation for the problem and study its associated polyhedron. Several families of facet-inducing inequalities are described and used in the design of a branch-and-cut procedure. The algorithm has been tested on a large set of benchmark instances and compared with other existing algorithms. The results obtained show that the branch-and-cut algorithm is able to solve large-sized instances optimally in reasonable computing times. es_ES
dc.description.sponsorship Authors thank Elisa Schaeffer for providing us with the instances and solutions of sets of instances Set1-Set4 and two anonymous referees for their comments and suggestions that have helped to improve the paper. Authors also wish to thank the Ministerio de Economia y Competitividad of Spain (MTM2012-36163-C06-02) and the Generalitat Valenciana (Project GVPROMETEO2013-049) for its support. es_ES
dc.language Inglés es_ES
dc.publisher Elsevier es_ES
dc.relation MINISTERIO DE ECONOMIA Y COMPETITIVIDAD/MTM2012-36163-C06-02 es_ES
dc.relation GENERALITAT VALENCIANA. CONSELLERIA D'EDUCACIO, CULTURA I ESPORT/PROMETEO/2013/049 es_ES
dc.relation.ispartof European Journal of Operational Research es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Windy rural postman problem es_ES
dc.subject Arc routing es_ES
dc.subject Profits es_ES
dc.subject Branch-and-cut algorithm es_ES
dc.subject Polyhedron es_ES
dc.subject.classification MATEMATICA APLICADA es_ES
dc.title A branch-and-cut algorithm for the Profitable Windy Rural Postman Problem es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1016/j.ejor.2015.10.016 es_ES
dc.rights.accessRights Cerrado 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 Ávila, T.; Corberán, A.; Plana, I.; Sanchís Llopis, JM. (2016). A branch-and-cut algorithm for the Profitable Windy Rural Postman Problem. European Journal of Operational Research. 249(3):1092-1101. https://doi.org/10.1016/j.ejor.2015.10.016 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1016/j.ejor.2015.10.016 es_ES
dc.description.upvformatpinicio 1092 es_ES
dc.description.upvformatpfin 1101 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 249 es_ES
dc.description.issue 3 es_ES
dc.relation.pasarela S\297787 es_ES
dc.contributor.funder Ministerio de Economía y Competitividad es_ES
dc.contributor.funder Generalitat Valenciana es_ES


This item appears in the following Collection(s)

Show simple item record