2026-07-23T20:44:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7608 2024-03-06T10:39:49Z ddc:004 open_access

Consumption Profiles in Route Planning for Electric Vehicles: Theory and Applications Baum, Moritz Sauer, Jonas Wagner, Dorothea Zündorf, Tobias electric vehicles charging station shortest paths route planning profile search algorithm engineering In route planning for electric vehicles (EVs), consumption profiles 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 EVs. In this work, we show that the complexity of a profile is at most linear in the graph size. Based on this insight, we derive a polynomial-time algorithm for the problem of finding an energy-optimal path between two locations that allows stops at charging stations. Exploiting efficient profile search, our approach also allows partial recharging at charging stations to save energy. In a sense, our results close the gap between efficient techniques for energy-optimal routes (based on simpler models) and NP-hard time-constrained problems involving charging stops for EVs. We propose a practical implementation, which we carefully integrate with Contraction Hierarchies and A* search. Even though the practical variant formally drops correctness, a comprehensive experimental study on a realistic, large-scale road network reveals that it always finds the optimal solution in our tests and computes even long-distance routes with charging stops in less than 300 ms. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Moritz Baum and Jonas Sauer and Dorothea Wagner and Tobias Zündorf 2017 Is Part Of LIPIcs, Volume 75, 16th International Symposium on Experimental Algorithms (SEA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2017.19 urn:nbn:de:0030-drops-76088 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2017.19 eng https://creativecommons.org/licenses/by/3.0/legalcode