路世昌，邵旭伦，李 丹

辽宁工程技术大学 工商管理学院，辽宁 葫芦岛125105

2021年7月，中国多省出现强降雨现象导致多地发生洪涝灾害，造成了人员与财产的损失。在发生大规模灾害后，迅速、有效地配送应急物资，是保障人民安全和救灾工作顺利进行的关键因素。国内外学者对自然灾害的应急物资配送做出了众多研究，例如，Mollah等[1]建立了一个成本优化模型进行救灾物资分配，并提出了基于混合整数规划和遗传算法进行求解。Sarma等[2]针对紧急情况下的人道主义救援建立了以总成本和总时间最小的、覆盖人口最大为目标的多目标灾后救助物流模型，利用LINGO 13.0优化求解器进行求解。Sabouhi等[3]提出了一个综合的疏散和分配物流系统，并提出了一种模因算法（memetic algorithm，MA）进行大规模的分配问题。Wei等[4]开发了一种混合蚁群算法对目标为开库成本、车辆固定成本和运输成本组成的总运营成本以及违反时间窗惩罚成本进行求解，以保证在应急物流总仓库位置和车辆路线的选择中做出快速正确的判断。

无人机的快速发展在运输物流、安全，灾害管理领域中同样发挥着重要作用，国内外各大公司也在积极推进无人机网络的构建，例如亚马逊于2016年公开测试Prime空运服务无人机、2021年7月DHL拟在欧洲使用4 000架货运无人机执行中程送货服务，以及顺丰2020年8月试飞的大型载货无人机、京东在上海亚洲消费电子展（CESAsia）期间展示的载货无人机，无不证实物流行业对无人机发展的重视。在研究领域，Liu等[5]建立了一种多旋翼无人机系统的功率消耗理论模型。Kirschstein[6]提出了一种用以描述无人机在不同环境条件和飞行模式下的能源消耗模型。Song等[7]提出了一个混合整数线性规划（MILP）公式来推导无人机的持续交付问题并开发了一种后退地平线任务分配（receding horizon task assignment，RHTA）启发式算法。袁建华等[8]设计了一种基于改进粒子群与滚动策略相结合的无人机路径规划与避障方法以解决无人机在三维环境中的避障与路径优化问题。范叶满等[9]设计了一种模拟退火算法对无人机三维运动的能效系数进行分析并找出山地作业情况下的能耗最优路径。Cheng等[10]针对多行程无人机路径问题，建立了一个考虑载荷量和飞行距离的非线性函数并提出分支-切割精确算法进行求解。

虽然无人机具有机动性、灵活性、低成本等明显优势，但由于飞行时间、载荷量等方面的限制，在大范围运输中难以应用。克服这种障碍的一种方法是使用大型地面运载工具组成混合运载系统，相对于其他传统大型地面运载工具，卡车-无人机协同运输具有显著优势，可以有效解决单无人机配送问题中无人机行程不足，运货量过小及单卡车配送问题中因道路或天气原因造成的无法面对面交接的情况，三种运输方式效果图如图1所示。Jeong[11]等考虑了包裹重量对无人机能量消耗的影响和存在禁飞区时无人机最后一公里运输问题，并提出了一个两阶段的搜索启发式算法以解决卡车-无人机混合运输路线。Othman等[12]将ALSD、NW-ALSDP、LSDP和NWLSDP四种模型作为寻找特殊结构的最小成本路径问题，用以解决卡车-无人机最后一公里配送问题。Yu等[13]对无人机配送后降落在无人车进行充电的路径问题进行了研究，并提出了GTSP-BASED算法解决客户访问顺序及寻找无人车进行充电的时间及地点问题。Murray等[14]建立了两种数学规划模型，并通过两种启发式算法进行求解，以解决大规模卡车-无人机配送问题。郭秀萍等[15]设计了一种三阶段的规划求解方法，对卡车-无人机联合配送模式的物流调度问题进行探究。彭勇等[16]提出通过卡车-无人机协同配送模式对新冠疫情严重地区进行配送，并设计嵌入简单启发式算法的混合邻域算法进行求解。Ponza[17]设计了一种模拟退火元启发式算法来解决卡车-无人机在最后一英里的配送问题。Moshref-Javadi等[18]针对货车与无人机联合作业的多模式运输系统，提出了运输路线优化规划的数学公式和启发式求解方法。

