疫情封控下的卡车和无人车联合配送问题研究

姜博涵，刘 翱，邓旭东，任 亮，彭琨琨，艾学轶

（武汉科技大学 管理学院，武汉 430065）

0 引言

新冠疫情爆发以来，全球经济都受到了严重的影响，后疫情时代的到来使各地的防疫形势依然严峻。作为中国经济体系的关键部分，物流业某些环节的薄弱点和不足也显露出来。在疫情防控下道路封闭、配送链断裂，导致居民生活和物资需求不能得到保障，传统的配送方式已不能满足物流需求。针对上述问题，考虑到城市中部分地区封控的情况下，无接触式配送能有效降低病毒传播的风险，卡车和无人车联合配送能为疫情封控背景下的配送活动提供可行的方案。

无人配送近年来广受学者关注，主要用到的工具是无人机和无人车。在无人机配送的研究中，Kuo 等［1］研究了考虑时间窗的无人机配送路径问题；张梦［2］和王新等［3］研究了车辆和无人机联合配送的优化方法，并设计算法进行求解验证。但基于无人机技术的发展受到各地政治、经济水平等因素的限制，在实际场所中无法得到广泛的应用。相较于无人机，无人车具有更大的优势，已经开始应用到实践中。

Taefi 等［4］认为，电动汽车在配送领域有很大的应用空间，可以很大程度减少运输成本和缓解环境问题；Miguel［5］对比了传统燃油车和无人车的碳排放和成本也验证了这一观点；赵国富［6］分析了无人车在普及过程中遇到的问题，并进行案例分析和规划设计；王愚勤［7］和Liu 等［8］研究了智联网下的无人车问题；Sonneberg［9］和赵思雨等［10］在研究无人车在“最后一公里”配送路径问题中，考虑了无人车电池容量和时间窗等因素；陈志强等［11］提出了一种遗传禁忌混合算法，求解基于无人车的带有时间窗车辆路径问题；施磊［12］研究了无人车和传统车辆结合的混合车队问题；郑李萍等［13］设计了4 种不同规模的无人车辆服务网络，并仿真分析了车辆配置对于配送网络的影响；孙珊［14］针对“最后一公里”配送问题，设计了一种卡车携带无人车协同配送的模式。

针对疫情封控下的物流配送现实困难，本文提出卡车和无人车联合选址-配送问题，在封控区设立无人车站点，由站点的无人车进行配送，而未被封控的地区保持原有的配送方式不变，并以此为基础建立最小化运输成本目标模型，运用最大最小距离算法（Maximum and Minimum Distance Algorithm，MMD），对需求点进行聚类操作并选出无人配送站点，使用粒子群算法（Particle Swarm Optimization，PSO）求解配送路径优化问题。

1 卡车和无人车联合配送优化模型

1.1 问题描述

假定封控区设立的无人车站点可以提供足够数量的车辆，而无人车站点的位置需要依据封控区需求点的位置去建立，站点的位置一经确定后不发生变化。卡车从配送中心出发，如遇到封控区的货物需求不能送达，需要将货物交接到无人车站点，并由站点的无人车进行无接触配送，卡车继续执行配送任务。卡车和无人车联合配送路线如图1 所示：

图1 卡车和无人车联合配送路线图Fig.1 A schematic diagram of the joint distribution of trucks and driverless cars

1.2 条件假设

本问题为不失一般性，基于以下假设：

（1）卡车从配送中心出发，执行配送后必须返回配送中心；

（2）无人车只能从站点出发，执行配送任务后须返回站点；

（3）需求点的需求量为qi，由于疫情防控货物只能在固定的时间段［ei，li］内到达，无人车站点的时间窗由需求点的最早和最晚时间点决定；

（4）卡车和无人车有容量和最大行驶里程的约束；

（5）配送任务中，每个需求点和站点只能被访问一次；

（6）封控区的需求点只能由无人车访问，而卡车只能访问无人车站点和未被封控的需求点；

（7）每个无人车站点只对其服务范围内的需求点展开配送。

1.3 符号说明

本文问题涉及的所有节点（包括配送中心、无人车站点、客户需求点等）都定义在一张无向图G ＝（N，E，F）上。

（1）点集合N ＝｛Nk∪Nv｝；

其中，Nk是卡车可到达的点集合，包括配送中心N0、无人车站点集合Ns、未被封控的需求点集合是无人车可到达的点集合，包括无人车站点集合Ns、被封控的需求点集合

（2）卡车行驶的边集合E ＝｛（i，j）｜i.j∈Nk，i≠j｝；

其中仅包含卡车可到达两点之间的连线。

（3）无人车行驶的边集合F ＝｛（i，j）｜i.j∈Nv，i≠j｝。

