Energy-Optimal Routes for Battery Electric Vehicles

Autor: Moritz Baum, Dorothea Wagner, Thomas Pajor, Julian Dibbelt, Jonas Sauer, Tobias Zündorf
Rok vydání: 2019
Předmět:
Zdroj: Algorithmica. 82:1490-1546
ISSN: 1432-0541
0178-4617
DOI: 10.1007/s00453-019-00655-9
Popis: 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.
Databáze: OpenAIRE
Externí odkaz: