一种基于改进金鹰优化算法的多配送中心多无人机核酸样品配送路径规划方法

摘要

本发明公开了一种基于改进金鹰优化算法的多配送中心多无人机核酸样品配送路径规划方法、包括以下步骤：S1、建立无人机动力学模型、无人机代价模型以及带时间窗的多配送中心多无人机核酸样品配送模型。S2、建立多无人机核酸样品配送路径规划的三维环境并对任务环境进行离散化处理，确定无人机的数量，无人机的起飞点以及终止点。S3、根据所述无人机动力学模型、无人机代价模型以及带时间窗的多配送中心多无人机核酸样品配送模型，采用在金鹰优化算法中引入梯度优化和柯西变异策略，通过所得到的基于梯度优化和柯西变异的金鹰优化算法(SGDCV‑GEO)对多配送中心多无人机核酸样品配送路径进行规划,获得多无人机核酸样品配送的最优路径。

说明书

技术领域

本发明涉及无人机城市物流配送领域，具体涉及一种基于改进金鹰优化算法的多配送中心多无人机核酸样品配送路径规划方法

背景技术

随着物联网技术以及无人机技术的飞速发展，无人机技术已应用到物流配送、农林植保、警务勘察等各个领域，给人民的生产生活带来了极大的便利。

疫情的全球范围性爆发为公众带来损害，核酸检测作为在当前环境下必不可少的举措无疑会增加外出感染的风险，核酸样品的无接触配送是当前炙手可热的话题。无人机样本运输配送网络具有分散采集，集中检测，随机响应，高时效运行，不产生聚集，不影响日常等特点。相对于车载运输和手提转运是一种更安全、可靠、低资耗、高可靠的系统化运输工具。在城市场景中，无人机冷链物流服务可实现全天候待命，形成随时随地触手可及的即时物流配送服务，更突破了地面交通影响。

在现有的技术中，通常采用传统算法及改进的智能优化算法实现无人机路径规划，但在现有技术的算法中，几乎没有将时间窗约束、无人机航时、载重、能耗约束、环境威胁等同时考虑完全的。无人机路径规划本身就是一个复杂且耦合的问题，同时将多种约束条件考虑完全，求解更是难上加难，现有技术中的算法很难在短时间内寻找出最优的航行路线。

本发明建立了一个带时间窗的多配送中心多无人机核酸样品配送模型，以配送时间最短、运输费用最低、无人机航迹代价和撞击代价最小为目标。在求解多目标优化的物资配送问题中精确算法显然不能满足条件，已有研究采用粒子群算法、模拟退火算法、遗传算法、差分进化及其改进算法进行模型的求解，但优化效果还可进一步提升。金鹰优化算法作为近几年新型的生物启发式算法在工程运输等领域有较好的应用前景。

目前的文章极少有同时考虑无人机配送时间窗约束、航时、载重、能耗约束等情况下的城市配送路径规划，并且几乎没有文章涉及到无人机具体配送过程中的真实环境威胁条件。

目前还没有专利将基于梯度优化和柯西变异的金鹰优化算法应用于无人机核酸样品配送的路径优化问题中。

发明内容

本发明充分考虑城市物流配送为背景下的多配送中心多无人机核酸样品配送路径优化问题的约束条件以及目标函数，与现有的研究不同，本发明将无人机动力学模型以及无人机代价模型引入无人机配送路径规划方案，以配送时间最短、运输费用最低、无人机航迹代价和撞击代价最小为目标建立数学模型，进一步提出了基于梯度优化和柯西变异的金鹰优化算法。该算法解决了传统优化算法求解多约束问题时收敛速度慢、收敛精度低等问题，从而设计出更加科学高效的核酸样品配送路径方案。具体的，本发明是这样实现的：基于梯度优化和柯西变异的金鹰优化算法的多无人机核酸样品配送路径规划方法，包括以下步骤：

