基于GA-SA组合算法的山区复杂环境无人机起降点选址

李章萍, 贺亚蒙

(中国民航大学交通科学与工程学院, 天津 300300)

随着前端科技不断创新,无人机技术不断成熟,无人机货运时发展的新趋势,发展无人机货运,起降点的选址分配是重点环节,是保证高效安全运输的关键。

目前,中外对于无人机货运研究的重点主要集中在城区物流末端配送环节,王垚等[1]对无人机任务分配问题转化为多旅行商问题,并将Metropolis准则引入遗传算法,分别求解不同规模的旅行商问题,验证改进算法的适用性;刘书山等[2]针对无人机的航迹优化问题,引进了全局搜索能力强的遗传算法和局部收敛速度快的模拟退火算法相结合的GA-SA组合算法,并将问题转化为旅行商问题进行求解,结合了两种算法的优势,本文研究将该思路应用到无人机的选址和任务分配问题研究中;宋育武等[3]无人机群体任务分配研究中建立了整数线性规划任务分配模型,但是仅仅以时间消耗最短为目标,目标函数较为单一;Zhang等[4]提出了一种无人机任务分配多目标优化方法,即最大化成功分配任务数量、最大化任务效益、最小化资源成本、最小化时间成本,并采用克隆算法进行求解;郭兴海等[5]将区块链思想引入拍卖算法中来解决最后一公里物流配送的任务分配问题,对无人机编队任务分配进行优化计算,计算方式由集成中心式计算转变为分布式计算;张连东等[6]以运输成本最小和客户满意度最大为目标函数,设计改进遗传算法,采用含精英保留的多轮盘赌选择机制和多种交叉与变异方式相结合的方式。这些有关城区末端无人机物流配送起降点的研究有些将问题简化为普通的物流中心选址问题,未考虑无人机飞行的特点以及自身设备的性能约束;有些未能考虑空域的可达性约束对分配结果的影响;有些未考虑备选起降点是否与潜在需求点需求规模匹配;有些研究考虑约束因素单一,与实际应用场景不符。

由此还可以看出,目前大量无人机应用研究集中在城区末端物流配送到终端用户这一环节[7],物流前端货物集散的无人机应用研究较少。特别是中国幅员辽阔,很多货物产地地处山区,地面交通运输困难,采用无人机进行前端货物运输能够节省时间成本;另一方面,在山区突发自然灾害条件下,特别是发生地震、泥石流等难以短时间内组织救援人员抵达灾害现场,无人机可迅速响应并承担运输医疗救援包以及食物等应急物资的任务[8]。

因此,现从无人机货运效率出发,以起降点综合建设成本最低和货物运输时间满意度最大为目标函数,建立无人机起降点的选址和任务分配模型,并设计遗传算法和模拟退火(GA-SA)组合算法进行模型仿真求解,得到最优选址方案,并对相关参数进行灵敏度分析。

1 货运无人机起降点选址分配问题建模

1.1 问题描述

中国四川雅江县山区存在多个货物运输需求点,现考虑采用货运无人机方式进行局部货物运输集散。假设该地区内所有货物均有能够垂直起降的充电式中型旋翼无人机完成运输任务,在具备货物集散和无人机起降的备选起降点中,得出满足选址模型要求的最优选址分配方案。单架货运无人机单次货运任务包含往返双程,即空载前往运输需求点和载货返回无人机起降点。以起降点选址建设综合成本和运输货物时间满意度为目标,研究该地区最优选址分配方案。

为简化计算过程,本文研究做以下假设[9]:①为方便计算,将起降中心和货物运输需求地区简化为点进行讨论;②仅考虑单类型货物运输;③所有货运无人机速度恒定;④不考虑货物装卸时间和成本。

1.2 货运无人机起降点选址模型

本文所建立的货运无人机起降点选址模型是多约束条件下的多目标函数模型,约束条件包含物流中心选址约束和货运无人机的性能约束两方面,从起降点的建设综合成本和货物运输时间满意度两方面综合考虑,建立货运无人机起降点选址分配模型。

