城市区域多物流无人机协同任务分配

李 翰, 张洪海, 张连东, 刘 皞

(南京航空航天大学民航学院, 江苏 南京 211106)

0 引 言

随着社会生活节奏的加快,城市物流需求量越来越大,对配送要求越来越高,物流无人机这种低成本、高灵活的运输载具越来越受到人们的青睐。同时,当前正处于新冠病毒肆虐期间,减少不必要的外出和人际接触成为阻断疫情传播的重要方式,进一步促进了无人机物流配送的发展,无人机物流已经成为全球物流业发展的重大趋势之一[1-2]。相较于单无人机,多无人机通过协同能够更高效地完成任务,符合城市无人机物流配送发展趋势。而多机执行任务往往具有范围大、数量多等特点,因此必须要考虑协同任务分配问题,其本质为建立无人机与任务目标之间的对应关系[3-5],实现全局层面的路径规划。

国内外众多专家学者对多无人机协同任务分配问题进行过研究。文献[6]提出了一种以无人机总巡航距离和使用无人机数量最少为目标的优化模型,并提出了多目标进化算法进行求解。文献[7]针对多无人作战飞机协同任务分配问题建立了一种扩展的多目标整数规划模型,采用量子粒子群优化(quantum particle swarm optimization, QPSO)算法求解最优方案。文献[8]针对异构多无人机完成攻击和毁伤评估任务的协同任务分配问题,提出了一种引力搜索算法与遗传算法相结合的混合算法,仿真结果表明,该算法可以快速、稳定地找到最佳解决方案。文献[9]以无人机能耗最小为目标函数,采用改进的聚类算法求解,通过数值模拟和物理实验表明,该方法可以为多无人机任务分配提供一种合理可行的解决方案。文献[10]建立协同多任务分配问题模型,采用多余负载竞拍方案减少非法劣解,通过实数编码建立粒子和实际分配方案之间的映射关系,解决实际分配问题。文献[11]针对反雷达作战中异构无人机编队协同任务分配的特点,提出了一种考虑时间窗的改进混合整数线性规划任务分配算法。文献[12]将多无人机协同任务分配问题转化为车辆路径规划问题,采用一种基于神经网络的自组织特征映射方法来解决任务分配问题,并与蚁群算法进行比较,结果表明了该方法具有可行性和有效性。文献[13]采用分布式任务规划策略,同时无人机在规划过程中进行评估,对不合理的任务分配结果进行重新规划。文献[14]考虑无人机可在站点进行充电的特点,提出了混合整数线性规划模型和滚动任务分配启发式算法,并在岛屿区域进行了验证。文献[15]建立带有时间窗约束和无人机性能约束的物流运输任务分配模型,并改进粒子群算法求解。文献[16]针对多架无人机进行载货运输的协同任务分配场景,提出了分布式控制器来保证固定的编队,仿真结果验证了该方法能够保障多无人机安全运输货物。文献[17]考虑了有限通信带宽条件下的多无人机组队任务分配问题,改进了基于一致性的竞拍算法(consensus-based bundle algorithm, CBBA),增加判断机制来确保任务分配的唯一性,以达到将多无人机分配给同一任务的目的。文献[18]提出了一种新的匈牙利方法来解决多任务分配问题,其中无人机的数量小于任务的数量,仿真结果表明该算法在所有情况下的性能均优于CBBA。文献[19]针对反雷达作战中异构无人机编队协同任务分配的特点,提出了一种考虑时间窗的改进混合整数线性规划任务分配算法。文献[20]针对异构固定翼多无人机协同任务分配问题,提出了一种多类型基因染色体编码策略的改进遗传算法,通过与随机搜索法、蚁群算法和粒子搜索算法相比,表明该算法具有更好的优化性能。文献[21]研究了一个基于无人机/无人值守地面车辆混合系统的复杂多任务问题,以完成任务所消耗的时间和能量最小化为目标,并提出了一种改进的动态规划算法,仿真结果表明该方法能够有效地减少时间和能量消耗。文献[22]针对应急救援下多无人机任务分配问题,提出了一种新的鱼类启发的多无人机任务分配算法(简称为FIAM),实验结果表明FIAM算法能够保持稳定的运行时间和减少平均救援时间,并大幅增加获救幸存者的百分比。文献[23]主要研究多无人机动态任务的实时分配问题,提出了一种基于agent的无人机群动态任务实时分配算法,根据大量的实验结果表明,该算法能够解决动态任务的实时任务分配问题,实现无人机群最佳作战性能。文献[24]针对有限时间约束下的三维多任务规划问题,提出了一种改进的蚁群算法,该算法通过引入变维向量系数和转移概率的时间自适应因子,降低了算法在次解集中的搜索概率,提高了算法的收敛速度。文献[25]提出了一种新的基于自适应参数调整和双向搜索的蚁群优化算法以求解多无人机协同任务分配问题,仿真结果表明该方法不仅可以有效地规划合理的航迹,而且可以解决不确定性问题,提高了多无人机的协同作战能力。

上述研究均提出了多无人机任务分配方法,但多是从军用作战无人机角度开展研究[7-8,10-11,14,19-20,23-25],部分研究则是转化为物流配送车辆调配规划问题[6,12,15,21],考虑影响因素较为单一。而在城市环境中进行物流配送需要考虑多种影响因素:一方面,城市物流配送任务点多、时效性强,需要充分发挥无人机灵活性强、速度快的优势,降低配送成本;另一方面,城市环境复杂,人口密集,作为新兴运载工具,在利用无人机进行配送时更要注重安全问题。如何综合考虑这些因素以对多无人机进行合理的任务分配仍然有待研究。

本文基于城市物流配送实际,考虑物流无人机性能、物流配送时效性、无人机飞行可靠性等影响因素,以最小化经济成本、时间损失、飞行风险为目标函数,构建代价最小的多约束多无人机物流任务分配模型,设计改进的QPSO (improved QPSO, IQPSO)算法,以获得最佳的任务分配方案。

1 物流无人机任务分配模型

1.1 问题描述与相关假设

假设某城市区域存在若干个物流需求点且位置已知,采用多架性能各异、可垂直起降的充电旋翼无人机进行物流配送。每架执行配送任务的无人机均从同一配送中心出发,完成所有任务后均返回配送中心。无人机出发后路径固定不变,不再接受新的任务指派。为了将物流配送任务在时间上和空间上最优地分配给多架无人机,需要在执行任务前进行合理的任务分配。城市区域多目标多机配送示意图如图1所示。

图1 城市区域多目标多物流无人机配送示意图Fig.1 Schematic diagram of multi-target and multiple logisticsUAVs distribution in urban areas

1.2 多机协同任务分配模型

1.2.1 决策变量

多无人机多目标任务分配的实质是为每架执行任务的无人机分配一条任务执行序列。设所有可被选用的无人机集合为U={U1,U2,…,UN}(简记为Ui);所有任务集合为T={T1,T2,…,TM,T0}(简记为Tj),其中T0为第(M+1)个任务(即有TM+1=T0),表示执行任务的无人机最终必须返回配送中心;{T1,T2,…,TM}表示需要执行的M个物流配送任务(M>N)。因此模型任务分配决策变量xij为

(1)

1.2.2 任务分配目标函数

(1) 经济成本

追求更低的配送成本是城市物流配送的重要目标,经济性是物流无人机配送的优势之一。无人机配送经济成本Cs包括无人机配送运输成本Cs1和无人机管理成本Cs2。

配送运输成本是指无人机在配送过程中产生的费用,包括电池能耗、折旧维护等费用,表达式为

(2)

式中:ηi表示无人机Ui的单位距离的运输成本;Lij为无人机Ui从当前位置飞至任务Tj的欧氏距离;特别地,无人机返回配送中心的任务TM+1所产生的运输成本也需要考虑在内。

此外,根据民航局发布的《轻小无人机运行规定咨询通告》,用于物流配送的无人机应予以有效管控,需要考虑无人机管理成本,表达式为

(3)

式中:cfi是指无人机Ui的管理成本;vi是指无人机Ui的飞行速度。

因此,采用物流无人机进行物流配送的经济成本Cs表达式为

Cs=Cs1+Cs2

(4)

(2) 延迟惩罚

配送时效性是物流运输所必须考虑的因素,顾客对物流配送的投诉多集中于时间超时。在城市实际物流配送中,顾客往往希望下单之后能够尽快送到,因此设置为单边软时间窗,若配送晚于客户要求的最晚时刻则存在延迟惩罚。设物流配送任务Tj可接受的时间窗为[0,Timej](返回配送中心无时间窗),若无人机在时间窗内将货物送达(到达并完成卸货),则无延迟惩罚;若无人机晚于最晚送达时间则存在惩罚,且延误时间越长,延迟惩罚越大。延迟惩罚Cτ的表达式为

(5)

(6)

(7)

(3) 安全风险

作为一种新兴的运载工具,安全性是采用无人机进行物流配送时必须要考虑的因素。需要从整个配送线路层面进行分析。编号为U1、U2的两架无人机从配送中心出发后,其配送路线之间相互独立,互不影响彼此的可靠性,类似于并联系统;而对于某一架无人机而言,飞行可靠性受配送线路上任务点数量和配送距离的影响,任务数量越多,飞行距离越长则剩余电量越少,可靠性越低,类似于串联系统。物流无人机配送串并联线路系统示意图如图2所示。

