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. 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).
    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. 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.
    8. 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).
    9. 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).
    10. 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).
    11. 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.
    12. Basma, Hussein & Mansour, Charbel & Haddad, Marc & Nemer, Maroun & Stabat, Pascal, 2022. "Energy consumption and battery sizing for different types of electric bus service," Energy, Elsevier, vol. 239(PE).
    13. Ali Saadon Al-Ogaili & Ali Q. Al-Shetwi & Thanikanti Sudhakar Babu & Yap Hoon & Majid A. Abdullah & Ameer Alhasan & Ammar Al-Sharaa, 2021. "Electric Buses in Malaysia: Policies, Innovations, Technologies and Life Cycle Evaluations," Sustainability, MDPI, vol. 13(21), pages 1-22, October.
    14. 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.
    15. 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.
    16. Chung-Jen Chou & Shyh-Biau Jiang & Tse-Liang Yeh & Chein-Chung Sun, 2021. "Fault-Tolerant Battery Power Network Architecture of Networked Swappable Battery Packs in Parallel," Energies, MDPI, vol. 14(10), pages 1-21, May.
    17. Battaïa, Olga & Dolgui, Alexandre & Guschinsky, Nikolai & Kovalyov, Mikhail Y., 2023. "Designing fast-charge urban electric bus services: An Integer Linear Programming model," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 171(C).
    18. Krzysztof KRAWIEC, 2021. "Vehicle Cycle Hierarchization Model To Determine The Order Of Battery Electric Bus Deployment In Public Transport," Transport Problems, Silesian University of Technology, Faculty of Transport, vol. 16(1), pages 99-112, March.
    19. Harris, Andrew & Soban, Danielle & Smyth, Beatrice M. & Best, Robert, 2020. "A probabilistic fleet analysis for energy consumption, life cycle cost and greenhouse gas emissions modelling of bus technologies," Applied Energy, Elsevier, vol. 261(C).
    20. Chen, Haoqian & Sui, Yi & Shang, Wen-long & Sun, Rencheng & Chen, Zhiheng & Wang, Changying & Han, Chunjia & Zhang, Yuqian & Zhang, Haoran, 2022. "Towards renewable public transport: Mining the performance of electric buses using solar-radiation as an auxiliary power source," Applied Energy, Elsevier, vol. 325(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.