Contextual Stochastic Vehicle Routing with Time Windows by Breno Serrano, Alexandre M. Florio, Stefan Minner, Maximilian Schiffer, and Thibaut Vidal has now been published in the INFORMS Journal on Computing; the paper studies the vehicle-routing problem with time windows (VRPTW) under stochastic travel times, where the decision-maker observes related contextual information — represented as feature variables — before committing to a route. The authors introduce the conditional stochastic VRPTW, which minimizes total transportation cost together with expected late-arrival penalties conditioned on the observed features. Because the joint distribution of travel times and features is unknown, they develop data-driven prescriptive models that learn from historical data, distinguishing point-based approximation, sample average approximation, and penalty-based approximation as three perspectives on handling stochastic travel times and features. To solve these models, the paper proposes specialized branch-price-and-cut algorithms and evaluates out-of-sample cost performance on instances with up to 100 customers. A key — and somewhat surprising — finding is that a feature-dependent sample average approximation outperforms both existing and newly proposed methods in most settings.
Read the full paper: doi.org/10.1287/ijoc.2025.1189