- -

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 sencillo del ítem

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
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-09-24T12:29:22Z
dc.date.available 2020-09-24T12:29:22Z
dc.date.issued 2007-07 es_ES
dc.identifier.issn 0028-3045 es_ES
dc.identifier.uri http://hdl.handle.net/10251/150647
dc.description.abstract [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 method presented here is based on a cutting-plane algorithm that identifies violated inequalities of several classes of facet-inducing inequalities for the corresponding polyhedron. The whole procedure has been tested over different sets of instances and is capable of solving to optimality large-size instances of several routing problems defined on undirected, mixed, and windy graphs. es_ES
dc.description.sponsorship Contract grant sponsors: Ministerio de Ciencia y Tecnología of Spain; Generalitat Valenciana es_ES
dc.language Inglés es_ES
dc.publisher John Wiley & Sons es_ES
dc.relation.ispartof Networks es_ES
dc.rights Reserva de todos los derechos es_ES
dc.subject Branch & cut es_ES
dc.subject Arc routing es_ES
dc.subject Windy general routing problem es_ES
dc.subject Windy rural postman problem es_ES
dc.subject.classification MATEMATICA APLICADA es_ES
dc.title A Branch & Cut algorithm for the Windy General Routing Problem and Special Cases es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1002/net.20176 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 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 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1002/net.20176 es_ES
dc.description.upvformatpinicio 245 es_ES
dc.description.upvformatpfin 257 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 49 es_ES
dc.description.issue 4 es_ES
dc.relation.pasarela S\32193 es_ES
dc.contributor.funder Generalitat Valenciana es_ES
dc.contributor.funder Ministerio de Ciencia y Tecnología es_ES
dc.description.references , , , Finding cuts in the TSP, Technical Report, DIMACS 95–05, 1995. es_ES
dc.description.references 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 es_ES
dc.description.references 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 es_ES
dc.description.references 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 es_ES
dc.description.references 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 es_ES
dc.description.references 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 es_ES
dc.description.references , , , An algorithm for the rural postman problem, Imperial College, London, 1981. es_ES
dc.description.references 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 es_ES
dc.description.references 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 es_ES
dc.description.references 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 es_ES
dc.description.references 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 es_ES
dc.description.references , , 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. es_ES
dc.description.references 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 es_ES
dc.description.references 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 es_ES
dc.description.references 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 es_ES
dc.description.references 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 es_ES
dc.description.references 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 es_ES
dc.description.references (Editor), Arc routing: Theory, solutions and applications, Kluwer, New York, 2000. es_ES
dc.description.references Edmonds, J., & Johnson, E. L. (1973). Matching, Euler tours and the Chinese postman. Mathematical Programming, 5(1), 88-124. doi:10.1007/bf01580113 es_ES
dc.description.references 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 es_ES
dc.description.references 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 es_ES
dc.description.references 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 es_ES
dc.description.references Guan, M. (1984). On the windy postman problem. Discrete Applied Mathematics, 9(1), 41-46. doi:10.1016/0166-218x(84)90089-1 es_ES
dc.description.references 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 es_ES
dc.description.references 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 es_ES
dc.description.references Minieka, E. (1979). The Chinese Postman Problem for Mixed Networks. Management Science, 25(7), 643-648. doi:10.1287/mnsc.25.7.643 es_ES
dc.description.references 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 es_ES
dc.description.references 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 es_ES
dc.description.references 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 es_ES
dc.description.references Papadimitriou, C. H. (1976). On the complexity of edge traversing. Journal of the ACM, 23(3), 544-554. doi:10.1145/321958.321974 es_ES
dc.description.references The windy general routing problem, Ph.D. Thesis, University of Valencia, Spain, 2005. es_ES
dc.description.references Contributions to routing problems, Ph.D. Thesis, University of Augsburg, Germany, 1987. es_ES


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

Mostrar el registro sencillo del ítem