图1 三种运输方式效果图Fig.1 Effect of three transportation methods

综上可知，卡车-无人机协同运输对于解决存在障碍区的最后一公里配送问题有着明显的优势，本文研究洪涝灾害应急物资配送过程中，存在的大量积水导致传统卡车运输或无人机运输无法有效完成应急物资的配送问题。将整个配送过程分为两个阶段，第一阶段设计改进k-means算法将需求节点进行聚类划分，在有效避免存在极值使算法陷入局部最优解的同时确定卡车可到，且各需求点位置处于无人机配送范围内的卡车等待点。第二阶段提出阶段性规划算法，将改进A*算法与改进的非线性收敛因子的模拟退火鲸鱼算法进行结合，在保证运输车辆安全的同时，以最短运输时间将救灾物资安全且快速地运送至各需求点，为救灾物资配送问题的探究提出了一种新的思路。

1.1 问题描述

已知若干位于积水障碍区内的需求节点需求量，且卡车无法独立完成运输。卡车载货物及多架无人机进行救灾物资配送，首先确定各货车等待点具体位置，待卡车停至等待点后，所载多架无人机携带物资进行同时配送，完成配送后返回等待点卡车内进行充电或换电池操作。卡车载无人机依此途经各等待点，确保各需求点都被服务一次，需求都被满足的情况下使总配送时间最短，卡车-无人机协同救灾配送路径示意图如图2所示。

图2 卡车-无人机协同救灾配送路径示意图Fig.2 Schematic diagram of truck-drone coordinated disaster relief distribution path

问题假设如下：

（1）各需求点需求已知，且都会得到服务；

（2）卡车载重足够满足所有需求点需求；

（3）卡车只能停在等待点发射无人机；

（4）无人机以稳定的速度飞行，假设空气和重力的流体密度是固定的；

（5）无人机充电及电池更换时间包括载卡车运输中；

（6）每架无人机每次只能为一个需求点服务；

（7）无人机飞行范围有限制，且飞行距离受实时荷载量影响；

（8）所有需求点距最近等待点欧氏距离小于无人机最大航程一半；

（9）所有需求点需求小于无人机荷载量上限。

1.2 积水障碍区二维化处理

积水障碍区内各需求点由无人机进行空中配送，无人机飞行分为四个阶段：起飞、水平飞行、悬停、降落，无人机交付理想飞行模式如图3所示。即无人机在水平飞行过程中，可将建筑物等三维物体进行二维化处理。同时，考虑卡车最短路问题及积水障碍区避障问题，将目标区域进行方形网格化处理。由于积水障碍区多属不规则图形，这对求解避障最短路径问题提出难题，故此，本研究将在目标区域方形网格化处理的基础上提出不规则图形网格化处理方式。

图3 无人机配送飞行模式Fig.3 Drones delivery flight mode

首先确定目标区域位置，本文参考面积内插模型[19]进行积水障碍区不规则图形的方形网格化处理，处理图如图4所示，具体步骤如下。

图4 积水障碍区方形网格化处理图Fig.4 Square grid treatment of waterlogged obstacle area

步骤1确定所选取不规则图形所处方形网格。

步骤2确定各方形网格内不规则图形所占网格面积比重。

步骤3按照不规则图形占方形网格面积比重确定选取方形网格的横/纵坐标。当面积比重低于30%，则选取横/纵坐标小的方形网格，当面积比重大于30%小于50%时，选取中点坐标，当面积比重大于50%，则选取横/纵坐标大的方形网格。

步骤4考虑或存在积水面积大于不规则图形网格化后的方形网格以及为可能存在的短时间高强度降水做出预留量，将步骤3完成后所有方形网格坐标扩大0.5，以保证配送任务的顺利完成。

2.1 符号说明

为更直观表述模型，设置参数及变量表如表1所示。

表1 参数及变量符号说明表Table 1 Parameter and variable symbol description table

2.2 符号说明

可建立如下数学模型：

其中，式（1）表示卡车载无人机返回仓库最小时间；
式（2）表示由一辆卡车完成任务，卡车自仓库出发并返回仓库；
式（3）表示卡车流量平衡；
式（4）、式（5）表示各需求点有且只有一架无人机进行配送服务；
式（6）表示无人机只能从卡车等待区起飞进行配送；
式（7）表示无人机i不允许直接飞回仓库；
式（8）表示无人机i不能直接自仓库起飞配送；
式（9）表示无人机荷载量约束；
式（10）表示无人机从等待区w发射的最大飞行距离；
式（11）表示卡车离开仓库的时间为0；
式（12）表示卡车到达等待区i的时间；
式（13）表示卡车离开等待区i的时间；
式（14）和式（15）表示消去不完整无人机回路；
式（16）和式（17）表示消去卡车不完整行车路线；
式（18）～（20）为0-1变量约束。

无人机-卡车协同配送问题作为传统TSP（traveling salesman problem，TSP）[20]问题的延伸，显然也属于NPhard问题，针对NP-hard大规模求解问题，启发式算法具有更强的优越性，故此，本文提出一种两阶段启发式算法，对于卡车-无人机协同救灾物资避障配送问题进行求解。第一阶段，考虑受灾地区交通网线分布情况及需求点分布情况，将积水障碍区二维化，设计改进k-means聚类算法，将众多需求点分成不同簇类，并确定货车等待区具体位置。第二阶段提出阶段性规划算法，结合A*算法的避障性与改进模拟退火鲸鱼算法的全局快速寻优性确定最优配送路线，以保证救灾物资避障配送流程的安全且快速完成。

4.1 确定卡车等待区位置

救灾物资配送问题常见于城市居民楼簇或村庄村落，相对于传统TSP问题中客户节点的无序分布，救灾物资需求点分布更加规整化，同时，无人机运输在中高空飞行时不能利用地形因素进行避让，且飞行高度在一次任务中变化不大，航迹规划可以简化成二维网格图，二维网格图最常用的距离规划方法之一是曼哈顿距离[21]，其更接近实际距离，故此，各需求点位置间距的确定使用曼哈顿距离，需求点配送模式区别图如图5所示。

图5 需求点配送模式区别图Fig.5 Demand point distribution model difference diagram

相对于传统的k-means聚类算法每次选出簇内平均值作为聚类中心而导致可能会存在某个极值点使算法陷入局部最优解的情况，本研究所提出的改进k-means聚类算法，选取簇内中心点作为聚类中心，并设立值f(f≤(1/2)F)在解决算法遇极值易陷最优解的同时确保各需求点都在某架无人机服务范围内，具体卡车等待点确定过程如下。

步骤1将积水障碍区二维化处理。

步骤2选定n个簇内中心点作为初始聚类中心，簇内中心个数n为：

步骤3计算各需求点到聚类中心距离，将各需求点分配至最近聚类中心。

步骤4更新聚类中心根据各需求点位置以及需求量，确定客户节点是否稳定。

步骤5计算当前需求点离最近网格距离，并设定该网格上点为预等待点。

步骤6计算预等待点与各需求点距离是否小于等于f，若大于f则将该需求点更换至次近聚类，转入步骤4，若都小于等于f，则转入步骤7。

步骤7将预等待点更改为等待点，并输出优化后聚类结果。

具体算法流程图，如图6所示。

图6 改进k-means算法流程图Fig.6 Flow chart of improved k-means algorithm

