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.

Original languageEnglish
Title of host publicationAAAI'11 Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence
Number of pages6
Publisher AAAI Press
Publication date02.11.2011
ISBN (Print)978-157735509-0
Publication statusPublished - 02.11.2011
Event25th AAAI Conference on Artificial Intelligence and the 23rd Innovative Applications of Artificial Intelligence Conference
- San Francisco, United States
Duration: 07.08.201111.08.2011
Conference number: 87049


Dive into the research topics of 'Efficient Energy-Optimal Routing for Electric Vehicles'. Together they form a unique fingerprint.

Cite this