随机需求连锁餐厅联合配送规划仿真研究

蒋 磊， 李晓明

（1 南京开放大学 装备与信息技术处， 南京 210000； 2 三江学院 计算机科学与工程学院， 南京 210012）

0 引 言

随着“互联网+电子商务”模式的不断发展，网上购物、网上订餐逐渐成为一种趋势，餐饮外卖行业为人们的日常饮食提供便利。 餐饮外卖商家的线上订单分配与处理、物流派送是快餐配送网络的核心环节，属于NP-hard 问题。 餐饮外卖企业订单处理与派送的主要特点在于：订单是随机产生的；订单数量在一定时间段内较为密集；订单的空间分布呈辐射状规律；连锁餐厅之间存在订单和派送员的相互调度问题；物流成本和履约率约束；订单合并问题等。 这些问题使得连锁快餐订单分配和派送员调度规划十分复杂［1］。 订单信息的整理与分配、派送员派送路径规划是快餐业务网络中的2 个重要环节，是一个有机整体。 通常一个快餐店的派送员数量是恒定的，订单量大、分布复杂时，派送员的需求量增加。 而派送员均处于派送途中且回程时间均不能满足顾客需求时间时，快餐店不得不停止接单。 所以订单的分配与派送规划是相互制约的，这种矛盾性就要求快餐店研究随机需求下，派送员联合配送模式，实时地进行订单分配与物流派送优化，并研究订单合并、增加派送员、停单等问题。

静态单配送中心最短路径配送问题的基本模型为VRP（Vehicle Routing Problem），增加时间要求的VRP 问题称为混合问题，另外一种描述称为时间窗VRP 问 题， 增 加 随 机 需 求 的 VRP 问 题 称 为SDVRPSDP 问题［2-3］。 在电子商务规划中，这一类问题的研究主要分为3 个方面：订单分配优化、物流配送调度、订单分配与物流调度联合优化（Location Routing Problem， LRP）［1］。 关于LRP 的研究又可以分为多级LRP、不确定性LRP、随机需求分解LRP、开放LRP 这四类问题。 这些数学模型归纳一般定义为：有一个或多个配送中心和若干个已知的需求点，规划行车路线通过每一个需求点，最终回到配送中心，并在车容量、行驶里程、时间等约束条件下，达到总路线最短、费用最低、时间最短等目标。扩展到连锁快餐订单配送问题中，需求点的快餐需求量、需求时间、要求送达时间、需求点分布是随机的，连锁餐厅之间存在派送员相互调度而中途不一定回到配送中心、多个配送员动态规划路线来保证订单系统不关闭等情况。 从目前的研究现状来看，现有研究成果可以满足定量的订单分配（包括静态和动态），并可以实现物流仓储设施点的选择和物流路径。 但是这一类解决方案只能解决一定规模的订单配送问题，对于餐饮外卖这样一种特殊的电子商务模式，这些解决方案不能满足随机需求的动态分配、需求点随机分布、订单的合并与停止接单等要求。 文献［4］建立了随机需求环境下三级供应链任务分配的双层规划模型，研究了随机环境下客户满意度和利润的关系，但是没有考虑多个配送周期的任务动态分配问题。 文献［5］提出了基于客户满意度的需求预测模型，为提高快速响应客户需求做出预测机制，但是模型受到以往数据和主观因素影响，存在缺陷。 部分研究者提出闭环物流网络模型，旨在缩小配送系统成本，增强对于需求的反应能力。

在算法设计上，研究者为了对所建立的模型进行处理，提出了一系列求解算法。 主要包括分支定界法、启发式算法、遗传算法、模拟退火法、禁忌表搜索法、蚁群算法等［6］。 葛显龙等人［6］提出了动态需求下多车型调度优化的云遗传算法，利用云滴的随机性和稳定倾向性改进了自适应遗传算法中的交叉变异率，提高了全局搜索能力。 文献［7］提出了随机合理化禁忌法，解决了随机需求同时取送货路径问题。 这些算法在求解优化问题时具有一定的时效性和稳定性，但仍需要根据具体问题做出改进。

基于以上分析，本文提出三维时间轴的概念来表示3 家连锁餐厅订餐服务时间，并可根据连锁餐厅数量进行多维度扩展。 采用随机模拟的思想模拟出随机订单，以总配送成本最小为目标函数建立连锁订单分配与派送员调度模型，对配送里程、派送员单程承载量、客户需求时间进行约束。 设计基于紧密程度的订单聚类算法，利用改进C-W 节约法混合蚁群算法求解最优派送方案。 本文算法为连锁餐饮企业订单分配与物流派送提供参考。

1 随机需求连锁快餐店配送建模

1.1 问题描述

某连锁餐饮企业有多家餐厅对外提供外卖送餐服务。 顾客通过企业提供的订餐方式向订餐中心提出订餐要求，订单信息包括：下单时间、送餐地址、需要的餐点、送货时间、联系方式等信息。 订餐中心对顾客订单进行分配，由餐厅完成餐点制备和送餐服务。 每个餐厅有固定人数的派送员，并且派送包的大小确定。 在订单分配的过程中可以进行并单、订单延迟、停单等处理，现要求探究随机订单的分配和派送路线，以及订单数量对于连锁餐厅运营状态的影响。

