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

(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]等吸收了随机信息，发现可以改进求解质量；李兵等[8]对于集货过程中随时有客户提出服务请求，或客户地址发生变化的DVRP，通过引入虚拟任务点将其转化为静态VRP求解；张景玲等[9]提出了2-OPT量子进化算法求解车辆实时配送过程中又有新客户加入的问题；Azi等[10]着重探讨了多路径DVRP下新客户的服务请求接受规则，以是否盈利作为判断准则。

带时间窗的VRP研究分为软时间窗和硬时间窗两种。在软时间窗情形下，早到或者晚到是允许的，不过有惩罚成本[11-21]；但硬时间窗条件下，早到或晚到是不允许的[13]。牛群[14]针对硬时间窗条件，设计了改进型烟花算法求解；Larsen[15]首次将时间窗与车辆路径问题相结合；Ahmmed[16]等提出多重蚁群优化算法求解DVRPTW(dynamic vehicle routing problem with time window)；王万全[17]等构建了软时间窗多配送中心VRP问题的数学模型，设计了混合3-OPT量子进化算法进行求解；Hong[18]等将时间划分成长度相等的时间片，采用事件驱动机制将动态问题转化为静态问题；张文博[19]等也将动态问题转化为多个瞬时静态问题，以提升服务准时性和最小配送成本为目标，采用模拟退火算法求解；翟劲松等[20]也采用时间切片原则，将时间均匀划分，以配送时间最短为目标，运用遗传算法得出最优配送路径；李桃迎等[21]基于同时送取货VRP问题的求解策略,引入时间惩罚成本，衡量外卖配送超出时间窗的情况,引入k-means，对“商家-客户”进行聚类,同一类设计“商家-客户”遗传算法求解；李常敏等[22]基于每个顾客对服务时间感知度不同，建立了基于顾客时间满意度的车辆配送模型，并利用模拟退火算法编程求解。

从现有文献看，目前带时间窗的VRP基本是采用惩罚成本的方式，研究硬时间窗的少，且现有DVRPTW研究多是采用对时间进行均匀切片的方法转化为静态VRP求解，现实中也是采用固定时间截单的做法，这种简单以固定时长切片的方法实际上损失了很多优化机会。本文拟杜绝固定时间截单这种将动态问题简化为静态问题求解的方法，尽可能等待更多订单进来，直到有订单采用直接配送才可能满足硬时间窗要求才出发，该订单作为第一个服务客户，回程再配送其他满足硬时间窗要求的订单，避免陷入局部最优，且方案随时间推移滚动执行，实现真正意义上的“动态”求解。

1 问题及模型

1.1 问题定义

该问题可定义为：一家提供外卖配送服务的餐饮店，不断有客户下单，并要求在一定的时间范围内送达，每笔订单有一定的订购量，那么店家该如何实施配送，使所有订单在顾客要求的时间范围内送达，又使配送成本最小。

为方便问题求解，做以下简化与假设。

1)车辆行驶速度。参照实际情况，配送车辆通常为电动车或者摩托车，在模型中将行驶速度统一设置为定值，即不考虑路况等外界因素干扰。

2)外卖加工时间。外卖为主的餐饮店在实际的运营中，通常会提前备餐，加工时间较短；另一方面，当顾客订购的餐品加工需时较长时，店家会向顾客提前申明，服务时间窗会自动延长，故在此模型中不考虑备餐时间，即假设下单时餐品已加工完成。

3)配送人员充足。假设有足够的配送人员，只要系统发出配送指令，就有配送员前去执行。

4)订单交接时间。实际配送中，外卖送达客户要求的地点后，一般交接时间很短，但有时需要等待一定时间，即送达后交付时间有波动，本文采用比较低的行驶速度将这些波动考虑进来，不考虑等待时间。

5)时间精度。下单时间、要求送达时间、实际送达时间都采用向下取整，如某订单的送达时间为11点55分11秒，取11点55分；行驶时间采用向上取整，如两相邻配送客户距离相差700 m，当车速为500 m/min时，则需行驶1.4 min，此时向上取整为2 min。

1.2 模型构建

外卖店所在地和订单需求点构成一个有向图G=(V，A)，其中：V是点集，V={V0，V1，…，Vn}，V0为外卖店所在地，即配送点，其他各点均为需求点；A是各点间路线的集合，A=(i，j)i,j∈V且i≠j，线路(i，j)的距离记为dij。

每趟配送最大装载量均为q(gi≤q)，需要的总配送次数为M，配送速度为定值v，S为集合N的任意子集，|S|表示S中的元素个数。