图2 物流无人机配送系统串并联线路示意图Fig.2 Schematic diagram of series and parallel lines of logisticsUAVs’ distribution system

设无人机可靠性为Cr,风险性为Cd,无人机配送安全风险表达式为

Cd=1-Cr

(8)

(9)

(10)

综上所述,本模型的目标函数C为

minC=α1Cs+α2Ct+α3Cd

(11)

式中:α1、α2、α3分别表示经济成本、延迟惩罚、安全风险的权重系数,且有α1+α2+α3=1。

1.2.3 任务分配约束条件

(1) 配送任务约束

物流无人机需要完成所有物流配送任务,同时每个物流配送任务只能由某一架无人机执行一次,满足约束为

(12)

(13)

(2) 货物载重约束

物流无人机在执行任务时所载货物质量不能超过载荷限制,满足约束为

(14)

式中:qj表示任务Tj货重;qi表示无人机Ui的载荷;qi(max)表示无人机Ui的最大载重。

(3) 飞行距离约束

每架无人机的航程有限,飞行距离不能超过最大航程,满足约束为

(15)

2 IQPSO算法

2.1 QPSO算法

QPSO算法[26]是孙俊于2004年提出的优化算法,借鉴量子力学中粒子行为特点,通过蒙特卡罗随机模拟方式来获得粒子位置,较好地改进了粒子群优化(particle swarm optimization, PSO)算法[27]搜索效率低、易陷入局部最优的缺陷。算法表达式为

(16)

pij(t)=ρpin(t)+(1-ρ)pg(t)

(17)

(18)

式中:u、ρ是在[0,1]上均匀分布的随机数;pmbest是种群平均最好位置;pξ(t)是第t次迭代时粒子个体的最优位置;pg(t)是第t次迭代时群体的最优位置;pij(t)是第t次迭代时粒子个体最优位置与粒子群体最优位置之间一个随机位置;Q是种群粒子的数目;W是粒子的维度;β是惯性权重(也称为收缩-扩张参数),是影响QPSO算法收敛速度的一个重要参数,可以为固定值,也可随着迭代次数动态变化。目前大多数学者对惯性权重采用线性递减策略得到迭代时的惯性权重值,表达式如下:

(19)

式中:βmax与βmin分别表示惯性权重的上下边界;t表示当前迭代次数;tmax表示最大迭代次数。通常β从1线性递减至0.5时能取得较好的结果。

2.2 IQPSO算法设计

传统QPSO算法虽然在一定程度上提升了算法性能,但依然存在以下问题:① 未对粒子种群初始值的选取做出规定。粒子初始化位置非常重要,合理的初始化可以增强搜索的多样性,有利于搜寻最优解;若选取不当则会使得算法很难搜索到全局最优解。② 在进行多次迭代时,易出现大量粒子趋同性,从而陷入局部最优解。③ 单个粒子搜索能力不强,算法全局搜索效率不高。

针对传统算法存在的不足,本文设计了以下改进方案:① 借鉴混沌理论,采用均匀化级联Logistic映射来初始化粒子,增强粒子的多样性和搜索遍历性;② 通过高斯概率分布引入扰动,对粒子进行变异;③ 设计自适应惯性权重处理方法,根据粒子的适应度好坏赋予不同粒子不同的惯性权重,以此提高粒子整体的搜索效率。

2.2.1 均匀化级联Logistic映射

1963年美国气象学家Edward Norton Lorenz提出混沌理论,指出混沌系统最重要的特性是具有随机性和遍历性。随机性使得搜索能够避免陷入局部最优,遍历性能够使迭代产生的解覆盖目标区域内所有的点,可以实现以任意精度逼近真实的最优解[28-29]。由于混沌系统的随机性、遍历性等特点,可以将混沌理论与QPSO算法相结合,以此提高算法的性能。Logistic映射是一种经典的混沌映射,数学表达式如下:

rn+1=μrn(1-rn)

(20)

式中:rn∈[0,1];μ∈[0,4]称为Logistic参数,当μ=4时,序列呈现出满映射状态,数值遍布整个值域空间。但是普通Logistic映射分布还不够均匀,所以本文在此基础上采用改进的均匀化级联 Logistic映射方式[30],对每个粒子位置进行初始化,表达式为

(21)

(22)

采用均匀化级联Logistic映射在[0,1]上完全遍历而且分布均匀,故可以有效提高种群的多样性和搜索的遍历性。

