刘旺盛，吴球军，严浩洲，敬添俊

(1.集美大学现代物流研究中心，福建 厦门 361021；2.荆门职业学院机电与信息工程学院，湖北 荆门 448000)

0 引言

快餐外卖在生活中扮演着越来越重要的角色，已成为餐饮行业发展的新生力量。经历过萌芽期、发展期、扩张期之后，快餐行业正在迈入一个较为稳定的阶段，即成熟阶段，各企业间的竞争已开始向提高服务质量，以及降低配送成本方向转变，越来越多的外卖行业开始着眼于配送服务与客户满意方面的优化[1]。顾客除了关注与外卖产品本身品质与口味以外，更加注重时效问题，也就是配送时效，很多企业为了抢占市场，提出了一定时间范围内送达的服务承诺。时效通常是依据顾客的预定时间与顾客心理预期综合设定的。送达的时间延迟越严重，该次配送服务的顾客满意度就会越低。因此，商家希望能寻找到较优的配送路线，实现总耗时或路程最短。由此可见，外卖配送中的车辆路径问题(vehicle routing problem,VRP)属于带时间窗的车辆路径问题。

车辆路径问题(vehicle routing problem,VRP)由Dantzig和Ramser[2]首次提出，在实际中应用广泛，关键参数不确定和需求有服务时间窗这两种情况研究得最多。

不确定参数下的VRP,研究方向主要集中于两类：一类是仅概率分布已知或关键参数未知的随机VRP，最常见的是顾客需求是随机的，Tillman等[3-6]对此类问题进行了研究，提出了一些模型和求解算法。另一类是关键参数与时间相关的动态车辆路径问题(dynamic vehicle routing problem,DVRP)，最常见的是顾客需求是随时间动态变化的，Hvattum[7]等吸收了随机信息，发现可以改进求解质量；……