车辆路径问题
计算机科学
数学优化
布线(电子设计自动化)
核密度估计
参数统计
启发式
非参数统计
缩小
核(代数)
概率分布
多路径等成本路由
理论(学习稳定性)
随机优化
目的地顺序距离矢量路由
供应链管理
局部搜索(优化)
最优化问题
旅行时间
供应链
运筹学
决策问题
分解
约束(计算机辅助设计)
作者
Shanshan Wang,Erick Delage,Leandro Callegari Coelho
标识
DOI:10.1287/msom.2024.0899
摘要
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 .
科研通智能强力驱动
Strongly Powered by AbleSci AI