IDEAS home Printed from https://ideas.repec.org/a/inm/ortrsc/v53y2019i6p1627-1655.html
   My bibliography  Save this article

Shortest Feasible Paths with Charging Stops for Battery Electric Vehicles

Author

Listed:
  • Moritz Baum

    (Karlsruhe Institute of Technology (KIT), Karlsruhe 76131, Germany)

  • Julian Dibbelt

    (Karlsruhe Institute of Technology (KIT), Karlsruhe 76131, Germany)

  • Andreas Gemsa

    (Karlsruhe Institute of Technology (KIT), Karlsruhe 76131, Germany)

  • Dorothea Wagner

    (Karlsruhe Institute of Technology (KIT), Karlsruhe 76131, Germany)

  • Tobias Zündorf

    (Karlsruhe Institute of Technology (KIT), Karlsruhe 76131, Germany)

Abstract

We study the problem of minimizing overall trip time for battery electric vehicles in road networks. As battery capacity is limited, stops at charging stations may be inevitable. Careful route planning is crucial because charging stations are scarce and recharging is time-consuming. We extend the constrained shortest-path problem for electric vehicles with realistic models of charging stops, including varying charging power and battery-swapping stations. Although the resulting problem is theoretically hard, we propose a combination of algorithmic techniques to achieve good performance in practice. Extensive experimental evaluation shows that our approach (CHArge) enables computation of optimal solutions on realistic inputs even of continental scale. Finally, we investigate heuristic variants of CHArge that derive high-quality routes in well below a second on sensible instances.

Suggested Citation

  • 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.
    • Handle: RePEc:inm:ortrsc:v:53:y:2019:i:6:p:1627-1655
    DOI: 10.1287/trsc.2018.0889
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/trsc.2018.0889
    Download Restriction: no
    File URL: https://libkey.io/10.1287/trsc.2018.0889?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
    ---><---

    References listed on IDEAS

    as
    1. 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.
    2. 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.
    3. Tung Tung, Chi & Lin Chew, Kim, 1992. "A multicriteria Pareto-optimal path algorithm," European Journal of Operational Research, Elsevier, vol. 62(2), pages 203-209, October.
    4. 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.
    5. Daniel Delling & Andrew V. Goldberg & Thomas Pajor & Renato F. Werneck, 2017. "Customizable Route Planning in Road Networks," Transportation Science, INFORMS, vol. 51(2), pages 566-561, May.
    6. Keisuke Murakami, 2018. "Formulation and algorithms for route planning problem of plug-in hybrid electric vehicles," Operational Research, Springer, vol. 18(2), pages 497-519, July.
    7. 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.
    8. Robert Geisberger & Peter Sanders & Dominik Schultes & Christian Vetter, 2012. "Exact Routing in Large Road Networks Using Contraction Hierarchies," Transportation Science, INFORMS, vol. 46(3), pages 388-404, August.
    9. Liao, Chung-Shou & Lu, Shang-Hung & Shen, Zuo-Jun Max, 2016. "The electric vehicle touring problem," Transportation Research Part B: Methodological, Elsevier, vol. 86(C), pages 163-180.
    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. Montoya, Alejandro & Guéret, Christelle & Mendoza, Jorge E. & Villegas, Juan G., 2017. "The electric vehicle routing problem with nonlinear charging function," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 87-110.
    12. 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).
    13. Strehler, Martin & Merting, Sören & Schwan, Christian, 2017. "Energy-efficient shortest routes for electric and hybrid vehicles," Transportation Research Part B: Methodological, Elsevier, vol. 103(C), pages 111-135.
    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. Daiane Maria Genaro Chiroli & Sérgio Fernando Mayerle & João Neiva Figueiredo, 2022. "Using state-space shortest-path heuristics to solve the long-haul point-to-point vehicle routing and driver scheduling problem subject to hours-of-service regulatory constraints," Journal of Heuristics, Springer, vol. 28(1), pages 23-59, February.
    2. Euler, Ricardo & Maristany de las Casas, Pedro, 2024. "Labeling methods for partially ordered paths," European Journal of Operational Research, Elsevier, vol. 318(1), pages 19-30.
    3. Junchi Ma & Yuan Zhang & Zongtao Duan & Lei Tang, 2023. "PROLIFIC: Deep Reinforcement Learning for Efficient EV Fleet Scheduling and Charging," Sustainability, MDPI, vol. 15(18), pages 1-22, September.
    4. 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.
    5. Maximiliano Cubillos & Mauro Dell’Amico & Ola Jabali & Federico Malucelli & Emanuele Tresoldi, 2023. "An Enhanced Path Planner for Electric Vehicles Considering User-Defined Time Windows and Preferences," Energies, MDPI, vol. 16(10), pages 1-19, May.
    6. Pottel, Steffen & Goel, Asvin, 2022. "Scheduling activities with time-dependent durations and resource consumptions," European Journal of Operational Research, Elsevier, vol. 301(2), pages 445-457.

    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. 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. 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.
    3. 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).
    4. 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.
    5. 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.
    6. 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.
    7. 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).
    8. Leandro do C. Martins & Rafael D. Tordecilla & Juliana Castaneda & Angel A. Juan & Javier Faulin, 2021. "Electric Vehicle Routing, Arc Routing, and Team Orienteering Problems in Sustainable Transportation," Energies, MDPI, vol. 14(16), pages 1-30, August.
    9. 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.
    10. Xu, Min & Meng, Qiang, 2019. "Fleet sizing for one-way electric carsharing services considering dynamic vehicle relocation and nonlinear charging profile," Transportation Research Part B: Methodological, Elsevier, vol. 128(C), pages 23-49.
    11. 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.
    12. 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.
    13. Zhou, Yu & Meng, Qiang & Ong, Ghim Ping, 2022. "Electric Bus Charging Scheduling for a Single Public Transport Route Considering Nonlinear Charging Profile and Battery Degradation Effect," Transportation Research Part B: Methodological, Elsevier, vol. 159(C), pages 49-75.
    14. 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.
    15. Alberto Ceselli & Ángel Felipe & M. Teresa Ortuño & Giovanni Righini & Gregorio Tirado, 2021. "A Branch-and-Cut-and-Price Algorithm for the Electric Vehicle Routing Problem with Multiple Technologies," SN Operations Research Forum, Springer, vol. 2(1), pages 1-33, March.
    16. 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.
    17. Alexandre M. Florio & Nabil Absi & Dominique Feillet, 2021. "Routing Electric Vehicles on Congested Street Networks," Transportation Science, INFORMS, vol. 55(1), pages 238-256, 1-2.
    18. Malladi, Satya S. & Christensen, Jonas M. & Ramírez, David & Larsen, Allan & Pacino, Dario, 2022. "Stochastic fleet mix optimization: Evaluating electromobility in urban logistics," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    19. Maximiliano Cubillos & Mauro Dell’Amico & Ola Jabali & Federico Malucelli & Emanuele Tresoldi, 2023. "An Enhanced Path Planner for Electric Vehicles Considering User-Defined Time Windows and Preferences," Energies, MDPI, vol. 16(10), pages 1-19, May.
    20. Muhammad Usama & Yongjun Shen & Onaira Zahoor, 2019. "Towards an Energy Efficient Solution for Bike-Sharing Rebalancing Problems: A Battery Electric Vehicle Scenario," Energies, MDPI, vol. 12(13), pages 1-21, June.

    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:inm:ortrsc:v:53:y:2019:i:6:p:1627-1655. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.