Coordinated Scheduling of Electric Buses for Multiple Routes Considering Stochastic Travel Times
Publication: Journal of Transportation Engineering, Part A: Systems
Volume 149, Issue 8
Abstract
Bus terminals function as both the origins of multiple routes and charging places for electric buses (EBs) in large cities. Coordinated scheduling of routes starting from the same terminal can avoid the simultaneous charging demands of EBs, reducing queuing times for charging. The synchronous degradation in the state of health of EB batteries can also be realized with the coordinated scheduling, so as to lighten the burden of public transit corporations caused by frequent battery retirements. This study proposes a multiroute coordinated scheduling method where an electric bus is not fixed to serve on a certain route but runs different routes based on requirements. Utilizing chance constraint programming, an optimization model was formulated considering the stochastic volatility in trip travel times and time-of-use tariff, addressing objectives to minimize the average queuing time for EB charging, the difference in operating intensities, and the charging cost. The Big M method was applied to convert the chance constraint programming model to a deterministic model, which is specifically a 0–1 integer programming model, and then solved by employing the branch-and-price method. Numerical tests were carried out using data from three real EB routes. Results indicate that the proposed scheduling method can reduce the average queuing time for charging, the daily charging cost, and the difference in operating intensities while maintaining the synchronous degradation of all EB batteries.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
The authors confirm that the data supporting the findings of this study that are not available within the article are available upon reasonable request from the corresponding author.
Acknowledgments
This work was supported by the Key Projects of National Natural Science Foundation of China under Grant Nos. 52131203 and 52220105001.
References
Alvo, M., G. Angulo, and M. A. Klapp. 2021. “An exact solution approach for an electric bus dispatch problem.” Transp. Res. Part E Logist. Transp. Rev. 156 (Dec): 102528. https://doi.org/10.1016/j.tre.2021.102528.
Alwesabi, Y., Y. Wang, R. Avalos, and Z. Liu. 2020. “Electric bus scheduling under single depot dynamic wireless charging infrastructure planning.” Energy 213 (Dec): 118855. https://doi.org/10.1016/j.energy.2020.118855.
Bie, Y., J. Ji, X. Wang, and X. Qu. 2021. “Optimization of electric bus scheduling considering stochastic volatilities in trip travel time and energy consumption.” Comput.-Aided Civ. Infrastruct. Eng. 36 (12): 1530–1548. https://doi.org/10.1111/mice.12684.
Bie, Y., Y. Liu, S. Li, and L. Wang. 2022. “HVAC operation planning for electric bus trips based on chance-constrained programming.” Energy 258 (Nov): 124807. https://doi.org/10.1016/j.energy.2022.124807.
Chediak, M. 2018. “Electric buses will take over half the world fleet by 2025.” Business Standard, February 1.
Freling, R., D. Huisman, and A. P. Wagelmans. 2003. “Models and algorithms for integration of vehicle and crew scheduling.” J. Sched. 6 (1): 63–85. https://doi.org/10.1023/A:1022287504028.
Gavish, B., and E. Shlifer. 1979. “An approach for solving a class of transportation scheduling problems.” Eur. J. Oper. Res. 3 (2): 122–134. https://doi.org/10.1016/0377-2217(79)90098-5.
Gkiotsalitis, K., C. Iliopoulou, and K. Kepaptsoglou. 2023. “An exact approach for the multi-depot electric bus scheduling problem with time windows.” Eur. J. Oper. Res. 306 (1): 189–206. https://doi.org/10.1016/j.ejor.2022.07.017.
Häll, C. H., A. Ceder, J. Ekström, and N. H. Quttineh. 2019. “Adjustments of public transit operations planning process for the use of electric buses.” J. Intell. Transp. Syst. 23 (3): 216–230. https://doi.org/10.1080/15472450.2018.1488131.
He, Y., Z. Liu, and Z. Song. 2020. “Optimal charging scheduling and management for a fast-charging battery electric bus system.” Transp. Res. Part E Logist. Transp. Rev. 142 (Oct): 102056. https://doi.org/10.1016/j.tre.2020.102056.
Houbbadi, A., R. Trigui, S. Pelissier, E. Redondo-Iglesias, and T. Bouton. 2019. “Optimal scheduling to manage an electric bus fleet overnight charging.” Energies 12 (14): 2727. https://doi.org/10.3390/en12142727.
Huang, D., and S. Wang. 2022. “A two-stage stochastic programming model of coordinated electric bus charging scheduling for a hybrid charging scheme.” Multimodal Transp. 1 (1): 100006. https://doi.org/10.1016/j.multra.2022.100006.
Huang, D., Y. Wang, S. Jia, Z. Liu, and S. Wang. 2022. “A Lagrangian relaxation approach for the electric bus charging scheduling optimisation problem.” Transportmetrica A 18 (Jan): 1–24. https://doi.org/10.1080/23249935.2021.2023690.
Jahic, A., M. Plenz, M. Eskander, and D. Schulz. 2021. “Route scheduling for centralized electric bus depots.” IEEE Open J. Intell. Transp. Syst. 2 (Jul): 149–159. https://doi.org/10.1109/OJITS.2021.3096115.
Jefferies, D., and D. Göhlich. 2020. “A comprehensive TCO evaluation method for electric bus systems based on discrete-event simulation including bus scheduling and charging infrastructure optimization.” World Electr. Veh. J. 11 (3): 56–98. https://doi.org/10.3390/wevj11030056.
Ji, J., Y. Bie, and L. Wang. 2023. “Optimal electric bus fleet scheduling for a route with charging facility sharing.” Transp. Res. Part C Emerging Technol. 147 (Feb): 104010. https://doi.org/10.1016/j.trc.2022.104010.
Ji, J., Y. Bie, Z. Zeng, and L. Wang. 2022. “Trip energy consumption estimation for electric buses.” Commun. Transp. Res. 2 (Dec): 100069. https://doi.org/10.1016/j.commtr.2022.100069.
Jiang, M., M. Y. Zhang, and Y. Zhang. 2022. “A branch-and-price algorithm for large-scale multidepot electric bus scheduling.” IEEE Trans. Intell. Transp. Syst. 2022 (May): 1–14. https://doi.org/10.1109/TITS.2022.3165876.
Jiang, N., and C. Xie. 2014. “Computing and analyzing mixed equilibrium network flows with gasoline and electric vehicles.” Comput.-Aided Civ. Infrastruct. Eng. 29 (8): 626–641. https://doi.org/10.1111/mice.12082.
Lam, L., and P. Bauer. 2012. “Practical capacity fading model for Li-ion battery cells in electric vehicles.” IEEE Trans. Power Electron. 28 (12): 5910–5918. https://doi.org/10.1109/TPEL.2012.2235083.
Li, B., Y. Chen, W. Wei, S. Huang, and S. Mei. 2021a. “Resilient restoration of distribution systems in coordination with electric bus scheduling.” IEEE Trans. Smart Grid 12 (4): 3314–3325. https://doi.org/10.1109/TSG.2021.3060801.
Li, J. Q. 2014. “Transit bus scheduling with limited energy.” Transp. Sci. 48 (4): 521–539. https://doi.org/10.1287/trsc.2013.0468.
Li, J. Q. 2016. “Battery-electric transit bus developments and operations: A review.” Int. J. Sustainable Transp. 10 (3): 157–169. https://doi.org/10.1080/15568318.2013.872737.
Li, L., H. K. Lo, W. Huang, and F. Xiao. 2021b. “Mixed bus fleet location-routing-scheduling under range uncertainty.” Transp. Res. Part B Methodol. 146 (Apr): 155–179. https://doi.org/10.1016/j.trb.2021.02.005.
Li, L., H. K. Lo, and F. Xiao. 2019. “Mixed bus fleet scheduling under range and refueling constraints.” Transp. Res. Part C Emerging Technol. 104 (Jul): 443–462. https://doi.org/10.1016/j.trc.2019.05.009.
Li, X., T. Wang, L. Li, F. Feng, W. Wang, and C. Cheng. 2020. “Joint optimization of regular charging electric bus transit network schedule and stationary charger deployment considering partial charging policy and time-of-use electricity prices.” J. Adv. Transp. 2020 (Dec): 1–16. https://doi.org/10.1155/2020/8863905.
Liu, K., H. Gao, Z. Liang, M. Zhao, and C. Li. 2021. “Optimal charging strategy for large-scale electric buses considering resource constraints.” Transp. Res. Part D Transp. Environ. 99 (Oct): 103009. https://doi.org/10.1016/j.trd.2021.103009.
Liu, K., H. Gao, Y. Wang, T. Feng, and C. Li. 2022. “Robust charging strategies for electric bus fleets under energy consumption uncertainty.” Transp. Res. Part D Transp. Environ. 104 (Mar): 103215. https://doi.org/10.1016/j.trd.2022.103215.
Liu, T., and A. A. Ceder. 2020. “Battery-electric transit vehicle scheduling with optimal number of stationary chargers.” Transp. Res. Part C Emerging Technol. 114 (May): 118–139. https://doi.org/10.1016/j.trc.2020.02.009.
Löbel, A. 1999. “Solving large-scale multiple-depot vehicle scheduling problems.” Lect. Notes Econ. Math. Syst. 1 (471): 193–220. https://doi.org/10.1007/978-3-642-85970-0_10.
Manzolli, J. A., J. P. Trovão, and C. H. Antunes. 2022. “A review of electric bus vehicles research topics—Methods and trends.” Renewable Sustainable Energy Rev. 159 (May): 112211. https://doi.org/10.1016/j.rser.2022.112211.
Mesquita, M., and J. Paixão. 1999. “Exact algorithms for the multi-depot vehicle scheduling problem based on multicommodity network flow type formulations.” Lect. Notes Econ. Math. Syst. 1 (471): 221–243. https://doi.org/10.1007/978-3-642-85970-0_11.
Pepin, A. S., G. Desaulniers, A. Hertz, and D. Huisman. 2009. “A comparison of five heuristics for the multiple depot vehicle scheduling problem.” J. Sched. 12 (1): 17–30. https://doi.org/10.1007/s10951-008-0072-x.
Perumal, S. S., R. M. Lusby, and J. Larsen. 2021. “Electric bus planning & scheduling: A review of related problems and methodologies.” Eur. J. Oper. Res. 301 (2): 395–413. https://doi.org/10.1016/j.ejor.2021.10.058.
Qu, X., S. Wang, and D. Niemeier. 2022. “On the urban-rural bus transit system with passenger-freight mixed flow.” Commun. Transp. Res. 2 (Dec): 100054. https://doi.org/10.1016/j.commtr.2022.100054.
Tang, X., X. Lin, and F. He. 2019. “Robust scheduling strategies of electric buses under stochastic traffic conditions.” Transp. Res. Part C Emerging Technol. 105 (Aug): 163–182. https://doi.org/10.1016/j.trc.2019.05.032.
Teng, J., T. Chen, and W. D. Fan. 2020. “Integrated approach to vehicle scheduling and bus timetabling for an electric bus line.” J. Transp. Eng. Part A Syst. 146 (2): 04019073. https://doi.org/10.1061/JTEPBS.0000306.
Uslu, T., and O. Kaya. 2021. “Location and capacity decisions for electric bus charging stations considering waiting times.” Transp. Res. Part D Transp. Environ. 90 (Jan): 102645. https://doi.org/10.1016/j.trd.2020.102645.
van Kooten Niekerk, M. E., J. M. Van den Akker, and J. A. Hoogeveen. 2017. “Scheduling electric vehicles.” Public Transp. 9 (1): 155–176. https://doi.org/10.1007/s12469-017-0164-0.
Wang, G., X. Xie, F. Zhang, Y. Liu, and D. Zhang. 2018. “bCharge: Data-driven real-time charging scheduling for large-scale electric bus fleets.” In Proc., 2018 IEEE Real-Time Systems Symp., 45–55. New York: IEEE. https://doi.org/10.1109/RTSS.2018.00015.
Wang, J., L. Kang, and Y. Liu. 2020. “Optimal scheduling for electric bus fleets based on dynamic programming approach by considering battery capacity fade.” Renewable Sustainable Energy Rev. 130 (Sep): 109978. https://doi.org/10.1016/j.rser.2020.109978.
Wen, M., E. Linde, S. Ropke, P. Mirchandani, and A. Larsen. 2016. “An adaptive large neighborhood search heuristic for the electric vehicle scheduling problem.” Comput. Oper. Res. 76 (Dec): 73–83. https://doi.org/10.1016/j.cor.2016.06.013.
Wu, W., Y. Lin, R. Liu, and W. Jin. 2022. “The multi-depot electric vehicle scheduling problem with power grid characteristics.” Transp. Res. Part B Methodol. 155 (Jan): 322–347. https://doi.org/10.1016/j.trb.2021.11.007.
Yao, E., T. Liu, T. Lu, and Y. Yang. 2020. “Optimization of electric vehicle scheduling with multiple vehicle types in public transport.” Sustainable Cities Soc. 52 (Jan): 101862. https://doi.org/10.1016/j.scs.2019.101862.
Yıldırım, Ş., and B. Yıldız. 2021. “Electric bus fleet composition and scheduling.” Transp. Res. Part C Emerging Technol. 129 (Aug): 103197. https://doi.org/10.1016/j.trc.2021.103197.
Zhang, L., Z. Zeng, and X. Qu. 2020. “On the role of battery capacity fading mechanism in the lifecycle cost of electric bus fleet.” IEEE Trans. Intell. Transp. Syst. 22 (4): 2371–2380. https://doi.org/10.1109/TITS.2020.3014097.
Zhang, W., H. Zhao, and M. Xu. 2021. “Optimal operating strategy of short turning lines for the battery electric bus system.” Commun. Transp. Res. 1 (Dec): 100023. https://doi.org/10.1016/j.commtr.2021.100023.
Zhu, C., and X. Chen. 2013. “Optimizing battery electric bus transit vehicle scheduling with battery exchanging: Model and case study.” Procedia Soc. Behav. Sci. 96 (Nov): 2725–2736. https://doi.org/10.1016/j.sbspro.2013.08.306.
Information & Authors
Information
Published In
Journal of Transportation Engineering, Part A: Systems
Volume 149 • Issue 8 • August 2023
Copyright
© 2023 American Society of Civil Engineers.
History
Received: Dec 2, 2022
Accepted: Mar 17, 2023
Published online: May 29, 2023
Published in print: Aug 1, 2023
Discussion open until: Oct 29, 2023
Authors
Metrics & Citations
Metrics
Citations
Download citation
If you have the appropriate software installed, you can download article citation data to the citation manager of your choice. Simply select your manager software from the list below and click Download.
Cited by
- Yang Liu, Bing Zeng, Kejun Long, Wei Wu, Enhancing Electric Bus Charging Scheduling: An Energy-Integrated Dynamic Bus Replacement Strategy with Time-of-Use Pricing, Sustainability, 10.3390/su16083334, 16, 8, (3334), (2024).
- Ande Chang, Yuan Cong, Chunguang Wang, Yiming Bie, Optimal Vehicle Scheduling and Charging Infrastructure Planning for Autonomous Modular Transit System, Sustainability, 10.3390/su16083316, 16, 8, (3316), (2024).
- Wensi Wang, Bin Yu, Yu Zhou, A real-time synchronous dispatching and recharging strategy for multi-line electric bus systems, Transportation Research Part E: Logistics and Transportation Review, 10.1016/j.tre.2024.103516, 185, (103516), (2024).