数学模型构建如下：

2)目标函数 该模型的目的是寻找配送成本最小的配送方案，在配送过程中，成本的主要影响因素为行驶路程，所以目标函数为总的行驶路程最短

3)约束条件：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

2 不定时间截单求解算法设计

算法的目的在于寻求成本最小的配送方案，需要做出的决策包括：哪些订单安排同一趟配送；每趟的发车时间以及配送员执行配送任务的具体行走路径。

算法分两步：第一步为订单信息确认；第二步为路径规划。首先将配送时间尽量后移，直至待配送订单中有订单需要直送才不超出时间窗要求时开始规划路线，以求尽可能多地确认需求信息，避免陷入局部最优，然后采用最近插入法进行路径规划。

相关符号定义如下：

具体算法步骤如下：

5)在N中找一个离新加入配送线路Lk最近的点j，然后在Lk的配送回路中找一个弧rp(rp≠0i，因为线路Lk是在i最晚出发时间发车，若插入其他点，i的送达时间将达不到要求)，使弧的两端节点到点j的距离之和减去弧长的值，即Δ=drj+djp-drp最小，若存在这样的多个点和多条弧，则按“先下单先配送”的原则选择；

8)重复第5至第7步，直至N中所有的点均已加入Lk或确认无法加入Lk中，配送发车。

3 实例验证

采用一外卖店中午11:00—12:00的实际订单,订单数据如表1所示。

表1 某外卖店11:00—12:00时间段内订单数据

外卖点及各需求点位置分布如图1所示。其中：点0表示外卖店所在地址；1～13为客户需求点，客户1和6位置重合。

在订餐平台下单的“顾客预计等待时间”一般为30～60 min，此例取40 min，那么要求送达时间均在下单时间上往后推40 min。

配送员骑电动车，设配送速度v为500 m/min。据调查，每趟能携带的餐盒数最大为50盒，在需要满足硬时间窗的前提下，基本上很难出现达到装载上限的情况，因此本例将各点需求量忽略。

按照算法流程，该例具体求解步骤如下：

5)在N中找到离L1回路最近的需求点6，根据最近插入法寻找最近的弧插入，即(1,0)和(0,1)两段弧，两段弧插入点6后增加值均为0，按下单先后规则，订单1应先于订单6配送，故考虑插入弧(1,0)；

8)在N中找到离L1最近的需求点10，若将该点插入L1中的弧(6,0)，弧长增加值最小，为600 m；

11)多次重复算法第5-7步，L1更新为{0,1,6,5,4,10,3,9,7,8,0}，N更新为{2,11}；

12)重复执行第5步，此时N中离L1回路最近的点为2，插入弧(7,8)和(9,7)，使回路增加均为最小值3 200 m，按先下单先配送的规则，将点2插入(9,7)间；

13)判断点2和之后的点预计到达时间是否符合要求，若将点2插入弧(9,7)，回路变为{0,1,6,5,4,10,3,9,2,7,8,0}，点2预计到达时间为12:18，不符合要求，不能将点2加入L1；

14)接下来考虑点11，同理将点11插入L1，使回路增加值最小的位置也是弧(9,7)，若将点11插入此位置，点11和其后的所有需求点的预计送达时间都能满足服务时间窗要求，因此点11能插入L1，至此N中所有的点均已考虑，开始配送发车，最终子回路L1为{0,1,6,5,4,10,3,9,11,7,8,0}，最晚发车时间为11:50，当前N为{2}；

配送线路如图2所示。

表2 不定时间截单和固定时间截单结果对比

由表2看出，本文设计的不定时间截单算法远远优于实际中采用的固定时间截单算法，可以节省一趟配送人力成本，行使的总距离也远远小于固定时间截单算法。不过为了满足硬时间窗要求，配送行走总距离相对无时间窗要求下会大很多。

4 结论

本文基于硬时间窗的约束条件，对待配送订单的分配问题、配送顺序问题进行研究，建立了数学模型，并设计了不固定时间截单算法。通过与实际固定时间截单做法的比较，证明不固定时间截单可以有效降低配送人力和成本。此外，需要说明的是：首先算例数量、订单容量不够庞大，一定程度上对算法效果的验证存在一定的影响；其次，对问题做了简化处理，如假定配送员人数充足、配送速度为平均行驶速度、餐品加工时间不计等。在实际中，会出现配送人员不够的情形，每种餐品加工时间不同，不同路段和时段、不同配送员行驶速度也存在差异等情况，将来可以考虑这些实际情况和因素，进行更为深入地研究和分析。