[go: up one dir, main page]
IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v155y2022icp322-347.html
   My bibliography  Save this article

The multi-depot electric vehicle scheduling problem with power grid characteristics

Author

Listed:
  • Wu, Weitiao
  • Lin, Yue
  • Liu, Ronghui
  • Jin, Wenzhou
Abstract
Electric buses can bring significant environmental and social benefits in the future public transportation systems. However, the large-scale adoption of electric buses faces major technical challenges caused by not only the limited running range and long charging time, but also the complex power grid characteristics, such as time-of-use (TOU) electricity tariffs and peak load risk. On one hand, the operation cost is determined by the TOU pricing and vehicle schedule. On the other hand, the unbalanced charging demand resulting from the vehicle schedule will cause peak load risk and pose a potential threat to the power grid safety. With the increasing penetration of electric buses, there is a real need to carefully design and manage electric bus scheduling to not only reduce the system costs but also ensure power grid safety. In this paper, we introduce a bi-objective multi-depot electric vehicle scheduling problem, a new generalization to the vehicle scheduling problem where the effects of TOU pricing and peak load risk are explicitly considered. The dual objectives are to minimize the total operation cost and to minimize the peak load resulting from concurrent recharging activities, as constrained by the running range of the electric buses and the capacity of charging depots/stations. A time-expanded network model is devised to represent this problem, while the bi-objective optimization model is reformulated by the lexicographic method. We propose a tailored branch-and-price method to solve the problem. Heuristics and a trip chain pool strategy are embedded into the branch-and-price method to expedite the computation time. Our method is validated through a benchmark network and a real-world bus network in Guangzhou, China. The results demonstrate that our method is effective in cost savings and peak load leveling, and far outperforms the off-the-shelf solver with respect to solution quality and computation efficiency. The real-world application results show that compared to state-of-the-practice, the peak load can be significantly reduced, on top of cost and fleet size savings.

