- -

A Branch-Price-and-Cut Algorithm for the Min-Max k -Vehicle Windy Rural Postman Problem

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

Compartir/Enviar a

Citas

Estadísticas

  • Estadisticas de Uso

A Branch-Price-and-Cut Algorithm for the Min-Max k -Vehicle Windy Rural Postman Problem

Mostrar el registro sencillo del ítem

Ficheros en el ítem

[Cerrado]
Nombre: 23-NETWORKSMMWRPP ...
Tamaño: 151.0Kb
Formato: PDF
Descripción: Versión editorial
Solicitar una copia al autor
dc.contributor.author Benavent Lopez, Enrique es_ES
dc.contributor.author Corberán, Angel es_ES
dc.contributor.author Desaulniers, Guy es_ES
dc.contributor.author Lessard, François es_ES
dc.contributor.author Plana, Isaac es_ES
dc.contributor.author Sanchís Llopis, José María es_ES
dc.date.accessioned 2018-07-06T07:18:05Z
dc.date.available 2018-07-06T07:18:05Z
dc.date.issued 2014 es_ES
dc.identifier.issn 0028-3045 es_ES
dc.identifier.uri http://hdl.handle.net/10251/105402
dc.description.abstract [EN] The min-max k -vehicles windy rural postman problem consists of minimizing the maximal distance traveled by a vehicle to find a set of balanced routes that jointly service all the required edges in a windy graph. This is a very difficult problem, for which a branch-and-cut algorithm has already been proposed, providing good results when the number of vehicles is small. In this article, we present a branch-price-and-cut method capable of obtaining optimal solutions for this problem when the number of vehicles is larger for the same set of required edges. Extensive computational results on instances from the literature are presented. es_ES
dc.description.sponsorship Contract grant sponsor: Ministerio de Education y Ciencia of Spain: Contract gram number: MTM2006-14961-C05-02 Canadian Natural Sciences and Engineering Research Council; Contract grant number: 157935-07
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 Rural postman problem es_ES
dc.subject Windy rural postman problem es_ES
dc.subject Multivehicle es_ES
dc.subject Column generation es_ES
dc.subject Branch-and-price es_ES
dc.subject Cutting planes es_ES
dc.subject.classification MATEMATICA APLICADA es_ES
dc.title A Branch-Price-and-Cut Algorithm for the Min-Max k -Vehicle Windy Rural Postman Problem es_ES
dc.type Artículo es_ES
dc.identifier.doi 10.1002/net.21520 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/NSERC//157935-07/ es_ES
dc.relation.projectID info:eu-repo/grantAgreement/MINECO//MTM2012-36163-C06-02/ES/MODELOS Y METODOS DE PROGRAMACION MATEMATICA Y SUS APLICACIONES (OPTIMOS3)/ 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 Benavent Lopez, E.; Corberán, A.; Desaulniers, G.; Lessard, F.; Plana, I.; Sanchís Llopis, JM. (2014). A Branch-Price-and-Cut Algorithm for the Min-Max k -Vehicle Windy Rural Postman Problem. Networks. 63(1):34-45. https://doi.org/10.1002/net.21520 es_ES
dc.description.accrualMethod S es_ES
dc.relation.publisherversion https://doi.org/10.1002/net.21520 es_ES
dc.description.upvformatpinicio 34 es_ES
dc.description.upvformatpfin 45 es_ES
dc.type.version info:eu-repo/semantics/publishedVersion es_ES
dc.description.volume 63 es_ES
dc.description.issue 1 es_ES
dc.relation.pasarela S\256985 es_ES
dc.contributor.funder Ministerio de Ciencia e Innovación es_ES
dc.contributor.funder Ministerio de Economía y Competitividad es_ES
dc.contributor.funder Natural Sciences and Engineering Research Council of Canada
dc.description.references Baldacci, R., Mingozzi, A., & Roberti, R. (2011). New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem. Operations Research, 59(5), 1269-1283. doi:10.1287/opre.1110.0975 es_ES
dc.description.references Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998). Branch-and-Price: Column Generation for Solving Huge Integer Programs. Operations Research, 46(3), 316-329. doi:10.1287/opre.46.3.316 es_ES
dc.description.references Benavent, E., Corberán, A., Plana, I., & Sanchis, J. M. (2009). Min-MaxK-vehicles windy rural postman problem. Networks, 54(4), 216-226. doi:10.1002/net.20334 es_ES
dc.description.references Benavent, E., Corberán, Á., & Sanchis, J. M. (2009). A metaheuristic for the min–max windy rural postman problem with K vehicles. Computational Management Science, 7(3), 269-287. doi:10.1007/s10287-009-0119-2 es_ES
dc.description.references Benavent, E., Corberán, A., Plana, I., & Sanchis, J. M. (2011). New facets and an enhanced branch-and-cut for the min-max K-vehicles windy rural postman problem. Networks, 58(4), 255-272. doi:10.1002/net.20469 es_ES
dc.description.references Boland, N., Dethridge, J., & Dumitrescu, I. (2006). Accelerated label setting algorithms for the elementary resource constrained shortest path problem. Operations Research Letters, 34(1), 58-68. doi:10.1016/j.orl.2004.11.011 es_ES
dc.description.references Corberán, A., Plana, I., & Sanchis, J. M. (2008). The Windy General Routing Polyhedron: A Global View of Many Known Arc Routing Polyhedra. SIAM Journal on Discrete Mathematics, 22(2), 606-628. doi:10.1137/050640886 es_ES
dc.description.references Á. Corberán I. Plana J.M. Sanchis Arc routing problems: Data instances www.uv.es/corberan/instancias.htm 2007 es_ES
dc.description.references Dantzig, G. B., & Wolfe, P. (1960). Decomposition Principle for Linear Programs. Operations Research, 8(1), 101-111. doi:10.1287/opre.8.1.101 es_ES
dc.description.references Desaulniers, G., Desrosiers, J., & Spoorendonk, S. (2011). Cutting planes for branch-and-price algorithms. Networks, 58(4), 301-310. doi:10.1002/net.20471 es_ES
dc.description.references Desaulniers, G., Lessard, F., & Hadjar, A. (2008). Tabu Search, Partial Elementarity, and Generalizedk-Path Inequalities for the Vehicle Routing Problem with Time Windows. Transportation Science, 42(3), 387-404. doi:10.1287/trsc.1070.0223 es_ES
dc.description.references Dror, M. (1994). Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW. Operations Research, 42(5), 977-978. doi:10.1287/opre.42.5.977 es_ES
dc.description.references Gilmore, P. C., & Gomory, R. E. (1961). A Linear Programming Approach to the Cutting-Stock Problem. Operations Research, 9(6), 849-859. doi:10.1287/opre.9.6.849 es_ES
dc.description.references Hadjar, A., Marcotte, O., & Soumis, F. (2006). A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem. Operations Research, 54(1), 130-149. doi:10.1287/opre.1050.0240 es_ES
dc.description.references Hoffman, K. L., & Padberg, M. (1993). Solving Airline Crew Scheduling Problems by Branch-and-Cut. Management Science, 39(6), 657-682. doi:10.1287/mnsc.39.6.657 es_ES
dc.description.references Jepsen, M., Petersen, B., Spoorendonk, S., & Pisinger, D. (2008). Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows. Operations Research, 56(2), 497-511. doi:10.1287/opre.1070.0449 es_ES
dc.description.references Lübbecke, M. E., & Desrosiers, J. (2005). Selected Topics in Column Generation. Operations Research, 53(6), 1007-1023. doi:10.1287/opre.1050.0234 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 Pearn, W. L. (1994). Solvable cases of the k-person Chinese postman problem. Operations Research Letters, 16(4), 241-244. doi:10.1016/0167-6377(94)90073-6 es_ES
dc.description.references Righini, G., & Salani, M. (2006). Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints. Discrete Optimization, 3(3), 255-273. doi:10.1016/j.disopt.2006.05.007 es_ES
dc.description.references Righini, G., & Salani, M. (2008). New dynamic programming algorithms for the resource constrained elementary shortest path problem. Networks, 51(3), 155-170. doi:10.1002/net.20212 es_ES
dc.description.references Ropke, S., & Cordeau, J.-F. (2009). Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows. Transportation Science, 43(3), 267-286. doi:10.1287/trsc.1090.0272 es_ES


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

Mostrar el registro sencillo del ítem