1.2.1 目标函数

(1)综合建设成本。

(1)

式(1)中:Cz综合建设成本;I为备选起降点集合;i为备选起降点编号;j为运输需求点编号;xi为0-1变量,表示在备选地址i处是否建立起降点;p为起降中心固定建设成本;aij为0-1变量,表示备选地址i和运输需求点j是否发生实际的货物运输;Dj为运输需求点j的运输需求量;m为货物在起降点的单位管理费用;dij为备选起降点i到运输需求点j的距离;c为无人机单位空载飞行成本;n为无人机单位负载运输成本。

(2)运输时间满意度。山区多为时效性较强类货物的产地,因此对运输时间较为敏感,此处考虑货物对运输时间的要求,引入运输时间满意度作为目标函数之一,本文研究采取线性时间满意度函数,运输时间满意度随着运输时间增长而均匀降低,其函数图像如图1所示。

(2)

t为运输时间;s(t)为运输时间的函数值;t1和t2为分段函数s(t)的分段点

式(2)中:S为全局运输时间满意度;S(tij)为单次运输任务时间满意度随时间变化函数;tij为备选地址i和运输需求点j的单次运输配送时间;fij为备选地址i和运输需求点j运输次数。

(3)

式(3)中:t1和t2为时间满意度函数中的定值参数。

第二个目标函数为运输时间满意度最大化。根据线性运输时间满意度的定义,得出无人机单次运输任务的时间满意度计算公式,以加权运输时间满意度为时间满意度目标函数。货物运输时间tij为

(4)

式(4)中:J为需求点集合;v为无人机的平均飞行速度。

1.2.2 约束条件

(1)点对点约束。每个运输需求点j由且仅由一个运输起降点i与之对应,约束条件为

(5)

(2)起降点数量约束。起降点数量不能超过备选场址数量,约束条件为

(6)

式(6)中:Z为备选无人机起降点数量。

(3)起降点容量约束。起降点负责的运输需求点的货物不能超过起降点的容量,约束条件为

(7)

式(7)中:Wi为备选起降点容量。

(4)配送范围约束。所有运输需求点均应在对应起降点的配送范围内,约束条件为

aijdij≤Li, ∃i∈I,∀j∈J

(8)

式(8)中:Li为备选起降点的配送范围。

(5)运输时间满意度约束。对每个运输需求点j,运输时间满意度要达到最低标准,约束条件为

dij≤dmax, ∃i∈I,∀j∈J

(9)

式(9)中:λi为运输需求点j的最低时间满意度;dmax为无人机最大航程。

(6)飞行航程约束。无人机的飞行航程不能超过自身设备性能所允许的最大航程,约束条件为

dij≤dmax, ∃i∈I,∀j∈J

(10)

(7)无人机飞行高度约束。飞行高度要在指定空域高度内,约束条件为

Hmin≤H≤Hmax

(11)

式(11)中:Hmin和Hmax为允许无人机飞行的最小高度和最大高度。

(8)无人机载重约束。无人机单次运输不得超大载重,约束条件为

qij≤Q, ∃i∈I,∀j∈J

(12)

式(12)中:Q为无人机最大载重量。

(9)空域约束。起降点与运输需求点间的路径处于不适航或者禁飞空域时,为空域不可达,无法执行运输任务,约束条件为

(13)

1.2.3 模型建立

根据1.4.1节和1.4.2节中的目标函数和约束条件的确定,即可建立物流无人机起降点选址分配模型,其模型为

(14)

(15)

s.t.

(16)

(17)

(18)

aijdij≤Li, ∃i∈I,∀j∈J

(19)

(20)

dij≤dmax, ∃i∈I,∀j∈J

(21)

Hmin≤H≤Hmax

(22)

qij≤Q, ∃i∈I,∀j∈J

