Demand Prediction and Placement Optimization for Electric Vehicle Charging Stations

Ragavendran Gopalakrishnan, Arpita Biswas, Alefiya Lightwala, Skanda Vasudevan, Partha Dutta, Abhishek TripathiIJCAI 2016 · OpenReview

Introduction

The transition to Electric Vehicles (EVs) faces a classic "chicken and egg" dilemma: consumers are hesitant to adopt EVs without a robust charging infrastructure, while operators are reluctant to build stations without guaranteed high demand. This deadlock often results in "charging deserts" outside of high-traffic city centers, exacerbating range anxiety for potential buyers. To address this, urban planners require tools that can both predict demand in data-sparse areas and optimize station placement to balance provider profitability with user accessibility.

Methodology

Demand Prediction: Multiple Dependent Regression (MDR)

Predicting demand at potential new sites is challenging because historical data is often non-existent. The authors propose a Multiple Dependent Regression (MDR) framework based on multi-view learning. Instead of simple linear regression, MDR utilizes Canonical Correlation Analysis (CCA) to model the relationship between charging demand and three distinct external "views":

  • Points of Interest (PoI): Proximity to amenities like malls, hospitals, and schools.
  • Traffic Density: Activity levels at nearby road junctions.
  • Neighboring Usage: Historical demand patterns at existing nearby stations.

By training separate models for each view and ensembling them, MDR captures complex dependencies that standard feature concatenation misses.

Placement Optimization: Iterative Pack And Cover (IPAC)

The placement problem is framed as a Mixed-Packing-and-Covering (MPC) optimization. The goal is to maximize total demand satisfied (Packing) while ensuring every location of interest is within a specific driving radius $r$ of a charger (Covering).

To incorporate user experience, the authors use $M/M/N_i$ queueing theory to calculate the number of charging slots required to keep wait times under 5 minutes. This requirement is converted into a capital cost, making user convenience a hard budget constraint. To solve this NP-hard problem efficiently, the authors developed the Iterative Pack And Cover (IPAC) heuristic, which dynamically reallocates budget between coverage and demand maximization.

Experimental Results

Prediction Accuracy

The MDR framework significantly outperformed baseline models. By treating different data sources as independent views, the model achieved a 27% reduction in Root Mean Square Error (RMSE) compared to simple linear regression and an 18% improvement over Bayesian CCA.

Figure 1: RMSE of demand prediction across different hours of the day, comparing MDR with baseline models. MDR consistently achieves the lowest error.

Optimization Performance

While an Integer Linear Program (ILP) can find an exact optimal solution, it is computationally expensive, taking nearly 30 hours for a single instance. In contrast, the IPAC heuristic provides a near-optimal solution in less than 0.5 seconds. As shown in the performance analysis, IPAC consistently captures approximately 90% or more of the optimal demand satisfaction across various coverage radii.

Figure 3: Performance of the IPAC heuristic relative to the optimal ILP solution. IPAC achieves near-optimal results (approaching 1.0) far more efficiently than naive approaches.

Furthermore, IPAC demonstrated a 10–15% improvement in demand satisfaction over a naive heuristic that prioritizes coverage first and spends remaining funds on demand. The system also proved robust against "noise" in land and setup costs, maintaining its performance edge even with fluctuating real-world data.

Conclusion

This research provides a scalable, data-driven pipeline for EV infrastructure planning. By combining multi-view demand prediction with an efficient optimization heuristic, the framework allows planners to design networks that are both economically viable for operators and geographically accessible for drivers. Future work may involve integrating demand prediction directly into the optimization loop to account for how new stations might influence future urban traffic and charging patterns.

Summary updated

Abstract

Effective placement of charging stations plays a key role in Electric Vehicle (EV) adoption. In the placement problem, given a set of candidate sites, an optimal subset needs to be selected with respect to the concerns of both (a) the charging station service provider, such as the demand at the candidate sites and the budget for deployment, and (b) the EV user, such as charging station reachability and short waiting times at the station. This work addresses these concerns, making the following three novel contributions: (i) a supervised multi-view learning framework using Canonical Correlation Analysis (CCA) for demand prediction at candidate sites, using multiple datasets such as points of interest information, traffic density, and the historical usage at existing charging stations; (ii) a mixed-packing-and-covering optimization framework that models competing concerns of the service provider and EV users; (iii) an iterative heuristic to solve these problems by alternately invoking knapsack and set cover algorithms. The performance of the demand prediction model and the placement optimization heuristic are evaluated using real world data.
BibTeX
@inproceedings{gopalakrishnan2016demand,
  author = {Ragavendran Gopalakrishnan and Arpita Biswas and Alefiya Lightwala and Skanda Vasudevan and Partha Dutta and Abhishek Tripathi},
  title = {{Demand Prediction and Placement Optimization for Electric Vehicle Charging Stations}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
  url = {https://openreview.net/forum?id=H1WJ1QMdZr},
}
Figure