Aviso: para depositar documentos, por favor, inicia sesión e identifícate con tu cuenta de correo institucional de la UCM con el botón MI CUENTA UCM. No emplees la opción AUTENTICACIÓN CON CONTRASEÑA
 

A Branch-and-Cut-and-Price Algorithm for the Electric Vehicle Routing Problem with Multiple Technologies

Simple item page
dc.contributor.authorCeselli, Alberto
dc.contributor.authorFelipe Ortega, Ángel
dc.contributor.authorOrtuño Sánchez, María Teresa
dc.contributor.authorRighini, Giovanni
dc.contributor.authorTirado Domínguez, Gregorio
dc.date.accessioned2023-06-17T08:32:33Z
dc.date.available2023-06-17T08:32:33Z
dc.date.issued2021
dc.descriptionEste artículo es parte de Topical Collection on Decomposition at 70
dc.description.abstractWe provide an exact optimization algorithm for the electric vehicle routing problem with multiple recharge technologies. Our branch-and-cut-and-price algorithm relies upon a path-based formulation, where each column in the master problem represents a sequence of customer visits between two recharge stations instead of a whole route. This allows for massive decomposition, and parallel implementation of the pricing phase, exploiting the large number of independent pricing sub-problems. The algorithm could solve instances with up to thirty customers, nine recharge stations, fve vehicles and three technologies to proven optimality. Near-optimal heuristic solutions were obtained with a general-purpose MIP solver from the columns generated at the root node.en
dc.description.departmentDepto. de Estadística e Investigación Operativa
dc.description.facultyFac. de Ciencias Matemáticas
dc.description.refereedTRUE
dc.description.sponsorshipComunidad de Madrid
dc.description.sponsorshipGobierno de España
dc.description.statuspub
dc.eprint.idhttps://eprints.ucm.es/id/eprint/77496
dc.identifier.citationCeselli, A., Felipe, Á., Ortuño, M.T., Righini, G., Tirado, G.: A Branch-and-Cut-and-Price Algorithm for the Electric Vehicle Routing Problem with Multiple Technologies. SN Oper. Res. Forum. 2, 8 (2021). https://doi.org/10.1007/s43069-020-00052-x
dc.identifier.doi10.1007/s43069-020-00052-x
dc.identifier.issn2662-2556
dc.identifier.officialurlhttps://doi.org/10.1007/s43069-020-00052-x
dc.identifier.urihttps://hdl.handle.net/20.500.14352/7402
dc.issue.number1
dc.journal.titleOperations Research Forum
dc.language.isodan
dc.relation.projectIDS2013/ICE-2845
dc.relation.projectIDMTM2015-65803-R
dc.rightsAtribución 3.0 España
dc.rights.accessRightsopen access
dc.rights.urihttps://creativecommons.org/licenses/by/3.0/es/
dc.subject.cdu51
dc.subject.keywordElectric vehicle routing
dc.subject.keywordColumn generation
dc.subject.keywordCutting planes
dc.subject.keywordDynamic programming
dc.subject.ucmMatemáticas (Matemáticas)
dc.subject.unesco12 Matemáticas
dc.titleA Branch-and-Cut-and-Price Algorithm for the Electric Vehicle Routing Problem with Multiple Technologiesen
dc.typejournal article
dc.volume.number2
dcterms.references1. Andelmin J, Bartolini E (2017) An exact algorithm for the green vehicle routing problem. Transportation Science 51(4):1288–1303 2. Barnhart C, Boland NL, Clarke LW, Johnson EL, Nemhauser GL, Shenoi RG (1998) Flight String Models for Aircraft Fleeting and Routing. Transportation Science 32(3):208–220 3. Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Operations Research 59:1269–1283 4. Basso S, Ceselli A (2017) Asynchronous Column Generation, Proc. of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX) 5. Ceselli A, Righini G (2020) The Electric Traveling Salesman Problem: properties and models, Technical Report 2434/789142 - University of Milan https://doi.org/10.13140/RG.2.2.17712.99848 6. Breunig U, Baldacci R, Hartl RF, Vidal T (2018) The Electric Two-Echelon Vehicle Routing Problem, Technical Report. Available at: https://arxiv.org/pdf/1803.03628.pdf 7. Bruglieri M, Mancini S, Pisacane O (2018) Solving the green vehicle routing problem with capacitated alternative fuel stations, in Proceedings of 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization. France, Paris, pp 196–199 8. Christofdes N, Mingozzi A, Toth P (1981) Exact Algorithms for the Vehicle Routing Problem, Based on Spanning Tree and Shortest Path Relaxations. Mathematical Programming 20:255–282 9. Conrad RG, Figliozzi MA (2011) The recharging vehicle routing problem, Proceedings of the 2011 Industrial Engineering Research Conference, T. Doolen, E. van Aken eds., Portland, USA 10. Desaulniers G, Errico F, Irnich S, Schneider M (2016) Exact algorithms for electric vehicle-routing problems with time windows. Opererations Research 64(6):1388–1405 11. Erdogan S, Miller-Hooks E (2012) A green vehicle routing problem. Transportation Research Part E 48:100–114 12. Feillet D, Dejax P, Gendreau M, Gueguen C (2004) An exact algorithm for the elementary shortest path problem with resource constraints: application to some vehicle routing problems. Networks 44:216–229 13. Felipe Ortega A, Ortuño Sánchez MT, Righini G, Tirado Domínguez G (2014) A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges, Transportation Research Part E, 71:111-128 14. Hiermann G, Puchinger J, Ropke S, Hartl RF (2016) The electric feet size and mix vehicle routing problem with time windows and recharging stations. Eur J Oper Res 252(3):995–1018 15. Keskin M, Çatay B (2018) A matheuristic method for the electric vehicle routing problem with time windows and fast chargers. Comput Oper Res 100:172–188 16. Keskin M, Laporte G, Çatay B (2019) Electric Vehicle Routing Problem with Time-Dependent Waiting Times at Recharging Stations. Comput Oper Res 107:77–94 17. Koç C, Jabali O, Laporte G (2018) uthors Jacques Desrosiers. Long-haul vehicle routing and scheduling with idling options, Journal of the Operations Research Society 69(2):235–246 18. Koyuncu I, Yavuz M (2019) Duplicating nodes or arcs in green vehicle routing: A computational comparison of two formulations. Transportation Research Part E 122:605–623 19. Li-Ying W, Yuan-Bin S (2015) Multiple charging station location-routing problem with time window of electric vehicle. J Eng Sci Technol Rev 8(5):190–201 20. Lysgaard J, Letchford AN, Eglese RW (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Mathematical Programming 100:423–445 21. Montoya A, Guaret C, Mendoza JE, Villegas JG (2017) The electric vehicle routing problem with nonlinear charging function, Transportation Research B 103:87-110 22. Pelletier S, Jabali O, Laporte G (2016) Goods distribution with electric vehicles: review and research perspectives. Transportation Science 50(1):3–22 23. Sassi O, Cherif WR, Oulamara A (2014) Vehicle Routing Problem with Mixed Fleet of Conventional and Heterogenous Electric Vehicles and Time Dependent Charging Costs, Technical Report. Available at: https://hal.archives-ouvertes.fr/hal-01083966/ 24. Schneider M, Stenger A, Goeke D (2014) The electric vehicle-routing problem with time windows and recharging stations. Transportation Science 48:500–520 25. Schneider M (2014) Personal Communication 26. SCIP: Solving Constraint Integer Programs, scip.zib.de, last accessed 7.4.2015 27. Sweda TM, Dolinskaya IS, Klabjan D (2017) Adaptive routing and recharging policies for electric vehicles. Transp. Sci. 51(4):1326–1348 28. Villegas J, Guaret C, Mendoza JE, Montoya A (2018) The Technician Routing and Scheduling Problem with Conventional and Electric Vehicle, Technical Report. Available at: https://hal.archives-ouvertes.fr/hal-01813887/document 29. Desrosiers J, Soumis F, Desrochers M (1984) Routing with time windows by column generation. Networks 14(4):545–565
dspace.entity.typePublication
relation.isAuthorOfPublication72ddce0d-fbc4-4233-800c-cbd2cc36a012
relation.isAuthorOfPublication6f9ad449-8cec-4e55-aca2-7dedcde6b101
relation.isAuthorOfPublication9a8e32e5-51d7-41cd-9e5f-781d838bce09
relation.isAuthorOfPublication.latestForDiscovery72ddce0d-fbc4-4233-800c-cbd2cc36a012

Download

Original bundle

Now showing 1 - 1 of 1
Thumbnail Image
Name:
angel_felipe_branch.pdf
Size:
1.97 MB
Format:
Adobe Portable Document Format
downoload Download

Collections

Artículos