Energy-optimal routes for electric vehicles

Baum, Moritz; Dibbelt, Julian; Pajor, Thomas; Wagner, Dorothea · 2013 · OpenAlex-citations

DOI: 10.1145/2525314.2525361

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 computing energy-optimal routes for electric vehicles (EVs) on large-scale road networks. The problem is motivated by the need to maximize cruising range and alleviate "range anxiety" for EV users, which requires precise modeling of energy consumption. This modeling must account for specific EV properties, including energy recuperation during downhill driving (resulting in negative arc costs), battery capacity constraints, and frequently changing cost functions due to factors like weather and vehicle load. The authors aim to develop an algorithm that is both fast in preprocessing and query execution, even on continental-scale networks. The authors extend the Customizable Route Planning (CRP) approach to handle these EV-specific constraints. Their method utilizes multi-level overlay graphs to accelerate queries. The approach involves three phases: a metric-independent preprocessing phase that partitions the graph; a metric-dependent customization phase that computes cost functions for overlay arcs using profile queries; and an online query phase. To handle negative costs from recuperation, they employ potential shifting to enable Dijkstra-based search. They introduce two bidirectional search variants: Bidirectional Profile-Evaluating Multi-Level-Dijkstra (BPE-MLD) and Bidirectional Distance-Bounding Multi-Level-Dijkstra (BDB-MLD). These algorithms guide the forward search using bounds derived from a backward search, carefully accounting for battery state-of-charge constraints. The implementation uses efficient data structures for piecewise linear cost functions and supports parallelization. Experimental results were conducted on a European road network using detailed consumption data from a Peugeot iOn (16 kWh battery) and an artificial high-capacity vehicle model (85 kWh). The study demonstrates that the metric-dependent customization phase takes approximately 4–5 seconds, allowing for rapid updates to cost functions. For random queries on the European network, the proposed algorithms achieve average query times of 0.3 ms for the Peugeot iOn model and 1.1–1.4 ms for the high-capacity model. These times are significantly faster than previous approaches, such as Contraction Hierarchies adapted for EVs, which reported query times of 38–45 ms on country-scale networks. The algorithm also scales well with increased battery capacity, maintaining sub-5 ms query times for long-range queries across Europe. The significance of this work lies in providing a practical, high-performance solution for EV route planning that supports interactive applications. By achieving fast preprocessing and query times, the method allows for dynamic updates to energy consumption models based on real-time data like weather forecasts. The approach effectively handles the complexities of negative arc costs and battery constraints without sacrificing speed, outperforming existing methods by orders of magnitude in preprocessing time and significantly reducing query latency. This enables robust route planning for current and future EVs with larger battery capacities.

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.

• eco driving