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).
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.
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