带硬时间窗的O2O 生鲜外卖即时配送路径优化

余海燕 ,唐婉倩 ,吴腾宇

(1.重庆交通大学 经济与管理学院,重庆 400074；2.智能物流网络重庆市重点实验室,重庆 400074；3.重庆邮电大学 经济管理学院,重庆 400065)

受新型冠状病毒肺炎的影响以及生活水平的不断提高,人们更倾向足不出户的购买生鲜,并对生鲜的品质和配送效率越来越关注,这对生鲜企业在如何平衡生鲜品质和配送效率方面提出了更高的配送管理要求。但目前生鲜企业仍然存在配送效率不高,配送距离过长等问题,严重影响生鲜的品质,因此,如何保证在既定时间内送达的同时降低即时配送的成本是值得研究的现实问题。

线上线下(Online To Offline,O2O)生鲜外卖即时配送的一般过程可以描述为：客户在盒马鲜生、京东生鲜等外卖平台下单,平台接收订单后,系统将会根据客户的时间窗、配送员位置及送货地点,分配订单给相应的配送员,配送员有车容量限制并且需要在每个客户的最晚送达时间内送达,在配送员服务完他所需服务的客户后返回配送中心。在上述过程中,需求订单实时产生,每个订单有相应的硬时间窗,平台只有在该需求订单出现时才获知该订单的信息,而平台需要根据实时的订单信息进行车辆调度和路径规划,保证在最晚送达时间内送达。考虑到需求订单实时产生、配送员位置分散、客户具有不同时间窗且必须在最晚时间内送达等特点,研究以配送距离最短为目标的O2O 生鲜外卖即时配送路径优化问题。

与带硬时间窗的O2O 生鲜外卖即时配送路径优化问题相关的文献包括带取送货的动态车辆路径问题(Dynamic Vehicle Routing Problem with Pickup and Delivery,DVRPPD)和带时间窗的车辆路径问题(Vehicle Routing Problem with Time Window,VRPTW)。

带取送货的车辆路径问题(Vehicle Routing Problem with Pickup and Delivery,VRPPD)是在车辆路径问题(VRP)中加入取送货作业,属于一类特殊的VRP,由Min[1]提出。根据需求信息是提前已知或是实时出现的,VRPPD 又可分为带取送货的动态车辆路径问题和带取送货的静态车辆路径问题。在已有的VRPPD 研究中,大多数学者的研究都是静态的。生鲜外卖即时配送路径优化问题由于订单需求实时特性和配送员的动态性,更类似于动态VRPPD。动态VRPPD 由Psaraftis[2]提出并与静态VRP 对比进行前景分析与展望。动态VRPPD 着重考虑对于实时信息的处理,由于需求的动态性,难以用精确方法求解,很难找到其最优解,故学者们往往采用智能算法求解,如遗传算法[3-4]、粒子群算法[5-6]以及蚁群算法[7-8]等。对上述关于DVRPPD 的研究鲜少针对带硬时间窗的生鲜配送问题进行研究。

随着VRP 的发展,许多学者开始把时间约束加入到VRP中,提出了VRPTW,VRPTW 是VRP的一个重要分支。根据时间窗的特点,VRPTW 可分为带硬时间窗的车辆路径问题和带软时间窗的车辆路径问题。其中,对于带硬时间窗的车辆路径问题,大多选用现代启发式算法[9-10]求解。对于带软时间窗的车辆路径问题的研究有：葛显龙等[11]考虑碳排放,建立带软时间窗的多车车辆路径模型,设计混合遗传算法从而降低成本；吴瑶等[12]针对易腐产品,考虑交付产品时的价值损耗,建立时变网络下的交付时间窗模型,并设计混合遗传算法求解；张建同等[13]考虑不同时段的车速,建立时变的带时间窗的车辆路径模型,设计变邻域模拟退火算法求解该模型；Gyorgyi等[14]提出带时间窗的动态随机取送货问题,考虑时间窗的不确定性,解决了单个决策点的最小成本流问题；Zulvia等[15]建立带时间窗的易腐产品绿色VRP 模型,考虑对运营成本、劣化成本、碳排放和顾客满意度的优化,并设计多目标梯度进化算法求解该模型。上述VRPTW 的相关研究为本文的时间窗的处理与路径优化算法的设计提供了重要参考,但是其中未考虑到订单的即时调度特性。

