- -

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 full item record

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

Files in this item

Item Metadata

Title: A branch-and-cut algorithm for the maximum benefit Chinese postman problem
Author: Corberán, Angel Plana, Isaac Rodríguez-Chía, Antonio Manuel Sanchís Llopis, José María
UPV Unit: Universitat Politècnica de València. Departamento de Matemática Aplicada - Departament de Matemàtica Aplicada
Issued date:
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 ...[+]
Subjects: Chinese postman problem , Maximum benefit Chinese postman problem , Rural postman Problem , Facets , Branch-and-cut
Copyrigths: Reserva de todos los derechos
Source:
Mathematical Programming. (issn: 0025-5610 )
DOI: 10.1007/s10107-011-0507-6
Publisher:
Springer-Verlag
Publisher version: https://doi.org/10.1007/s10107-011-0507-6
Project ID:
Ministerio de Ciencia e Innovación/MTM2009-14039-C06-02
Junta de Andalucía/P10-FQM-5849
MICINN/DE2009-0057
MICINN/MTM2010-19576-C02-02
Thanks:
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. ...[+]
Type: 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)

[-]

This item appears in the following Collection(s)

Show full item record