文章基本信息

标题：Consumption Profiles in Route Planning for Electric Vehicles: Theory and Applications
本地全文：下载
作者：Moritz Baum ; Jonas Sauer ; Dorothea Wagner 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：75
页码：19:1-19:18
DOI：10.4230/LIPIcs.SEA.2017.19
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：electric vehicles; charging station; shortest paths; route planning; profile search; algorithm engineering