IDEAS home Printed from https://ideas.repec.org/a/gam/jeners/v14y2021i20p6610-d655566.html
   My bibliography  Save this article

A GRASP Approach for Solving Large-Scale Electric Bus Scheduling Problems

Author

Listed:
  • Raka Jovanovic

    (Qatar Environment and Energy Research Institute, Hamad bin Khalifa University, Doha P.O. Box 5825, Qatar)

  • Islam Safak Bayram

    (Department of Electronic and Electrical Engineering, University of Strathclyde, 204 George St, Glasgow G1 1XW, UK)

  • Sertac Bayhan

    (Qatar Environment and Energy Research Institute, Hamad bin Khalifa University, Doha P.O. Box 5825, Qatar)

  • Stefan Voß

    (Institute of Information Systems, University of Hamburg, 20146 Hamburg, Germany)

Abstract

Electrifying public bus transportation is a critical step in reaching net-zero goals. In this paper, the focus is on the problem of optimal scheduling of an electric bus (EB) fleet to cover a public transport timetable. The problem is modelled using a mixed integer program (MIP) in which the charging time of an EB is pertinent to the battery’s state-of-charge level. To be able to solve large problem instances corresponding to real-world applications of the model, a metaheuristic approach is investigated. To be more precise, a greedy randomized adaptive search procedure (GRASP) algorithm is developed and its performance is evaluated against optimal solutions acquired using the MIP. The GRASP algorithm is used for case studies on several public transport systems having various properties and sizes. The analysis focuses on the relation between EB ranges (battery capacity) and required charging rates (in kW) on the size of the fleet needed to cover a public transport timetable. The results of the conducted computational experiments indicate that an increase in infrastructure investment through high speed chargers can significantly decrease the size of the necessary fleets. The results also show that high speed chargers have a more significant impact than an increase in battery sizes of the EBs.

