何宛澄

（武汉工程大学，武汉 430073）

无人机作为一种新型运载工具，能够在救援行动中发挥重要作用，为提高其使用效率，则解决无人机优化运用问题显得尤为重要。

无人机的行驶路线可看做旅行商问题（TSP），针对TSP问题，易云飞[1]针对粒子群算法求解旅行商问题时易陷入局部最优解的情况进行了改进，何庆[2]提出一种基于改进遗传模拟退火算法的TSP优化算法，林敏[3]将小数和整数结合，改进得出基因-表现型的布谷鸟算法。可以看出，有很多种智能算法用于解决TSP问题，本文对无人机运用简化成TSP问题，选用改进的遗传算法进行研究。

1 实际问题中的运用

1.1 背景资料

本文以四川阿坝州九寨沟县7.0级地震为实际研究对象，将考虑使用无人机巡查7个重点区域（A-G）中心方圆10公里（并集记为S）以内的灾情。假设无人机飞行高度恒为4200米，若所有无人机均从某基地H处派出，且完成任务后再回到H，希望在4小时之内使区域S内海拔3000米以下的地方尽可能多地被巡查到。因此，需要计算出无人机的需求量及飞行里程数及无人机的飞行路线。

1.2 地形图及重灾区范围绘制

根据已有灾区地形的数据，建立地形图并绘制7个重灾区与基地的相对位置，考虑具体约束条件，实现分析目标函数。读取3000米以下的数据高程，得到一个等高线图，如图1所示，其中蓝色区域表示3000米以下，进一步计算出图1中各个重灾区的区域面积，计算结果如图2所示红色区。

其中的约束条件和目标函数分别为：

巡查3000米以下区域的飞行时间（含返回基地）：T路+T巡≤4h

图1 灾区等高线图

图2 重灾区有效面积

1.3 飞行区域权重系数

根据图2的运行结果以及数据文件，可以得到红色区域的面积与受灾区的面积总和的比值，该比值即为权重系数，根据计算结果，其中各区域权重系数计算结果如表1所示。

表1 各重灾区域权重系数

从表2中可以看出，A区域权重系数最小，即表明该域3000米以下范围较少，海拔普遍偏高，受灾情况相较最轻。为了约束条件下尽可能多地被巡查到重灾区，考虑舍弃A区域。

1.4 无人机数量及飞行路线选择

问题简化为4小时内，在六个重灾区域内规划最少数量的无人机并优化路径，而飞行速度为定值，则时间越短的飞行计划安排其路径也最短，即转化为求时间最短的路径，无人机均同时为基地出发，巡查后回到基地，若多架飞机巡查路径不同，只要保证最长路径是满足4小时要求的，则其他路径一定满足。本文无人机问题则抽象为基于遗传算法的TSP问题，改进具体算法，利用matlab进行最优化路径规划，得到以下飞机安排表（见表2）。

从表2中可以看出来，4架无人机的时候虽然飞行的总距离为最短，但是无人机数量是最多的，且飞行时间超过4小时，因此舍弃该路径。当无人机数量为2架时，每架飞机任务量很重，飞行的距离也远，飞行时间也超过了4小时。因此，3架无人机的数量，飞行距离居中，时间在4小时以内，基本符合各约束条件，且与其他路径相比为最优解，即飞行路线为1.H-C-B-H；2.H-DE-H；3.H-G-F-H；

表2 无人机路径优化

2 结束语

本文对实际受灾地区建立了三维模型，对比了各重灾区与救援基底的相对位置，通过权重系数衡量了一定时间内救援的有效性。并将无人机行驶问题简化为旅行商问题，对在一定约束条件下的无人机行驶数量及路线进行了研究，通过设置约束条件和目标函数，运用Matlab软件实现改进的遗传算法，比较分析了3种不同数量无人机行驶的飞行总路程和总时间，综合考虑得出最优解即使用3架无人机执行救援任务，并给出了无人机的最优飞行线路。

[1] 易云飞，林晓东，蔡永乐.求解旅行商问题的改进粒子群算法[J].计算机工程与设计，2016，37（8）：2195-2223.

[2] 何庆，吴意乐，徐同伟.改进遗传模拟退火算法在TSP优化中的应用[J].控制与决策，2018，33（2）：219-225.

[3] 林敏，钟一文，刘比雄等.基因-表现型的布谷鸟算法求解旅行商问题[J].计算机工程与应用，2017，53（24）：172-181.