- -

A branch-and-cut algorithm for the maximum benefit Chinese postman problem

RiuNet: Institutional repository of the Polithecnic University of Valencia

Share/Send to

Cited by

Statistics

A branch-and-cut algorithm for the maximum benefit Chinese postman problem

Show simple item record

Files in this item

Thumbnail
Name: Corberán;Plana;Ro ...
Size: 376.7Kb
Format: PDF
Description: Versión del Autor.
Open
[Cerrado]
Name: 22-MP-MBCPP-Chia2 ...
Size: 447.5Kb
Format: PDF
Description: Versión editorial
Request a copy of the document
dc.contributor.author Corberán, Angel es_ES
dc.contributor.author Plana, Isaac es_ES
dc.contributor.author Rodríguez-Chía, Antonio Manuel es_ES
dc.contributor.author Sanchís Llopis, José María es_ES
dc.date.accessioned 2020-10-07T03:34:44Z
dc.date.available 2020-10-07T03:34:44Z
dc.date.issued 2013-10 es_ES
dc.identifier.issn 0025-5610 es_ES
dc.identifier.uri http://hdl.handle.net/10251/151300
dc.description.abstract [EN] The Maximum Benefit Chinese Postman Problem (MBCPP) is an NP-hard problem that considers several benefits associated with each edge, one for each time the edge is traversed with a service. The objective is to find a closed walk with maximum benefit.We propose an IP formulation for the undirected MBCPP and, based on the description of its associated polyhedron, we propose a branch-and-cut algorithm and present computational results on instances with up to 1,000 vertices and 3,000 edges. es_ES
dc.description.sponsorship The authors wish to thank the Ministerio de Innovacion y Ciencia/FEDER of Spain (projects MTM2009-14039-C06-02, MTM2010-19576-C02-02 and DE2009-0057) and Junta de Andalucia/FEDER (grant number FQM-5849) for its support. They also thank two anonymous referees for their careful reading of the manuscript and for their many suggestions and comments that have helped to improve the contents and readability of the paper. 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 Chinese postman problem es_ES
dc.subject Maximum benefit Chinese postman problem es_ES
dc.subject Rural postman Problem es_ES
dc.subject Facets es_ES
dc.subject Branch-and-cut es_ES
dc.subject.classification MATEMATICA APLICADA es_ES
dc.title A branch-and-cut algorithm for the maximum benefit Chinese postman problem es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1007/s10107-011-0507-6 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/Junta de Andalucía//P10-FQM-5849/ES/Nuevos desafíos de la matemática combinatoria: Enfoques no estándares en optimización discreta y álgebra computacional. Aplicaciones/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/MICINN//DE2009-0057/ES/DE2009-0057/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/MICINN//MTM2010-19576-C02-02/ES/DISEÑO OPTIMO EN REDES LOGISTICAS/ 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.; Rodríguez-Chía, AM.; Sanchís Llopis, JM. (2013). A branch-and-cut algorithm for the maximum benefit Chinese postman problem. Mathematical Programming. 141(1-2):21-48. https://doi.org/10.1007/s10107-011-0507-6 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1007/s10107-011-0507-6 es_ES
dc.description.upvformatpinicio 21 es_ES
dc.description.upvformatpfin 48 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 141 es_ES
dc.description.issue 1-2 es_ES
dc.relation.pasarela S\256758 es_ES
dc.contributor.funder Junta de Andalucía es_ES
dc.contributor.funder European Regional Development Fund es_ES
dc.contributor.funder Ministerio de Ciencia e Innovación es_ES
dc.description.references Aráoz J., Fernández E., Franquesa C.: The clustered price-collecting arc-routing problem. Transp. Sci. 43, 287–300 (2009) es_ES
dc.description.references Aráoz J., Fernández E., Meza O.: Solving the prize-collecting rural postman problem. Eur. J. Oper. Res. 196, 886–896 (2009) es_ES
dc.description.references Aráoz J., Fernández E., Zoltan C.: Privatized rural postman problems. Comput. Oper. Res. 33, 3432–3449 (2006) es_ES
dc.description.references Archetti C., Feillet D., Hertz A., Speranza M.G.: The undirected capacitated arc routing problem with profits. Comput. Oper. Res. 37, 1860–1869 (2010) es_ES
dc.description.references Barahona F., Grötschel M.: On the cycle polytope of a binary matroid. J. Comb. Theory B 40, 40–62 (1986) es_ES
dc.description.references Fernández E., Fernández E., Franquesa C., Sanchis J.M.: The windy clustered prize-collecting problem. Transp. Sci. 45, 317–334 (2011) es_ES
dc.description.references Letchford A.N., Letchford A.N., Sanchis J.M.: A cutting-plane algorithm for the general routing problem. Math. Progr. 90, 291–316 (2001) es_ES
dc.description.references Plana I., 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, Á., Plana, I., Sanchis, J.M.: Arc Routing Problems: Data Instances. http://www.uv.es/corberan/instancias.htm es_ES
dc.description.references Sanchis J.M., Sanchis J.M.: A polyhedral approach to the rural postman problem. Eur. J. Oper. Res. 79, 95–114 (1994) es_ES
dc.description.references Feillet D., Dejax P., Gendreau M.: The profitable arc tour problem: solution with a branch-and-price algorithm. Transp. Sci. 39, 539–552 (2005) es_ES
dc.description.references Franquesa, C.: The Clustered Prize-collecting Arc Routing Problem. PhD Thesis, Technical University of Catalonia, Barcelona (2008) es_ES
dc.description.references Ghiani G., Laporte G.: A branch-and-cut algorithm for the undirected rural postman problem. Math. Progr. 87, 467–481 (2000) es_ES
dc.description.references Lenstra J.K., Rinnooy Kan A.H.G.: On general routing problems. Networks 6, 593–597 (1976) es_ES
dc.description.references Letchford A.N., Reinelt G., Theis D.O.: Odd minimum cut-sets and b-matchings revisited. SIAM J. Discret. Math. 22, 1480–1487 (2008) es_ES
dc.description.references Malandraki C., Daskin M.S.: The maximum benefit chinese postman problem and the maximum benefit traveling salesman problem. Eur. J. Oper. Res. 65, 218–234 (1993) es_ES
dc.description.references Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, New York (1988) es_ES
dc.description.references Orloff C.S.: A fundamental problem in vehicle routing. Networks 4, 35–64 (1974) es_ES
dc.description.references Pearn W.L., Chiu W.C.: Approximate solutions for the maximum benefit Chinese postman problem. Int. J. Syst. Sci. 36, 815–822 (2005) es_ES
dc.description.references Pearn W.L., Wang K.H.: On the maximum benefit Chinese postman problem. OMEGA 31, 269–273 (2003) es_ES
dc.description.references Reinelt G., Theis D.O.: Transformation of facets of the general routing problem polytope. SIAM J. Optim. 16, 220–234 (2005) es_ES


This item appears in the following Collection(s)

Show simple item record