4.2 阶段性规划算法避障路径确定

鲸鱼算法（whale optimization algorithm，WOA）是2016年由Mirjalili等提出的一种模仿自然界中鲸鱼捕食行为的新型群体智能优化算法，其具有易于实现，调整参数少以及鲁棒性强等优点，将改进A*算法与改进非线性收敛因子的模拟退火鲸鱼算法优点相结合，以实现全局高效避障路径优化。

4.2.1 改进A＊算法设置

A*算法作为最受欢迎的寻路算法之一，具有很强的灵活性，已被广泛应用于智能寻路、无人机突防等领域中。在算法搜索过程中，需构造open list与closelist两表，其中，open list用于记录已被计算但未被拓展节点，close list用于记录已被拓展节点，首先选择open list中代价最小节点，将其放入close list中进行拓展及分析，之后对open list与close list进行更新。赋予评估节点i权重，并选择代价最少的节点作为下一位置，重复此过程直至到达最终节点，其公式表达为：

其中，Gi表示从初始等待点s到指定方格的移动消耗，Hi表示从指定方格移动到下一等待点e的预计消耗。（Hi消耗使用曼哈顿距离计算）。

传统A*算法虽然计算速度快，但是在移动过程中，存在过多不必要的拐点以及冗余节点，影响算法整体速度，为降低计算复杂度，消除不满足路径规划约束子节点，本文设定方格搜索范围为朝向下一到达节点的最大转角小于等于90°的方格，即将可选择的8个方格缩减至5个，方格选择图如图7所示。

图7 方格选择图Fig.7 Grid selection chart

具体算法流程如下：

步骤1设立open list，从初始等待点s开始，将s点放入open list。

步骤2获取方向朝向下一等待点e的最大转角小于等于90°的方格，将它们放入open list，设置它们的父方格为s。

步骤3设立open list，从open list中删除初始等待点s，将s放入close list。

步骤4计算每个选定周围方格的F值。

步骤5从open list中选择F值最低的方格k，将其从open list中删除，移至close list中。

步骤6获取方格k朝向下一等待点e的最大转角小于等于90°的方格，其中，障碍方格（unwalkable node）和处于close list中的方格不予考虑，若考虑方格不在open list中，将它们加入open list中，并设置方格k为父方格。若选中相邻方格p到方格e的新路径，且该路径经过k节点，并进行判断。

（1）新路径G值更低，则修改父方格为方格k，重新计算F值，H值不变。

（2）新路径G值更高，说明新路径消耗高，则G值不变。

步骤7继续从open list中找出最小F值方格，将其从open list中删除，添加至open list中，如此循环。

步骤8目标路径已经在open list中，最优路径被找到。

4.2.2 改进鲸鱼算法设置

（1）非线性收敛因子

传统收敛因子α在WOA算法中会随着迭代次数的增加从2至0线性递减，在求解复杂优化问题时存在迭代前期搜索猎物不彻底，迭代后期种群个体多样性减少，陷入局部最优解的问题，因此，设计了一种非线性收敛因子α，使算法在迭代前期速度放慢，提高全局搜索能力，在迭代后期速度加快，对提高局部搜索的准确性，防止陷入局部最优，非线性收敛因子公式如下：

非线性收敛因子迭代图如图8所示。

图8 收敛因子迭代图Fig.8 Convergence factor iteration diagram

且鲸鱼个体Xi在最佳鲸鱼个体Xd的影响下的下一位置的计算公式如下：

（2）编码与解码

根据车辆路径常规编码分析，设计了一种M×M矩阵结构，将矩阵行设置为配送顺序，矩阵列设置为等待点排列，生成[0，1]矩阵。

卡车配送路径为1->3->2->7->6->4->5，则通过矩阵转化为整数编码为（0，1，3，2，7，6，4，5，0），其中0为出发仓库，表示卡车自仓库出发进行配送，最终返回仓库。

（3）种群初始化

