Enabling E-Mobility: Facility Location for Battery Loading Stations

Sabine Storandt, Stefan FunkeAAAI 2013 · DOI

Abstract

The transition to electric mobility (E-mobility) is significantly hindered by the limited cruising range of electric vehicles (EVs), a phenomenon known as "range anxiety." This paper investigates the optimal placement of battery loading stations (LSs) to ensure comprehensive network coverage. We define two primary objectives: EV-Reachability Cover (ERC), ensuring every node is reachable from a starting point, and EV-Connectivity Cover (ECC), ensuring round-trip feasibility between any two points. Despite the theoretical NP-hardness of these problems, we demonstrate that heuristic approaches can achieve near-optimal station layouts on large-scale road networks.

Problem Formulation

Optimizing EV charging infrastructure differs from standard facility location problems due to two critical factors:

  1. Energy Recuperation: Topographical variations allow EVs to regain energy during downhill segments, resulting in "negative" edge costs.
  2. Battery Constraints: State-of-charge must remain within the $[0, M]$ interval, where $M$ is the battery capacity. You cannot charge beyond 100%, nor can you drop below 0%.

We model the road network as a directed graph $G=(V, E)$ where edge weights represent energy consumption. A Reachability Graph is constructed where a direct edge exists between two nodes if an EV can travel between them on a single charge.

Methodology

The paper proves that ERC is equivalent to the Strongly Connected Dominating Set (SCDS) problem, which implies it is NP-hard and cannot be approximated better than a logarithmic factor ($\ln n$). ECC is even more complex, relating to the Set Cover by Pairs (SCP) problem, making it significantly harder to optimize than ERC.

To address these challenges, we employ a two-phase heuristic:

  • Greedy Selection: Strategies such as "Restricted Random" (RR) and "k-Greedy" (kG) are used to establish initial "weak" coverage (ensuring one can get to a destination).
  • MST Lifting: To ensure strong connectivity (ECC), the selected stations are treated as nodes in a secondary graph. Minimum Spanning Trees (MSTs) identify necessary "bridge" stations to connect isolated components, ensuring drivers can return to their starting points.

Experimental Evaluation

The proposed algorithms were evaluated using the road network of Germany, derived from OpenStreetMap data. The dataset consists of approximately 15 million nodes and 30.7 million edges. Elevation data from the Shuttle Radar Topography Mission (SRTM) was integrated to accurately calculate energy consumption and recuperation based on inclines.

Visualization of the optimized loading station network across the German road infrastructure.

Results and Discussion

The heuristics were tested across various Average Cruising Ranges (ACR) from 75km to 175km. As shown in the results table, the number of required stations decreases as vehicle range increases. For instance, at a 75km range, the lower bound for stations is 105, while at 175km it drops to 14.

Quantitative results showing station requirements and optimality gaps for various cruising ranges.

Key findings include:

  • Connectivity vs. Reachability: Achieving round-trip connectivity (ECC) is significantly more resource-intensive than simple reachability (ERC). For a 100km range, the heuristic found that 96 stations were needed for reachability, while 379 stations were required for full connectivity.
  • Optimality Gap: The solutions remain within a factor of ~3 of the lower bound for ERC and ~8 for ECC, which are remarkably tight results for a country-sized network. Because global optimality is hard to prove, the authors use instance-based lower bounds (Partial EV-Cover) to demonstrate the efficacy of their heuristics on the specific map of Germany.
  • Computational Trade-offs: The k-Greedy approach reduces station count by approximately 10% compared to random selection but increases computation time significantly (e.g., from 30 minutes to 9.5 hours).

Conclusion and Future Work

This study provides a robust framework for large-scale EV infrastructure planning, demonstrating that near-optimal coverage is achievable even for complex, energy-constrained routing. Future research should address station capacity and queuing models, heterogeneous battery capacities across vehicle fleets, and real-world land-use or power grid constraints.

Summary updated

BibTeX
@inproceedings{storandt2013enabling,
  author = {Sabine Storandt and Stefan Funke},
  title = {{Enabling E-Mobility: Facility Location for Battery Loading Stations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  doi = {10.1609/aaai.v27i1.8478},
}
Figure