(23)

βij=1, ∃i∈I,∀j∈J

(24)

在上述模型中,式(14)和式(15)为模型目标函数,式(16)～式(21)为模型约束条件,包括无人机起降点中心的约束,运输需求点方面的约束,式(22)～式(24)为物流无人机的性能约束,相关空域是否适航由参数βij体现。

2 算法设计

根据所建立模型,对遗传算法进行设置,具体设置如下。

2.1 编码

所求解的问题本质上是一个选址分配问题,编码要能够体现每个方案的要求,因此采用符号编码方法进行编码。针对染色体个体,设计j+i个基因表示无人机起降点和运输需求点之间的对应关系,每个染色的1～j个基因表示运输需求点的编号,(j+1)～(j+i)基因表示备选起降点的编号。现假设有6个运输需求点,最多允许4个起降点负责货物运输任务,那么其中一种可行的染色体表达方式为[1,2,7,3,4,8,5,9,6],其中1～6表示运输需求点编号,7～9代表无人机起降点,其将6个需求点划分为4段,表示4个备选起降点全部启用。第一个起降点编号为7-6=1,表示备选起降点1负责编号1、2的运输需求点;第二个起降点编号为8-6=2,表示备选起降点2负责编号3、4的运输需求点;第三个起降点编号为9-6=3,表示备选起降点3负责编号5的运输需求点,备选起降点4负责编号6的运输需求点。

2.2 生成初始种群

通过随机的方式,以空域是否可达为标准判断备选起降点是否能够被选择,在满足空域约束和其他约束条件的限制下,生成适当规模大小的初始种群。

2.3 适应度函数设置

由于本文建立的模型是一个多约束条件下的多目标函数,其中包括最小值规划问题的同时,还包含了最大值问题,两个目标函数的函数值量级差距较大,因此借鉴城区物流无人机任务分配问题,建立两个目标函数的隶属度函数[10]进行目标函数模型处理,原理如下。

(1)首先,在满足选址模型所有约束条件的前提下,分别计算出两个目标函数的最大值与最小值,并以此结果为分量构建边界向量即Mmax=(Czmax,Smax),Mmin=(Czmin,Smin),其中Czmax、Czmin为式(1)的最大值和最小值,Smax和Smin为式(2)的最大值和最小值。

(2)其次,定义各目标函数的隶属度函数为

(25)

(26)

式中:Czs∈[0,1]、Ss∈[0,1]分别为综合建设成本和运输时间满意度目标函数转化后的隶属度函数。

(3)最终,将两个目标函数的隶属度函数通过分配不同权重转化成模糊目标函数求解,因此适应度函数设置为

F(x)=max(α1Czs+α2Ss)

(27)

式(27)中:F(x)∈[0,1)为适应度函数;α1和α2分别为建设总成本目标函数和运输时间满意度函数的权重系数,α1、α2≥0且α1+α2=1。

2.4 选择

选择算子是算法进行迭代的一个关键,其本质就是从当前所有的基因池中选择更适合下一代繁衍的子代作为下一个循环的父代,直到达到收敛条件,具体操作就是选择适应度函数值大的,且适应度值与被选中的概率成正相关。本文研究采用轮盘赌法,计算每个个体被选择进入下一代的概率,即

(28)

式(28)中:Fi为第i个个体的适应度函数值;N为种群规模大小;Pi为选中第i个个体基因的概率。

2.5 交叉变异

将选择环节中选择的优秀个体进行交叉算子操作,将两个染色体的基因进行交叉,从而产生基因结构更复杂、个体表现更优良的个体,并且按照算法设置的变异概率对基因的片段进行变异操作。

交叉算子操作中,交叉的概率设置会直接对算法的收敛性产生影响,在常规的遗传算法中交叉概率设为定值,如果该参数值设置过大会导致算法前期迭代过程收敛速度过快,迭代后期缺少新个体的产生,适应度是过于平缓,可能造成个体表现优秀的染色体基因遭到破坏;定值设置过小会导致迭代速度缓慢,效率低下。

