- -

A Branch & Cut algorithm for the Windy General Routing Problem and Special Cases

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

Compartir/Enviar a

Citas

Estadísticas

  • Estadisticas de Uso

A Branch & Cut algorithm for the Windy General Routing Problem and Special Cases

Mostrar el registro completo del ítem

Corberán, A.; Plana, I.; Sanchís Llopis, JM. (2007). A Branch & Cut algorithm for the Windy General Routing Problem and Special Cases. Networks. 49(4):245-257. https://doi.org/10.1002/net.20176

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

Ficheros en el ítem

[Cerrado]
Nombre: Corberán;Plana;Sanchís ...
Tamaño: 201.4Kb
Formato: PDF
Descripción: Versión editorial
Solicitar una copia al autor

Metadatos del ítem

Título: A Branch & Cut algorithm for the Windy General Routing Problem and Special Cases
Autor: Corberán, A. Plana, I. 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] In this paper, we present an exact algorithm for the Windy General Routing Problem. This problem generalizes many important Arc Routing Problems and also has some interesting real-life applications. The Branch & Cut ...[+]
Palabras clave: Branch & cut , Arc routing , Windy general routing problem , Windy rural postman problem
Derechos de uso: Cerrado
Fuente:
Networks. (issn: 0028-3045 )
DOI: 10.1002/net.20176
Editorial:
John Wiley & Sons
Versión del editor: https://doi.org/10.1002/net.20176
Agradecimientos:
Contract grant sponsors: Ministerio de Ciencia y Tecnología of Spain; Generalitat Valenciana
Tipo: Artículo

References

, , , Finding cuts in the TSP, Technical Report, DIMACS 95–05, 1995.

Balaguer, C., Giménez, A., Pastor, J. M., Padrón, V. M., & Abderrahim, M. (2000). A climbing autonomous robot for inspection applications in 3D complex environments. Robotica, 18(3), 287-297. doi:10.1017/s0263574799002258

Benavent, E., Carrotta, A., Corberán, A., Sanchis, J. M., & Vigo, D. (2007). Lower bounds and heuristics for the Windy Rural Postman Problem. European Journal of Operational Research, 176(2), 855-869. doi:10.1016/j.ejor.2005.09.021 [+]
, , , Finding cuts in the TSP, Technical Report, DIMACS 95–05, 1995.

Balaguer, C., Giménez, A., Pastor, J. M., Padrón, V. M., & Abderrahim, M. (2000). A climbing autonomous robot for inspection applications in 3D complex environments. Robotica, 18(3), 287-297. doi:10.1017/s0263574799002258

Benavent, E., Carrotta, A., Corberán, A., Sanchis, J. M., & Vigo, D. (2007). Lower bounds and heuristics for the Windy Rural Postman Problem. European Journal of Operational Research, 176(2), 855-869. doi:10.1016/j.ejor.2005.09.021

Benavent, E., Corberán, A., Piñana, E., Plana, I., & Sanchis, J. M. (2005). New heuristic algorithms for the windy rural postman problem. Computers & Operations Research, 32(12), 3111-3128. doi:10.1016/j.cor.2004.04.007

Brucker, P. (1981). The chinese postman problem for mixed graphs. Lecture Notes in Computer Science, 354-366. doi:10.1007/3-540-10291-4_26

Chopra, S., & Rinaldi, G. (1996). The Graphical Asymmetric Traveling Salesman Polyhedron: Symmetric Inequalities. SIAM Journal on Discrete Mathematics, 9(4), 602-624. doi:10.1137/s089548019122232x

, , , An algorithm for the rural postman problem, Imperial College, London, 1981.

Christofides, N., Campos, V., Corberán, A., & Mota, E. (1986). An algorithm for the Rural Postman problem on a directed graph. Netflow at Pisa, 155-166. doi:10.1007/bfb0121091

Corberáan, A., Letchford, A. N., & Sanchis, J. M. (2001). A cutting plane algorithm for the General Routing Problem. Mathematical Programming, 90(2), 291-316. doi:10.1007/pl00011426

Corberán, A., Mejía, G., & Sanchis, J. M. (2005). New Results on the Mixed General Routing Problem. Operations Research, 53(2), 363-376. doi:10.1287/opre.1040.0168

