When traffic flow meets power flow: On charging station deployment with budget constraints

The lack of charging facilities has been a main obstacle to the widespread use of electric vehicles (EVs). What is worse is that existing chargers are still underutilized. Meanwhile, the grid instability caused by EV charging is becoming much more significant with increasing EV penetration. This paper studies how to size and locate charging stations in traffic networks considering grid constraints to balance the charging demand and power network stability. First, a spatiotemporal model of charging demand is proposed, and a 1-(1/e) approximation algorithm to maximize the charging demand is designed. We analytically prove that 1-(1/e) is the best bound that can be obtained in polynomial time. Then, a linearized power network model (LPNM) is proposed. Based on LPNM, a heuristic algorithm involving the grid constraints (HAG) is designed. Finally, the proposed models and algorithms are evaluated on real-world traffic networks and power networks. The relative error of the voltage deviation estimated by LPNM is about 4%. Compared with the plain demand model, adopting the spatiotemporal charging demand model improves the utilization of chargers by 5% at least. Compared with the greedy algorithm with grid constraints (GAG), HAG improves the carrying capacity of the power network by 20.7%, reduces the voltage deviation by 25%, and increases the EVs charged by 18.07%.