随着外卖市场的的繁荣,网上订餐的消费模式日益深入人心,已经成为上班族用餐的主要形式,网上订餐订单量越来越大。然而,订单配送成本一直居高不下,一个重要原因是,传统车辆调度问题通常将商户生产餐品的时间(出餐时间)作为一个确定值考虑,而实际场景中,商户的出餐时间具有很强的不确定性。车辆到达商户时,若商户未出餐,则要等待;若商户早已出餐,则餐品送达顾客时口感可能已经发生改变,均会降低顾客满意度。因此,有必要考虑出餐时间不确定的情况下,如何规划车辆配送路线的问题。本文对多商户的、商户出餐时间不确定的车辆路径问题进行研究,该问题具有以下三个特点:(1)商户出餐时间是随机变量,这具有随机车辆路径问题的特征;(2)安排车辆配送路线时要考虑商户和对应顾客的配送顺序限制,这具有带取送货的车辆路径问题的特征;(3)顾客有服务时间窗的要求,规划车辆配送路线时要保证一定的顾客满意度。本文的研究目标是规划出期望物流成本最小的配送路线,且满足相关约束条件。本文对该问题进行了详细定义和假设,建立了该问题的两阶段随机规划数学模型,并基于问题特征,设计了商户的插入策略,采用多空间采样算法(Multi-space Sampling Heuristic,MSH)对问题进行求解。本文以Solomon标准数据集算例为基础,对算例经过初步处理,进行实验。实验结果显示,MSH算法求解结果整体优于插入算法,解质量比改插入算法普遍提高了6%-9%左右。实验证明,MSH算法在求解出餐时间不确定的车辆路径问题上的可行性和有效性。