Optimal Electric Vehicle Charging Station Placement

Yanhai Xiong, Jiarui Gan, Bo An, Chunyan Miao, Ana L. C. Bazzan

Introduction

As urban centers transition toward electric vehicle (EV) adoption, the strategic placement of charging infrastructure presents a complex logistical challenge. Traditional models often focus on minimizing construction costs or maximizing geographic coverage, yet they frequently overlook the dynamic interplay between infrastructure and driver behavior. This research, originally presented at IJCAI 2015, addresses the "chicken and egg" problem of EV infrastructure by accounting for the strategic, "selfish" behavior of drivers and the resulting impact on city-wide traffic congestion and queuing times.

Methodology: The OCEAN Algorithm

The researchers model the placement problem as a bilevel optimization program. At the upper level, the government or planning authority determines the allocation of a fixed budget of chargers across city zones to minimize total "social cost"—defined as the sum of all travel and queuing times. At the lower level, drivers engage in a "congestion game," choosing charging locations (either in their home zone or adjacent ones) to minimize their personal costs.

Solving such bilevel problems is computationally intensive because the lower-level equilibrium must be recalculated for every potential upper-level decision. To overcome this, the authors introduced OCEAN (Optimizing eleCtric vEhicle chArging sta tioN placement). The algorithm leverages a mathematical property termed Simple Deviation: if a driver cannot reduce their cost by shifting a small amount of strategy probability, they cannot improve their cost through any complex strategy. This insight allows the transformation of the complex game-theoretical problem into a solvable single-level non-linear program.

To further enhance scalability, the authors developed OCEAN-C, which utilizes continuous relaxation—treating the number of chargers as a decimal during initial computation—before rounding to a final integer solution. This significantly accelerates the optimization process without compromising solution quality.

Experimental Evaluation

The model was evaluated using real-world data from Singapore, a high-density urban environment where "queue anxiety" often outweighs "range anxiety." The study utilized a 23-zone partition of the city, incorporating traffic and demographic data from the Land Transport Authority (LTA) and the Department of Statistics (DOS).

Zonal partitioning of Singapore used for the case study.

The simulation assumed a 5% EV adoption rate, with 10% of those vehicles requiring public charging during peak hours. Distances between zones were calculated using Google Maps to ensure geographic accuracy.

Results and Analysis

The experimental results demonstrate that OCEAN-C consistently outperforms traditional placement benchmarks, including demand-based (placing chargers where EV owners live), traffic-based (placing chargers in low-congestion areas), and uniform distribution methods.

Performance evaluation of OCEAN and OCEAN-C across runtime, social cost, budget, and robustness metrics.

Key findings include:

  • Computational Efficiency: OCEAN-C achieved the same solution quality as the exact OCEAN algorithm but with a significantly lower runtime, proving its viability for large-scale urban planning.
  • Social Cost Reduction: By accounting for queuing as a traffic factor, the model successfully identified placements that prevent charging stations from becoming bottlenecks that ripple through the road network.
  • Robustness: The model remained effective even when assuming "irrational" driver behavior (deviations of up to 10% from the optimal strategy), suggesting it is resilient to real-world unpredictability.

Conclusion

This research provides a practical framework for urban planners to optimize EV infrastructure. By treating charging stations not just as destinations but as potential sources of congestion, the OCEAN algorithm offers a sophisticated tool for minimizing the social costs of the green energy transition. Future work may involve expanding the model to accommodate megacities with hundreds of zones and integrating real-time variables such as fluctuating electricity pricing.

Summary updated

Abstract

Many countries like Singapore are planning to introduce Electric Vehicles (EVs) to replace traditional vehicles to reduce air pollution and improve energy efficiency. The rapid development of EVs calls for efficient deployment of charging stations both for the convenience of EVs and maintaining the efficiency of the road network. Unfortunately, existing work makes unrealistic assumption on EV drivers' charging behaviors and focus on the limited mobility of EVs. This paper studies the Charging Station PLacement (CSPL) problem, and takes into consideration 1) EV drivers' strategic behaviors to minimize their charging cost, and 2) the mutual impact of EV drivers' strategies on the traffic conditions of the road network and service quality of charging stations. We first formulate the CSPL problem as a bilevel optimization problem, which is subsequently converted to a single-level optimization problem by exploiting structures of the EV charging game. Properties of CSPL problem are analyzed and an algorithm called OCEAN is proposed to compute the optimal allocation of charging stations. We further propose a heuristic algorithm OCEAN-C to speed up OCEAN. Experimental results show that the proposed algorithms significantly outperform baseline methods.
BibTeX
@inproceedings{xiong2015optimal,
  author = {Yanhai Xiong and Jiarui Gan and Bo An and Chunyan Miao and Ana L. C. Bazzan},
  title = {{Optimal Electric Vehicle Charging Station Placement}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure