基于改进蚁群算法的动态航路规划研究

武丁杰，邹德龙，葛 昆

（中国民用航空飞行学院 空中交通管理学院，四川 广汉 618307）

0 引 言

随着我国民航业的发展，航路航线上危险天气等气象要素对航空运输的影响越来越显著。而目前针对该问题的处理方式，仍为人工判别，自动化程度较低，这不仅增加了空中交通管制员的工作负荷，还给我国民航运输业带来了不便。不仅如此，由于天气预报的不确定性，空中交通管制员通常会选择较为保守的距离绕过天气活动。天气预报也并不总是将当前条件与计划航路的进展相匹配，并且由于空中交通管制员在天气事件中特别繁忙，因此他们可能会错过围绕恶劣天气的更有效路线的可行机会。

改航路径规划是指在局部空域内，由于受到随机因素的影响而产生飞行受限区时，通过设置对受到该随机因素干扰的航路进行调整，规划出临时飞行路径以实现空域障碍规避的方法。危险天气主要是指飓风、雷暴、湍流、风切变和强对流等中小规模天气系统。危险天气区域根据其分布差异分为：块状区域、带状区域和散点状区域。目前，针对危险天气影响下的改航路径规划研究主要包括：空域的划设、单/多航班改航路径规划和空域流量分配等问题。

Dixon 等人最早于1993 年研究了危险天气影响下的改航路径规划问题。1999 年，Krozel 等人发现航站楼附近的恶劣天气是造成航空器延误的主要原因，并对风暴影响下的航路规划问题展开研究。在国内，孟令航等人在2012 年利用云团预测状态的不确定性和外推位置的随机误差等现象，提出了考虑改航路径偏差及距离的动态航路规划模型。张兆宁等分别在2015 年和2016 年提出危险天气下基于多重Morphin 算法的终端区三维实时改航方法和散点状分布危险天气下的终端区动态改航方法。吕宗平等人也在2017 年从雷暴图中解析飞行限制区，以最短航段距离和最大转弯角度为限制条件，建立的模型可以在航路网受到影响的情况下，为多个航空器规划出改航路径。

危险天气会直接导致空域容量的减小，目前常见的应对方法主要包括地面等待措施、空中等待措施和改航措施。前两者在实际运行中相对容易实现，但是燃油和时间的成本大大增加；虽然空域容量减小，但是在空域流量未达到容量时，实施改航措施是最有效也是最经济的办法。另外由于危险天气的位置是随着时间不断变化的，当飞机临近存在危险天气区域的空域时，仅采用起飞前所规划的静态航路，并不能满足实际的应用需求，因此进行实时路径规划是非常有必要的。

1 空域元胞的演化

Von Neumann 在20 世纪50 年代提出元胞自动机（Cellular Automata，CA），是一种在状态、空间、时间上都离散，时间因果关系与空间相互作用作为局部，能模拟复杂的系统时空演化过程的网络动力学模型。散布于规则网格中的每一个元胞取有限的离散状态，遵照同样的作用规则，依据确定的局部规则作同步更新。大量元胞依据简单的相互作用构成了动态系统的演化。其特点是在状态、空间、时间上都离散，每个变量只取有限的多个状态，且其状态改变的规则在空间和时间上均为局部的。

当对航路进行的动态规划时，可以将需要改航的空域看作是二维的空间。本文先将目标航路空域分解为栅格单元，每一个栅格单元都代表一个空域元胞。其中，空域元胞的状态分别为1 或0，0 表示为自由的空域元胞，1 为有天气的空域限制元胞。由于危险天气在实际情况中是不断移动的，因此可以将已知的危险天气区域用栅格法在空域中表示出来，如图1 所示。

图1 危险天气区域运行环境元胞

并按照以下规则来模拟危险天气区域的移动。其规则如下：（1） 空域元胞的初始状态为0，所有的元胞都是可以通过的，将已知的危险天气的范围与位置，在空域的相应位置划设出来。（2） 已知危险天气区域的元胞按照一定的速度及方向进行移动。

设在t 时刻，一个有天气的空域限制元胞i 的位置为（X（t ）,Y（t）），移动速度为V（t ），则在t+1 时刻的该空域限制元胞的位置更新为：

其中：k 为根据已知移动方向所设置的参数，取值为1 或-1。

2 改进蚁群算法的路径寻优

目前，多种动态环境路径规划方法已经被广泛应用，常用的算法包括势场法、A*算法和Dijkstra 算法等基本算法，以及蚁群算法、粒子群算法、遗传算法和人工神经网络等启发式优化算法。蚁群算法、遗传算法、粒子群算法及人工鱼群算法等均为基于概率型的全局优化算法，约束条件的处理方式相对简单，其中蚁群算法以其抗干扰能力强、并行性及易于其他算法结合等优点在解决路径规划问题时脱颖而出。

蚁群算法的本质是起始点和终点之间路径的长短与在路径上残留的信息素之间呈负相关，而信息素的浓度与该路径被后续蚁群选中的可能性为正相关，因此路径的长短与被选概率的大小呈负相关的。蚁群算法只需要根据已有路径中残留的信息素这一局部信息而无需了解整个空域内所有障碍物的情况便可搜索到起始点和终点之间的最优路径。

如果仅采用基本蚁群算法的搜寻方式，航空器所在的空域元胞会存在8 个相邻的空域元胞作为可移动的元胞（不考虑已经路过的空域元胞和障碍元胞），这种搜寻方式会随着空域元胞数量的增加以及设定的蚂蚁数量，大量增加搜索时间，且容易造成如图2 所示的奇异航段。

图2 基本蚁群算法的举例

因此采用基于CA 的改进蚁群算法，根据起始位置以及终点的相对位置，设置一定的搜索策略。减少搜寻的节点数，缩小搜寻范围，不仅节约时间成本，还能够提高优化的效率。本文假设路径优化航段的方向为从A 到B，如图3 所示。

图3 改进蚁群的搜索策略

此时，进行路径搜寻时只需要搜寻如图中的1、2、3、4、5 这个5 个元胞（不考虑已经路过的空域元胞和障碍元胞）。

本文采用的是基于CA 模型的改进蚁群算法，在危险天气不断移动的过程中，不断规避危险天气区域的基础上寻求并优化路径，流程图如图4 所示，具体步骤如下：

图4 基于元胞自动机的改进蚁群算法流程图

（1） 建立栅格环境及参数初始化。将目标空域转化为一个二值矩阵，确定起始节点和目标节点在空域中的位置。根据不同的需要，本文设定蚂蚁的数目以及算法的迭代次数均为100，将所有的蚂蚁都放在起始点的位置，且各蚂蚁之间保持相对独立。

（2） 禁忌表初始化，将各蚂蚁禁忌表清空，再将所有蚂蚁出发点以及所有危险限制空域所在元胞存入各蚂蚁的禁忌表。

（3） 所有蚂蚁从元胞i 移动j 到的可行性大小为p（t），公式如下：

其中：σ 为信息启发式因子，k 为期望启发式因子，该时刻t 与上文中空域元胞演化时刻中的t 相同，τ（t ）则表示在t 时刻路径（i,j ）上的残留信息素的浓度；η为启发函数，表示路径（i,j ）上的能见度，同时体现了蚂蚁在元胞间转移时的启发程度，一般取η=1/d，d为蚂蚁待选的转移元胞j 与目标节点之间的距离。

（4） 每一代完成路径搜索之后，基于以下公式，根据信息素挥发程度以及本代蚁群留下的信息素，重新计算路径上的信息素浓度。

（5） 更新禁忌表，各蚂蚁转移到新的空域元胞时，把该蚂蚁当前所在元胞添加到它的禁忌表里面。

（6） 记录每只蚂蚁经过的空域元胞的顺序以及所走过的路径长度。

（7） 若迭代完成，则循环结束。输出最优的蚂蚁经过的空域元胞顺序以及该路径的长度。

3 动态路径规划仿真

改航路径在能够绕飞危险天气区域并保证飞行安全的同时，不影响空域利用率且兼顾运行的效率，因此在建立优化模型前，提出合理的假设，假设条件如下：（1） 假设航空器为一个质点，沿航路的中心线以相同的速度匀速飞行，且不考虑航空器个体差异，例如速度、机型等；（2） 航路网络元胞是二维的平面网络结构，不考虑航空器的上升和下降，且将所有航空器都放置于同一高度层；（3） 由于存在危险天气的限制空域内部是不可以穿越的，对其边界分别经过扩展处理后，属于安全区；（4） 由于危险天气区域的移动速度远远小于航空器的飞行速度，因此假设航空器在绕飞危险天气区域时，危险天气区域的移动速度为0。

本文是通过Matlab 语言编程，进行仿真工作。整个路径仿真的空域运行环境在25×25 的元胞中，进行实时路径规划，元胞的网格边长a=20km。随着危险天气元胞的不断移动，分析在块状危险天气区、带状危险天气区以及散点状危险天气区，三种危险天气情况下的基于改进蚁群算法的路径规划。块状危险天气区的基于改进蚁群算法的动态航路规划如图5 所示。

图5 块状天气区实时路径规划

带状危险天气区的基于改进蚁群算法的动态航路规划如图6 所示。

图6 带状天气区实时路径规划

散点状危险天气区的基于改进蚁群算法的动态航路规划如图7 所示。

图7 散点状天气区实时路径规划

分析上述的仿真结果可以得知：在各类的危险天气区域对空域航路航线造成影响的场景下，随着危险天气区域的移动，进行实时的动态航路规划，可以有效地规划出一条航路，保证航班安全地规避危险天气的同时，提升航路的容量，减小飞行的成本。各类危险天气场景下，路径规划的长度以及所消耗的时间（包括危险天气区域移动、改航路径规划） 如表1 所示。

表1 三种天气下的最优路径长度及耗时结果

4 结 论

（1） 构建目标空域的元胞自动机模型，描述已知危险天气区，针对不断移动的危险天气区域，提出基于改进蚁群算法的动态航路规划模型，并确定了约束条件。

（2） 改进传统蚁群算法中的搜寻方式，以提高路径搜索中的有效性，减少搜寻节点，节约搜寻时间成本，提高优化效率。仿真结果表明：运用该算法能够针对动态的危险天气，实时的进行路径规划。

（3） 方法仅考虑航空器二维的路径规划，未涉及改变航空器的飞行高度，该问题将是下一阶段的研究方向。