- -

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

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

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

Ficheros en el ítem

[Cerrado]
Nombre: 23-NETWORKSMMWRPP ...
Tamaño: 151.0Kb
Formato: PDF
Descripción: Versión editorial
Solicitar una copia al autor

Metadatos del ítem

Título: A Branch-Price-and-Cut Algorithm for the Min-Max k -Vehicle Windy Rural Postman Problem
Autor: Benavent Lopez, Enrique Corberán, Angel Desaulniers, Guy Lessard, François Plana, Isaac 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 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. ...[+]
Palabras clave: Rural postman problem , Windy rural postman problem , Multivehicle , Column generation , Branch-and-price , Cutting planes
Derechos de uso: Cerrado
Fuente:
Networks. (issn: 0028-3045 )
DOI: 10.1002/net.21520
Editorial:
John Wiley & Sons
Versión del editor: https://doi.org/10.1002/net.21520
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/NSERC//157935-07/
info:eu-repo/grantAgreement/MINECO//MTM2012-36163-C06-02/ES/MODELOS Y METODOS DE PROGRAMACION MATEMATICA Y SUS APLICACIONES (OPTIMOS3)/
Agradecimientos:
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
Tipo: Artículo

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

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

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 [+]
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

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

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

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

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

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

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

Á. Corberán I. Plana J.M. Sanchis Arc routing problems: Data instances www.uv.es/corberan/instancias.htm 2007

Dantzig, G. B., & Wolfe, P. (1960). Decomposition Principle for Linear Programs. Operations Research, 8(1), 101-111. doi:10.1287/opre.8.1.101

Desaulniers, G., Desrosiers, J., & Spoorendonk, S. (2011). Cutting planes for branch-and-price algorithms. Networks, 58(4), 301-310. doi:10.1002/net.20471

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

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

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

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

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

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

Lübbecke, M. E., & Desrosiers, J. (2005). Selected Topics in Column Generation. Operations Research, 53(6), 1007-1023. doi:10.1287/opre.1050.0234

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

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

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

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

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

[-]

recommendations

 

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

Mostrar el registro completo del ítem