A Benders Dual Decomposition Approach to Fast-Charging Station Planning Problem

This paper investigates the planning of fast-charging stations when charging demands are highly uncertain. To address this issue, a stochastic programming (SP) model is formulated. Since handling continuous probability distributions is computationally difficult, the sample average approximation (SAA) method is applied. By using SAA, the original stochastic model is converted into a deterministic mixed-integer linear programming (MILP) format. However, directly solving this MILP can be very time-consuming for large-scale networks. Therefore, we design a Benders dual decomposition (BDD) approach. This algorithm improves the traditional Benders decomposition by using Lagrangian relaxation to generate tighter bounds. In our method, the master variables are transferred to the subproblem and subsequently priced in the objective function. We test our model on a 25-node network and the California state road network. The results show that, in comparison with direct exact solvers, the proposed BDD method markedly reduces computational time and iteration counts.