Contextual Stochastic Vehicle Routing with Time Windows

We study the vehicle-routing problem with time windows (VRPTW) and stochastic travel times, in which the decision-maker observes related contextual information, represented as feature variables, before making routing decisions. Despite the extensive literature on stochastic VRPs, the integration of feature variables has received limited attention in this context. We introduce the conditional stochastic VRPTW, which minimizes the total transportation cost and expected late arrival penalties conditioned on the observed features. Because the joint distribution of travel times and features is unknown, we present novel data-driven prescriptive models that use historical data to provide an approximate solution to the problem. We distinguish the prescriptive models between point-based approximation, sample average approximation, and penalty-based approximation, each taking a different perspective on dealing with stochastic travel times and features. We develop specialized branch-price-and-cut algorithms to solve these data-driven prescriptive models. In our computational experiments, we compare the out-of-sample cost performance of different methods on instances with up to 100 customers. Our results show that, surprisingly, a feature-dependent sample average approximation outperforms existing and novel methods in most settings.

History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms-Discrete.

Funding: This work was supported by Deutsche Forschungsgemeinschaft [GRK2201/277991500] and by Calcul Québec (calculquebec.ca) and the Digital Research Alliance of Canada (alliancecan.ca).

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1189) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2025.1189). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.