Efficient Energy-Optimal Routing for Electric Vehicles

Martin Sachenbacher, Martin Leucker, Andreas Artmeier, Julian Haselmayr


Traditionally routing has focused on finding shortest paths in networks with positive, static edge costs representing the distance between two nodes. Energy-optimal routing for electric vehicles creates novel algorithmic challenges, as simply understanding edge costs as energy values and applying standard algorithms does not work. First, edge costs can be negative due to recuperation, excluding Dijkstra-like algorithms. Second, edge costs may depend on parameters such as vehicle weight only known at query time, ruling out existing preprocessing techniques. Third, considering battery capacity limitations implies that the cost of a path is no longer just the sum of its edge costs. This paper shows how these challenges can be met within the framework of A*search. We show how the specific domain gives rise to a consistent heuristic function yielding an O(n2) routing algorithm. Moreover, we show how battery constraints can be treated by dynamically adapting edge costs and hence can be handled in the same way as parameters given at query time, without increasing run-time complexity. Experimental results with real road networks and vehicle data demonstrate the advantages of our solution.

TitelAAAI'11 Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence
Herausgeber (Verlag) AAAI Press
ISBN (Print)978-157735509-0
PublikationsstatusVeröffentlicht - 02.11.2011
Veranstaltung25th AAAI Conference on Artificial Intelligence and the 23rd Innovative Applications of Artificial Intelligence Conference
- San Francisco, USA / Vereinigte Staaten
Dauer: 07.08.201111.08.2011
Konferenznummer: 87049


Untersuchen Sie die Forschungsthemen von „Efficient Energy-Optimal Routing for Electric Vehicles“. Zusammen bilden sie einen einzigartigen Fingerprint.