KIT | KIT-Bibliothek | Impressum | Datenschutz

Shortest Feasible Paths with Charging Stops for Battery Electric Vehicles

Baum, Moritz; Dibbelt, Julian; Gemsa, Andreas; Wagner, Dorothea; Zündorf, Tobias


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, since 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. While the resulting problem is NP-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.

Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht/Preprint
Publikationsmonat/-jahr 11.2019
Sprache Englisch
Identifikator ISSN: 0041-1655, 1526-5447
KITopen-ID: 1000104997
HGF-Programm 37.06.01 (POF III, LK 01) Networks and Storage Integration
Verlag informs
Serie Transportation Science ; 53
Nachgewiesen in arXiv
Relationen in KITopen
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page