Optimizing the deployment of electric vehicle charging stations using pervasive mobility data

With the recent advances in battery technology and the resulting decrease in the charging times, public charging stations are becoming a viable option for Electric Vehicle (EV) drivers. Concurrently, emergence and the wide-spread use of location-tracking devices in mobile phones and wearable devices has paved the way to track individual-level human movements to an unprecedented spatial and temporal grain. Motivated by these developments, we propose a novel methodology to perform data-driven optimization of EV charging station locations. We formulate the problem as a discrete optimization problem on a geographical grid, with the objective of covering the entire demand region while minimizing a measure of drivers' total excess driving distance to reach charging stations, the related energy overhead, and the number of charging stations. Since optimally solving the problem is computationally infeasible, we present computationally efficient solutions based on the genetic algorithm. We then apply the proposed methodology to optimize EV charging stations layout in the city of Boston, starting from Call Detail Records (CDR) of one million users over the span of 4 months. The results show that the genetic algorithm provides solutions that significantly reduce drivers' excess driving distance to charging stations, energy overhead, and the number of charging stations required compared to both a locally-optimized feasible solution and the current charging station deployment in the Boston metro area. We further investigate the robustness of the proposed methodology and show that building upon well-known regularity of aggregate human mobility patterns, the layout computed for demands based on the single day movements preserves its advantage also in later days and months. When collectively considered, the results presented in this paper indicate the potential of data-driven approaches for optimally placing public charging facilities at urban scale.