鲸鱼个体适应度由总配送时间决定，故配送时间越小，鲸鱼体适应度越大。

其中，fi为鲸鱼个体Xi的适应度，zi为鲸鱼个体Xi的目标函数值。

（4）选择操作

为提高鲸群算法的精确度，采用精英保留策略与剩余随机抽样相结合，首先计算鲸群中每个鲸鱼个体在下一代的期望值ei。

其中，m为种群大小，fi为第i个鲸鱼个体的适应度。

然后将期望值ei的整数部分作为个体i在下一代的存活数，因此可以确定下一代e个体。

（5）鲸鱼个体位置更新

采用线性顺序交叉策略[22]，选择鲸鱼个体Xi当前位置信息，将其复制到鲸鱼个体Xi预位置，将预位置串中存在问题（元素相同）的基因进行修复，使预位置信息合法，鲸鱼个体位置更新图如图9所示。

图9 鲸鱼个体位置更新图Fig.9 Whale individual location update figure

（6）局部搜索操作

为了提高算法的精确性以及解的质量，采用逆转操作和插入操作以提高算法精度，将鲸鱼个体Xi上两个位置之间所有元素排列进行逆转，设N为配送节点数目。即鲸鱼W可表示为：

选择逆转位置为i和j(i≠j,i≥1,j≤N)，则将第i个和第j个位置之间所有元素逆转后的解可表示为：

执行插入操作，将第一个位置上选择的元素插入第二个位置上选择的元素后，则鲸鱼个体W可表示为：

若选择插入的位置为i和j，那么将第i个位置上的元素插入第j个位置上的元素后的解为：

（7）最优解选取策略

当前大多数群优化算法在求解复杂优化问题时，存在迭代后期种群个体多样性减少，陷入局部最优解问题，因此，本研究将模拟退火算法中的Metropolis抽样稳定准则与鲸鱼算法进行结合，以一定概率接受较差鲸鱼位置，从而提高算法跳出局部最优解的能力。

首先计算更新解前后差值Δf,Δf=f(xj)-f(xi)，若Δf≤0则接受新解并且替代当前解，若Δf＞0则需要计算该点接受概率，通过计算目标函数的差值对比当前概率。

其中，t代表当前温度，并产生一伪随机数c，符合区间[0，1]之间的均匀分布，若P(Δf)≤s，则使用当前新解，否则，弃用新解仍使用原点进行下一次的Metropolis过程。

阶段性规划算法流程图如图10所示。

图10 阶段性规划算法流程图Fig.10 Stage planning algorithm flow chart

为验证所提出两阶段启发式算法的有效性，本文采用两个2021年7月国内受灾区域实际地理位置数据，结合当地等高线、俯拍图等，选取两个区域6个居住集群中50个节点作为救灾物资配送需求点。卡车载5架无人机自仓库出发，由于天气、积水原因，卡车行驶速度为30 km/h，无人机飞行速度恒定为30 km/h，无人机服务半径为15 km且无人机悬停取货时间为20 min。需求点分布图如图11所示。

图11 需求点分布图Fig.11 Demand point distribution map

5.1 卡车等待点确定

将需求点分布图二维网格化，按照1方格边长=150 m的换算比例将网格化后的需求点分布图置于110×100的网格图中，并将需求点网格图进行简化处理，确定仓库及各需求点具体位置，仓库编号设置为0，二维方形网格化流程图如图12所示，仓库及需求点坐标如表2所示。

表2 仓库及需求点坐标表Table 2 Coordinate list of warehouse and demand point

图12 需求点二维网格化图Fig.12 Two-dimensional gridding map of demand points

通过需求节点的改进k-means聚类操作，按卡车等待点确定步骤确定10个卡车等待点及其所服务的需求点如表3所示，完成算法第一阶段。

表3 卡车等待区服务表Table 3 Truck waiting area service table

5.2 避障路径确定