根据GA算法交叉的基本原理,本文研究取缔传统算法中交叉概率参数固定的做法,采用自适应交叉概率[11],根据算法中种群迭代过程中适应度值的变化,对交叉概率的值进行动态调整,提高全局搜索能力。

(29)

式(29)中:Fmax为当前种群个体适应度最大值;Fb为进行交叉操作的个体中的适应度较大值;Fa为每一代种群中的适应度平均值;Pc1、Pc2∈(0,1)为交叉操作的相关概率参数。

采用自适应度动态交叉概率,能够效避免只用子代进行筛选时有可能破坏掉“父代出现了适应度很高,但后来由于交叉破坏掉其适应度形成劣势子代”现象。

2.6 融合算法操作

首先通过改进遗传算法进行模型的初步求解,将适应度值较高表现优良的个体保留下来作为模拟退火算法的初始种群,如此可以提高算法的局部搜索能力。根据初始种群设置初始温度,设置温度衰退系数,进行模拟退火操作。初始温度和退火函数为

(30)

Tk+1=εTk

(31)

Pa=e-ΔF/Tk

(32)

式中:T0为退火操作初始温度;Tk为经过k次退温操作后的温度;ΔF为适应度函数值得极差;Pa为相对接受概率;ε为温度衰退系数。

2.7 终止条件

达到设置的迭代次数。

3 算例分析

3.1 算例描述及参数设置

为验证所提模型和算法的有效性,采用MATLAB R2016b进行模型仿真实验,模拟某山区40 km×40 km×0.2 km范围内的无人机货运场景,现假设该区域内有50个货运需求点和5个无人机起降点备选中心,其分布情况如图2所示。各个需求点的需求量如表1所示。

表1 运输需求点需求规模Table 1 Scale of demand

红色叉号及右边数字表示运输需求点及其编号;绿色菱形及右边数字表示备选无人机起降点及其编号

为尽量贴合无人机货运中心选址和任务实际规划过程,无人机起降点的参数设置如表2所示。

表2 无人机起降点参数设置Table 2 Landing point parameters of take-off

对比目前市场上的无人机机型,对本文研究中采用的无人机进行性能参数设置如表3所示。

表3 无人机参数设置Table 3 Parameters of UAV

有关客户满意度函数中的参数设置,每个运输需求点的最低满意度取0.5。

第二步采用模拟退火算法的相关参数设置为:初始种群规模为50,两个目标函数的隶属度函数所占权重分别为0.6和0.4,变异概率Pb为0.002;Pc1为0.4;Pc2为0.6;ε为0.99;迭代次数500。

3.2 结果仿真分析

基于以上仿真环境设置和参数界定,首先通过遗传算法对模型进行仿真求解,得到一个较优解,然后通过模拟退火算法调用遗传算法的解作为初始解,进行第二步的仿真模拟最终得到无人机起降中心选址和任务分配结果(图3)。

红色叉号及右边数字表示运输需求点及其编号;绿色菱形及右边数字表示备选无人机起降点及其编号

由图3可知,当在5个备选起降中心选择编号为2、3、4的无人机起降点时,适应度函数最优为0.657 15,对应的起降点建设总成本为996 263.233 6元,运输时间满意度为0.895 17。

为分析本文采取的组合算法的优良性,保持仿真环境和参数不变,单独采用模拟退火算法进行模型求解,并对两种算法的迭代过程和结果进行比较,如图4所示,对比中能够直观看出,本文研究中采用的组合算法迭代结果最终的适应度函数值更高,迭代过程收敛速度更快,对模型的仿真效果更好,表明采用的GA-SA组合算法在研究无人机起降中心选址和任务分配问题,具有较好的适用性。

图4 算法迭代过程对比Fig.4 Iterative comparison

3.3 参数灵敏度分析

