In this paper, we study a data-driven stochastic vehicle routing problem (VRP) with deadlines and endogenous uncertainty, where the travel time depends on the routing decisions, which is motivated by a real-world food delivery problem. We use the non-parametric approaches, including k-nearest neighbor (kNN) and kernel density estimation, to estimate the decision-dependent probability distribution of travel time. In order 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. The results show that our proposed algorithm significantly outperforms the default LBBD and a genetic algorithm heuristic. Under the kNN method, the data-driven stochastic VRP can significantly reduce the out-of-sample expected delay when compared to a state-of-the-art data-driven parametric approach.
Article
View Data-driven Stochastic Vehicle Routing Problems with Deadline Assignment