武丁杰 邹德龙 葛昆

摘  要：文章通过研究目前危险天气对航路航线的影响，在分析最优航线选取的基础上，细化航路航线的选取方向，定义空域元胞尺寸和速度位置演化的规则，构造危险天气元胞自动机模型，在此基础上，利用改进蚁群算法进行最优路径规划。提出了基于空域元胞位置演化规则的动态局部航路规划方法。在建模环境下的仿真结果表明，基于此元胞自动机演化规则的方法，能够完成在动态环境下的最优路径选取的任务，并且在路径的长度上有较为明显的改善，快速高效的规划并选取出一条路径，并随环境的变化相应的改变，具有一定的稳定性和很强的适应能力。

  关键词：元胞自动机;改进蚁群算法;动态环境;航路规划

  中图分类号：F560    文献标识码：A

Abstract：
In this paper， by studying the impact of current dangerous weather on air routes， based on the analysis of the selection of optimal routes， the selection direction of air routes is refined， the airspace cell size and the rules for the evolution of speed position are defined， and the dangerous weather cellular automaton is constructed. Based on this model， the improved ant colony algorithm is used for optimal path planning. A dynamic local route planning method based on airspace cell position evolution rules is proposed. The simulation results in the modeling environment show that the method based on this cellular automaton evolution rule can complete the task of selecting the optimal path in a dynamic environment， and there is a more obvious improvement in the length of the path， which is fast and efficient. Plan and select a path， and change accordingly with changes in the environment， with a certain degree of stability and strong adaptability.

Key words：
cellular automata; improved ant colony algorithm; dynamic environment; route planning

0  引  言

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

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

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

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

1  空域元胞的演化

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

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

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

设在t时刻，一个有天气的空域限制元胞i的位置为

Xt，

Yt，移动速度为Vt，则在t+1时刻的该空域限制元胞的位置更新为：

Xt+1=Xt+kVt

Yt+1=Yt+kVt

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

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

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

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

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

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

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

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

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

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

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

pt=    i∈

allowed; j∈otherwise

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

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

τt+n=1-ρ·τt+Δτt

Δτt=∑Δτt

Δτ=

其中：Δτ表示的是蚂蚁k在边i，j中残留的单位长度的信息素量;ρ为信息素挥发系数，1-ρ为信息素的残留因子;L代表在这一轮路径搜索中，第k只蚂蚁所走过的路径长度;Q则代表信息素强度，制约着此算法构造解收敛速度。

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

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

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

3  动态路径规划仿真

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

（4）由于危险天气区域的移动速度远远小于航空器的飞行速度，因此假设航空器在绕飞危险天气区域时，危险天气区域的移动速度为0。

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

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

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

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

4  结  论

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

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

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

参考文献：

[1]  Evans A D， Sridhar B， Mcnally D. Improving Operational Acceptability of Dynamic Weather Routes Through Analysis of Commonly Use Routings[C] // Aiaa Aviation Technology， Integration & Operations Conference， 2016.

[2]  DIXON M， WEINER G. Automated Aircraft Routing Through Weather-Impacted Airspace[C] // Vienna， VA：
Fifth International Conference on Aviation Weather Systema， 1993：295-298.

[3] 孟令航，徐肖豪，李善梅，等. 不确定强对流天气下动态改航路径规划[J]. 西南交通大学学报，2012，47（4）：686-691.

[4] 张兆宁，魏中慧. 散点状分布危险天气下的终端区动态改航方法[J]. 中国安全科学学报，2016，26（1）：40-44.

[5] 吕宗平，王清琦，靳宇波，等. 超级单体雷暴下的改航模型研究[J]. 飞行力学，2017，2（2）：88-91，96.

[6] 向征，张文奇，张文军. 雷暴天气下基于多航空器冲突避让的路徑规划[J]. 中国安全科学学报，2019，29（8）：155-160.

[7] 郦晴云. 基于交通流特征的航路网络节点布局优化[D]. 南京：南京航空航天大学（硕士学位论文），2018.

[8] 杨凯，康瑞. 基于元胞自动机的航空器起降间隔研究[J]. 工程科学与技术，2016（S2）：127-134.

[9] Wang S， Cao X， Haiyun L I， et al. Air route network optimization in fragmented airspace based on cellular automata[J]. 中国航空学报（英文版），2017（30）：1184-1195.

[10] 梁凯，毛剑琳. 动态环境下基于改进蚁群算法的路径规划研究[J]. 电子测量技术，2020（1）：82-87.

[11] 王瑛，郑煜坤，姚頔，等. 危险天气下改航路径网络规划[J]. 系统工程与电子技术，2019，41（6）：1309-1315.