IDEAS home Printed from https://ideas.repec.org/p/ant/wpaper/2022005.html
   My bibliography  Save this paper

The electric on-demand bus routing problem with partial charging and nonlinear functions

Author

Listed:
  • LIAN, Ying
  • LUCAS, Flavien
  • SÖRENSEN, Kenneth

Abstract

Electric vehicle routing problems (EVRPs) with recharging policy consider the limited range of electric vehicles and thus include intermediate visits to charging stations (CSs). In general, minimizing the resultant charging costs such as charging duration or charging amount are also part of the objective of EVRP. Accordingly, EVRPs have received considerable attention over the past years. Nevertheless, this type of problems in the domain of passenger transportation, a VRP variant, has been rarely studied in the literature, especially with time windows, a realistic nonlinear charging function or partial charging policy. Hence this research extends the existing work on EVRP to an On-Demand Bus Routing Problem (ODBRP) which transports passengers with bus station assignment (BSA). The resultant problem is the EODBRP. Specifically, each passenger can have more than one stations to board or alight, and they are assigned to the ones with the smallest increase in the total user ride time (URT). In EODBRP, frequent intermediate visits to CSs are considered. Moreover, nonlinear charging functions are in use and partial charging strategy is applied. To solve the EODBRP, a greedy insertion method with ‘charging first, routing second’ strategy is developed, followed by a large neighborhood search (LNS) which consists of local search (LS) operators to further improve the solution quality. Experimental data were generated by a realistic instance generator based on a real city map, and the corresponding results show that the proposed heuristic algorithm performs well in solving the EODBRP. Finally, sensitivity analyses with divergent parameters such as the temporal distributions of passengers and bus ranges may provide practical guidance