1.2 问题分析

快餐店开启订餐服务的时间为［Te，Ts］，建立三维时间轴，3 家连锁餐厅分别在ΔTi（i ＝1，2，3）时间内产生随机订单。 以一家餐厅为例，ΔT时间内产生订单为K0，考虑外卖餐饮的实际情况，订单数量在时间维上满足正态分布，而在ΔT内满足泊松分布，即：

其中，λ为随机订单参数。 需求点的分布服从二维正态分布。 根据订单信息建立需求点描述向量DM ＝｛T1j，T2j，Sj，Lij｝，i，j∈V，V为节点集合，DM描述了下单时间、需求时间、需求量和节点距离。 现根据时间和派送容积限制讨论订单合并的条件。 记tij，i∈｛0｝∪V，j∈V表示节点i到节点j的派送时间，v0表示派送员平均行驶速度，则tij ＝Lij／ v0，送达需求点的总时间为t0j ＝t01+t12+…+tj -1，j。 同样建立派送员的描述向量DP ＝｛tg，tb｝，tg为出发时刻，tb为回到快餐店的时刻。 建立三维时间轴如图1 所示。

图1 三维时间轴示意图Fig.1 3D timeline diagram

在ΔTi（i ＝1，2，3） 时间内，快餐店可以进行派送的人员为n11，n21，n31，已经分配出去的派送员数量为n1 11，n1 21，n1 31，剩余数量为n2 11，n2 21，n2 31，规划好的派送员k回程时间tk db ＝tk d0j+Lk dj0／v0，d ＝1，2，3 表示3 家餐厅，j为节点。 派送员能否加入到下一轮的调度就需要比较回程时间和三维时间轴的坐标。 结合图1 分析，第一次派送之后，如果tk db ＜2ΔTd，n2d2＝n2d1+1，在第m个派送区间，如果（m-1）ΔTd ＜tk db ＜mΔTd，n2dm ＝n2d，m -1+1。 每产生一个随机订单即加入到路径规划中，不断比较区间上派送员数量和规划路径，从而为餐厅提供派送参考。 3 个快餐店配送中心的动态路径规划示意图如图2 所示。

图2 配送中心动态路径规划示意图Fig.2 Schematic diagram of dynamic path planning of distribution center

1.3 跨区域联合调度模型

1.3.1 模型假设

（1）不考虑订单制作时间和派送员在客户节点处的逗留时间。

（2）每个客户只被一个派送员服务，一个客户的订单只需要一个派送员就能够满足。

（3）单个配送中心情况下，派送员必须回到原来餐厅，而多个配送中心情况下，派送员不是必须回到原来餐厅。

（4）需求点随机产生，需求向量也随机产生，均服从一定的概率分布。

1.3.2 符号与决策变量

除在1.2 节问题分析部分外的符号定义如下：C1为单位里程派送费用；C2为增加一个派送员的成本；Lij为节点i与节点j之间的距离；tij为节点i与节点j之间的行驶时间；nΔT为时间轴上n段时间；一个快餐占据空间为V0，派送包容积为Q；V为节点集合；M为派送员集合；m0为总的派送员数量；Md为增加派送员数量集合；xijk为0-1 变量，如果派送员k从节点i送到节点j，则xijk ＝1，否则xijk ＝0；yik为0-1 变量，如果节点i是由派送员k配送的，则yik ＝1，否则yik ＝0；zi为0-1 变量，如果需要增加第i个派送员，则zi ＝1，否则，zi ＝0。

1.3.3 配送模型

其中，式（3）表示配送系统的总成本最小，主要包括配送路程成本和增加派送员成本；式（4）为派送包容量约束，表示规划的路线上总的快餐体积不大于派送包体积；式（5）为配送时间约束，表示派送员送达时间不超过客户需求时间；式（6）表示一次派送中，一个需求点只能被派送员送一次；式（7）和式（8）表示从快餐店出发和回到快餐店的派送员数量不超过派送员总数量与增加的派送员数量之和。

2 算法设计

2.1 聚类分配算法

将随机产生的订单按照距离和订单承受能力进行聚类，分配到3 家餐厅分别进行配送规划，每当产生一批新订单就加入到聚类样本中进行动态分类。ΔT时间内产生需求点集合C ＝｛c1，c2，…，cp｝，D为餐厅集合。 定义需求节点到餐厅的紧密程度Rid为：

其中，Fid为需求点i到餐厅d的亲和力，定义为：

其中，λ1和λ2为正的加权系数；Iid为0-1 变量，如果i需求点已经分配给d餐厅，则Iid ＝1，否则Iid ＝0；Bd为当前d餐厅的订单承载能力，具体为：

其中，qi为0-1 变量，如果派送员i已经分配到d餐厅，qi ＝1，否则，qi ＝0。 式（11）一个主要缺点在于假设了派送员满载派送而实际情况不一定满载，但是满载体现了承载能力的最大化，这只是订单分配的条件，实际路径规划中是否满载是约束条件（3） 判断的。