2.2.2 基于高斯分布的粒子变异

针对粒子的聚集导致算法陷入局部最优解的问题,通过高斯概率分布来引入粒子扰动,进行粒子变异。表达式如下:

pm(t)=pmbest+εH

(23)

式中:pm(t)是种群平均最好位置变异后的位置;ε是预先规定的参数;H是满足均值为0,方差为1的高斯分布。则原粒子位置表达式(16)变为

(24)

本文设置粒子群的变异范围随着代数的增加而降低,即在寻优初期作用于所有粒子,中期作用于部分粒子,后期则不再变异,促使粒子能够在最优解邻近区域进行精细搜索。高斯变异粒子作用范围与迭代次数关系如图3所示。

图3 高斯变异粒子作用范围与迭代次数关系Fig.3 Relationship between the action range of Gauss mutation particles and iteration number

2.2.3 自适应惯性权重

在QPSO算法中惯性权重的大小影响全局搜索能力与局部搜索能力。传统上对惯性权重的取值方式有固定取值、线性递减、非线性递减等。目前最常用的方法为线性递减,如式(19)所示。这种方法可以在迭代后期改善局部搜索的精度,存在合理性。但是在该方法中,同一代的粒子具有相同的惯性权重,不存在搜索能力的区分;如果算法在迭代过程中发生早熟,会使粒子很难跳出局部最优点,因此存在缺陷。

综合以上讨论,本文基于前人研究[31],采用自适应惯性权重的赋值方法,根据粒子适应度值的优劣来赋予不同粒子不同的适应度值。对于适应度好的粒子,惯性权重适当减小,注重寻找周围值;适应度差的粒子,惯性权重适当增大,重点寻找其他位置。这样每个粒子以不同的速度且有目标地向全局最优解的方向和位置移动,从而使算法的全局搜索能力与运行效率能够得到提高,表达式为

(25)

式中:βmax为设定的惯性权重最大值;βmin为设定的惯性权重最小值;fit(x)是粒子当前的适应度;fitworst是种群最差粒子的适应度;fitbest是种群最好粒子的适应度。

2.2.4 粒子编码方式

在粒子群算法中,每个粒子就是一个备选解,多个粒子协同进化寻优。寻求合适的编码方式来建立物流无人机任务分配方案与粒子对应关系,是应用粒子群算法求解问题的关键。本文采用实数编码的方式对粒子进行编码:设粒子维度W等于任务数量M,每个维度代表一个待执行的任务;粒子数值在[1,N+1)内变化,相同的整数部分表示同一架无人机执行任务,小数部分数值越大执行顺序越靠前;而每个任务只对应一架无人机。通过计算适应度值判定整个任务计划分配的优劣。任务分配方案与粒子间的映射关系示意图如图4所示。

图4 任务分配方案与粒子间的映射关系示意图Fig.4 Schematic diagram of mapping relationship between task allocation scheme and particles

2.2.5 改进算法流程

IQPSO算法流程的具体步骤如下。

步骤 1建立粒子群,设定粒子群粒子数目Q、惯性权重上界βmax和下界βmin、迭代次数tmax等,采用均匀化级联Logistic映射初始化每个粒子的位置。

步骤 2根据编码方式对粒子进行解码,根据多无人机任务分配数学模型,计算每个粒子的适应度值。

步骤 3寻找种群在搜索过程中所出现的个体最优位置pin和种群最优位置pg,记录其对应的适应度值,并根据式(18)求得粒子群的平均最优位置pmbest。

步骤 4判断是否满足进行基于高斯分布的粒子变异的条件,若满足则按照式(24)进行粒子位置变异和位置更新;否则转到步骤5。

步骤 5不进行粒子变异,按式(16)更新粒子位置。

步骤 6判断是否满足结束条件(达到最大迭代次数),若满足则退出循环,输出粒子群所得的最优个体和对应的适应度值;否则转到步骤2,进入下一次迭代。

3 仿真验证

3.1 仿真环境及参数设置

为验证本文模型和算法的有效性、合理性,使用Visual Studio 2019进行仿真实验。由于当前物流无人机配送仍处于测试或试运行阶段,各项成本的具体数据属于各公司的保密范畴,故本文仅对无人机的配送成本作粗略估计,从理论层面对模型和算法进行仿真验证。假设某配送中心共有8架性能各异的无人机可被选用,参数设置如表1所示;共需要执行20个任务点的物流配送,配送点分布如图5所示，参数设置如表2所示;其他实验参数设置如表3所示。

表1 无人机参数

表2 物流配送任务点参数

表3 其他参数

图5 物流配送任务点布局Fig.5 Logistics distribution task point layout