Suggested Citation

  • LIAN, Ying & LUCAS, Flavien & SÖRENSEN, Kenneth, 2022. "The electric on-demand bus routing problem with partial charging and nonlinear functions," Working Papers 2022005, University of Antwerp, Faculty of Business and Economics.
    • Handle: RePEc:ant:wpaper:2022005
    as

    Download full text from publisher

    File URL: https://repository.uantwerpen.be/docstore/d:irua:12522
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Dayarian, Iman & Crainic, Teodor Gabriel & Gendreau, Michel & Rei, Walter, 2016. "An adaptive large-neighborhood search heuristic for a multi-period vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 95(C), pages 95-123.
    2. Yan Zhou & Michael Wang & Han Hao & Larry Johnson & Hewu Wang & Han Hao, 2015. "Plug-in electric vehicle market penetration and incentives: a global review," Mitigation and Adaptation Strategies for Global Change, Springer, vol. 20(5), pages 777-795, June.
    3. Moritz Baum & Julian Dibbelt & Andreas Gemsa & Dorothea Wagner & Tobias Zündorf, 2019. "Shortest Feasible Paths with Charging Stops for Battery Electric Vehicles," Transportation Science, INFORMS, vol. 53(6), pages 1627-1655, November.
    4. Pelletier, Samuel & Jabali, Ola & Laporte, Gilbert & Veneroni, Marco, 2017. "Battery degradation and behaviour for electric vehicles: Review and numerical analyses of several models," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 158-187.
    5. Schiffer, Maximilian & Walther, Grit, 2017. "The electric location routing problem with time windows and partial recharging," European Journal of Operational Research, Elsevier, vol. 260(3), pages 995-1013.
    6. Schiffer, Maximilian & Walther, Grit, 2018. "Strategic planning of electric logistics fleet networks: A robust location-routing approach," Omega, Elsevier, vol. 80(C), pages 31-42.
    7. David Pisinger & Stefan Ropke, 2019. "Large Neighborhood Search," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, edition 3, chapter 0, pages 99-127, Springer.
    8. Timothy M. Sweda & Irina S. Dolinskaya & Diego Klabjan, 2017. "Adaptive Routing and Recharging Policies for Electric Vehicles," Transportation Science, INFORMS, vol. 51(4), pages 1326-1348, November.
    9. Pelletier, Samuel & Jabali, Ola & Laporte, Gilbert, 2019. "The electric vehicle routing problem with energy consumption uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 225-255.
    10. Guy Desaulniers & Fausto Errico & Stefan Irnich & Michael Schneider, 2016. "Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows," Operations Research, INFORMS, vol. 64(6), pages 1388-1405, December.
    11. Bongiovanni, Claudia & Kaspi, Mor & Geroliminis, Nikolas, 2019. "The electric autonomous dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 436-456.
    12. Zhang, Li & Liu, Zhongshan & Yu, Lan & Fang, Ke & Yao, Baozhen & Yu, Bin, 2022. "Routing optimization of shared autonomous electric vehicles under uncertain travel time and uncertain service time," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 157(C).
    13. Maximilian Schiffer & Grit Walther, 2018. "An Adaptive Large Neighborhood Search for the Location-routing Problem with Intra-route Facilities," Transportation Science, INFORMS, vol. 52(2), pages 331-352, March.
    14. Hiermann, Gerhard & Puchinger, Jakob & Ropke, Stefan & Hartl, Richard F., 2016. "The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations," European Journal of Operational Research, Elsevier, vol. 252(3), pages 995-1018.
    15. Hof, Julian & Schneider, Michael & Goeke, Dominik, 2017. "Solving the battery swap station location-routing problem with capacitated electric vehicles using an AVNS algorithm for vehicle-routing problems with intermediate stops," Transportation Research Part B: Methodological, Elsevier, vol. 97(C), pages 102-112.
    16. Cordeau, Jean-François & Laporte, Gilbert, 2003. "A tabu search heuristic for the static multi-vehicle dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 37(6), pages 579-594, July.
    17. Schneider, M. & Stenger, A. & Goeke, D., 2014. "The Electric Vehicle Routing Problem with Time Windows and Recharging Stations," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 62382, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    18. Healy, Patrick & Moll, Robert, 1995. "A new extension of local search applied to the Dial-A-Ride Problem," European Journal of Operational Research, Elsevier, vol. 83(1), pages 83-104, May.
    19. Michael Schneider & Andreas Stenger & Dominik Goeke, 2014. "The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations," Transportation Science, INFORMS, vol. 48(4), pages 500-520, November.
    20. Timo Gschwind & Michael Drexl, 2019. "Adaptive Large Neighborhood Search with a Constant-Time Feasibility Test for the Dial-a-Ride Problem," Transportation Science, INFORMS, vol. 53(2), pages 480-491, March.
    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. Lian, Ying & Lucas, Flavien & Sörensen, Kenneth, 2024. "Prepositioning can improve the performance of a dynamic stochastic on-demand public bus system," European Journal of Operational Research, Elsevier, vol. 312(1), pages 338-356.

    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. Asghari, Mohammad & Mirzapour Al-e-hashem, S. Mohammad J., 2021. "Green vehicle routing problem: A state-of-the-art review," International Journal of Production Economics, Elsevier, vol. 231(C).
    2. Erfan Ghorbani & Mahdi Alinaghian & Gevork. B. Gharehpetian & Sajad Mohammadi & Guido Perboli, 2020. "A Survey on Environmentally Friendly Vehicle Routing Problem and a Proposal of Its Classification," Sustainability, MDPI, vol. 12(21), pages 1-71, October.
    3. Mohammad Asghari & Seyed Mohammad Javad Mirzapour Al-E-Hashem, 2021. "Green vehicle routing problem: A state-of-the-art review," Post-Print hal-03182944, HAL.
    4. Maximilian Schiffer & Michael Schneider & Grit Walther & Gilbert Laporte, 2019. "Vehicle Routing and Location Routing with Intermediate Stops: A Review," Transportation Science, INFORMS, vol. 53(2), pages 319-343, March.
    5. Singh, Nitish & Dang, Quang-Vinh & Akcay, Alp & Adan, Ivo & Martagan, Tugce, 2022. "A matheuristic for AGV scheduling with battery constraints," European Journal of Operational Research, Elsevier, vol. 298(3), pages 855-873.
    6. Raeesi, Ramin & Zografos, Konstantinos G., 2022. "Coordinated routing of electric commercial vehicles with intra-route recharging and en-route battery swapping," European Journal of Operational Research, Elsevier, vol. 301(1), pages 82-109.
    7. Masmoudi, Mohamed Amine & Hosny, Manar & Demir, Emrah & Genikomsakis, Konstantinos N. & Cheikhrouhou, Naoufel, 2018. "The dial-a-ride problem with electric vehicles and battery swapping stations," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 118(C), pages 392-420.
    8. Bongiovanni, Claudia & Kaspi, Mor & Geroliminis, Nikolas, 2019. "The electric autonomous dial-a-ride problem," Transportation Research Part B: Methodological, Elsevier, vol. 122(C), pages 436-456.
    9. Bektaş, Tolga & Ehmke, Jan Fabian & Psaraftis, Harilaos N. & Puchinger, Jakob, 2019. "The role of operational research in green freight transportation," European Journal of Operational Research, Elsevier, vol. 274(3), pages 807-823.
    10. Raeesi, Ramin & Zografos, Konstantinos G., 2020. "The electric vehicle routing problem with time windows and synchronised mobile battery swapping," Transportation Research Part B: Methodological, Elsevier, vol. 140(C), pages 101-129.
    11. Cortés-Murcia, David L. & Prodhon, Caroline & Murat Afsar, H., 2019. "The electric vehicle routing problem with time windows, partial recharges and satellite customers," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 130(C), pages 184-206.
    12. Azra Ghobadi & Mohammad Fallah & Reza Tavakkoli-Moghaddam & Hamed Kazemipoor, 2022. "A Fuzzy Two-Echelon Model to Optimize Energy Consumption in an Urban Logistics Network with Electric Vehicles," Sustainability, MDPI, vol. 14(21), pages 1-31, October.
    13. 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.
    14. Dönmez, Sercan & Koç, Çağrı & Altıparmak, Fulya, 2022. "The mixed fleet vehicle routing problem with partial recharging by multiple chargers: Mathematical model and adaptive large neighborhood search," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 167(C).
    15. Xiao, Yiyong & Zhang, Yue & Kaku, Ikou & Kang, Rui & Pan, Xing, 2021. "Electric vehicle routing problem: A systematic review and a new comprehensive model with nonlinear energy recharging and consumption," Renewable and Sustainable Energy Reviews, Elsevier, vol. 151(C).
    16. Li, Lu & Lo, Hong K. & Huang, Wei & Xiao, Feng, 2021. "Mixed bus fleet location-routing-scheduling under range uncertainty," Transportation Research Part B: Methodological, Elsevier, vol. 146(C), pages 155-179.
    17. Sina Rastani & Bülent Çatay, 2023. "A large neighborhood search-based matheuristic for the load-dependent electric vehicle routing problem with time windows," Annals of Operations Research, Springer, vol. 324(1), pages 761-793, May.
    18. Schiffer, Maximilian & Schneider, Michael & Laporte, Gilbert, 2018. "Designing sustainable mid-haul logistics networks with intra-route multi-resource facilities," European Journal of Operational Research, Elsevier, vol. 265(2), pages 517-532.
    19. Yusuf Yilmaz & Can B. Kalayci, 2022. "Variable Neighborhood Search Algorithms to Solve the Electric Vehicle Routing Problem with Simultaneous Pickup and Delivery," Mathematics, MDPI, vol. 10(17), pages 1-22, August.
    20. Seyfi, Majid & Alinaghian, Mahdi & Ghorbani, Erfan & Çatay, Bülent & Saeid Sabbagh, Mohammad, 2022. "Multi-mode hybrid electric vehicle routing problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 166(C).

    More about this item

    Keywords

    On-demand bus routing problem; Electric vehicle; Non-linear charging function; Partial charging;
    All these keywords.

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:ant:wpaper:2022005. 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: Joeri Nys (email available below). General contact details of provider: https://edirc.repec.org/data/ftufsbe.html .

    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.