其中仅包含无人车可到达两点之间的连线。

设卡车的集合为K，无人车的集合为V。其中卡车的最大行驶里程和载重量分别为Lk和Qk；无人车的最大行驶里程和最大载重量为Lv和Qv。a和b分别代表单辆卡车和无人车的使用成本分别表示单辆卡车和无人车从点i到点j的行驶成本。dij表示节点i到节点j之间的距离；Sv表示第v辆无人车的所属站点；ti表示节点i所需的服务时间；qi表示第i个点的需求量。

根据所述问题，定义xijk、yijv变量如下：

1.4 模型构建

基于问题描述、条件假设和符号说明可构建以下模型：

其中，式（1）为总成本最低目标函数，包括卡车和无人车的使用成本和路径成本；式（2）表示每个无人车站点和未封控需求点只被卡车访问一次；式（3）表示每个封控的需求点只被无人车访问一次；式（4）表示封控的需求点只能由无人车访问，而未封控的需求点只能被卡车访问；式（5）表示只有卡车对无人车站点进行访问之后，该站点的无人车才能开始执行配送任务；式（6）和式（7）是卡车和无人车最大容量的约束；式（8）和式（9）表示卡车和无人车最大行驶里程约束；式（10）和式（11）表示卡车和无人车完成配送任务后，必须返回配送中心或站点；式（12）表示卡车满足未封控需求点和无人车站点的时间窗约束；式（13）表示无人车满足封控需求点的时间窗约束；式（14）表示配送时间满足时间窗约束。

2 基于MMD 算法的无人车站点选址

2.1 MMD 算法的基本原理

最大最小距离（MMD 算法）是模式识别中一种基于试探的类聚算法，以欧式距离为基础，取尽可能远的对象作为聚类中心。其基本思想是对待分类模式样本集采取以最大距离原则选取新的聚类中心，以最小距离原则进行模式归类。结合该算法的基本思想，将被封控的需求点进行聚类处理，确定聚类中心，建立无人车站点。

2.2 算法基本步骤

步骤1在被封控的需求点集合中任选一个需求点，作为第一个聚类中心z1；

步骤2选取距离z1最远的一个需求点为第二个聚类中心z2；

步骤3计算其余需求点到z1与z2之间的距离，并得出最小值：

则选取新的需求点o1作为第三个聚类中心z3，判断是否存在新的聚类中心，若不存在，则转到步骤6。其中，θ为比例系数。

步骤5假设存在k个聚类中心，计算各需求点到各个聚类中心的距离xij，并计算：

若假设成立，则确定新的需求点o1为新的聚类中心，继续判断有无新的聚类中心存在，若没有，转到步骤6；

步骤6当判断没有新的聚类中心存在时，将封控区需求点集合按最小距离原则分配到各类中，并计算：

步骤7确定各聚类中心为无人车站点的位置。

3 基于粒子群优化的卡车与无人机联合配送路径优化

粒子群算法（PSO）是模仿鸟类觅食时的飞行特征，通过模拟鸟类群体在一片随机的有边界的区域内寻找一块食物并飞行到其所在位置，要制定较好的策略，通过寻找离食物最近的鸟，并对其附近进行搜索。若将该算法应用到优化问题中，则将每一个鸟当作一个粒子，承载了一个目标函数的适应度值。通过制定其飞行速度和方向规则，追寻当前最优粒子，去寻找当前解空间中最优目标的位置。

3.1 粒子编码

假设顾客数目为L，车辆最大使用数为M，构造粒子位置为2 行L列的矩阵，矩阵由左至右依次为编号1-L对应的列。第一行为顾客对应的车辆编号Xv，第二行为车辆顺序编号Xr。

现假设有6 位顾客，2 辆车辆，对应以上定义，一个可能出现的粒子［Xv；Xr］如下：

车辆编号：2 2 1 1 1 2 顺序编号：6 4 2 3 5 1

将第1 辆车服务的需求点3、4、5 放在一起，第2 辆车服务的顾客1、2、6 放在一起，然后按照各个需求点的顺序编号，按从小到大的顺序访问需求点。对上述粒子进行调整，可得到以下配送方案：

车辆1 0→2→3→5→0 车辆2 0→6→4→1→0

3.2 粒子初始化

在粒子位置的初始化时，［Xv；Xr］中Xv和Xr每个位置的元素分别为区间1-M和1-L的随机数。对于粒子编码操作中不能判断需求点被服务的次序时，按照Xr的大小，对次序进行更新。

粒子的更新公式如式（20），为粒子速度的更新公式如式（21）：

在粒子速度的初始化中，Xv对应速度Vv，Xr对应速度Vr。则Vv中每个位置上的元素都应该为-（M -1）～（M -1）的随机数，Vr中每个位置上的元素都应该为-（L -1）～（L -1）的随机数。