依据所提出的阶段性规划算法，进行避障路径确定，将10个等待点及仓库位置信息带入算法，应用Matlab2016a进行求解，所得最优结果如表4所示。

表4 救灾物资避障配送优化结果表Table 4 Disaster relief supplies avoidance distribution optimization results table 单位：min

卡车自仓库出发，按照0-10-4-3-1-2-5-6-7-8-9-0的顺序一次行驶至各等待点进行无人机配送，最后返回仓库，卡车共计行驶52.643 km，其中部分等待路径优化图，如图13所示。

图13 部分等待点避障路径优化图Fig.13 Part of waiting point obstacle avoidance path optimization map

5.3 算法对比

为进一步验证本研究所提出算法有效性，针对本文实例，采用：（1）本研究所提出两阶段启发式算法求得最优路径；
（2）k-means聚类算法与遗传算法计算最优路径；
（3）k-means聚类算法与Dijkstra算法计算最优路径；
（4）本研究第一阶段聚类算法与遗传算法计算最优路径；
（5）本研究第一阶段聚类算法与Dijkstra算法计算最优路径进行对比，实验对比结果如表5所示。

表5 五算法对比表Table 5 Five-algorithm comparison table单位：min

图13

从卡车最短配送时间、无人机最短配送时间与最小配送总时间三个方面及对五种算法进行对比，算法对比图如图14。

图14 五算法对比图Fig.14 Five-algorithm comparison chart

从实验结果看，本研究所提出的两阶段启发式算法在求解救灾物资避障配送路径优化问题时能力最优，对比（2）、（3）、（4）、（5）算法，所提出算法最小配送总时间方面分别优化4.76%、4.26%、3.14%和2.61%。可发现所提出两阶段启发式算法综合了改进A*算法避障性与改进鲸鱼算法快速全局精确搜索的优势，在保证配送安全的前提下，快速运输救灾物资，使灾区群众生命安全在第一时间得到保障。

为保障灾区人民生命安全，快速将急需物资运送至处于积水区、大型载货工具无法运至需求点的问题，本研究采用卡车-无人机协同运输的方式进行救灾物资的避障配送，建立了以总配送时间最短为目标函数的优化模型，并提出了一种两阶段启发式算法解决此问题。首先将积水障碍区、仓库及各需求点进行二维网格化处理，运用改进k-means算法将所有需求点以无人机数量，无人机飞行半径为约束进行聚类，并确定各卡车等待点具体位置，创建阶段性规划算法，设计改进A*算法，规定搜索方向性有效提升A*算法速度，同时设计非线性收敛因子的模拟退火鲸鱼算法，使算法在迭代前期速度放慢，提高全局搜索能力，在迭代后期速度加快，提高局部搜索的准确性，同时加入Metropolis准则，以一定概率接受较差鲸鱼位置，防止算法陷入局部最优的困境。有效减少卡车及无人机运输时间，通过实例仿真可以看出，所提出的两阶段启发式算法在选定等待点及优化避障配送路径方面都具有优势，为解决救灾物资的避障配送问题提出了新的思路。

在后续研究中，会进一步考虑不同风向及风力等级差异对无人机飞行距离产生的影响以及在实时运输中需求点需求量突增导致的二次配送等问题。

猜你喜欢 方格鲸鱼卡车 小鲸鱼幼儿100(2022年41期)2022-11-24方格里填数数学小灵通(1-2年级)(2021年12期)2021-12-30方格里填数数学小灵通(1-2年级)(2020年12期)2021-01-14迷途鲸鱼数学大王·趣味逻辑(2020年9期)2020-09-06鲸鱼小天使·二年级语数英综合(2019年4期)2019-10-06卡车赛收官对决汽车观察(2018年12期)2018-12-26忙碌的卡车小学生必读(低年级版)(2018年9期)2018-12-13分方格小学生导刊(2018年16期)2018-11-30鲸鱼岛——拖延症动漫星空(2018年4期)2018-10-26分方格小学生导刊(2018年1期)2018-03-15