已有研究对带时间窗的车辆路径问题和带取送货的动态车辆路径问题进行了充分研究,但对基于数据的动态实时出现的带时间窗的生鲜配送订单分配和路径优化研究还不足。并且,以往研究模型不适宜本文研究的问题,因此建立原创性的模型加以研究。本文针对生鲜农产品新鲜度要求高、时效性强等特点,考虑订单的动态性、硬时间窗等因素,以配送路径最短为优化目标,建立带硬时间窗的即时配送模型,并设计滚动时域延迟配送算法求解该模型。最后,通过大量数值仿真研究验证该算法的有效性,并对滚动时域时长、时间窗时间间隔、配送员数量及车容量等参数进行敏感性分析,为生鲜企业的配送策略选择提供参考。下文将从问题描述、建模、提出滚动时域延迟配送算法、仿真结果分析及结论等方面来论述。

1 问题描述及数学模型

1.1 问题描述

假设在一个O2O 生鲜外卖平台上,如盒马鲜生等商家自有平台,客户可以在平台上实时下单,每个客户需求订单都要求在一定的时间范围内送货上门,即每个订单具有一个固定的时间窗且每个订单的需求量为1,同时众包配送员为生鲜外卖订单提供即时配送服务。需求订单实时出现后,平台系统根据一定的规则分配订单给配送员。初始状态下配送员随机分布在某一区域内,配送员接受订单后,需要在配送中心取货,取货点始终在配送中心,且只有一个配送中心。一个配送员可以服务多个客户(一对多),最大载重量为配送员的最大容量C,每个客户只能被服务一次,配送车辆相同,配送员均以速度v行进,配送员需要在服务完他所需要服务的订单后返回配送中心,并且需要保证在最晚配送时间范围内,送至某一区域的不同客户手中。问题是,如何进行实时的订单分配和路径规划使得所有配送员的配送距离最短。

该问题中订单的实时动态性为理论模型的建立增加了难度,为了更清晰地描述订单的实时出现和动态分配过程,本文将连续时间进行离散化处理。如图1所示,时刻1产生订单O1、O2,生鲜外卖平台获知包括其时间窗、送货点位置在内的所有订单信息,而对未来即将出现的订单信息未知,此时生鲜外卖平台需要决策是否进行订单分配与路径规划。若平台决定暂时不进行订单分配,等到下一时刻再进行决策。在时刻2产生新的订单O3、O4和O5,并获知相应的订单信息,此时生鲜外卖平台又需要进行决策。例如其可以将之前产生的所有订单分配给配送员1并进行如图1所示的配送路线规划。根据图1表现出的对动态信息的处理及硬时间窗的要求,可以构建如下模型。

图1 配送路线图

1.2 符号说明

G=(V,E)——网络图,订单需求点均位于网络图G上,其中,顶点集合V={v1,v2,…,vn1},边集合E={e1,e2,…,en2}

l(vi,vj)——网络图中vi与vj之间的距离

u0——为取货点(配送中心)

σ={O1,O2,…,On}——订单序列,共有n个订单

Oi=(ri,di,LTi)——订单,其中：ri为需求订单的释放时间；di∈V表示订单位置；LTi为订单Oi允许的最晚送达时间,i∈I={1,2,…,n}

t∈T——当前时间t,将其视为离散数据,T为当前时间的集合

k∈K——配送员k,K为所有配送员的集合

C——配送员的容量

v——配送员的行驶速度

M——足够大的正数

决策变量

xikt——订单Oi在时刻t是否正在由配送员k服务,1为是,0为否。正在服务的含义已经将订单Oi分配给配送员k,但还未完成服务

1.3 即时调度模型

