Benders decomposition for charging station location-routing problem with time-dependent travel times: a space-time-electricity network perspective

The urgency of carbon reduction has made electric vehicle (EV) adoption essential. Charging station planning is key to easing range anxiety and advancing green energy use. Although numerous studies examine location-routing problems on space networks, limited attention has been given to time-dependence, charging capacity constraints, or space-time models that accurately capture feasible paths. To address these gaps, we propose a mixed-integer linear programming (MILP) model for intercity electric freight transportation within a space-time-electricity network. The model integrates time-dependent travel times, station capacity limits, time windows, queuing delays, nonlinear energy consumption and heterogeneous deliveries. To improve efficiency, a branch-and-Benders-cut approach based on classical Benders decomposition is proposed, dividing the origin problem into an assignment problem (i.e., the master problem) and a minimum-cost flow problem with capacity constraints (i.e., the subproblem). The master problem is solved only once, while the subproblem dynamically provides cuts along the branching. Computational experiments on 178 instances from the Sioux Falls, inter-district road and inter-city expressway networks in real world demonstrate that the proposed method reduces computation time by 65.5 %-70.6 % compared to conventional Benders decomposition and by 11.1 %-39.5 % relative to branch-and-bound. Incorporating time-dependent dynamics reduces objective values by 9.3 %-33.1 %. Sensitivity analysis offers further insights for infrastructure development and policy-making.