Benders decomposition for the charging station location-routing problem under stochastic energy consumption: a two-stage model with a space-electricity network perspective

The growing adoption of electric vehicles (EV) under green development goals is challenged by limited driving range, insufficient charging infrastructure, and energy consumption uncertainty in real-world traffic. Existing location models often overlook key EV-specific behaviors, including the joint optimization of vehicle routing with residential travel demand, stochastic energy consumption, repeated and partial charging, and endogenous initial state of charge (SOC). To address these gaps, this study proposes a novel two-stage stochastic integer linear programming location-routing model embedded in a tailored space-electricity (SE) network framework, capturing realistic EV operations under scenario-based uncertainty. The model jointly optimizes charging station locations and vehicle routing while accommodating nonlinear battery discharge behavior and shortest-path deviations. A tailored branch-and-Benders-cut (B&BC) algorithm is developed, integrating multi-cut and stabilizing Benders decomposition procedures to enhance computational efficiency. The problem is decomposed into a facility location master problem and multiple scenario-coupled shortest-path subproblems, enabling efficient cut generation throughout the branch-and-bound process. Numerical experiments on a 6-node toy network, the Sioux Falls network, and a real-world Shanxi Province expressway network demonstrate that the proposed method achieves computation time reductions of 66.5%–88.9% compared to classical Benders decomposition. Sensitivity analyses on battery capacity and routing deviations provide actionable insights for infrastructure planning under uncertainty.