Optimal and efficient planning of charging stations for electric vehicles in urban areas: formulation, complexity and solutions

The deployment of charging infrastructure for electric vehicles is crucial in extending their range. Many studies on the charging infrastructure deployment adopt the Mixed Integer Linear Programming (MILP) method to optimize various objectives. However, as the number of integer variables and constraints increases, the computational time and memory requirements of MILP models increase exponentially. This makes it impractical to use MILP models to solve large-scale optimization problems. In this paper, we formulate and prove that the Planning of Electric Vehicle Charging Stations (PEVCS) is an NP-complete combinatorial optimization problem. We also prove that PEVCS has a significant effect, that is, submodularity. Additionally, we propose two efficient methods that use submodularity to improve the conventional methodology for PEVCS. Furthermore, we provide a provable guarantee for the performance of our proposed methods. Our experimental results demonstrate the efficiency and effectiveness of these methods on small-scale and large-scale datasets, especially in realistic large-scale situations.