Abstract:

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, the authors formulate and prove that the Planning of Electric Vehicle Charging Stations (PEVCS) is an NP-complete combinatorial optimization problem. The authors also prove that PEVCS has a significant effect, that is, submodularity. Additionally, this paper proposes two efficient methods that use submodularity to improve the conventional methodology for PEVCS. Furthermore, the authors provide a provable guarantee for the performance of our proposed methods. The results demonstrate the efficiency and effectiveness of these methods on small-scale and large-scale datasets, especially in realistic large-scale situations.