在上述模型中,式(1)表示总行驶距离最小的目标函数,式(2)～(4)为订单约束,其中：式(2)保证每个订单由且仅由一个配送员服务；式(3)保证每个订单最多由一个配送员服务；式(4)保证当订单Oi分配给配送员k且路径被选中时,xikt的值在订单Oi的服务时间段内都取1；式(5)为时间窗约束,订单Oi的实际送达时间不早于订单Oi的释放时间,不晚于订单Oi允许的服务最晚送达时间。式(6)～(8)为配送员约束,其中：式(6)保证每个配送员每个时刻正在服务的订单数不超过其最大容量；式(7)保证每个配送员仅选取一条配送路径；式(8)保证只有当订单Oi分配给配送员k时,订单Oi才会出现在配送员k的路径上。式(9)～(13)为路径约束,其中：式(9)保证只有当订单Oi在配送员k的第j条路径上时,订单Oi在路径中的送达时间才不为0；式(10)保证每个订单的取货时间早于其送货时间；式(11)保证每个订单的取货时间晚于其释放时间；式(12)、(13)表示在路径中订单的取货与送货时间不早于配送员按速度v行驶能到达其取货点和送货点的最早时间,配送员在行驶途中可以等待,故其到达时间可能晚于其最早可能的到达时间。式(14)～(17)为变量约束,其中：式(14)表示在路径中订单Oi的实际送达时间,若订单Oi不在路径则为0；式(15)表示订单Oi的实际取货时间；式(16)保证当订单取货后且服务完成之前决策变量xikt才能取1；式(17)为决策变量的约束。

上述建立的带硬时间窗的O2O 生鲜外卖即时配送路径优化模型中,由于订单的释放时间ri是无法提前获知的,即该问题是一个实时调度问题,无法采用最优算法对该问题进行求解,故设计基于滚动时域的延迟配送算法用于解决该实时调度问题,与滚动时域非延迟配送算法对比,并用数值仿真方法进行研究。

2 求解算法

下面将给出滚动时域延迟配送算法和滚动时域非延迟配送算法,通过分析各种参数的变化对目标函数值的影响,对比两种算法的有效性和适用性。

2.1 滚动时域延迟配送算法

滚动时域延迟配送算法的思路：每间隔一段时间重新进行订单分配与路径规划,每次重新规划时,在每个订单的时间窗约束下尽量推迟订单的分配,以保证有更多的订单可以进行合并配送。算法步骤如下：

(1)初始化信息,等待滚动时域时长分钟,更新待服务订单集合后转步骤(2)。

(2)判断下一个时域订单是否超过最晚送达时间,若是,则转步骤(3)；若否,则转步骤(4)。

(3)计算下一个时域即将超过最晚送达时间的订单数量,若此订单数量小于等于一辆车的车容量,则分配给距离配送中心最近的配送员,再调用TSP模型,进行路径优化；若此订单数量大于每辆车车容量,则分配给距离配送中心最近的(订单数/车容量)个配送员,再调用VRP模型进行订单分配和路径优化。

(4)进入下一个时域,更新所有订单及配送员信息,输出在当前时间的订单信息、配送员信息、最优路径和目标函数值。

(5)最后判断是否有未服务的订单,若是,则转步骤(2)；若否,则结束。

2.2 滚动时域非延迟配送算法

滚动时域非延迟配送算法的思路：每间隔一段时间重新进行订单分配与路径规划,每次重新规划时,在每个订单的时间窗约束下分配,保证订单在时间窗范围内送达。算法步骤如下：

天脊集团是社会的一分子，是社会哺育了天脊，发展的天脊更要反哺社会。30多年的发展，天脊集团培养了大批技术人才、管理人才贡献中国煤化工事业。从天脊集团走进科研院所、走向全国大型煤化工企业高管团队的优秀人才达300人以上。

(1)初始化信息,等待滚动时域时长分钟,更新待服务订单集合后转步骤(2)。

(2)判断当前时间,订单是否在时间窗内,若是,则转步骤(3)；若否,则转步骤(4)。

(3)计算在时间窗内的订单数量,若此订单数量小于等于一辆车的车容量,则分配给距离配送中心最近的配送员,再调用TSP模型,进行路径优化；若此订单数量大于每辆车车容量,则分配给距离配送中心最近的尽量少个配送员,再调用VRP 模型进行订单分配和路径优化。

(4)进入下一个时域,更新所有订单及配送员信息,输出在当前时间的订单信息、配送员信息、最优路径和目标函数值。

(5)最后判断是否有未服务的订单,若是,则转步骤(2)；若否,则结束。

利用专业的数学仿真软件对两种算法进行仿真研究,仿真流程如图2所示。

图2 滚动时域延迟配送算法和滚动时域非延迟配送算法仿真流程图

