A Stochastic Dual Dynamic Programming Approach for Fixed-Route Electric Vehicle Charging under Congestion Uncertainty

Abstract

Deploying heavy-duty electric trucks under real-world uncertainty is operationally challenging, particularly when multiple vehicles compete for limited public charging resources and face uncertain wait times. This research studies the Fixed-Route Vehicle Charging Problem and formulates it as a multistage stochastic program under charging congestion uncertainty. The delivery system is modeled as a discrete-event process triggered by physical route milestones, and charging congestion uncertainty is represented by a Markovian transition. To address the resulting mixed-integer structure, we apply stochastic dual dynamic programming (SDDP) as a tactical planning approach, while accommodating discrete vehicle dynamics within the convexity requirements. Computational experiments on a California logistics network showed that the proposed approach performed effectively across multiple geographically diverse delivery routes. Compared to a multistage stochastic integer programming benchmark, SDDP achieved a competitive solution quality while reducing training time as the number of route instances increased. Out-of-sample simulations further demonstrated that policies derived from SDDP remained robust under distributional shifts toward more congested scenarios. Overall, this study establishes SDDP as a tractable and scalable framework for generating high-quality operational policies for heavy-duty electric fleets under congestion uncertainty.