Shortest Feasible Paths with Charging Stops for Battery Electric Vehicles

Moritz Baum (), Julian Dibbelt (), Andreas Gemsa (), Dorothea Wagner () and Tobias Zündorf ()
Additional contact information
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

Transportation Science, 2019, vol. 53, issue 6, 1627-1655

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.

Keywords: route planning; road networks; speedup techniques; algorithm engineering; shortest paths; electric vehicles; energy consumption; charging stations (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1287/trsc.2018.0889 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:53:y:2019:i:6:p:1627-1655

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().