Suggested Citation

  • Wu, Weitiao & Lin, Yue & Liu, Ronghui & Jin, Wenzhou, 2022. "The multi-depot electric vehicle scheduling problem with power grid characteristics," Transportation Research Part B: Methodological, Elsevier, vol. 155(C), pages 322-347.
    • Handle: RePEc:eee:transb:v:155:y:2022:i:c:p:322-347
    DOI: 10.1016/j.trb.2021.11.007
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191261521002125
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.trb.2021.11.007?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Shen, Zuo-Jun Max & Feng, Bo & Mao, Chao & Ran, Lun, 2019. "Optimization models for electric vehicle service operations: A literature review," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 462-477.
    2. Vahid Zeighami & François Soumis, 2019. "Combining Benders’ Decomposition and Column Generation for Integrated Crew Pairing and Personalized Crew Assignment Problems," Transportation Science, INFORMS, vol. 53(5), pages 1479-1499, September.
    3. Wu, Weitiao & Liu, Ronghui & Jin, Wenzhou, 2016. "Designing robust schedule coordination scheme for transit networks with safety control margins," Transportation Research Part B: Methodological, Elsevier, vol. 93(PA), pages 495-519.
    4. Huisman, Dennis & Wagelmans, Albert P.M., 2006. "A solution approach for dynamic vehicle and crew scheduling," European Journal of Operational Research, Elsevier, vol. 172(2), pages 453-471, July.
    5. Jonathan D. Adler & Pitu B. Mirchandani, 2017. "The Vehicle Scheduling Problem for Fleets with Alternative-Fuel Vehicles," Transportation Science, INFORMS, vol. 51(2), pages 441-456, May.
    6. M. E. Kooten Niekerk & J. M. Akker & J. A. Hoogeveen, 2017. "Scheduling electric vehicles," Public Transport, Springer, vol. 9(1), pages 155-176, July.
    7. Cynthia Barnhart & Ellis L. Johnson & George L. Nemhauser & Martin W. P. Savelsbergh & Pamela H. Vance, 1998. "Branch-and-Price: Column Generation for Solving Huge Integer Programs," Operations Research, INFORMS, vol. 46(3), pages 316-329, June.
    8. Wu, Weitiao & Liu, Ronghui & Jin, Wenzhou, 2017. "Modelling bus bunching and holding control with vehicle overtaking and distributed passenger boarding behaviour," Transportation Research Part B: Methodological, Elsevier, vol. 104(C), pages 175-197.
    9. Rogge, Matthias & van der Hurk, Evelien & Larsen, Allan & Sauer, Dirk Uwe, 2018. "Electric bus fleet size and mix problem with optimization of charging infrastructure," Applied Energy, Elsevier, vol. 211(C), pages 282-295.
    10. Hanne L. Petersen & Allan Larsen & Oli B. G. Madsen & Bjørn Petersen & Stefan Ropke, 2013. "The Simultaneous Vehicle Scheduling and Passenger Service Problem," Transportation Science, INFORMS, vol. 47(4), pages 603-616, November.
    11. Uçar, Ezgi & İlker Birbil, Ş. & Muter, İbrahim, 2017. "Managing disruptions in the multi-depot vehicle scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 105(C), pages 249-269.
    12. Argote-Cabanero, Juan & Daganzo, Carlos F. & Lynn, Jacob W., 2015. "Dynamic control of complex transit systems," Transportation Research Part B: Methodological, Elsevier, vol. 81(P1), pages 146-160.
    13. Matthias Ehrgott, 2005. "Multicriteria Optimization," Springer Books, Springer, edition 0, number 978-3-540-27659-3, December.
    14. Wu, Weitiao & Liu, Ronghui & Jin, Wenzhou & Ma, Changxi, 2019. "Simulation-based robust optimization of limited-stop bus service with vehicle overtaking and dynamics: A response surface methodology," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 130(C), pages 61-81.
    15. Desfontaines, Lucie & Desaulniers, Guy, 2018. "Multiple depot vehicle scheduling with controlled trip shifting," Transportation Research Part B: Methodological, Elsevier, vol. 113(C), pages 34-53.
    16. Ahmed Hadjar & Odile Marcotte & François Soumis, 2006. "A Branch-and-Cut Algorithm for the Multiple Depot Vehicle Scheduling Problem," Operations Research, INFORMS, vol. 54(1), pages 130-149, February.
    17. He, Yi & Liu, Zhaocai & Song, Ziqi, 2020. "Optimal charging scheduling and management for a fast-charging battery electric bus system," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 142(C).
    18. Kulkarni, Sarang & Krishnamoorthy, Mohan & Ranade, Abhiram & Ernst, Andreas T. & Patil, Rahul, 2018. "A new formulation and a column generation-based heuristic for the multiple depot vehicle scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 118(C), pages 457-487.
    19. Wei, Ran & Liu, Xiaoyue & Ou, Yi & Kiavash Fayyaz, S., 2018. "Optimizing the spatio-temporal deployment of battery electric bus system," Journal of Transport Geography, Elsevier, vol. 68(C), pages 160-168.
    20. Shen, Yindong & Xu, Jia & Li, Jingpeng, 2016. "A probabilistic model for vehicle scheduling based on stochastic trip times," Transportation Research Part B: Methodological, Elsevier, vol. 85(C), pages 19-31.
    21. Bi, Zicheng & Keoleian, Gregory A. & Ersal, Tulga, 2018. "Wireless charger deployment for an electric bus network: A multi-objective life cycle optimization," Applied Energy, Elsevier, vol. 225(C), pages 1090-1101.
    22. Carosi, Samuela & Frangioni, Antonio & Galli, Laura & Girardi, Leopoldo & Vallese, Giuliano, 2019. "A matheuristic for integrated timetabling and vehicle scheduling," Transportation Research Part B: Methodological, Elsevier, vol. 127(C), pages 99-124.
    23. Boyer, Vincent & Ibarra-Rojas, Omar J. & Ríos-Solís, Yasmín Á., 2018. "Vehicle and Crew Scheduling for Flexible Bus Transportation Systems," Transportation Research Part B: Methodological, Elsevier, vol. 112(C), pages 216-229.
    24. Jing-Quan Li, 2014. "Transit Bus Scheduling with Limited Energy," Transportation Science, INFORMS, vol. 48(4), pages 521-539, November.
    25. Wang, Yusheng & Huang, Yongxi & Xu, Jiuping & Barclay, Nicole, 2017. "Optimal recharging scheduling for urban electric buses: A case study in Davis," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 100(C), pages 115-132.
    26. Argote-Cabanero, Juan & Daganzo, Carlos F & Lynn, Jacob W, 2015. "Dynamic Control of Complex Transit Systems," Institute of Transportation Studies, Research Reports, Working Papers, Proceedings qt6j16889k, Institute of Transportation Studies, UC Berkeley.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Zou, Kaijie & Zhang, Ke & Li, Meng, 2024. "Operational design for modular electrified transit in corridor areas," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 187(C).
    2. Zhou, Yu & Wang, Hua & Wang, Yun & Yu, Bin & Tang, Tianpei, 2024. "Charging facility planning and scheduling problems for battery electric bus systems: A comprehensive review," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 183(C).
    3. Matina L. Y. Chau & Diamanto Koutsompina & Konstantinos Gkiotsalitis, 2024. "The Electric Vehicle Scheduling Problem for Buses in Networks with Multi-Port Charging Stations," Sustainability, MDPI, vol. 16(3), pages 1-21, February.
    4. Dai, Zhuang & Han, Ke, 2023. "Exploring the drive-by sensing power of bus fleet through active scheduling," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 171(C).
    5. Kayhan Alamatsaz & Sadam Hussain & Chunyan Lai & Ursula Eicker, 2022. "Electric Bus Scheduling and Timetabling, Fast Charging Infrastructure Planning, and Their Impact on the Grid: A Review," Energies, MDPI, vol. 15(21), pages 1-39, October.
    6. Lim, Lek Keng & Muis, Zarina Ab & Ho, Wai Shin & Hashim, Haslenda & Bong, Cassendra Phun Chien, 2023. "Review of the energy forecasting and scheduling model for electric buses," Energy, Elsevier, vol. 263(PD).
    7. Li, Peng & Wu, Weitiao & Pei, Xiangjing, 2023. "A separate modelling approach for short-term bus passenger flow prediction based on behavioural patterns: A hybrid decision tree method," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 616(C).
    8. Kayhan Alamatsaz & Frédéric Quesnel & Ursula Eicker, 2024. "Enhancing Electric Shuttle Bus Efficiency: A Case Study on Timetabling and Scheduling Optimization," Energies, MDPI, vol. 17(13), pages 1-26, June.
    9. Fan Liu & Jing Xun, 2023. "An Automatic Train Operation Based Real-Time Rescheduling Model for High-Speed Railway," Mathematics, MDPI, vol. 11(21), pages 1-15, November.
    10. Wang, Yiran & Chen, Jingxu & Tang, Tianli & Liu, Zhiyuan, 2024. "A holistic approach to multi-depot electric bus scheduling for energy saving considering limitations in charging facilities," Energy, Elsevier, vol. 303(C).
    11. Zhai, Cong & Wu, Weitiao & Xiao, Yingping, 2023. "The jamming transition of multi-lane lattice hydrodynamic model with passing effect," Chaos, Solitons & Fractals, Elsevier, vol. 171(C).
    12. Naihui Wang & Yulong Pei & Yi-Jia Wang, 2022. "Antecedents in Determining Users’ Acceptance of Electric Shuttle Bus Services," Mathematics, MDPI, vol. 10(16), pages 1-19, August.
    13. Cui, Shaohua & Gao, Kun & Yu, Bin & Ma, Zhenliang & Najafi, Arsalan, 2023. "Joint optimal vehicle and recharging scheduling for mixed bus fleets under limited chargers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 180(C).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Perumal, Shyam S.G. & Lusby, Richard M. & Larsen, Jesper, 2022. "Electric bus planning & scheduling: A review of related problems and methodologies," European Journal of Operational Research, Elsevier, vol. 301(2), pages 395-413.
    2. Foda, Ahmed & Abdelaty, Hatem & Mohamed, Moataz & El-Saadany, Ehab, 2023. "A generic cost-utility-emission optimization for electric bus transit infrastructure planning and charging scheduling," Energy, Elsevier, vol. 277(C).
    3. Zhou, Yu & Wang, Hua & Wang, Yun & Yu, Bin & Tang, Tianpei, 2024. "Charging facility planning and scheduling problems for battery electric bus systems: A comprehensive review," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 183(C).
    4. Gkiotsalitis, K. & Cats, O., 2021. "At-stop control measures in public transport: Literature review and research agenda," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 145(C).
    5. Gkiotsalitis, K. & Iliopoulou, C. & Kepaptsoglou, K., 2023. "An exact approach for the multi-depot electric bus scheduling problem with time windows," European Journal of Operational Research, Elsevier, vol. 306(1), pages 189-206.
    6. Boud Verbrugge & Mohammed Mahedi Hasan & Haaris Rasool & Thomas Geury & Mohamed El Baghdadi & Omar Hegazy, 2021. "Smart Integration of Electric Buses in Cities: A Technological Review," Sustainability, MDPI, vol. 13(21), pages 1-23, November.
    7. Yiming Bie & Mingjie Hao & Mengzhu Guo, 2021. "Optimal Electric Bus Scheduling Based on the Combination of All-Stop and Short-Turning Strategies," Sustainability, MDPI, vol. 13(4), pages 1-21, February.
    8. Kayhan Alamatsaz & Sadam Hussain & Chunyan Lai & Ursula Eicker, 2022. "Electric Bus Scheduling and Timetabling, Fast Charging Infrastructure Planning, and Their Impact on the Grid: A Review," Energies, MDPI, vol. 15(21), pages 1-39, October.
    9. Hatem Abdelaty & Ahmed Foda & Moataz Mohamed, 2023. "The Robustness of Battery Electric Bus Transit Networks under Charging Infrastructure Disruptions," Sustainability, MDPI, vol. 15(4), pages 1-25, February.
    10. Alvo, Matías & Angulo, Gustavo & Klapp, Mathias A., 2021. "An exact solution approach for an electric bus dispatch problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 156(C).
    11. Foda, Ahmed & Mohamed, Moataz, 2024. "The impacts of optimization approaches on BEB system configuration in transit," Transport Policy, Elsevier, vol. 151(C), pages 12-23.
    12. Guschinsky, Nikolai & Kovalyov, Mikhail Y. & Pesch, Erwin & Rozin, Boris, 2023. "Cost minimizing decisions on equipment and charging schedule for electric buses in a single depot," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 180(C).
    13. Diefenbach, Heiko & Emde, Simon & Glock, Christoph H., 2023. "Multi-depot electric vehicle scheduling in in-plant production logistics considering non-linear charging models," European Journal of Operational Research, Elsevier, vol. 306(2), pages 828-848.
    14. Feifeng Zheng & Zhixin Wang & Zhaojie Wang & Ming Liu, 2023. "Daytime and Overnight Joint Charging Scheduling for Battery Electric Buses Considering Time-Varying Charging Power," Sustainability, MDPI, vol. 15(13), pages 1-19, July.
    15. Kuo, Yong-Hong & Leung, Janny M.Y. & Yan, Yimo, 2023. "Public transport for smart cities: Recent innovations and future challenges," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1001-1026.
    16. Liang, Shidong & He, Shengxue & Zhang, Hu & Ma, Minghui, 2021. "Optimal holding time calculation algorithm to improve the reliability of high frequency bus route considering the bus capacity constraint," Reliability Engineering and System Safety, Elsevier, vol. 212(C).
    17. Kulkarni, Sarang & Krishnamoorthy, Mohan & Ranade, Abhiram & Ernst, Andreas T. & Patil, Rahul, 2018. "A new formulation and a column generation-based heuristic for the multiple depot vehicle scheduling problem," Transportation Research Part B: Methodological, Elsevier, vol. 118(C), pages 457-487.
    18. Cui, Shaohua & Gao, Kun & Yu, Bin & Ma, Zhenliang & Najafi, Arsalan, 2023. "Joint optimal vehicle and recharging scheduling for mixed bus fleets under limited chargers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 180(C).
    19. Enzi, Miriam & Parragh, Sophie N. & Pisinger, David & Prandtstetter, Matthias, 2021. "Modeling and solving the multimodal car- and ride-sharing problem," European Journal of Operational Research, Elsevier, vol. 293(1), pages 290-303.
    20. Perumal, S.S.G. & Dollevoet, T.A.B. & Huisman, D. & Lusby, R.M. & Larsen, J. & Riis, M., 2020. "Solution Approaches for Vehicle and Crew Scheduling with Electric Buses," Econometric Institute Research Papers EI-2020-02, Erasmus University Rotterdam, Erasmus School of Economics (ESE), Econometric Institute.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transb:v:155:y:2022:i:c:p:322-347. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.