滚动时域延迟配送算法着重考虑：①对动态信息的处理。订单出现后判断此订单在下一个时域是否超过最晚送达时间,若超过则需立即配送,没有超过则等待下一次更新,并且以是否有未服务的订单为整个程序结束的条件。②订单分配和路径优化。根据订单数量、车容量和配送员距离配送中心的距离进行订单分配,并且调用TSP或VRP模型进行路径优化。而滚动时域非延迟配送算法考虑在时间窗范围内送达,不必尽量推迟订单的分配。根据上述两种算法仿真流程图进行仿真,因此有如下仿真研究。

3 仿真研究

采用滚动时域延迟配送算法和非延迟配送算法,选取实际网络和一般网络进行对比,说明其有效性。通过变化滚动时域时长、时间窗时间间隔、车容量及订单数量等参数,观察平均每单配送距离的变化,进行适用性分析并得出结论。

3.1 有效性分析

为了研究两种算法在不同网络下的有效性,选取两种具有代表性的网络数据进行对比分析：

(1)以重庆市南岸区盒马鲜生(南湖路店)为配送中心,向周围辐射3 km,选取真实住宅小区的地理位置,如图3所示。

图3 真实住宅小区的地理位置图

考虑到客户下单的可能性,选取离配送中心1 km内的小区25个,离配送中心1～2 km 内的小区15个,离配送中心2～3 km 内的小区10个作为需求点。通过专业的数学仿真软件对滚动时域延迟配送算法和非延迟配送算法进行编程,其中,仿真时间为120 min,配送员数量为50,车容量为10,时间窗时间间隔为30,滚动时域时长取15～35 min,间隔5 min观察其变化,每轮数据仿真50次,取平均值,得到目标函数值。由表1和图4可以看出,配送员数量为50,车容量为10,滚动时域时长为25 min,当时间窗时间间隔为30时,滚动时域延迟配送算法平均每单配送距离为1.378 8 km。滚动时域非延迟配送算法平均每单配送距离逐渐减少。

(2)随机生成一个仿真网络,以一配送中心为原点,半径为3 km 的圆内均匀生成50个客户点及客户的时间窗。通过专业的数学仿真软件对滚动时域延迟配送算法和非延迟配送算法进行编程,仿真时间为120 min,其中,配送员数量为50,车容量为10,时间窗时间间隔为30,滚动时域时长取15～35 min,间隔5 min观察其变化,每轮数据仿真50次,取平均值,得到目标函数值。由表1和图4可以看出,配送员数量为50,车容量为10,滚动时域时长为25 min,当时间窗时间间隔为30时,滚动时域延迟配送算法平均每单配送距离为1.050 9 km。滚动时域非延迟配送算法平均每单配送距离逐渐减少。

表1 不同网络下平均每单配送距离变化表

图4 不同网络下订单平均每单配送距离变化图

结论1随着滚动时域时长的增加,滚动时域延迟配送算法的平均每单配送距离先增大后减小,中间出现平均每单配送距离的最大值。滚动时域非延迟配送算法的平均每单配送距离逐渐减小。

由表1和图4可知,两种网络的仿真结果所得的平均每单的配送距离与实际相符,从而验证了本仿真系统和算法的有效性。对于滚动时域延迟配送算法,随着滚动时域时长的增加,平均每单配送距离都是先增大后减小,当滚动时域时长为15 min时,平均每单配送距离达到最大值,并且两种网络的最大值相差不大,在误差范围内。出现这种结果是因为滚动时域时长如果越短,订单将会一直等待,直到累积到一定数量的订单再进行配送,避免一单一送,一个配送员配送更多的货物,平均每单配送距离会越小。滚动时域时长如果越长,累积更多的订单,一个配送员也会配送更多的货物,平均每单配送距离会越小。对于滚动时域非延迟配送算法,随着滚动时域时长的增加,平均每单配送距离逐渐减少,这是因为不考虑尽量推迟订单的分配,累积的订单没有滚动时域延迟配送算法的订单多,滚动时域时长越长,集合订单一起配送,每单配送距离越短。但滚动时域时长越长,会影响生鲜的品质。因此,从生鲜品质和平均每单距离综合考虑,滚动时域延迟配送算法优于非延迟配送算法。下面选取一般网络“配送员数量为50,车容量为10,滚动时域时长为25,时间窗时间间隔为30”作为标准案例进行适用性分析。

3.2 适用性分析

适用性分析的目的是找出影响目标函数的因素,分析变动的原因,确定其影响的程度。此适用性分析将上述一般网络“配送员数量为50,车容量为10,滚动时域时长为25,时间窗时间间隔为30”作为标准案例,基于标准案例,调整算法中的某些参数,包括时间窗时间间隔、车容量及订单数量,观察对平均每单配送距离的影响。

