Data-Driven Stochastic Vehicle Routing Problems with Deadlines Under Decision-Dependent Travel Time

Problem definition: Vehicle routing problems (VRPs) with deadlines have received significant attention around the world. Motivated by a real-world food delivery problem, we assume that the travel time depends on the routing decisions, and we study a data-driven stochastic VRP with deadlines and endogenous uncertainty. Methodology/results: We use the nonparametric approaches, including k-nearest neighbor (kNN) and kernel density estimation (KDE), to estimate the decision-dependent probability distribution of travel time. To solve the resulting problem efficiently, we employ a logic-based Benders decomposition (LBBD) algorithm with several algorithmic enhancements. In particular, we propose a novel family of optimality cuts that includes the expected delay for all the subroutes. Moreover, we solve a total travel cost minimization problem to warm start the algorithm. We also use a local search procedure to improve the current routing decision and propose a machine learning–based lower bound heuristic to efficiently solve problems of realistic size. A practical case study for a food delivery routing problem using real-world data is conducted to show the efficiency of the proposed techniques and the advantage of the data-driven stochastic VRP in reducing the expected delay. Managerial implications: In our case study, we show that incorporating routing decisions into a nonparametric model outperforms a state-of-the-art data-driven parametric model by 23% on average in terms of the expected delay and the order-assignment decisions obtained from a robust model with travel-time predictors by 26% on average. Moreover, compared with the drivers’ actual routes and arc-based VRP models that ignore the endogenous uncertainty, our suggested routes can significantly improve the on-time performance of delivery services. We also quantify the value of the proposed routes with different service deadlines. Funding: S. Wang was partially supported by the Natural Sciences and Engineering Research Council of Canada Grant RGPIN-2016-05208, IVADO, and a joint project between the Fonds de Recherche du Québec - Société et Culture (FRQSC) and the National Natural Science Foundation of China (NSFC) Grant 295837. She is also most recently supported by the National Natural Science Foundation of China Grants 72501014, 72371022, and 72272014. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2024.0899 .