Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
Energy-Optimal Routes for Battery Electric Vehicles
Ist Teil von
Algorithmica, 2020-05, Vol.82 (5), p.1490-1546
Ort / Verlag
New York: Springer US
Erscheinungsjahr
2020
Link zum Volltext
Quelle
Alma/SFX Local Collection
Beschreibungen/Notizen
We study the problem of computing paths that minimize energy consumption of a battery electric vehicle. For that, we must cope with specific properties, such as regenerative braking and constraints imposed by the battery capacity. These restrictions can be captured by
profiles
, which are a functional representation of optimal energy consumption between two locations, subject to initial state of charge. Efficient computation of profiles is a relevant problem on its own, but also a fundamental ingredient to many route planning approaches for battery electric vehicles. In this work, we prove that profiles have linear complexity. We examine different variants of Dijkstra’s algorithm to compute energy-optimal paths or profiles. Further, we derive a
polynomial-time
algorithm for the problem of finding an energy-optimal path between two locations that allows stops at charging stations. We also discuss a heuristic variant that is easy to implement, and carefully integrate it with the well-known Contraction Hierarchies algorithm and A* search. Finally, we propose a practical approach that enables computation of energy-optimal routes within milliseconds after fast (metric-dependent) preprocessing of the
whole
network. This enables flexible updates due to, e. g., weather forecasts or refinements of the consumption model. Practicality of our approaches is demonstrated in a comprehensive experimental study on realistic, large-scale road networks.