3.3 粒子更新取整与越界处理

基于粒子更新后可能会出现向量中元素不为整数的情况（Xv不为整数），则需进行向上取整操作，Xr是顺序向量，体现出大小就行，不需取整操作；而后对Xv和Xr中的越界元素进行处理，将越界元素赋值为边界值。

3.4 局部搜索

为使配送方案满足约束，增加局部搜索算子提高解的质量。具体操作步骤如下：

步骤1判断得出配送方案VC 是否满足终止条件，若满足条件转至步骤5，否则转步骤2；

步骤2计算VC 每条线路上车辆开始服务时间ti与需求点li的差值，即违反约束的值，挑出违反约束最大的需求点，记录到一个n行2 列的矩阵R中，第一列为n个违反约束的需求点编号，第二列为违反约束值，如未违反约束，则矩阵中的各个值记为0；转到步骤3；

步骤3若R中存在正值，找出对应的需求点i并移除，得到RVC 转到步骤4；若R中所有值都为0，则将违反约束的需求点插入到距离该顾客最近的两个节点中，转到步骤1；

步骤4将矩阵插回到配送方案RVC 中满足约束且距离增量最小的位置，得到新的配送方案VC；

步骤5计算目标函数值。

4 算例分析

本文采用solomon 的测试算例c101，使用matlab 编写MMD 算法和粒子群算法进行求解；运行的计算机参数配置为11th Gen Intel（R）Core（TM）i5-11400 ＠ 2.60 GHz 2.59 GHz、RAM 16 GB、windowsl0 操作系统。

4.1 无人车站点的选址

为了简化问题和满足一般性，基于算例，本文假设疫情封控区为图2 矩形框内的区域（即横坐标20～60 和纵坐标0～40 的区域）。

图2 封控区表示图Fig.2 The control area

将比例系数θ设置为0.5，运行MMD 算法得出可将封控区需求点聚类为3 个区域（如图3）。其中3 个聚类中心为无人车站点的位置，坐标分别为（50，35）、（35，5）、（25，30）。

图3 聚类结果及选址点表示Fig.3 Cluster results and site selection points representation

4.2 参数设置

分别计算3 个区域需求点的总需求，以节点最早和最晚的时间点为无人车站的时间窗。其它参数设置如下：

卡车的最大装载量为200、无人车的最大装载量为50、卡车的车辆最大使用数为25、无人车的最大使用数为5、卡车的单位路径成本为10、无人车的单位路径成本为2、单辆卡车的使用成本为100、单辆无人车的使用成本为20。

4.3 计算结果分析

4.3.1 第一阶段求解

在求解第一阶段配送时参数设置为：惯性因子ω初始值为1，衰减率为0.98，c1和c2分别为1.5 和2。迭代50 次得到的配送路径见表1。

表1 卡车配送路径表Tab.1 Truck delivery path table

算法运行时间为110.65 s，求得全局最优总运输成本为8 753，卡车的使用数目为10，卡车的总行驶里程为775，其中卡车5、7、10 前往无人车站点执行配送。

4.3.2 第二阶段求解

求解第二阶段无人车前往封控区需求点的配送方案参数设置：惯性因子初始值为1，衰减率为0.95，c1和c2分别为1.5 和2，迭代20 次得到配送路径见表2。

算法运行时间为37 s，求得全局最优总运输成本为485，无人车的使用数目为10，无人车的行驶总里程为193。综上，可得最终求得的全局最优解的总成本为9 228。

4.4 结果对比

为更好的证明卡车和无人车联合配送的优势，通过计算某一卡车司机和需求点顾客出现感染时造成的疫情传播风险，对两种情况进行对比，表3 为传统模式的配送方案。

表3 传统模式配送路径表Tab.3 Table of traditional mode distribution paths

假设卡车司机5、需求点57（封控）感染病毒，密接的感染率为4.41%［15］，计算一次配送任务中的总传播风险值见表4。

表4 传统和联合配送模式对比表Tab.4 Comparison table of traditional and joint distribution modes

卡车和无人车的配送成本小于传统的配送模式，节省了运输成本。而针对以上一辆卡车只服务无人车站点的情况，恰好符合疫情防控的需求，疫情传播的风险远小于传统模式，有利于疫情防控。

5 结束语

本文研究了在城市局部区域疫情封控的背景下卡车和无人车联合配送模式，并考虑了部分需求点属于封控区域情况，在保证完成正常配送任务的同时，设立无人车站，对封控区的需求点进行配送；建立了最小化运输成本为目标，并用两阶段算法对算例进行求解，结果证明了模型和算法是可行的，为疫情防控背景下的物流配送提供了启示。