Exact two-stage stochastic programming for electric vehicle routing with time windows

Abstract

Electric vehicle routing models are typically deterministic. However, stochastic vehicle routing models rarely include a battery constraint. This study addresses that gap with a two-stage stochastic mixed-integer programme for electric vehicle routing with time windows, in which routing, load, and load-dependent energy are first-stage decisions and travel-time-driven lateness is a second-stage recourse. Load and battery charge are proved scenario-invariant given any fixed route, collapsing the recourse to a timing sub-problem and yielding an exact multi-cut Benders decomposition with finite-convergence and complexity results. The formulation was implemented and solved with an open-source solver; this process identified and corrected three formulation defects, each documented. On Solomon-benchmark instances scaling from 3 to 20 customers, the implementation reproduces an independent hand calculation exactly, remains solver-certified optimal throughout, and shows empirical solve time scaling approximately with the square of the decision variable count (R²=0.99). This study also reports a value-of-the-stochastic-solution analysis, a battery-capacity threshold effect, and a robustness finding: time-window width, not spatial distribution, drives resilience to travel-time uncertainty. Scope limitations are stated explicitly, with full-scale benchmarking left as future work.