Electric Vehicle Fleets: Scalable Route and Recharge Scheduling Through Column Generation

References

• Adler JD, Mirchandani PB (2017) The vehicle scheduling problem for fleets with alternative-fuel vehicles. Transportation Sci. 51(2):441–456.Link, Google Scholar
• Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: Column generation for solving huge integer programs. Oper. Res. 46(3):316–329.Link, Google Scholar
• Bengio Y, Lodi A, Prouvost A (2021) Machine learning for combinatorial optimization: A methodological tour d’horizon. Eur. J. Oper. Res. 290(2):405–421.Crossref, Google Scholar
• BloombergNEF (2021) Electric vehicle outlook. Accessed February 21, 2023, https://about.bnef.com/electric-vehicle-outlook/.Google Scholar
• Bodin L, Golden B, Assad A, Ball M (1983) Routing and scheduling of vehicles and crews: The state of the art. Comput. Oper. Res. 10(2):63–211.Crossref, Google Scholar
• Bolívar MA, Lozano L, Medaglia AL (2014) Acceleration strategies for the weight constrained shortest path problem with replenishment. Optim. Lett. 8(8):2155–2172.Crossref, Google Scholar
• Brandstätter G, Gambella C, Leitner M, Malaguti E, Masini Fi, Puchinger J, Ruthmair M, et al. (2016) Overview of optimization problems in electric car-sharing system design and management. Dawid H, Doerner KF, Feichtinger G, Kort PM, Seidl A, eds. Dynamic Perspectives on Managerial Decision Making (Springer International Publishing, Berlin), 441–471.Crossref, Google Scholar
• Breunig U, Baldacci R, Hartl R, Vidal T (2019) The electric two-echelon vehicle routing problem. Comput. Oper. Res. 103:198–210.Crossref, Google Scholar
• Bunte S, Kliewer N (2009) An overview on vehicle scheduling models. Public Transportation (Berlin) 1(4):299–317.Crossref, Google Scholar
• Cabrera N, Medaglia AL, Lozano L, Duque D (2020) An exact bidirectional pulse algorithm for the constrained shortest path. Networks 76(2):128–146.Crossref, Google Scholar
• De Jong S (2018) London’s iconic black cabs go electric. Accessed February 21, 2023, https://abcnews.go.com/International/londons-iconic-black-cabs-electric/story?id=53907312.Google Scholar
• Desaulniers G, Errico F, Irnich S, Schneider M (2016) Exact algorithms for electric vehicle-routing problems with time windows. Oper. Res. 64(6):1388–1405.Link, Google Scholar
• Desrosiers J, Dumas Y, Solomon MM, Soumis F (1995) Time constrained routing and scheduling. Ball M, Magnanti TL, Monma CL, Nemhauser GL, eds. Network Routing (North-Holland, Amsterdam), 35–139.Crossref, Google Scholar
• Dumitrescu I, Boland N (2003) Improved preprocessing, labeling and scaling algorithms for the weight-constrained shortest path problem. Networks 42(3):135–153.Crossref, Google Scholar
• Dunne MJ (2017) China deploys aggressive mandates to take lead in electric vehicles. Accessed February 21, 2023, https://www.forbes.com/sites/michaeldunne/2017/02/28/china-deploys-aggressive-mandates-to-stay-no-1-in-electric-vehicles.Google Scholar
• Felipe Á, Ortuño MT, Righini G, Tirado G (2014) A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges. Transportation Res., Part E Logist. Transportation Rev. 71:111–128.Crossref, Google Scholar
• Gasse M, Chetelat D, Ferroni N, Charlin L, Lodi A (2019) Exact combinatorial optimization with graph convolutional neural networks. Wallach H, Larochelle H, Beygelzimer A, d’Alché Buc F, Fox E, Garnett R, eds. Advances in Neural Information Processing Systems, vol. 32 (Curran Associates, Red Hook, NY).Google Scholar
• Haghani A, Banihashemi M (2002) Heuristic approaches for solving large-scale bus transit vehicle scheduling problem with route time constraints. Transportation Res. Part A Policy Practice 36:309–333.Crossref, Google Scholar
• Hiermann G, Hartl R, Puchinger J, Vidal T (2019) Routing a mix of conventional, plug-in hybrid, and electric vehicles. Eur. J. Oper. Res. 272(1):235–248.Crossref, Google Scholar
• 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–1018.Crossref, Google Scholar
• Hu L, Dong J, Lin Z, Yang J (2018) Analyzing battery electric vehicle feasibility from taxi travel patterns: The case study of New York City, USA. Transportation Res. Part C: Emerging Tech. 87:91–104.Crossref, Google Scholar
• Irnich S, Desaulniers G (2005) Shortest path problems with resource constraints. Desaulniers G, Desrosiers J, Solomon MM, eds., Column Generation (Springer, New York), 33–65.Crossref, Google Scholar
• Joshi CK, Laurent T, Bresson X (2019) An efficient graph convolutional network technique for the travelling salesman problem. Preprint, submitted October 14, https://arxiv.org/abs/1906.01227.Google Scholar
• Kergosien Y, Giret A, Neron E, Sauvanet G (2021) An efficient label-correcting algorithm for the multiobjective shortest path problem. INFORMS J. Comput. 34(1):76–92.Google Scholar
• 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.Crossref, Google Scholar
• Li J-Q (2014) Transit bus scheduling with limited energy. Transportation Sci. 48(4):521–539.Link, Google Scholar
• Li Y, Zhan C, de Jong M, Lukszo Z (2016) Business innovation and government regulation for the promotion of electric vehicle use: Lessons from Shenzhen, China. J. Clean Production 134:371–383.Crossref, Google Scholar
• London Authorities (2018) Mayor marks key milestone of 100 rapid charging points across London. Accessed February 21, 2023, https://www.london.gov.uk/press-releases/mayoral/mayor-marks-100th-rapid-charge-point-in-london.Google Scholar
• Mahmoud M, Garnett R, Ferguson M, Kanaroglou P (2016) Electric buses: A review of alternative powertrains. Renewable Sustainable Energy Rev. 62:673–684.Crossref, Google Scholar
• Martinelli R, Pecin D, Poggi M, Longo H (2011) A branch-cut-and-price algorithm for the capacitated arc routing problem. Proc. Internat. Sympos. on Experiment. Algorithms (Springer, Berlin), 315–326.Google Scholar
• Montoya A, Guéret C, Mendoza JE, Villegas JG (2017) The electric vehicle routing problem with nonlinear charging function. Transportation Res. Part B: Methodological 103:87–110.Crossref, Google Scholar
• Parmentier A (2019) Algorithms for non-linear and stochastic resource constrained shortest paths. Math. Methods Oper. Res. 89:281–317.Crossref, Google Scholar
• Pelletier S, Jabali O, Laporte G (2016) 50th anniversary invited article—Goods distribution with electric vehicles: Review and research perspectives. Transportation Sci. 50(1):3–22.Link, Google Scholar
• Pelletier S, Jabali O, Laporte G, Veneroni M (2017) Battery degradation and behaviour for electric vehicles: Review and numerical analyses of several models. Transportation Res. Part B: Methodological 103:158–187.Crossref, Google Scholar
• Pessoa A, Uchoa E, De Aragão MP, Rodrigues R (2010) Exact algorithm over an arc-time-indexed formulation for parallel machine scheduling problems. Math. Programming Comput. 2(3):259–290.Crossref, Google Scholar
• Ribeiro CC, Soumis F (1994) A column generation approach to the multiple-depot vehicle scheduling problem. Oper. Res. 42(1):41–52.Link, Google Scholar
• Sadykov R, Vanderbeck F, Pessoa A, Tahiri I, Uchoa E (2019) Primal heuristics for branch and price: The assets of diving methods. INFORMS J. Comput. 31(2):251–267.Link, Google Scholar
• Schiffer M, Schneider M, Walther G, Laporte G (2019) Vehicle routing and location-routing with intermediate stops: A review. Transportation Sci. 53(2):319–343.Link, Google Scholar
• Schiffer M, Walther G (2017) The electric location routing problem with time windows and partial recharging. Eur. J. Oper. Res. 260(3):995–1013.Crossref, Google Scholar
• Scorrano M, Danielis R, Giansoldati M (2020) Mandating the use of the electric taxis: The case of Florence. Transportation Res. Part A Policy Practice 132:402–414.Crossref, Google Scholar
• Smith OJ, Boland N, Waterer H (2012) Solving shortest path problems with a weight constraint and replenishment arcs. Comput. Oper. Res. 39(5):964–984.Crossref, Google Scholar
• Thomas BW, Calogiuri T, Hewitt M (2019) An exact bidirectional A* approach for solving resource-constrained shortest path problems. Networks 73(2):187–205.Crossref, Google Scholar
• Tilk C, Rothenbächer A-K, Gschwind T, Irnich S (2017) Asymmetry matters: Dynamic half-way points in bidirectional labeling for solving shortest path problems with resource constraints faster. Eur. J. Oper. Res. 261(2):530–539.Crossref, Google Scholar
• van Kooten Niekerk ME, van den Akker JM, Hoogeveen JA (2017) Scheduling electric vehicles. Public Transportation (Berlin) 9(1–2):155–176.Crossref, Google Scholar
• Vidal T, Laporte G, Matl P (2020) A concise guide to existing and emerging vehicle routing problem variants. Eur. J. Oper. Res. 286:401–416.Crossref, Google Scholar
• Wang Y, Huang Y, Xu J, Barclay N (2017) Optimal recharging scheduling for urban electric buses: A case study in Davis. Transportation Res., Part E Logist. Transportation Rev. 100:115–132.Crossref, Google Scholar
• Wen M, Linde E, Ropke S, Mirchandani P, Larsen A (2016) An adaptive large neighborhood search heuristic for the electric vehicle scheduling problem. Comput. Oper. Res. 76:73–83.Crossref, Google Scholar