A New Approach for Vehicle Routing with Stochastic Demand: Combining Route Assignment with Process Flexibility

• 成果类型: Article; Early Access
• 署名作者: Ledvina, Kirby; Qin, Hanzhang; Simchi-Levi, David; Wei, Yehua
• 署名单位: Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Duke University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2304
• 发表日期: 2022
• 关键词: stochastic vehicle routing; route design; Process; probabilistic analysis

摘要

We propose a new approach for the vehicle routing problem with stochastic customer demands revealed before vehicles are dispatched. We combine ideas from vehicle routing and manufacturing process flexibility to propose overlapped routing strategies with customer sharing. We characterize the asymptotic performance of the overlapped routing strategies under probabilistic analysis while also providing an upper bound on the asymptotic performance that depends only on the mean and standard deviation of the customer demand distribution. Moreover, we show that the optimality gap of our approach decays exponentially as the size of overlapped routes increases. We demonstrate that our overlapped routing strategies perform close to the theoretical lower bound derived from the reoptimization strategy and significantly outperform the routing strategy without overlapped routes. The effectiveness of the proposed overlapped routing strategies in nonasymptotic regimes is further verified through numerical analysis.