Efficient Energy-Optimal Routing for Electric Vehicles
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 algorithmic challenges of energy-optimal routing for electric vehicles (EVs), a problem distinct from traditional shortest-path routing due to three specific factors: negative edge costs caused by regenerative braking, dynamic edge costs dependent on query-time parameters like vehicle payload, and battery capacity constraints that make path costs non-additive. Standard algorithms like Dijkstra’s are inapplicable due to negative weights, while preprocessing techniques are ruled out by dynamic parameters. The authors propose a solution within the A* search framework that achieves a worst-case time complexity of $O(n^2)$, improving upon previous $O(n^3)$ approaches. The method models the road network as a directed graph where edge costs are split into potential energy changes (based on elevation) and energy losses (due to friction and aerodynamics). To handle negative weights without preprocessing, the authors utilize the potential energy function as a consistent heuristic, allowing the use of Dijkstra-like logic on reduced weights. For dynamic parameters and battery constraints, the algorithm dynamically adjusts edge costs during the search. Specifically, it incorporates an additional cost function that accounts for battery limits: if a path exceeds the battery’s initial charge, the cost becomes infinite; if recuperation is limited by a full battery, the "lost" energy is added to the cost. This dynamic adjustment preserves the consistency of the heuristic, ensuring optimality and maintaining the $O(n^2)$ complexity bound. Experimental results were conducted using a prototype system on a real-world road network of Bavaria, Germany, comprising over 2.4 million vertices and 4.9 million edges, using OpenStreetMap and NASA elevation data. The authors compared their Energy-A* algorithm against two generic shortest-path strategies (Dijkstra and Pallottino variants) from prior work. The results demonstrated that the proposed algorithm significantly outperformed the generic approaches, improving runtime by an order of magnitude. The experiments confirmed that the algorithm efficiently handles the complex, dynamic nature of EV energy consumption while respecting battery constraints. The significance of this work lies in providing a computationally efficient and theoretically sound method for EV route planning that accounts for physical realities like recuperation and battery limits. By achieving $O(n^2)$ complexity, the approach is viable for real-time navigation systems. The authors conclude that the framework can be extended to predict remaining range and suggest future work on incorporating kinetic energy and stochastic models to assess the risk of running out of energy.
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.
| Stage | Outcome | Tool | Model | Prompt | Attempts | Completed |
|---|---|---|---|---|---|---|
| discover | success | Crossref | — | — | 1 | 2026-06-19 |
| archive | success | canonical_url | — | — | 1 | 2026-06-26 |
| extract | success | cached | — | — | 2 | 2026-06-26 |
| clean | success | clean | — | — | 1 | 2026-06-19 |
| chunk | success | chunk | — | — | 1 | 2026-06-19 |
| embed | success | embed | Qwen/Qwen3-Embedding-8B | — | 1 | 2026-06-19 |
| promote | success | — | — | — | 1 | 2026-06-19 |
| summarize | success | llm | qwen3.6-27b-prismaquant | summ-v5 | 1 | 2026-06-26 |
| tag | success | vector_similarity | — | — | 6 | 2026-06-19 |
| verify | success | — | — | — | 1 | 2026-06-26 |
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.