The Effect of Nonlinear Charging Function and Line Change Constraints on Electric Bus Scheduling

  • Aijia Zhang School of Transportation, Southeast University, Nanjing, China
  • Tiezhu Li School of Transportation, Southeast University, Nanjing, China
  • Ran Tu School of Transportation, Southeast University, Nanjing, China
  • Changyin Dong School of Transportation, Southeast University, Nanjing, China
  • Haibo Chen Institute for Transport Studies, University of Leeds, UK
  • Jianbing Gao Institute for Transport Studies, University of Leeds, UK
  • Ye Liu Institute for Transport Studies, University of Leeds, UK
Keywords: electric bus scheduling problem, nonlinear charging function, line change constraints, mixed integer optimisation, heuristic algorithm

Abstract

The recharging plans are a key component of the electric bus schedule. Since the real-world charging function of electric vehicles follows a nonlinear relationship with the charging duration, it is challenging to accurately estimate the charging time. To provide a feasible bus schedule given the nonlinear charging function, this paper proposes a mixed integer programming model with a piecewise linear charging approximation and multi-depot and multi-vehicle type scheduling. The objective of the model is to minimise the total cost of the schedule, which includes the vehicle purchasing cost and operation cost. From a practical point of view, the number of line changes of each bus is also taken as one of the constraints in the optimisation. An improved heuristic algorithm is then proposed to find high-quality solutions of the problem with an efficient computation. Finally, a real-world dataset is used for the case study. The results of using different charging functions indicate a large deviation between the linear charging function and the piecewise linear approximation, which can effectively avoid the infeasible bus schedules. Moreover, the experiments show that the proposed line change constraints can be an effective control method for transit operators.

References

Li J-Q. Battery-electric transit bus developments and operations: A review. International Journal of Sustainable Transportation. 2016;10(3): 157-69. DOI: 10.1080/15568318.2013.872737

Liu T, Ceder AA. Battery-electric transit vehicle scheduling with optimal number of stationary chargers. Transportation Research Part C: Emerging Technologies. 2020;114:118-39. DOI: 10.1016/j.trc.2020.02.009

Bertossi AA, Carraresi P, Gallo G. On some matching problems arising in vehicle scheduling models. Networks. 1987;17(3): 271-81. DOI: 10.1002/net.3230170303

Bunte S, Kliewer N. An overview on vehicle scheduling models. Public Transport. 2009;1(4): 299-317. DOI: 10.1007/s12469-010-0018-5

Kliewer N, Mellouli T, Suhl L. A time–space network based exact optimization model for multi-depot bus scheduling. European journal of operational research. 2006;175(3): 1616-27. DOI: 10.1016/j.ejor.2005.02.030

Kliewer N, Gintner V, Suhl L. Line change considerations within a time-space network based multi-depot bus scheduling model. In: Hickman M, Mirchandani P, Voß S. (eds) Computer-aided Systems in Public Transport. Springer; 2008. p. 57-70. DOI: 10.1007/978-3-540-73312-6_4

Chao Z, Xiaohong C. Optimizing battery electric bus transit vehicle scheduling with battery exchanging: Model and case study. Procedia-Social and Behavioral Sciences. 2013;96: 2725-36. DOI: 10.1016/j.sbspro.2013.08.306

Li J-Q. Transit bus scheduling with limited energy. Transportation Science. 2014;48(4): 521-39. DOI: 10.1287/trsc.2013.0468

Wen M, et al. An adaptive large neighborhood search heuristic for the electric vehicle scheduling problem. Computers & Operations Research. 2016;76: 73-83. DOI: 10.1016/j.cor.2016.06.013

Tang X, Lin X, He F. Robust scheduling strategies of electric buses under stochastic traffic conditions. Transportation Research Part C: Emerging Technologies. 2019;105: 163-82. DOI: 10.1016/j.trc.2019.05.032

Rogge M, van der Hurk E, Larsen A, Sauer DU. Electric bus fleet size and mix problem with optimization of charging infrastructure. Applied Energy. 2018;211: 282-95. DOI: 10.1016/j.apenergy.2017.11.051

Li L, Lo HK, Xiao F. Mixed bus fleet scheduling under range and refueling constraints. Transportation Research Part C: Emerging Technologies. 2019;104: 443-62. DOI: 10.1016/j.trc.2019.05.009

Rinaldi M, Picarelli E, D'Ariano A, Viti F. Mixed-fleet single-terminal bus scheduling problem: Modelling, solution scheme and potential applications. Omega. 2020;96: 102070. DOI: 10.1016/j.omega.2019.05.006

Pelletier S, Jabali O, Laporte G, Veneroni M. Battery degradation and behaviour for electric vehicles: Review and numerical analyses of several models. Transportation Research Part B: Methodological. 2017;103: 158-87. DOI: 10.1016/j.trb.2017.01.020

Montoya A, Guéret C, Mendoza JE, Villegas JG. The electric vehicle routing problem with nonlinear charging function. Transportation Research Part B: Methodological. 2017;103: 87-110. DOI: 10.1016/j.trb.2017.02.004

Froger A, Mendoza JE, Jabali O, Laporte G. Improved formulations and algorithmic components for the electric vehicle routing problem with nonlinear charging functions. Computers & Operations Research. 2019;104: 256-94. DOI: 10.1016/j.cor.2018.12.013

Olsen N, Kliewer N. Scheduling Electric Buses in Public Transport: Modeling of the Charging Process and Analysis of Assumptions. Logist Res. 2020;13(1): 4. DOI: 10.23773/2020_4

Hõimoja H, Rufer A, Dziechciaruk G, Vezzini A, editors. An ultrafast EV charging station demonstrator. International Symposium on Power Electronics Power Electronics, Electrical Drives, Automation and Motion, 20-22 June 2012, Sorrento, Italy. IEEE; 2012. p. 1390-5. DOI: 10.1109/SPEEDAM.2012.6264617

Zuo X, et al. A new formulation of the electric vehicle routing problem with time windows considering concave nonlinear charging function. Journal of Cleaner Production. 2019;236: 117687. DOI: 10.1016/j.jclepro.2019.117687

Guedes PC, Borenstein D. Column generation based heuristic framework for the multiple-depot vehicle type scheduling problem. Computers & Industrial Engineering. 2015;90: 361-70. DOI: 10.1016/j.cie.2015.10.004

Adler JD. Routing and scheduling of electric and alternative-fuel vehicles. Arizona State University; 2014.

Yao E, Liu T, Lu T, Yang Y. Optimization of electric vehicle scheduling with multiple vehicle types in public transport. Sustainable Cities and Society. 2020;52: 101862. DOI: 10.1016/j.scs.2019.101862

Wang Y, Huang Y, Xu J, Barclay N. Optimal recharging scheduling for urban electric buses: A case study in Davis. Transportation Research Part E: Logistics and Transportation Review. 2017;100: 115-32. DOI: 10.1016/j.tre.2017.01.001

Published
2021-08-05
How to Cite
1.
Zhang A, Li T, Tu R, Dong C, Chen H, Gao J, Liu Y. The Effect of Nonlinear Charging Function and Line Change Constraints on Electric Bus Scheduling. Promet - Traffic&Transportation. 2021;33(4):527-38. DOI: 10.7307/ptt.v33i4.3730
Section
Articles