步骤一、根据无人机的物理性能约束、真实环境约束等条件建立无人机动力学模型、无人机代价模型以及带时间窗的多配送中心多无人机核酸样品配送模型，如下所示：

无人机动力学模型：

将无人机从任意航迹i-1～i通过向量(x

其中

其中

无人机的总升力和总功率之间存在以下近似线性关系：

变换可得：

其中k和b均为常数。由功率及能耗之间的关系可得：

无人机在航迹段i内的飞行可表示为：

无人机代价模型：

无人机代价模型建立过程如下所示，

其中，α为城市遮蔽系数，m为无人机的重量，

带时间窗的多配送中心核酸样品多无人机配送模型：

核酸样品配送费用计算规则如下：

其中，

其中，

λ＞1的配送总时间：

其中，

因此，目标函数为：

无人机物理性能及真实环境限制等约束条件：

惩罚决策：无人机对取货点时间窗的惩罚决策，λ为超出取货点规定时间的惩罚系数且λ＞1；

检测中心服务能力约束：一个检测中心最多可服务六个取货点；

无人机执行任务约束：每个无人机最多可以到达两个取货点；

取货点约束：每个取货点都会被检测中心取货；

载重约束：无人机的载重不超过最大重量限制；

体积约束：无人机配送货物的体积不超过最大配送体积限制；

高度约束：无人机的飞行高度在允许高度范围内；

速度约束：无人机的飞行速度不超过最大飞行速度；

航时约束：无人机的航行时间不超过最大允许航行时间；

无人机飞行范围约束：无人机只能在规定区域范围内飞行；

无人机的转弯角约束：不能超过最大允许转弯角度；

无人机的爬升角约束：不能超过最大允许爬升角度；

无人机的最大平飞速度约束：不能超过最大允许平飞速度；

无人机的最大爬升速度约束：不能超过最大允许爬升速度。

其中，

步骤二、基于所建立的无人机动力学模型、无人机代价模型以及带时间窗的多配送中心多无人机核酸样品配送模型，采用金鹰优化算法，将核酸配送路径的寻优过程映射到种群狩猎的行为进化中，模仿种群中个体的交换信息，攻击和巡航等方式来对问题进行逐步求解。具体步骤如下：

步骤2.1、对金鹰种群位置进行初始化；

步骤2.2、初始化相关参数；

步骤2.3、根据目标函数值计算每个个体的适应度值，适应度值越小的个体位置越优；

步骤2.4、将无人机路径寻优的过程映射到金鹰种群交换信息、攻击搜索的迭代进化中，计算更新个体的适应度值，更新金鹰种群位置，直到搜索到个体最优适应度值时对应的位置。

步骤三、在金鹰优化算法中引入梯度优化和柯西变异策略，利用所改进的金鹰优化算法即基于梯度优化和柯西变异的金鹰优化算法(SGDCV-GEO)对多配送中心多无人机核酸样品配送的路径进行优化，从而得到最优的无人机配送路径。具体步骤如下：

步骤3.1：初始化金鹰种群数量及位置；

步骤3.2：计算适应度函数并初始化种群记忆位置；

步骤3.3：初始化攻击矢量和巡航矢量；

步骤3.4：更新金鹰位置，更新攻击矢量

攻击矢量

其中，

巡航矢量c

其中，c

步骤3.5：基于种群的记忆位置，计算攻击矢量，并选择猎物。选择猎物是基于随机梯度下降法进行的。提取随机梯度下降法中的非凸函数进行改进，其每次仅选择一个样本的特性与金鹰选择猎物的方式像匹配，在每次金鹰迭代的位置更新中，其更新公式为：

伪代码为：

步骤3.6：计算巡航矢量、步长矢量，更新位置并计算新位置的适应度函数。位置更新是基于柯西变异策略进行的。原金鹰算法中的围绕旋转的金鹰是随机选择的，因此在该处会不容易找到全局最优解。针对这个问题，选择柯西逆累积分布函数对金鹰进行变异，通过柯西分布的尾端较长的特点，让金鹰种群选择的旋转金鹰的范围更广。同时，该变异方法与金鹰种群随机选择金鹰进行旋转的特点相辅相成，进一步提高了局部寻优能力，避免了盲目变异。

柯西逆累积分布函数表达如下：

F

金鹰种群选择旋转金鹰时得到搜索公式如下：

其中，F

步骤3.7：更新最优解及最优位置；

步骤3.8：若达到最大迭代次数，则输出最优金鹰位置和全局最优解；否则，返回步骤 3.4。

本发明有益效果：

本发明提供一种高效的多配送中心多无人机核酸样品配送路径规划方法，以城市应急物流配送为背景，提出了一种以配送时间最短、运输费用最低、无人机航迹代价和撞击代价最小为优化目标的多配送中心核酸样品多无人机配送模型，考虑了真实环境下无人机自身性能、真实环境威胁、配送时间窗等多重约束条件。同时，为了提高无人机配送效率以及减少能源消耗，缩短无效的飞行航迹，采用基于梯度优化和柯西变异的金鹰优化算法(SGDCV-GEO)对所建立的模型进行求解，完成核酸配送任务。

附图说明

图1是基于梯度优化和柯西变异的金鹰优化算法(SGDCV-GEO)的流程图；

图2是医院与社区之间的距离矩阵；

图3是实验选用的无人机相关参数；

图4是某医院三维环境建模；

图5是四种算法优化路径结果；

图6是平均适应度曲线。

具体实施方式

为了使本发明的目的、技术方案以及优点更加清楚明白，下面结合附图与实例对本发明作进一步详细说明，但所举事例不作为本发明的限定。

实施例1：

本发明搭载配送箱的多无人机核酸样品配送路径优化方案至少有一架四旋翼无人机，一个满足核酸运输条件的配送箱。

本实例中一种基于改进金鹰优化算法的多配送中心多无人机核酸样品配送路径规划方法，采用以下步骤：

步骤一、根据无人机的物理性能约束、真实环境约束等条件建立无人机动力学模型、无人机代价模型以及带时间窗的多配送中心多无人机核酸样品配送模型，如下所示：

无人机动力学模型：

将无人机从任意航迹i-1～i通过向量(x

其中

其中

无人机的总升力和总功率之间存在以下近似线性关系：

变换可得：

其中k和b均为常数。由功率及能耗之间的关系可得：

无人机在航迹段i内的飞行可表示为：

无人机代价模型：

无人机代价模型建立过程如下所示，

其中，α为城市遮蔽系数，m为无人机的重量，

带时间窗的多配送中心核酸样品多无人机配送模型：

核酸样品配送费用计算规则如下：

其中，

其中，

λ＞1的配送总时间：

其中，

因此，目标函数为：

无人机物理性能及真实环境限制等约束条件：

惩罚决策：无人机对取货点时间窗的惩罚决策，λ为超出取货点规定时间的惩罚系数且λ＞1；

检测中心服务能力约束：一个检测中心最多可服务六个取货点；

无人机执行任务约束：每个无人机最多可以到达两个取货点；

取货点约束：每个取货点都会被检测中心取货；

载重约束：无人机的载重不超过最大重量限制；

体积约束：无人机配送货物的体积不超过最大配送体积限制；

高度约束：无人机的飞行高度在允许高度范围内；

速度约束：无人机的飞行速度不超过最大飞行速度；

航时约束：无人机的航行时间不超过最大允许航行时间；

无人机飞行范围约束：无人机只能在规定区域范围内飞行；

无人机的转弯角约束：不能超过最大允许转弯角度；

无人机的爬升角约束：不能超过最大允许爬升角度；

无人机的最大平飞速度约束：不能超过最大允许平飞速度；

无人机的最大爬升速度约束：不能超过最大允许爬升速度。

其中，

步骤二、基于所建立的无人机动力学模型、无人机代价模型以及带时间窗的多配送中心多无人机核酸样品配送模型，采用金鹰优化算法，将核酸配送路径的寻优过程映射到种群狩猎的行为进化中，模仿种群中个体的交换信息，攻击和巡航等方式来对问题进行逐步求解。具体步骤如下：

步骤2.1、对金鹰种群位置进行初始化；

步骤2.2、初始化相关参数；

步骤2.3、根据目标函数值计算每个个体的适应度值，适应度值越小的个体位置越优；

步骤2.4、将无人机路径寻优的过程映射到金鹰种群交换信息、攻击搜索的迭代进化中，计算更新个体的适应度值，更新金鹰种群位置，直到搜索到个体最优适应度值时对应的位置。

步骤三、在金鹰优化算法中引入梯度优化和柯西变异策略，利用所改进的金鹰优化算法即基于梯度优化和柯西变异的金鹰优化算法(SGDCV-GEO)对多配送中心多无人机核酸样品配送的路径进行优化，从而得到最优的无人机配送路径。具体步骤如下：

步骤3.1：初始化金鹰种群数量及位置；

步骤3.2：计算适应度函数并初始化种群记忆位置；

步骤3.3：初始化攻击矢量和巡航矢量；

步骤3.4：更新金鹰位置，更新攻击矢量

攻击矢量

其中，

巡航矢量c

其中，c

步骤3.5：基于种群的记忆位置，计算攻击矢量，并选择猎物。选择猎物是基于随机梯度下降法进行的。提取随机梯度下降法中的非凸函数进行改进，其每次仅选择一个样本的特性与金鹰选择猎物的方式像匹配，在每次金鹰迭代的位置更新中，其更新公式为：

伪代码为：

步骤3.6：计算巡航矢量、步长矢量，更新位置并计算新位置的适应度函数。位置更新是基于柯西变异策略进行的。原金鹰算法中的围绕旋转的金鹰是随机选择的，因此在该处会不容易找到全局最优解。针对这个问题，选择柯西逆累积分布函数对金鹰进行变异，通过柯西分布的尾端较长的特点，让金鹰种群选择的旋转金鹰的范围更广。同时，该变异方法与金鹰种群随机选择金鹰进行旋转的特点相辅相成，进一步提高了局部寻优能力，避免了盲目变异。

柯西逆累积分布函数表达如下：

F

金鹰种群选择旋转金鹰时得到搜索公式如下：

其中，F

步骤3.7：更新最优解及最优位置；

步骤3.8：若达到最大迭代次数，则输出最优金鹰位置和全局最优解；否则，返回步骤 3.4。

试验过程

本文算法编程工具采用MATLAB R2017a，操作系统为Windows 10，电脑内存16G，CPU为Intel i7-8750H。

无人机配送模型适用于于大范围的城市环境中，在进行智能优化算法进行无人机路径优化时，首先需要进行医院与社区的定点采集调度分配。本文依据上海市浦东新区的真实地理环境，采集了共8家医院、57家社区的距离矩阵，如图2所示，无人机配送相关参数取值如图3所示。

基于图2中的距离矩阵，得到医院和社区的位置坐标。根据无人机的最大航程和能耗代价进行模拟，得到无人机的路径分配。

对某医院进行三维环境建模，如图4。无人机出发点为[0，0，0]，目标点为[130，80，18]。利用本文所提出的SGDCV-GEO算法与模拟退火算法(SA)，粒子群算法(PSO)以及金鹰搜索算法(GEO)在内的三种算法进行对比。利用每种优化算法各30次优化的仿真实验进行对比，得到四种算法路径优化结果如图5所示，平均适应度曲线如图6所示。

以上显示和描述了本发明的基本原理、主要特征和本发明的优点。本行业的技术人员应该了解，本发明不受上述实施例的限制，上述实施例和说明书中描述的仅为本发明的优选例，并不用来限制本发明，在不脱离本发明精神和范围的前提下，本发明还会有各种变化和改进，这些变化和改进都落入要求保护的本发明范围内。本发明要求保护范围由所附的权利要求书及其等效物界定。