GPU-based Split algorithm for Large-Scale CVRPSD

Stochastic combinatorial optimization problems, such as the Capacitated Vehicle Routing Problem with Stochastic Demands (CVRPSD), remain notoriously challenging due to the high computational cost of evaluating second-stage recourse actions across large scenario sets. Traditional approaches typically rely on limited samples, leading to biased cost estimation and brittle first-stage policies. In this work, we introduce a GPU-accelerated framework for ultra-large-scale scenario-based evaluation in stochastic combinatorial optimization. At its core is a dynamic programming–based split algorithm reformulated to exploit two-dimensional GPU parallelism across both demand scenarios and transition states. This design enables simultaneous evaluation of tens or even hundreds of thousands of scenarios, a scale previously unattainable in practice. Integrated into a meta-heuristic framework, our method achieves orders-of-magnitude speedups over CPU-based multi-threading while producing more robust out-of-sample solutions. Beyond vehicle routing, our approach provides a general-purpose tool for scalable GPU-accelerated stochastic optimization under data-driven uncertainty.