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.
- Open Access
- Article
A Benders Dual Decomposition Approach to Fast-Charging Station Planning Problem
Author Information
Received: 31 Dec 2025 | Revised: 31 Mar 2026 | Accepted: 07 Apr 2026 | Published: 21 Apr 2026
Abstract
Keywords
fast-charging station planning | Benders dual decomposition | sample average approximation | uncertain charging demand
References
- 1.
International Energy Agency. In Global Electric Vehicle Outlook 2022; International Energy Agency: Paris, France , 2022.
- 2.
Singh, V.; Singh, V.; Vaibhav, S. A Review and Simple Meta-Analysis of Factors Influencing Adoption of Electric Vehicles. Transp. Res. Part D Transp. Environ. 2020, 86, 102436.
- 3.
Liu, Y.; Zhao, X.; Lu, D.; et al. Impact of Policy Incentives on the Adoption of Electric Vehicle in China. Transp. Res. Part A Policy Pract. 2023, 176, 103801.
- 4.
Arias, M.B.; Kim, M.; Bae, S. Prediction of Electric Vehicle Charging-Power Demand in Realistic Urban Traffic Networks. Appl. Energy 2017, 195, 738–753.
- 5.
Zhang, H.; Yang, K.; Gao, Y.; et al. Accelerating Benders Decomposition for Stochastic Incomplete Multimodal Hub Location Problem in Many-to-Many Transportation and Distribution Systems. Int. J. Prod. Econ. 2022, 248, 108493.
- 6.
Ullah, I.; Liu, K.; Yamamoto, T.; et al. Modeling of Machine Learning with SHAP Approach for Electric Vehicle Charging Station Choice Behavior Prediction. Travel Behav. Soc. 2023, 31, 78–92.
- 7.
Orzechowski, A.; Lugosch, L.; Shu, H.; et al. A Data-Driven Framework for Medium-Term Electric Vehicle Charging Demand Forecasting. Energy AI 2023, 14, 100267.
- 8.
Wu, F.; Sioshansi, R. A Stochastic Flow-CapturingModel to Optimize the Location of Fast-Charging Stations with Uncertain Electric Vehicle Flows. Transp. Res. Part D Transp. Environ. 2017, 53, 354–376.
- 9.
Taherkhani, G.; Alumur, S.A.; Hosseini, M. Robust Stochastic Models for Profit-Maximizing Hub Location Problems. Transp. Sci. 2021, 55, 1322–1350.
- 10.
Kim, J.; Oh, H.; Lee, J. Data-Driven Cost-Effective Capacity Provisioning Scheme in Electric Vehicle Charging Facility. Comput. Ind. Eng. 2022, 173, 108743.
- 11.
Contreras, I.; Cordeau, J.F.; Laporte, G. Stochastic Uncapacitated Hub Location. Eur. J. Oper. Res. 2011, 212, 518–528.
- 12.
Liu, X.; Liu, X.; Zhang, X.; et al. Optimal Location Planning of Electric Bus Charging Stations with Integrated Photovoltaic and Energy Storage System. Comput.-Aided Civ. Infrastruct. Eng. 2023, 38, 1424–1446.
- 13.
Bai, M.; Yan, P.; Chen, Z.; et al. Two-Stage Approximation Allocation Approach for Real-Time Parking Reservations Considering Stochastic Requests and Reusable Resources. Adv. Eng. Inform. 2024, 59, 102251.
- 14.
Wang, M.; Jiang, H.; Li, Y.; et al. Location Determination of Hierarchical Service Facilities Using a Multi-Layered Greedy Heuristic Approach. Eng. Optim. 2023, 55, 1422–1436.
- 15.
Zhang, H.; Moura, S.J.; Hu, Z.; et al. A Second-Order Cone Programming Model for Planning PEV Fast-Charging Stations. IEEE Trans. Power Syst. 2018, 33, 2763–2777.
- 16.
Muffak, A.; Arslan, O. A Benders Decomposition Algorithm for the Maximum Availability Service Facility Location Problem. Comput. Oper. Res. 2023, 149, 106030.
- 17.
Oliveira, F.A.; de S´a, E.M.; de Souza, S.R. Benders Decomposition Applied to Profit Maximizing Hub Location Problem with Incomplete Hub Network. Comput. Oper. Res. 2022, 142, 105715.
- 18.
Zhang, H.; Moura, S.J.; Hu, Z.; et al. Joint PEV Charging Network and Distributed PV Generation Planning Based on Accelerated Generalized Benders Decomposition. IEEE Trans. Transp. Electrif. 2018, 4, 789–803.
- 19.
Lee, C.; Han, J. Benders-and-Price Approach for Electric Vehicle Charging Station Location Problem Under Probabilistic Travel Range. Transp. Res. Part B Methodol. 2017, 106, 130–152.
- 20.
Furugi, A. Sequence-Dependent Time- and Cost-Oriented Assembly Line Balancing Problems: A Combinatorial Benders’ Decomposition Approach. Eng. Optim. 2022, 54, 170–184.
- 21.
Li, Y.; Yu, G.; Zhang, J. A Three-Stage Stochastic Model for Emergency Relief Planning Considering Secondary Disasters. Eng. Optim. 2021, 53, 551–575.
- 22.
Chen, S.; Zeng, Q. Carbon-Efficient Scheduling Problem of Electric Rubber-Tyred Gantry Cranes in a Container Terminal. Eng. Optim. 2022, 54, 2034–2052.
- 23.
Guo, P.; He, X.; Luan, Y.; et al. Logic-Based Benders Decomposition for Gantry Crane Scheduling with Transferring Position Constraints in a Rail-Road Container Terminal. Eng. Optim. 2021, 53, 86–106.
- 24.
Hamzadayı, A. An Effective Benders Decomposition Algorithm for Solving the Distributed Permutation Flowshop Scheduling Problem. Comput. Oper. Res. 2020, 123, 105006.
- 25.
Rahmaniani, R.; Ahmed, S.; Crainic, T.G.; et al. The Benders Dual Decomposition Method. Oper. Res. 2020, 68, 878–895.
- 26.
MirHassani, S.A.; Ebrazi, R. A Flexible Reformulation of the Refueling Station Location Problem. Transp. Sci. 2013, 47, 617–628.
This work is licensed under a Creative Commons Attribution 4.0 International License.
Suite 4002 Level 4, 447 Collins Street, Melbourne, Victoria 3000, Australia
General Inquiries: info@sciltp.com