因为所建模型的3个子目标函数的取值范围存在较大的量级差别,所以在进行仿真实验时,对每个子目标函数值采用min-max标准化方法,使其取值落在[0,1]之间,表达式为

(26)

式中:f(x)max和f(x)min分别是各个目标函数的最大值和最小值,f(x)是子目标函数实际值,f′(x)是归一化后的数值。

3.2 仿真结果分析

为了比较算法性能,分别采用QPSO、IQPSO、遗传算法3种算法对所建模型进行求解。为公平比较,所有算法迭代次数相同,算法的种群规模亦保持一致。为避免偶然性,每个算法独立运行50次,每次进行200次迭代,取归一化后的平均值,记录每个算法所得最终结果如表4所示。

表4 3种算法实验结果比较

由表4可知,3种算法的适应度值分别为0.145 5、0.136 9、0.146 1。与QPSO和遗传算法相比,IQPSO算法的代价值分别下降了5.9%和6.3%,改进算法结果优势显著;而且改进算法在各个子目标函数均保持了较好结果,验证了改进算法的有效性和合理性。将IQPSO算法仿真实验中最优粒子对应的任务分配方案记录于表5,可以看出该任务分配方案共选用了7架无人机,通过协同合作完成了物流配送任务,且各架无人机均满足自身航程和载重约束要求,进一步验证了算法的合理性。根据表5最佳任务分配方案,其中配送顺序中0表示配送中心,飞行时长包括卸货时间。为形象描述每架无人机的任务执行顺序和飞行时间,绘制物流无人机飞行时序图,如图6所示。图中横坐标轴表示任务时间,从无人机自配送中心起飞后开始计时;纵坐标轴表示任务编号,所有无人机按照任务分配方案依序执行任务,较粗的条块表示无人机在任务处的卸货时长。

表5 最佳任务分配方案

图6 物流无人机飞行时序Fig.6 Flight time sequential of logistics UAVs

3.3 参数设置分析

目标函数权重{α1,α2,α3}和算法种群规模Q取值会对求解结果产生影响,因此采用对照实验法对参数取值进行分析。

3.3.1 目标函数权重分析

城市物流配送首先要保证安全,故安全风险权重α3不变,分析经济成本权重α1和延迟惩罚权重α2取值对结果的影响,进行21组对照实验,每组实验重复50次取平均值。将实验数据记录于表6,绘制变化趋势如图7。结合表6和图7进行分析可知,随着经济成本α1增大,经济成本在波动中逐渐下降;延迟惩罚则表现为逐渐增加的变化;安全风险略有下降的趋势;算法时长有所波动,但是变化不大。基于构建模型的目标函数并考虑算法时长,以实验10所得结果为最佳,则最优代价权重值为α1=0.225,α2=0.275,α3=0.500。

图7 目标函数权重值的影响Fig.7 Influence of objective function weight value

表6 不同目标函数权重对任务分配结果的影响

3.3.2 算法种群规模分析

固定上述最优目标函数权重系数不变,分析算法种群规模Q的取值对结果的影响。在该规划环境下进行12组对照实验,每组实验重复50次取平均值,将实验数据记录于表7,绘制变化趋势如图8。结合表7和图8进行分析可知,随着种群规模Q增大,经济成本、延迟惩罚和安全风险的数值虽有起伏,但是从整体看来均呈现逐渐下降的趋势。与此同时,算法时长则表现为近似线性增加的变化。显然种群规模越大,搜索的结果越多,越有可能获得更好的任务分配结果,然而却要付出算法时间的代价。而且从第5组之后的实验组,各个子目标下降幅度很小,但是算法运行时间却越来越长。综合上述分析,基于构建模型的目标函数并合理考虑算法时长影响,以实验6所得结果为最佳,则最优种群规模为Q=150。

表7 不同种群规模对任务分配结果的影响

图8 算法种群规模权重值的影响Fig.8 Influence of algorithm population size on weight value

4 结 论

本文基于城市区域多无人机多配送目标场景,构建了以经济成本最小、延迟惩罚最少、安全风险最低为目标函数的多机协同任务分配模型,贴合城市区域物流配送实际。在传统QPSO算法的基础上,融入均匀化级联 Logistics 映射、高斯扰动和自适应惯性权重等方式设计IQPSO算法。仿真实验表明,改进算法较传统算法所得结果更优,而且能够跳出局部最优解,可有效地获得最佳任务分配方案。本文方法可用于多物流无人机任务分配,且规划结果受目标函数权重系数、算法种群规模等参数影响。在不同环境和规划要求下,可采用本文参数设置分析方法进行分析得到最佳参数值。