Multi-Stage Stochastic Programming for Heavy-Duty Electric Truck Routing Under Public Charging Congestion Uncertainty

This study explores multi-stage stochastic optimization frameworks for routing heavy-duty electric trucks making long-haul deliveries, while dealing with uncertainty in public charging station congestion. We examine a multi-stage problem in which multiple vehicles share limited charging resources in a dynamic environment. Each decision stage corresponds to a distinct routing event, such as the arrival at a delivery location, with congestion levels at public charging stations progressively revealed. The key state variable is the vehicle’s position, represented as integer indices based on predefined route sequences. These route sequences introduce global constraints that must be reconciled with the stage-wise independence assumption.To solve this integer-state problem, we compare two decomposition algorithms: Stochastic Dual Dynamic integer Programming (SDDiP) using strengthened Benders’ cuts and Stochastic Dual Dynamic Programming (SDDP) using piecewise linear Bellman cuts. Computational experiments are conducted on a realistic mid-mile transportation network in California, featuring up to 15 vehicles, 169 delivery nodes and 25 public charging stations. We evaluate computational time, convergence behavior and policy performance across varying network scales. On a 5-vehicle instance, our results show that SDDP reduces runtime per iteration by up to 17.22% compared with SDDiP solver and delivers policy within a 2.90% convergence gap. We conclude with practical insights regarding the scalability and stability of the linear programming relaxation (LP-relaxation) cuts versus integer-state cuts in large-scale Electric Vehicle Routing Problem (EVRP) applications.