Using activity patterns to place electric vehicle charging stations in Urban regions

There is growing interest in the adoption of electric vehicles (EVs) in urban regions. However, because of the limited battery range, the EV charging station infrastructure needs to be significantly expanded. We introduce EVChargingStation, the problem of optimizing charging stations so that each EV can be charged at a location within a certain service distance. Our formulation explicitly incorporates urban activity patterns, and considers multiple types of charging stations. We show that EVChargingStation is NP-hard, in general, and present approximation algorithms with provable performance guarantees. We evaluate one of our algorithms using a detailed urban activity model for the city of Portland, OR. Our results show a tradeoff between the number of charging stations and the maximum service distance, thus providing a systematic methodology for urban planners to evaluate policies for increasing EV deployment. We also show that considering such activity patterns is necessary, in the sense that deploying charging stations at 'high traffic' locations can lead to significantly worse solutions.