Data-driven stochastic vehicle routing problems with deadlines

, et

référence BibTeX

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 study a data-driven stochastic VRP with deadlines and endogenous uncertainty. We use the non-parametric 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. In our case study, we show that incorporating routing decisions in a non-parametric 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, 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.

, 28 pages

Axes de recherche

Application de recherche


G2422.pdf (860 Ko)