Modeling and Engineering Constrained Shortest Path Algorithms for Battery Electric Vehicles

Baum, Moritz; Dibbelt, Julian; Wagner, Dorothea; Zündorf, Tobias · 2020 · Crossref

DOI: 10.1287/trsc.2020.0981

archive: archived pipeline: cataloged verified

Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)

Summary

This paper addresses the challenge of route planning for battery electric vehicles (EVs), specifically focusing on computing constrained shortest paths that account for adaptive driving speeds. The primary motivation is the limited battery capacity of EVs, which often renders the fastest routes infeasible without intermediate charging. To mitigate range anxiety and avoid time-consuming stops, the authors propose a framework that allows drivers to deliberately reduce speed to conserve energy, particularly on high-speed roads. This approach also incorporates energy recuperation during braking. The problem is formulated as finding the fastest route where energy consumption does not exceed the battery capacity, a task complicated by the NP-hard nature of the optimization when speed adaptation is included. Previous methods often sacrificed model accuracy or correctness for speed, or relied on discrete speed sampling that led to exponential growth in solution space. To solve this, the authors develop a novel framework that models the tradeoff between driving time and energy consumption using continuous, nonlinear functions derived from realistic physical models. Instead of treating speed as a fixed scalar or using parallel arcs for discrete speed samples, the method defines consumption functions $c_a(x)$ that map driving time $x$ to energy consumption for each road segment. These functions incorporate aerodynamic drag, slope, and speed limits. The core algorithmic contribution involves extending the bicriteria shortest path algorithm to propagate these continuous consumption functions along paths. The authors derive operations to compute the lower envelope of consumption functions for path segments, ensuring convexity, and define bivariate state-of-charge functions to handle battery constraints. To achieve practical performance on large road networks, they integrate these models with advanced search techniques, including A* search with vertex potentials and Contraction Hierarchies (CH). A significant engineering challenge addressed is the computation of shortcuts in CH that represent bivariate functions to capture the complex constraints of the consumption model. Experimental evaluations on realistic road networks demonstrate that the proposed approach computes optimal solutions in less than a second for typical battery capacities, matching the performance of previous inexact heuristic methods. The algorithm successfully handles the complexity of continuous speed adaptation without the exponential blowup associated with discrete sampling. For applications requiring even faster query times, the authors show that the approach can be extended with heuristics that provide high-quality solutions within milliseconds. The results indicate that optimal route planning with adaptive speeds is feasible for interactive applications, providing both path and speed recommendations that ensure the destination is reached without battery depletion. The significance of this work lies in its ability to provide provably optimal solutions for EV route planning using realistic physical models, bridging the gap between theoretical accuracy and practical efficiency. By demonstrating that optimal constrained shortest paths with continuous speed adaptation can be computed efficiently, the paper advances the state of the art in transportation algorithms. This is particularly relevant for the growing adoption of EVs and autonomous vehicles, where precise energy management and speed planning are critical for user experience and operational efficiency. The framework offers a robust alternative to heuristic-only approaches, ensuring reliability in route recommendations while maintaining the speed necessary for real-time navigation systems.

Provenance

The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.

Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.

Topics

Ranked by relevance to this paper. Hover a topic for its definition.

• speed choice