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/ .