The Effect of Nonlinear Charging Function and Line Change Constraints on Electric Bus Scheduling
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
Copyright (c) 2021 Aijia Zhang, Tiezhu Li, Ran Tu, Changyin Dong, Haibo Chen, Jianbing Gao, Ye Liu
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