在利用组合算法对模型进行仿真分析时,参数的设置会对收敛速度和最终迭代结果产生影响。本文采用控制变量法,探究空域约束和需求量变化对规划结果的影响[12]。

3.3.1 空域约束分析

通过设置0-1矩阵来表示运输需求点和无人机起降点备选中心的可达性,通过调整可达矩阵来实现空域条件的改变,分别增加和减少禁飞区域,图5和图6分别为减少和增加禁飞区域后的布局规划方案。

图5 减少禁飞区域Fig.5 Reduce no-fly airspace

图6 增加禁飞区域Fig.6 Increase no-fly airspace

调整可达矩阵减少禁飞区域的情况下,选择编号1、3、4的起降点为最优方案,布局方案的建设成本为925 263.217元,运输时间满意度为0.915 11;增加禁飞区域时,选择编号1、2、5的起降点为最优方案,最优布局方案的建设成本为1 119 670.093 6元,运输时间满意度为0.730 82。

综上分析,不同空域约束条件下,山区无人机起降中心选址以及任务分配结果会有较大差异。当禁飞区域较多,可达矩阵的可达性较弱,无人机起降中心会负担距离较远的运输需求点,飞行里程增加,导致成本升高,全局运输时间满意度降低;反之,整个区域可达性增强,无人机起降中心会率先负责较近的运输需求点,飞行里程减少,成本降低,全局运输时间满意度提高。因此,山区的地形环境越复杂,模型中的空域约束条件增多,无人机起降中心的建设成本增加,全局运输时间满意度降低。

3.3.2 需求规模分析

在最初参数不变的基础上对需求点的需求量扩大到原来的2倍和缩小至原来的1/2来对需求规模进行灵敏度分析[13]。图7和图8分别是增加需求规模和减少需求规模后的布局方案,经过算法模型求解,在扩大需求规模的情况下,综合建设成本为2 011 439. 956 9元,运输时间满意度为0.800 059;减小需求规模的情况下,综合建设成本为620 733.308元,运输时间满意度为0.935 44。

图7 增加需求规模Fig.7 Increase the size of demand

图8 减少需求规模Fig.8 Decrease the size of demand

当需求规模不同时选址布局方案也会发生变化,随着需求规模扩大,起降点运输任务量增加,综合建设成本随之升高,当需求规模超过一定范围时,因为备选起降点的规模并未改变,需求点不能够被就近的起降点满足,导致选址分配结果较原方案会有较大改变;当需求规模缩小,建设成本会随之降低,运输时间满意的也得到提升,但是备选起降点的容量过剩,且个别起降点负担较重,整个布局并不均衡,因此备选起降点的选择要与需求规模相匹配[14]。

4 结论

以建设总成本最小和运输时间满意度最大为目标函数,综合考虑无人机的性能与空域限制等问题,构建了物流前端无人机货运起降点的选址和任务分配模型,设计改进了遗传算法和模拟退火算法的组合算法进行求解,并通过仿真验证了该算法在解决此类问题具有较高的适用性和模型的合理性,并得出以下结论。

(1)空域约束条件不同的情况下,起降点的建设成本会有较大差异。山区地形环境越复杂,飞行条件越苛刻,选址模型的空域约束越多,起降点的建设成本越高。

(2)当需求量的需求规模不同时,选址布局方案也会有所不同。当需求规模过大时,备选起降点规模未改变,需求点需求难以满足,整体时间满意度降低;当需求规模变小时,备选点容量过剩,局部起降点负担过重,选址布局失调,因此备选起降点要与需求点的需求规模相匹配。

随着物流产业的不断发展,无人机物流是大势所趋,目前有关城区末端配送无人机应用研究有很多,但是受人口密度,空域限制等诸多因素影响,全面普及需要一定的时间,而在山区等地进行无人机货运是无人机发展应用的新趋势,在服务经济等同时,还能在自然灾害突发时为公共安全提供保证。