2020/10/01 by Moritz Baum, Julian Dibbelt, Dorothea Wagner +1 · 37 citations
Computer Science · Engineering · Mathematics · Social Sciences · #Algorithm #Battery (electricity) #Battery electric vehicle #Computer science #Constrained Shortest Path First #Correctness #Dijkstra's algorithm #Electrical engineering #Energy (signal processing) #Energy consumption #Engineering #Heuristics #K shortest path routing #Matching (statistics) #Mathematical optimization #Mathematics #Path (computing) #Shortest path problem #Transportation Planning and Optimization #Transportation and Mobility Innovations #Vehicle Routing Optimization Methods #cs.DS
paper · pdf · doi:10.1287/trsc.2020.0981
published in Transportation Science 54(6), 1571-1600 (Institute for Operations Research and the Management Sciences)
openalex publication_date 2020/10/01 · arxiv created 2020/11/20 · arxiv updated 2020/11/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We study the problem of computing constrained shortest paths for battery electric vehicles. Because battery capacities are limited, fastest routes are often infeasible. Instead, users are interested in fast routes on which the energy consumption does not exceed the battery capacity. For that, drivers can deliberately reduce speed to save energy. Hence, route planning should provide both path and speed recommendations. To tackle the resulting [Formula: see text]-hard optimization problem, previous work trades correctness or accuracy of the underlying model for practical running times. We present a novel framework to compute optimal constrained shortest paths (without charging stops) for electric vehicles that uses more realistic physical models, while taking speed adaptation into account. Careful algorithm engineering makes the approach practical even on large, realistic road networks: We compute optimal solutions in less than a second for typical battery capacities, matching the performance of previous inexact methods. For even faster query times, the approach can easily be extended with heuristics that provide high quality solutions within milliseconds.