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.
Bibliographical noteFunding Information:
This work is jointly supported by the National Natural Science Foundation of China (No. 52078212 ), the State Key Laboratory of Simulation and Regulation of Water Cycle in River Basin, and China Institute of Water Resources and Hydropower Research, China (No. IWHR-SKL-202003 ).
- Charging station planning
- Combinatorial optimization
- Electric vehicle
- Mixed Integer Linear Programming