Shortest feasible paths with charging stops for battery electric vehicles

Baum, Moritz; Dibbelt, Julian; Gemsa, Andreas; Wagner, Dorothea; Zündorf, Tobias · 2015 · Crossref

DOI: 10.1145/2820783.2820826

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 problem of finding the fastest feasible routes for battery electric vehicles (EVs) in road networks, accounting for necessary charging stops. The motivation stems from the limitations of EVs, including restricted driving range, scarce charging infrastructure, and time-consuming recharging processes. Unlike conventional route planning, EV routing must ensure the battery does not deplete while minimizing total trip time, which includes both driving and charging durations. The authors extend the Constrained Shortest Path (CSP) problem to incorporate realistic charging models, such as varying charging powers and battery swapping, which previous works often simplified or ignored. The authors propose an algorithmic approach called CHArge, which combines a label-setting search with speedup techniques to solve this NP-hard problem. The core method involves a Charging Function Propagating (CFP) algorithm that uses labels of constant size to represent continuous tradeoffs between charging time and state of charge (SoC). To improve performance, the authors integrate Contraction Hierarchies (CH) and A* search, adapting them to handle the bicriteria nature of driving time and energy consumption. They also introduce heuristic variants that sacrifice optimality for significantly faster query times. The experimental evaluation uses realistic, large-scale road network data, including continental-scale graphs, to test the effectiveness of these methods. The results demonstrate that the CHArge approach can compute optimal solutions for realistic inputs within seconds, even on large-scale networks. The algorithm effectively handles complex charging scenarios, including nonlinear charging rates and different station types, outperforming existing state-of-the-art methods. The heuristic variants provide high-quality routes in well under a second, making them suitable for practical applications where speed is critical. The study confirms that incorporating detailed charging models does not preclude efficient computation, as the proposed techniques scale to country-sized and larger graphs. The significance of this work lies in its contribution to the field of EV route planning by providing a practical solution to a complex, realistic problem. By addressing the limitations of previous models that assumed constant charging times or ignored charging dynamics, the authors enable more accurate and efficient route planning for EVs. This advancement supports the broader adoption of electromobility by ensuring that route planning tools can handle the specific constraints of electric vehicles, thereby improving user experience and operational efficiency. The paper also highlights the potential for further research into heuristic methods and dynamic metrics in EV routing.

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.

• exposure measurement