Corberán, A., Mota, E., & Sanchis, J. M. (2006). A comparison of two different formulations for arc routing problems on mixed graphs. Computers & Operations Research, 33(12), 3384-3402. doi:10.1016/j.cor.2005.02.010

, , The windy general routing polyhedron: A global view of many known arc routing polyhedra, Technical Report TR06-2005 (http://www.uv.es/sestio/TechRep/tr06-05.pdf), Department of Statistics and O.R., University of Valencia, Spain.

Corberán, A., Plana, I., & Sanchis, J. M. (2006). Zigzag inequalities: a new class of facet-inducing inequalities for Arc Routing Problems. Mathematical Programming, 108(1), 79-96. doi:10.1007/s10107-005-0643-y

Corber�n, A., Romero, A., & Sanchis, J. M. (2003). The mixed general routing polyhedron. Mathematical Programming, 96(1), 103-137. doi:10.1007/s10107-003-0391-9

Corberán, A., & Sanchis, J. M. (1994). A polyhedral approach to the rural postman problem. European Journal of Operational Research, 79(1), 95-114. doi:10.1016/0377-2217(94)90398-0

Corberán, A., & Sanchis, J. M. (1998). The general routing problem polyhedron: Facets from the RPP and GTSP polyhedra. European Journal of Operational Research, 108(3), 538-550. doi:10.1016/s0377-2217(96)00337-2

Cornuéjols, G., Fonlupt, J., & Naddef, D. (1985). The traveling salesman problem on a graph and some related integer polyhedra. Mathematical Programming, 33(1), 1-27. doi:10.1007/bf01582008

(Editor), Arc routing: Theory, solutions and applications, Kluwer, New York, 2000.

Edmonds, J., & Johnson, E. L. (1973). Matching, Euler tours and the Chinese postman. Mathematical Programming, 5(1), 88-124. doi:10.1007/bf01580113

Eiselt, H. A., Gendreau, M., & Laporte, G. (1995). Arc Routing Problems, Part II: The Rural Postman Problem. Operations Research, 43(3), 399-414. doi:10.1287/opre.43.3.399

Fleischmann, B. (1985). A cutting plane procedure for the travelling salesman problem on road networks. European Journal of Operational Research, 21(3), 307-317. doi:10.1016/0377-2217(85)90151-1

Grötschel, M., & Win, Z. (1992). A cutting plane algorithm for the windy postman problem. Mathematical Programming, 55(1-3), 339-358. doi:10.1007/bf01581206

Guan, M. (1984). On the windy postman problem. Discrete Applied Mathematics, 9(1), 41-46. doi:10.1016/0166-218x(84)90089-1

Hertz, A., Laporte, G., & Hugo, P. N. (1999). Improvement Procedures for the Undirected Rural Postman Problem. INFORMS Journal on Computing, 11(1), 53-62. doi:10.1287/ijoc.11.1.53

Letchford, A. N. (1997). New inequalities for the General Routing Problem. European Journal of Operational Research, 96(2), 317-322. doi:10.1016/s0377-2217(96)00346-3

Minieka, E. (1979). The Chinese Postman Problem for Mixed Networks. Management Science, 25(7), 643-648. doi:10.1287/mnsc.25.7.643

Naddef, D., & Rinaldi, G. (1991). The symmetric traveling salesman polytope and its graphical relaxation: Composition of valid inequalities. Mathematical Programming, 51(1-3), 359-400. doi:10.1007/bf01586945

Padberg, M. W., & Rao, M. R. (1982). Odd Minimum Cut-Sets andb-Matchings. Mathematics of Operations Research, 7(1), 67-80. doi:10.1287/moor.7.1.67

Padberg, M., & Rinaldi, G. (1987). Optimization of a 532-city symmetric traveling salesman problem by branch and cut. Operations Research Letters, 6(1), 1-7. doi:10.1016/0167-6377(87)90002-2

Papadimitriou, C. H. (1976). On the complexity of edge traversing. Journal of the ACM, 23(3), 544-554. doi:10.1145/321958.321974

The windy general routing problem, Ph.D. Thesis, University of Valencia, Spain, 2005.

Contributions to routing problems, Ph.D. Thesis, University of Augsburg, Germany, 1987.

[-]

recommendations

 

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

Mostrar el registro completo del ítem