Electric Bus Scheduling Considering Limited Charging Facility Capacity for Large-Scale Operation
Publication: Journal of Transportation Engineering, Part A: Systems
Volume 148, Issue 9
Abstract
Electric buses (e-buses) have been increasingly introduced to urban transit systems in recent years. E-bus scheduling has become a critical problem to ensure cost-efficient transit service. To support continuous e-bus operation, charging facilities are established at the depots to provide charging service. In real-world scenarios, charging facility capacity measured by the number of chargers is always limited. To reduce charging congestions, it is critical to consider the charging facility capacity in the e-bus scheduling problem. In this study, we addressed a multidepot e-bus scheduling problem considering limited charging facility capacity and vehicle-depot constraint. A mixed-integer programming model based on discrete-event optimization method and a large neighborhood search (LNS) heuristic are proposed to solve the problem. Comprehensive numerical experiments based on the real-world operation cases in Shenzhen were conducted. The results verify the model and show that the LNS heuristic can generate near-optimal solutions for large-scale problem instances. Lack of charging facilities at the depots can lead to more e-buses charging at the peak time regarding the time-of-use tariff, resulting in increased total operational cost.
Get full access to this article
View all available purchase options and get full access to this article.
Data Availability Statement
Some or all data, models, or code that support the findings of this study are available from the corresponding author upon reasonable request.
Acknowledgments
This research was supported in part by the Basic Research Program of Shenzhen Science and Technology Innovation Committee (JCYJ20180307123910003), Scientific Research Start-up Funds of Tsinghua Shenzhen International Graduate School (QD2021007N), and National Natural Science Foundation of China (61673233).
References
Abdelwahed, A., P. L. van den Berg, J. C. Tobias Brandt, and W. Ketter. 2020. “Evaluating and optimizing opportunity fast-charging schedules in transit battery electric bus networks.” Transp. Sci. 54 (6): 1601–1615. https://doi.org/10.1287/trsc.2020.0982.
Alwesabi, Y., Y. Wang, R. Avalos, and Z. Liu. 2020. “Electric bus scheduling under single depot dynamic wireless charging infrastructure planning.” Energy (Oxford) 213 (Dec): 118855. https://doi.org/10.1016/j.energy.2020.118855.
An, K. 2020. “Battery electric bus infrastructure planning under demand uncertainty.” Transp. Res. Part C: Emerging Technol. 111 (Feb): 572–587. https://doi.org/10.1016/j.trc.2020.01.009.
Bertossi, A., P. Carraresi, and G. Gallo. 1987. “On some matching problems arising in vehicle scheduling models.” Networks 17 (3): 271–281. https://doi.org/10.1002/net.3230170303.
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.
BNEF (Bloomberg New Energy Finance). 2020. “Electric vehicle outlook 2020.” Accessed August 24, 2021. https://www.sustainable-bus.com/news/electric-vehicle-outlook-2020-bnef-electric-buses/.
Bunte, S., and N. Kliewer. 2009. “An overview on vehicle scheduling models.” Public Transp. 1 (4): 299–317. https://doi.org/10.1007/s12469-010-0018-5.
Dai, Q., T. Cai, S. Duan, and F. Zhao. 2014. “Stochastic modeling and Forecasting of load demand for electric bus battery swap station.” IEEE Trans. Power Delivery 29 (4): 1909–1917. https://doi.org/10.1109/TPWRD.2014.2308990.
Häll, C. H., A. A. Ceder, J. Ekström, and N. Quttineh. 2018. “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: 102056. https://doi.org/10.1016/j.tre.2020.102056.
Jahic, A., M. Eskander, and D. Schulz. 2019. “Charging schedule for load peak minimization on Large-Scale electric bus depots.” Appl. Sci. 9 (9): 1748. https://doi.org/10.3390/app9091748.
Janoveca, M., and M. Kohánia. 2019. “Exact approach to the electric bus fleet scheduling.” Transp. Res. Procedia 40 (Jan): 1380–1387. https://doi.org/10.1016/j.trpro.2019.07.191.
Janoveca, M., and M. Kohánia. 2020. “Comparison of continuous and discontinuous charging models for the electric bus scheduling problem.” In Vol. 1 of Proc., 9th Int. Conf. on Operations Research and Enterprise Systems, 179–186. Setúbal, Portugal: SCITEPRESS. https://doi.org/10.5220/0008962901790186.
Jiang, M., Y. Zhang, and Y. Zhang. 2021. “Optimal electric bus scheduling under travel time uncertainty: A robust model and solution method.” J. Adv. Transp. 2021 (Dec): 1–19. https://doi.org/10.1155/2021/1191443.
Jiang, M., Y. Zhang, and Y. Zhang. 2022. “Multi-depot electric bus scheduling considering operational constraint and partial charging: A case study in Shenzhen, China.” Sustainability 14 (1): 255. https://doi.org/10.3390/su14010255.
Kunith, A., R. Mendelevitch, and D. Goehlich. 2017. “Electrification of a city bus network—An optimization model for cost-effective placing of charging infrastructure and battery sizing of fast-charging electric bus systems.” Int. J. Sustainable Transp. 11 (10): 707–720. https://doi.org/10.1080/15568318.2017.1310962.
Li, J. 2014. “Transit bus scheduling with limited energy.” Transp. Sci. 48 (4): 521–539. https://doi.org/10.1287/trsc.2013.0468.
Li, J. 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. 2018. Optimal mixed bus fleet management strategy for emissions reduction. Hong Kong: Hong Kong Univ. of Science and Technology.
Li, L., H. K. Lo, and F. Xiao. 2019. “Mixed bus fleet scheduling under range and refuelling constraints.” Transp. Res. Part C: Emerging Technol. 104 (Jul): 443–462. https://doi.org/10.1016/j.trc.2019.05.009.
Lin, Y., K. Zhang, Z. J. M. Shen, B. Ye, and L. Miao. 2019. “Multistage large-scale charging station planning for electric buses considering transportation network and power grid.” Transp. Res. Part C: Emerging Technol. 107 (Oct): 423–443. https://doi.org/10.1016/j.trc.2019.08.009.
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.
Liu, X., X. Qu, and X. Ma. 2021. “Optimizing electric bus charging infrastructure considering power matching and seasonality.” Transp. Res. Part D: Transp. Environ. 100 (Nov): 103057. https://doi.org/10.1016/j.trd.2021.103057.
Liu, Z., and Z. Song. 2017. “Robust planning of dynamic wireless charging infrastructure for battery electric buses.” Transp. Res. Part C: Emerging Technol. 83 (Oct): 77–103. https://doi.org/10.1016/j.trc.2017.07.013.
Lu, T., E. Yao, Y. Zhang, and Y. Yang. 2021. “Joint optimal scheduling for a mixed bus fleet under micro driving conditions.” IEEE Trans. Intell. Transp. Syst. 22 (4): 2464–2475. https://doi.org/10.1109/TITS.2021.3061202.
Pepin, A., G. Desaulniers, A. Hertz, and D. Huisman. 2009. “A comparison of five heuristics for the multiple depot vehicle scheduling problem.” J. Scheduling 12 (1): 17–30. https://doi.org/10.1007/s10951-008-0072-x.
Perumal, S. S. G., T. Dollevoet, D. Huisman, R. M. Lusby, J. Larsen, and M. Riis. 2021. “Solution approaches for integrated vehicle and crew scheduling with electric buses.” Comput. Oper. Res. 132 (Aug): 105268. https://doi.org/10.1016/j.cor.2021.105268.
Qin, N., A. Gusrialdi, R. Paul Brooker, and A. T-Raissi. 2016. “Numerical analysis of electric bus fast charging strategies for demand charge reduction.” Transp. Res. Part A Policy Pract. 94: 386–396. https://doi.org/10.1016/j.tra.2016.09.014.
Rinaldi, M., E. Picarelli, A. D’Ariano, and F. Viti. 2020. “Mixed-fleet single-depot bus scheduling problem: Modelling, solution scheme and potential applications.” Omega 96 (Oct): 102070. https://doi.org/10.1016/j.omega.2019.05.006.
Rogge, M., E. van der Hurk, A. Larsen, and D. U. Sauer. 2018. “Electric bus fleet size and mix problem with optimization of charging infrastructure.” Appl. Energy 211: 282–295. https://doi.org/10.1016/j.apenergy.2017.11.051.
Ropke, S., and D. Pisinger. 2006. “An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows.” Transp. Sci. 40 (4): 455–472. https://doi.org/10.1287/trsc.1050.0135.
Shaw, P. 1998. “Using constraint programming and local search methods to solve vehicle routing problems.” In Vol. 1520 of Principles and Practice of Constraint Programming—CP98. CP 1998. Lecture Notes in Computer Science, edited by M. Maher and J. F. Puget. Berlin: Springer. https://doi.org/10.1007/3-540-49481-2_30.
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 (Aug): 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–2): 155–176. https://doi.org/10.1007/s12469-017-0164-0.
Wang, X., C. Yuen, N. U. Hassan, N. An, and W. Wu. 2017a. “Electric vehicle charging station placement for urban public bus systems.” IEEE Trans. Intell. Transp. Syst. 18 (1): 128–139. https://doi.org/10.1109/TITS.2016.2563166.
Wang, Y., Y. Huang, J. Xu, and N. Barclay. 2017b. “Optimal recharging scheduling for urban electric buses: A case study in Davis.” Transp. Res. Part E: Logist. Transp. Rev. 100 (Apr): 115–132. https://doi.org/10.1016/j.tre.2017.01.001.
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.
Xylia, M., S. Leduc, P. Patrizio, F. Kraxner, and S. Silveira. 2017. “Locating charging infrastructure for electric buses in Stockholm.” Transp. Res. Part C: Emerging Technol. 78 (May): 183–200. https://doi.org/10.1016/j.trc.2017.03.005.
Yang, Y., W. Guan, and J. Ma. 2016. “Battery electric transit bus scheduling problem based on column generation approach.” J. Transp. Syst. Eng. Inf. Technol. 16 (5): 198–204. https://doi.org/10.16097/j.cnki.1009-6744.2016.05.030.
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: 103197.
You, P., Z. Yang, Y. Zhang, S. H. Low, and Y. Sun. 2016. “Optimal charging schedule for a battery switching station serving electric buses.” IEEE Trans. Power Syst. 31 (5): 3473–3483. https://doi.org/10.1109/TPWRS.2015.2487273.
Zhang, L., S. Wang, and X. Qu. 2021. “Optimal electric bus fleet scheduling considering battery degradation and non-linear charging profile.” Transp. Res. Part E: Logist. Transp. Rev. 154 (Oct): 102445. https://doi.org/10.1016/j.tre.2021.102445.
Zhou, G., D. Xie, X. Zhao, and C. Lu. 2020. “Collaborative optimization of vehicle and charging scheduling for a bus fleet mixed with electric and traditional buses.” IEEE Access 8 (Jan): 8056–8072. https://doi.org/10.1109/ACCESS.2020.2964391.
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 148 • Issue 9 • September 2022
Copyright
© 2022 American Society of Civil Engineers.
History
Received: Oct 27, 2021
Accepted: Mar 31, 2022
Published online: Jun 24, 2022
Published in print: Sep 1, 2022
Discussion open until: Nov 24, 2022
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
- Sen Deng, Zhaocheng He, Jiaming Zhong, Jiemin Xie, Bus Rescheduling for Long-Term Benefits: An Integrated Model Focusing on Service Capability and Regularity, Applied Sciences, 10.3390/app14051872, 14, 5, (1872), (2024).
- Zhitao Hu, Di Huang, Shuaian Wang, Joint Optimization of Bus Scheduling and Targeted Bus Exterior Advertising, Journal of Transportation Engineering, Part A: Systems, 10.1061/JTEPBS.TEENG-7812, 149, 5, (2023).
- A. A. Chernyshev, D. G. Moroz, Ph. V. Akopov, G. G. Popov, Means to Improve the Efficiency of Operation of Electric Buses with Ultrafast Charging on Municipal Routes of Regular Transportation in Cities, 2022 Intelligent Technologies and Electronic Devices in Vehicle and Road Transport Complex (TIRVED), 10.1109/TIRVED56496.2022.9965515, (1-4), (2022).