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

Thumbnail Image
Full text at PDC
Publication Date
Ceselli, Alberto
Ortuño, M. Teresa
Righini, Giovanni
Tirado, Gregorio
Advisors (or tutors)
Journal Title
Journal ISSN
Volume Title
Google Scholar
Research Projects
Organizational Units
Journal Issue
We 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.
Este artículo es parte de Topical Collection on Decomposition at 70
UCM subjects
Matemáticas (Matemáticas)
Unesco subjects
12 Matemáticas
1. 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 6. Breunig U, Baldacci R, Hartl RF, Vidal T (2018) The Electric Two-Echelon Vehicle Routing Problem, Technical Report. Available at: 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: 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,, 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: 29. Desrosiers J, Soumis F, Desrochers M (1984) Routing with time windows by column generation. Networks 14(4):545–565