Suggested Citation

  • Raka Jovanovic & Islam Safak Bayram & Sertac Bayhan & Stefan Voß, 2021. "A GRASP Approach for Solving Large-Scale Electric Bus Scheduling Problems," Energies, MDPI, vol. 14(20), pages 1-23, October.
    • Handle: RePEc:gam:jeners:v:14:y:2021:i:20:p:6610-:d:655566
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/1996-1073/14/20/6610/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/1996-1073/14/20/6610/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Rahman, Imran & Vasant, Pandian M. & Singh, Balbir Singh Mahinder & Abdullah-Al-Wadud, M. & Adnan, Nadia, 2016. "Review of recent trends in optimization techniques for plug-in hybrid, and electric vehicle charging infrastructures," Renewable and Sustainable Energy Reviews, Elsevier, vol. 58(C), pages 1039-1047.
    2. Alwesabi, Yaseen & Wang, Yong & Avalos, Raul & Liu, Zhaocai, 2020. "Electric bus scheduling under single depot dynamic wireless charging infrastructure planning," Energy, Elsevier, vol. 213(C).
    3. Jari Vepsäläinen & Antti Ritari & Antti Lajunen & Klaus Kivekäs & Kari Tammi, 2018. "Energy Uncertainty Analysis of Electric Buses," Energies, MDPI, vol. 11(12), pages 1-29, November.
    4. M. E. Kooten Niekerk & J. M. Akker & J. A. Hoogeveen, 2017. "Scheduling electric vehicles," Public Transport, Springer, vol. 9(1), pages 155-176, July.
    5. Dennis Dreier & Björn Rudin & Mark Howells, 2020. "Comparison of management strategies for the charging schedule and all-electric operation of a plug-in hybrid-electric bi-articulated bus fleet," Public Transport, Springer, vol. 12(2), pages 363-404, June.
    6. Wang, Jing & Kang, Lixia & Liu, Yongzhong, 2020. "Optimal scheduling for electric bus fleets based on dynamic programming approach by considering battery capacity fade," Renewable and Sustainable Energy Reviews, Elsevier, vol. 130(C).
    7. Jing-Quan Li, 2014. "Transit Bus Scheduling with Limited Energy," Transportation Science, INFORMS, vol. 48(4), pages 521-539, November.
    8. Gao, Zhiming & Lin, Zhenhong & LaClair, Tim J. & Liu, Changzheng & Li, Jan-Mou & Birky, Alicia K. & Ward, Jacob, 2017. "Battery capacity and recharging needs for electric buses in city transit service," Energy, Elsevier, vol. 122(C), pages 588-600.
    9. Zeyuan Song & Yingqi Liu & Hongwei Gao & Suxiu Li, 2020. "The Underlying Reasons behind the Development of Public Electric Buses in China: The Beijing Case," Sustainability, MDPI, vol. 12(2), pages 1-16, January.
    10. Orhan Topal & İsmail Nakir, 2018. "Total Cost of Ownership Based Economic Analysis of Diesel, CNG and Electric Bus Concepts for the Public Transport in Istanbul City," Energies, MDPI, vol. 11(9), pages 1-17, September.
    11. Christina Iliopoulou & Konstantinos Kepaptsoglou & Eleni Vlahogianni, 2019. "Metaheuristics for the transit route network design problem: a review and comparative analysis," Public Transport, Springer, vol. 11(3), pages 487-521, October.
    12. Neil Quarles & Kara M. Kockelman & Moataz Mohamed, 2020. "Costs and Benefits of Electrifying and Automating Bus Transit Fleets," Sustainability, MDPI, vol. 12(10), pages 1-15, May.
    13. Haghani, Ali & Banihashemi, Mohamadreza, 2002. "Heuristic approaches for solving large-scale bus transit vehicle scheduling problem with route time constraints," Transportation Research Part A: Policy and Practice, Elsevier, vol. 36(4), pages 309-333, May.
    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. 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.
    2. Teresa Pamuła & Danuta Pamuła, 2022. "Prediction of Electric Buses Energy Consumption from Trip Parameters Using Deep Learning," Energies, MDPI, vol. 15(5), pages 1-19, February.
    3. Krystian Pietrzak & Oliwia Pietrzak, 2022. "Tram System as a Challenge for Smart and Sustainable Urban Public Transport: Effects of Applying Bi-Directional Trams," Energies, MDPI, vol. 15(15), pages 1-29, August.

    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. 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.
    2. 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.
    3. Hatem Abdelaty & Moataz Mohamed, 2021. "A Prediction Model for Battery Electric Bus Energy Consumption in Transit," Energies, MDPI, vol. 14(10), pages 1-26, May.
    4. 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.
    5. 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).
    6. 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.
    7. Shehabeldeen, Ali & Foda, Ahmed & Mohamed, Moataz, 2024. "A multi-stage optimization of battery electric bus transit with battery degradation," Energy, Elsevier, vol. 299(C).
    8. 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).
    9. Cong, Yuan & Wang, Heqi & Bie, Yiming & Wu, Jiabin, 2023. "Double-battery configuration method for electric bus operation in cold regions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 180(C).
    10. Ali Saadon Al-Ogaili & Ali Q. Al-Shetwi & Hussein M. K. Al-Masri & Thanikanti Sudhakar Babu & Yap Hoon & Khaled Alzaareer & N. V. Phanendra Babu, 2021. "Review of the Estimation Methods of Energy Consumption for Battery Electric Buses," Energies, MDPI, vol. 14(22), pages 1-28, November.
    11. 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.
    12. 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).
    13. Szilassy, Péter Ákos & Földes, Dávid, 2022. "Consumption estimation method for battery-electric buses using general line characteristics and temperature," Energy, Elsevier, vol. 261(PA).
    14. 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.
    15. López-Ibarra, Jon Ander & Gaztañaga, Haizea & Saez-de-Ibarra, Andoni & Camblong, Haritza, 2020. "Plug-in hybrid electric buses total cost of ownership optimization at fleet level based on battery aging," Applied Energy, Elsevier, vol. 280(C).
    16. Wang, Wensi & Yu, Bin & Zhou, Yu, 2024. "A real-time synchronous dispatching and recharging strategy for multi-line electric bus systems," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 185(C).
    17. Carola Leone & Laura Sturaro & Giacomo Geroli & Michela Longo & Wahiba Yaici, 2021. "Design and Implementation of an Electric Skibus Line in North Italy," Energies, MDPI, vol. 14(23), pages 1-22, November.
    18. 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.
    19. Zhao, Li & Ke, Hanchen & Li, Yuqi & Chen, Yong, 2023. "Research on personalized charging strategy of electric bus under time-varying constraints," Energy, Elsevier, vol. 276(C).
    20. He, Yi & Liu, Zhaocai & Zhang, Yiming & Song, Ziqi, 2023. "Time-dependent electric bus and charging station deployment problem," Energy, Elsevier, vol. 282(C).

    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:gam:jeners:v:14:y:2021:i:20:p:6610-:d:655566. 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: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    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.