上述分析可知，紧密程度Rid最大，需求点i就被分配到d餐厅。

2.2 C-W 节约法混合蚁群算法

Clarke-Wright 节约算法是一种随机合理化动态衍生方法，首先生成初始方案，利用随机合理化动态衍生方法构造备选方案集，计算出备选方案集中的送货代价，在此基础上进行禁忌选优，确定优化方案，提高了搜索效率。 在本文多配送中心随机需求的问题中，随机计算过程复杂，在需求分配初期仍然采用CW 节约法生产初始方案，这里从载重限制、时间窗限制等方面改进C-W 节约法。 但是利用改进C-W 节约法生成的线路受到起始需求点影响较大，相同的需求点下虽然满足了载重和时间限制，但是行驶路径存在可能交叉现象，并不最优。 所以引进蚁群算法，通过蚁群的全局搜索能力，在需求点之间形成最短路径，C-W 混合蚁群算法同时缩短了求解时间，提高系统效率。 时间上，在一段时间内产生的订单加入需求点集合中进行分配；空间上，繁忙程度高的餐厅（ndm＜0） 产生订单加入到其它餐厅分配。

随机需求下多配送中心联合调度算法流程如下：

步骤1采用蒙特卡洛随机模拟的思想，在第一个ΔT时间内，按照式（1） 产生随机订单，参数λ在［Te，Ts］上满足正态分布。 同时确定需求点描述向量DM。

步骤2根据需求点与餐厅之间的紧密程度将需求点聚类。

步骤3在第一个ΔT内， 每个餐厅先进行独立分配。 单配送中心利用C-W 算法思想计算节约值并进行排序，根据载重限制（3）和需求时间限制（4）逐层连接需求点，生成初始分配方案。

步骤4利用蚁群算法将初始分配方案优化，按照式（2）优化路线，同时生成派送员描述向量DP。

步骤5在mΔT内产生随机订单，计算tk db ＝tk d0j + Lk dj0／v0在时间轴上位置，更新ndm、n1dm与n2dm。 如果n2dm ＞0 则配送工作正常，否则，调整路径，将多余需求点加入到其它餐厅。 遍历d，如果仍不能满足n2dm ＞0，则采用增加派送员机制。 不断循环步骤5，直到m ＞（Ts - Te）／ ΔT。

步骤6改变随机模拟参数，探究不同繁忙程度下多配送中心订单配送情况。 动态变化过程的路径规划算法图3 所示。

图3 动态变化过程的路径规划算法Fig.3 Path planning algorithm for dynamic change process

3 仿真实验分析

设定的外卖餐厅工作时间区间为10：00 ～13：00，时间间隔均为10 min，在工作时间内产生订单的最大值为8，方差为2，数据产生区域在3 km 以内，外卖派送包容积为5 份，每个需求点需求量为1-2，派送员一次行程最远距离为2.0 km，行驶速度为0.6 km／min，3 家快餐店距离相同。 设定区间3 家外卖餐厅位置分别位于边长6 km 正方形区域内坐标为（0，1 000），（-1 000，-1 000），（1 000，-1 000）位置。 利用本文算法获得的派送路径如图4 所示。

图4 随机订单下派送路径规划Fig.4 Delivery path planning under random orders

10 点开始派送状态下的派送路径情况见表1。

表1 初始状态下派送路径表Tab.1 Delivery path table in initial state

表1 中，-2、-1、0 分别表示3 家餐厅，其余点编号表示订餐中心在10 点时刻累计的客户。 选择各个配送员第三次配送的情况见表2。

表2 第三次配送路径规划情况Tab.2 Third distribution route planning

表2中选取了动态派送路径规划中每名派送员第3 次的派送路径，其中派送员P1第3 次派送的起始时间为10：18，派送员P2第3 次派送的起始时间为10：55， 派送员P3第3 次派送的起始时间为10：28。

按运送费用最小为目标得出最优路径的求解结论有：

（1）订单派送过程未发生订餐中心停单情况。

（2）完成所有订单累计最少消耗成本为1 002.14 元。

（3）随机产生的订单总数为432 个。

（4）损失的客户数为52 名，损失的订单数为98个，可得客户损失率约为24.1%，订单的损失率约为22.7%。

从模型的求解结果可以看出，该模型能够完成订单的派送任务，累计最少消耗成本较高，通过计算完成了对模型的检验，证明该模型的设计是合理的。

4 结束语

本文研究了随机订单生成状态下，配送员的路径规划问题。 不失一般性，研究了3 家连锁餐厅随机订单生成与配送规划。 建立了以总配送成本最小为目标函数建立连锁订单分配与派送员调度模型，对配送里程、派送员单程承载量、客户需求时间进行约束。 通过仿真研究验证了算法有效性。 在实际的餐厅订单配送过程中，可能会存在更多的约束条件，且各约束条件之间还可能相互冲突，因此需根据实际情况对模型进行适当的调整。 本文算法对于实际连锁餐饮店的动态订单生成配送问题提供了一定的解决方案。