结论2随着时间窗时间间隔的增加,滚动时域延迟配送算法的平均每单配送距离趋于稳定,最大值与最小值相差6.3%。滚动时域非延迟配送算法的平均每单配送距离逐渐减少。

出现这种结果是因为滚动时域延迟配送算法只考虑了在最晚送达时间内送达,是单边时间窗,时间窗间隔的变化对平均每单配送距离影响较小。而滚动时域非延迟配送算法的平均每单配送距离逐渐减少,因为滚动时域时长越长,集合订单一起配送,每单配送距离越短,但此算法在时间窗内都可以配送,累积的订单比滚动时域延迟配送算法的订单少,需要比滚动时域延迟配送算法派出的配送员多,所以整体比滚动时域延迟配送算法的平均每单配送距离大。

结论3在两种算法下,车容量越大,平均每单配送距离越小。

由表2和图5可以看出,两种算法的平均每单配送距离减速较为稳定,由此可知,车容量越大,配送员一次带的量越大,可能有时只需一个配送员就可以配送完成,所以平均每单配送距离越短。整体来看,滚动时域非延迟配送算法比延迟配送算法的平均每单配送距离大。

表2 各参数影响订单平均每单配送距离表 km

图5 各参数影响订单平均每单配送距离图

结论4随着单位时间内订单数量的增加,滚动时域延迟配送算法的平均每单配送距离逐渐稳定。滚动时域非延迟配送算法的平均每单配送距离逐渐减少。

由表2和图5可以看出,滚动时域延迟配送算法在订单数很少时,积累的订单数不够多,会出现一单一送的情况,所以此时平均每单配送距离很大,随着订单数量的增加,积累的订单数足够多,合单配送,平均每单配送距离逐渐稳定。滚动时域非延迟配送算法的平均每单配送距离逐渐减少,这是因为订单数量越多,合单配送,平均每单的配送距离越小。整体来看,滚动时域非延迟配送算法比延迟配送算法的平均每单配送距离大。

上述结论可为生鲜外卖平台的配送策略提供参考,可保证在最晚送达时间内送达的同时,选择最优路径。并且,可得出生鲜外卖平台的管理启示：

(1)平台的调度算法应该选取合适的滚动时域时长,不宜选取中间数值。

(2)在实际允许的情况下,尽可能增加每辆车的车容量。

(3)在生鲜外卖点单高峰期,即单位时间内订单数量较多时,采用滚动时域延迟配送算法比较合适。

(4)基于对生鲜品质和每单配送距离的综合考虑,选择滚动时域延迟配送算法比较合适。

4 结语

针对生鲜农产品新鲜度要求高和时效性强的特点,对带硬时间窗的O2O 生鲜外卖即时配送路径优化问题进行了研究,考虑动态的订单需求、订单的滚动时域时长以及客户时间窗等因素,以配送总距离最小为优化目标,建立带硬时间窗的即时配送模型,并设计更适应该问题的滚动时域延迟配送算法求解该模型。通过大量数值仿真研究验证两种算法的有效性,并且发现：在滚动时域延迟配送算法下,随着滚动时域时长的增加,平均每单配送距离先增大后减小,中间出现平均每单配送距离的最大值。随着时间窗时间间隔的增加,平均每单配送距离趋于稳定。车容量越大,平均每单配送距离越小。随着单位时间内订单数量的增加,平均每单配送距离逐渐稳定。滚动时域时长、车容量及订单数量等变量均对目标函数值有较大影响。该模型可以有效的用于优化路径,保证在最晚送达时间内送达的同时,使配送员尽可能多拿订单,针对该模型的滚动时域延迟配送算法取得了良好的结果,整体平均每单配送距离比滚动时域非延迟配送算法小,可为生鲜企业的配送提供参考。

在实际应用中,生鲜外卖平台采用的算法应选择合适的滚动时域时长,要满足客户更短的送达时间要求,需要付出的配送成本将会增加,要降低配送成本可适当延长承诺的最短送达时间,为了降低配送距离及其成本可以增大每个配送员的车容量。进一步,还可以考虑每个客户时间窗时间间隔不同和每个客户需求量不同的情形下,生鲜外卖即时配送路径优化问题。