{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,16]],"date-time":"2026-04-16T16:48:14Z","timestamp":1776358094838,"version":"3.51.2"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,1,26]],"date-time":"2021-01-26T00:00:00Z","timestamp":1611619200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,1,26]],"date-time":"2021-01-26T00:00:00Z","timestamp":1611619200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100009882","name":"Regione Lombardia","doi-asserted-by":"publisher","award":["E97F17000000009"],"award-info":[{"award-number":["E97F17000000009"]}],"id":[{"id":"10.13039\/501100009882","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002911","name":"Universidad Complutense de Madrid","doi-asserted-by":"publisher","award":["Visitantes Distinguidos 2011-12"],"award-info":[{"award-number":["Visitantes Distinguidos 2011-12"]}],"id":[{"id":"10.13039\/501100002911","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Government of Madrid","award":["project S2013\/ICE-2845"],"award-info":[{"award-number":["project S2013\/ICE-2845"]}]},{"name":"Government of Spain","award":["project MTM2015-65803-R"],"award-info":[{"award-number":["project MTM2015-65803-R"]}]},{"DOI":"10.13039\/100012352","name":"Universit\u00e0 degli Studi di Milano","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100012352","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["SN Oper. Res. Forum"],"published-print":{"date-parts":[[2021,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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, five 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.<\/jats:p>","DOI":"10.1007\/s43069-020-00052-x","type":"journal-article","created":{"date-parts":[[2021,1,26]],"date-time":"2021-01-26T06:02:51Z","timestamp":1611640971000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["A Branch-and-Cut-and-Price Algorithm for the Electric Vehicle Routing Problem with Multiple Technologies"],"prefix":"10.1007","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0983-2706","authenticated-orcid":false,"given":"Alberto","family":"Ceselli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u00c1ngel","family":"Felipe","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. Teresa","family":"Ortu\u00f1o","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giovanni","family":"Righini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gregorio","family":"Tirado","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,1,26]]},"reference":[{"issue":"4","key":"52_CR1","doi-asserted-by":"publisher","first-page":"1288","DOI":"10.1287\/trsc.2016.0734","volume":"51","author":"J Andelmin","year":"2017","unstructured":"Andelmin J, Bartolini E (2017) An exact algorithm for the green vehicle routing problem. Transp Sci 51(4):1288\u20131303","journal-title":"Transp Sci"},{"issue":"3","key":"52_CR2","doi-asserted-by":"publisher","first-page":"208","DOI":"10.1287\/trsc.32.3.208","volume":"32","author":"C Barnhart","year":"1998","unstructured":"Barnhart C, Boland NL, Clarke LW, Johnson EL, Nemhauser GL, Shenoi RG (1998) Flight String Models for Aircraft Fleeting and Routing. Transp Sci 32(3):208\u2013220","journal-title":"Transp Sci"},{"key":"52_CR3","doi-asserted-by":"publisher","first-page":"1269","DOI":"10.1287\/opre.1110.0975","volume":"59","author":"R Baldacci","year":"2011","unstructured":"Baldacci R, Mingozzi A, Roberti R (2011) New route relaxation and pricing strategies for the vehicle routing problem. Oper Res 59:1269\u20131283","journal-title":"Oper Res"},{"key":"52_CR4","doi-asserted-by":"crossref","unstructured":"Basso S, Ceselli A (2017)\u00a0Asynchronous Column Generation, Proc. of the Ninteenth Workshop on Algorithm Engineering and Experiments (ALENEX)","DOI":"10.1137\/1.9781611974768.16"},{"key":"52_CR5","doi-asserted-by":"publisher","unstructured":"Ceselli A, Righini G (2020)\u00a0The Electric Traveling Salesman Problem: properties and models, Technical Report 2434\/789142 - University of Milan https:\/\/doi.org\/10.13140\/RG.2.2.17712.99848","DOI":"10.13140\/RG.2.2.17712.99848"},{"key":"52_CR6","unstructured":"Breunig U, Baldacci R, Hartl RF, Vidal T (2018)\u00a0The Electric Two-Echelon Vehicle Routing Problem, Technical Report. Available at: https:\/\/arxiv.org\/pdf\/1803.03628.pdf"},{"key":"52_CR7","first-page":"196","volume-title":"Solving the green vehicle routing problem with capacitated alternative fuel stations, in Proceedings of 16th Cologne-Twente Workshop on Graphs and Combinatorial Optimization","author":"M Bruglieri","year":"2018","unstructured":"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\u2013199"},{"key":"52_CR8","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/BF01589353","volume":"20","author":"N Christofides","year":"1981","unstructured":"Christofides N, Mingozzi A, Toth P (1981) Exact Algorithms for the Vehicle Routing Problem, Based on Spanning Tree and Shortest Path Relaxations. Math Program 20:255\u2013282","journal-title":"Math Program"},{"key":"52_CR9","unstructured":"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"},{"issue":"6","key":"52_CR10","doi-asserted-by":"publisher","first-page":"1388","DOI":"10.1287\/opre.2016.1535","volume":"64","author":"G Desaulniers","year":"2016","unstructured":"Desaulniers G, Errico F, Irnich S, Schneider M (2016) Exact algorithms for electric vehicle-routing problems with time windows. Oper Res 64(6):1388\u20131405","journal-title":"Oper Res"},{"key":"52_CR11","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/j.tre.2011.08.001","volume":"48","author":"S Erdogan","year":"2012","unstructured":"Erdogan S, Miller-Hooks E (2012) A green vehicle routing problem. Transp Res Part E 48:100\u2013114","journal-title":"Transp Res Part E"},{"key":"52_CR12","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1002\/net.20033","volume":"44","author":"D Feillet","year":"2004","unstructured":"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\u2013229","journal-title":"Networks"},{"key":"52_CR13","doi-asserted-by":"crossref","unstructured":"Felipe Ortega\u00a0A,\u00a0Ortu\u00f1o S\u00e1nchez MT,\u00a0Righini G, Tirado Dom\u00ednguez G (2014) A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges, Transp Res Part E, 71:111-128","DOI":"10.1016\/j.tre.2014.09.003"},{"issue":"3","key":"52_CR14","doi-asserted-by":"publisher","first-page":"995","DOI":"10.1016\/j.ejor.2016.01.038","volume":"252","author":"G Hiermann","year":"2016","unstructured":"Hiermann G, Puchinger J, Ropke S, Hartl RF (2016) The electric fleet size and mix vehicle routing problem with time windows and recharging stations. Eur J Oper Res 252(3):995\u20131018","journal-title":"Eur J Oper Res"},{"key":"52_CR15","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1016\/j.cor.2018.06.019","volume":"100","author":"M Keskin","year":"2018","unstructured":"Keskin M, \u00c7atay B (2018) A matheuristic method for the electric vehicle routing problem with time windows and fast chargers. Comput Oper Res 100:172\u2013188","journal-title":"Comput Oper Res"},{"key":"52_CR16","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/j.cor.2019.02.014","volume":"107","author":"M Keskin","year":"2019","unstructured":"Keskin M, Laporte G, \u00c7atay B (2019) Electric Vehicle Routing Problem with Time-Dependent Waiting Times at Recharging Stations. Comput Oper Res 107:77\u201394","journal-title":"Comput Oper Res"},{"issue":"2","key":"52_CR17","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1057\/s41274-017-0202-y","volume":"69","author":"C Ko\u00e7","year":"2018","unstructured":"Ko\u00e7 C, Jabali O, Laporte G (2018) Long-haul vehicle routing and scheduling with idling options. J Oper Res Soc 69(2):235\u2013246","journal-title":"J Oper Res Soc"},{"key":"52_CR18","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1016\/j.tre.2018.11.003","volume":"122","author":"I Koyuncu","year":"2019","unstructured":"Koyuncu I, Yavuz M (2019) Duplicating nodes or arcs in green vehicle routing: A computational comparison of two formulations. Transp Res Part E 122:605\u2013623","journal-title":"Transp Res Part E"},{"issue":"5","key":"52_CR19","doi-asserted-by":"publisher","first-page":"190","DOI":"10.25103\/jestr.085.24","volume":"8","author":"W Li-Ying","year":"2015","unstructured":"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\u2013201","journal-title":"J Eng Sci Technol Rev"},{"key":"52_CR20","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/s10107-003-0481-8","volume":"100","author":"J Lysgaard","year":"2004","unstructured":"Lysgaard J, Letchford AN, Eglese RW (2004) A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math Program 100:423\u2013445","journal-title":"Math Program"},{"key":"52_CR21","doi-asserted-by":"crossref","unstructured":"Montoya A, Guaret C, Mendoza JE, Villegas JG (2017) The electric vehicle routing problem with nonlinear charging function, Transp Res B 103:87-110","DOI":"10.1016\/j.trb.2017.02.004"},{"issue":"1","key":"52_CR22","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1287\/trsc.2015.0646","volume":"50","author":"S Pelletier","year":"2016","unstructured":"Pelletier S, Jabali O, Laporte G (2016) Goods distribution with electric vehicles: review and research perspectives. Transp Sci 50(1):3\u201322","journal-title":"Transp Sci"},{"key":"52_CR23","unstructured":"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\/"},{"key":"52_CR24","doi-asserted-by":"publisher","first-page":"500","DOI":"10.1287\/trsc.2013.0490","volume":"48","author":"M Schneider","year":"2014","unstructured":"Schneider M, Stenger A, Goeke D (2014) The electric vehicle-routing problem with time windows and recharging stations. Transp Sci 48:500\u2013520","journal-title":"Transp Sci"},{"key":"52_CR25","unstructured":"Schneider M (2014) Personal Communication"},{"key":"52_CR26","unstructured":"SCIP: Solving Constraint Integer Programs, scip.zib.de, last accessed 7.4.2015"},{"issue":"4","key":"52_CR27","doi-asserted-by":"publisher","first-page":"1326","DOI":"10.1287\/trsc.2016.0724","volume":"51","author":"TM Sweda","year":"2017","unstructured":"Sweda TM, Dolinskaya IS, Klabjan D (2017) Adaptive routing and recharging policies for electric vehicles. Transp Sci 51(4):1326\u20131348","journal-title":"Transp Sci"},{"key":"52_CR28","unstructured":"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"},{"key":"52_CR29","doi-asserted-by":"crossref","unstructured":"Desrosiers J, Soumis F, Desrochers M (1984) Routing with time windows by column generation. Networks 14(4):545\u2013565","DOI":"10.1002\/net.3230140406"}],"container-title":["Operations Research Forum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-020-00052-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s43069-020-00052-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s43069-020-00052-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,18]],"date-time":"2021-11-18T13:22:34Z","timestamp":1637241754000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s43069-020-00052-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,26]]},"references-count":29,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["52"],"URL":"https:\/\/doi.org\/10.1007\/s43069-020-00052-x","relation":{},"ISSN":["2662-2556"],"issn-type":[{"value":"2662-2556","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,26]]},"assertion":[{"value":"9 March 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 December 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 January 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"On behalf of all authors, the corresponding author states that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}}],"article-number":"8"}}