- -

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

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

Compartir/Enviar a

Citas

Estadísticas

  • Estadisticas de Uso

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

Mostrar el registro completo del ítem

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

Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10251/151300

Ficheros en el ítem

Thumbnail
Nombre: Corberán;Plana;Ro ...
Tamaño: 376.7Kb
Formato: PDF
Descripción: Versión del Autor.
Abrir/Preview
[Cerrado]
Nombre: 22-MP-MBCPP-Chia2 ...
Tamaño: 447.5Kb
Formato: PDF
Descripción: Versión editorial
Solicitar una copia al autor

Metadatos del ítem

Título: A branch-and-cut algorithm for the maximum benefit Chinese postman problem
Autor: Corberán, Angel Plana, Isaac Rodríguez-Chía, Antonio Manuel 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] 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 ...[+]
Palabras clave: Chinese postman problem , Maximum benefit Chinese postman problem , Rural postman Problem , Facets , Branch-and-cut
Derechos de uso: Reserva de todos los derechos
Fuente:
Mathematical Programming. (issn: 0025-5610 )
DOI: 10.1007/s10107-011-0507-6
Editorial:
Springer-Verlag
Versión del editor: https://doi.org/10.1007/s10107-011-0507-6
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/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/
info:eu-repo/grantAgreement/MICINN//DE2009-0057/ES/DE2009-0057/
info:eu-repo/grantAgreement/MICINN//MTM2010-19576-C02-02/ES/DISEÑO OPTIMO EN REDES LOGISTICAS/
Agradecimientos:
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. ...[+]
Tipo: Artículo

References

Aráoz J., Fernández E., Franquesa C.: The clustered price-collecting arc-routing problem. Transp. Sci. 43, 287–300 (2009)

Aráoz J., Fernández E., Meza O.: Solving the prize-collecting rural postman problem. Eur. J. Oper. Res. 196, 886–896 (2009)

Aráoz J., Fernández E., Zoltan C.: Privatized rural postman problems. Comput. Oper. Res. 33, 3432–3449 (2006) [+]
Aráoz J., Fernández E., Franquesa C.: The clustered price-collecting arc-routing problem. Transp. Sci. 43, 287–300 (2009)

Aráoz J., Fernández E., Meza O.: Solving the prize-collecting rural postman problem. Eur. J. Oper. Res. 196, 886–896 (2009)

Aráoz J., Fernández E., Zoltan C.: Privatized rural postman problems. Comput. Oper. Res. 33, 3432–3449 (2006)

Archetti C., Feillet D., Hertz A., Speranza M.G.: The undirected capacitated arc routing problem with profits. Comput. Oper. Res. 37, 1860–1869 (2010)

Barahona F., Grötschel M.: On the cycle polytope of a binary matroid. J. Comb. Theory B 40, 40–62 (1986)

Fernández E., Fernández E., Franquesa C., Sanchis J.M.: The windy clustered prize-collecting problem. Transp. Sci. 45, 317–334 (2011)

Letchford A.N., Letchford A.N., Sanchis J.M.: A cutting-plane algorithm for the general routing problem. Math. Progr. 90, 291–316 (2001)

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)

Corberán, Á., Plana, I., Sanchis, J.M.: Arc Routing Problems: Data Instances. http://www.uv.es/corberan/instancias.htm

Sanchis J.M., Sanchis J.M.: A polyhedral approach to the rural postman problem. Eur. J. Oper. Res. 79, 95–114 (1994)

Feillet D., Dejax P., Gendreau M.: The profitable arc tour problem: solution with a branch-and-price algorithm. Transp. Sci. 39, 539–552 (2005)

Franquesa, C.: The Clustered Prize-collecting Arc Routing Problem. PhD Thesis, Technical University of Catalonia, Barcelona (2008)

Ghiani G., Laporte G.: A branch-and-cut algorithm for the undirected rural postman problem. Math. Progr. 87, 467–481 (2000)

Lenstra J.K., Rinnooy Kan A.H.G.: On general routing problems. Networks 6, 593–597 (1976)

Letchford A.N., Reinelt G., Theis D.O.: Odd minimum cut-sets and b-matchings revisited. SIAM J. Discret. Math. 22, 1480–1487 (2008)

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)

Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley, New York (1988)

Orloff C.S.: A fundamental problem in vehicle routing. Networks 4, 35–64 (1974)

Pearn W.L., Chiu W.C.: Approximate solutions for the maximum benefit Chinese postman problem. Int. J. Syst. Sci. 36, 815–822 (2005)

Pearn W.L., Wang K.H.: On the maximum benefit Chinese postman problem. OMEGA 31, 269–273 (2003)

Reinelt G., Theis D.O.: Transformation of facets of the general routing problem polytope. SIAM J. Optim. 16, 220–234 (2005)

[-]

recommendations

 

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

Mostrar el registro completo del ítem