The Shortest Path Problem Revisited: Optimal Routing for Electric Vehicles

Artmeier, Andreas; Haselmayr, Julian; Leucker, Martin; Sachenbacher, Martin · 2010 · OpenAlex-citations

DOI: 10.1007/978-3-642-16111-7_35

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 optimal routing for electric vehicles (EVs), which differ from conventional vehicles due to limited battery capacity, long recharge times, and the ability to recover energy through regenerative braking. These characteristics necessitate finding energy-efficient routes rather than merely the shortest or fastest ones. The authors formalize this task as a special case of the constrained shortest path problem (CSP), incorporating hard constraints (battery cannot discharge below zero) and soft constraints (battery cannot exceed maximum capacity during recuperation). While general CSP is NP-complete, the authors demonstrate that energy-efficient routing with recuperation is a tractable variant that can be solved in polynomial time. To solve this problem, the authors propose an adaptation of a generic shortest-path algorithm, termed the ConstrainedGenericShortestPath algorithm. This method operates on a directed graph where edge weights represent energy consumption or gain. The algorithm introduces specific modifications to handle battery constraints: it initializes the source vertex based on remaining storage capacity and enforces checks to ensure the battery level never drops below zero or exceeds its maximum capacity. The authors analyze several expansion strategies for processing vertices, including Dijkstra’s strategy, a FIFO strategy (Bellman-Ford), and two novel strategies: *expand* and *expand-distance*. They prove that the *expand-distance* strategy guarantees a worst-case time complexity of $O(n^3)$ for arbitrary weights and $O(n^2)$ for non-negative weights, making it suitable for graphs with negative weights caused by energy recuperation. The proposed algorithms were implemented and evaluated within a prototypic navigation system using OpenStreetMap data and NASA elevation data for a road network in the Allgäu region, comprising over 776,000 vertices and 1.7 million edges. Experiments compared the runtime of four strategies across varying battery capacities. The results showed that the *FIFO* and *expand* strategies were impractical, failing to produce results within one minute for capacities above 20 kWh. In contrast, the *expand-distance* strategy performed efficiently, running less than twice as slow as Dijkstra’s algorithm in these tests while maintaining polynomial worst-case complexity. This confirms that *expand-distance* is the most viable approach for energy-optimal routing in large-scale road networks. The significance of this work lies in providing a computationally efficient solution for EV routing that accounts for the unique physical constraints of battery-powered vehicles. By framing the problem as a tractable variant of CSP, the authors enable the development of navigation systems that prioritize energy efficiency. The study concludes by suggesting future research directions, including the development of tailored heuristics, the incorporation of stochastic models to assess the risk of running out of energy, and the extension of the framework to manage fleets of EVs in car-sharing scenarios.

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