基于A*算法的雷雨条件下航班流绕飞路径生成方法

Flight Stream Rerouting Path Generation Method under Thunderstorm Conditions Based on A* Algorithm

摘要: 针对雷雨条件下航班绕飞路径研究多基于理想化模拟场景、且聚焦单一航班最优路径，与实际空管运行需求存在差距的问题，本文提出一套面向实际应用的航班流绕飞路径生成与拓展方法。首先，设计包含二值化、去噪、像素聚类及边界提取的天气雷达图处理流程，构建有效寻路地图；其次，提出符合空管运行要求的绕飞航段分段策略；随后，模拟航空器从天气区域两侧绕飞的常规运行模式，迭代应用A*算法与视距缩减优化算法，生成多条可行绕飞路径；最后，参考拓扑学同胚概念，创新性地定义“同胚路径簇”，通过平行拓展策略进一步丰富绕飞路径解集。该方法旨在为雷雨条件下空中航班流全局规划提供具有较高可执行性的基础路径集合，有效弥补现有研究在实用性、可操作性及面向航班流规划方面的不足。

Abstract: Existing research on detour routes for flights under thunderstorm conditions mostly relies on idealized simulation scenarios and focuses on the optimal route for a single flight, creating a discrepancy between research outcomes and the practical operational requirements of air traffic control (ATC). To address this issue, this paper proposes a practical application-oriented method for generating and expanding detour routes for flight flows. Firstly, a weather radar image processing workflow including binarization, denoising, pixel clustering, and boundary extraction is designed to construct an effective pathfinding map. Secondly, a segment division strategy for detour route segments that meets ATC operational requirements is proposed. Subsequently, by simulating the conventional operational mode where aircraft takes detour routes around both sides of the weather-affected area, the A* algorithm combined with the line-of-sight reduction optimization algorithm is applied iteratively to generate multiple feasible detour routes. Finally, with reference to the topological concept of homeomorphism, the “homeomorphic flight paths” are innovatively defined, and the solution set of detour routes is further enriched through a parallel expansion strategy. This method aims to provide a set of basic routes with high executability for the global planning of air flight flows under thunderstorm conditions, effectively making up for the shortcomings of existing research in terms of practicality, operability, and adaptability to flight flow planning.

1. 引言

雷雨天气下，航空器无法沿计划航路飞行，导致空域容量与飞行冲突难以预测，既严重威胁飞行安全，又显著降低运行效率，是民航运行中不可避免的挑战。诸多学者从理论与实践层面针对雷雨天气条件下的飞行规划这一难题展开研究。

Stephen Zobell等人分析了天气对空中交通拥堵与延误的影响，介绍了交通流量管理(TFM)中的天气重路由决策支持工具(CRCT-WPR)为雷雨天气空管辅助程序的开发提供了思路与框架[1]。王莉莉等通过栅格化处理路径规划地图，结合动态规划算法进行路径规划，同时提出平行航路的改航优先权机制，但该研究仅考虑中小尺度的天气绕飞规划[2]。朱振强等提出改进的A*算法用于路径规划，但未考虑算法实际应用中的空管限制条件，也未涉及算法在多路径生成中的应用[3]。李雄、徐肖豪等人采用在航路点角平分线上选取等距备选绕航点的方式，利用多目标动态规划模型求解绕航路径[4]，但受天气块复杂分布的限制，备选点可能均位于其他相邻天气块内，且相邻备选点的连线可能全部穿过天气区域，存在较大局限性。

目前的研究存在两个方面的不足[5]-[10]。一方面是大多数研究以单个航班为对象从数学角度通过目标函数优化选取最优的单条绕飞路径，却较少从实际层面分析绕飞路径的实用性、可操作性及规划航迹与实际运行轨迹的差异，再加上天气边界的不确定性、雷达回波图的时间滞后性、航空器性能限制及管制指令执行延迟等因素，会导致理论计算的最优解难以应用于实际运行。空管运行的核心诉求在于规划航迹的可执行性，即飞行员能否接受规划路径，在这一点上，当前研究存在盲区。另一方面是实际运行中需要对整体航班流进行规划，而不是单一的航班流，更不是某一个航班。因此对单一航班流规划多方向可执行的绕飞路径，然后在此基础上进行综合目标优化对雷雨条件下的整体航路规划更具现实意义。这方面的研究成果和应用实例较少。

2. 天气雷达图处理

从天气雷达图中提取恶劣天气范围，是进行绕飞航路规划的前提和基础。本部分首先对天气雷达图进行二值化处理，然后在此基础上进行像素聚类形成块状天气范围。

2.1. 图像二值化处理

如图1所示，天气雷达回波图以不同颜色表征天气强度[3]，每个像素均由红、绿、蓝三个分量构成，每种分量取值范围均为0~255。由于天气雷达图片中的像素颜色种类有限，因此可将天气图中的颜色依次编号，序号大小亦表征天气强度，通过匹配天气雷达图的像素颜色得到颜色序号矩阵。定义强度阈值WX_QD：若像素强度 > WX_QD，说明存在危险天气，该像素所在网格赋值为0；若像素强度 ≤ WX_QD，说明不存在危险天气，该像素所在网格赋值为1。最终得到二值矩阵A。

Figure 1. Colour coding for weather radar maps

图1. 天气雷达图的颜色编号

通常，恶劣天气像素分布十分分散，孤立的天气像素可能给路径规划和优化带来不必要的寻优工作量。为消除天气图内的离散天气点，需要将相邻网格进行整体赋值。如图2所示，假设已获得天气雷达图对应的M × N的二值矩阵$A\in {\left\{0,1\right\}}^{M\times N}$ ，以每个完整的3 × 3邻域网格作为整体，若该邻域内9个网格对应的0的数量小于3个，即比例小于1/3，则该邻域内所有9个网格都赋值1，否则全部置0。在图像边界，因无法形成完整3 × 3邻域，各网格保持原值。

Figure 2. 3 × 3 local pixel processing

图2. 3 × 3临域像素整体处理

2.2. 天气像素聚类

二值矩阵A中以左上角为原点(0, 0)，任意一个像素位置p_i的坐标为$\left(x_i,y_i\right)$ ，设置聚类距离阈值为D，定义两个天气像素点之间的曼哈顿距离为：

$M_d=\left|x_i-x_j\right|+\left|y_i-y_j\right|$ (1)

聚类过程为：首先找出所有的天气像素(二值矩阵中值为0)的角标组成天气像素角标集合，从该集合中选取第一个点作为第一个类GROUP 1的聚类核心，计算其他所有点到核心的曼哈顿距离，距离小于阈值D的点加入到GROUP 1并同时将点从集合中去除。循环计算直到集合中的元素值不再减少，得到GROUP 1中的点集作为第一块天气的像素集合。重复上述操作直至集合为空，即可完成所有天气块的聚类。

2.3. 边界提取后的处理

根据文献[11]中算法得到每个聚类的边界，将边界及边界内所有网格赋值为0，其余位置赋值1，得到块状的危险天气范围，具体过程如图3所示。

Figure 3. Example of weather image processing procedure

图3. 天气图片处理过程示例

3. 绕飞起止点和中间点的确定

3.1. 确定绕飞起止点

在计划航路方向上，从第一个航路点起，依次对计划航路的每个航段进行判别：运用Bresenham算法[12]计算出计划航路所经过的全部像素网格。若某条航段穿越天气区域，则将该航段的起点设为绕飞起点。绕航终点的判定条件为：距离航路天气的网格距离的较大值大于给定阈值，如图4所示。依此方法依次判断，直至最后一个航路点。据此，可将原计划航路进行分段，并对每一段实施绕飞规划。

Figure 4. Selection of the final waypoint for rerouting flight

图4. 绕飞终点选择

在已处理好的天气雷达二值图中，依据天气雷达覆盖的经纬度范围，能够将某条具体的计划航路投影到图片上。如图5所示，圆点表示计划航路的航路点，根据上述算法，可得出具体的分段结果。由于天气覆盖范围较大，计划航路被划分为几个独立的绕飞航段(不同颜色表示不同的绕飞航段)。如此既符合雷雨条件下的绕飞运行限制，又减小了后续A*算法的搜索空间。

Figure 5. Route segment results

图5. 航路分段结果

3.2. 确定绕飞中间点

如图6所示，若仅考虑水平绕飞，在确定绕飞航段后，选取计划航路所穿越的天气团中(航段左右两侧)距离航路进出天气点连线所在直线垂直距离最长的点作为绕飞的中间点，进而可在危险天气的左右两侧生成两条绕飞路线。

航段与危险天气多边形边界的交点为S_k和T_k，两交点形成的航段为e_k。$w_i$ 表示危险天气多边形的第i个边界点，无论垂足是否在线段e_k内，$w_i$ 到e_k的距离计算过程如式(2)所示。

$d\left(w_i,e_k\right)=\frac{\left|SW\times ST\right|}{\Vert ST\Vert }$ (2)

其中，航段向量：

$ST=T_k-S_k=\left(t_{kx}-s_{kx},t_{ky}-s_{ky}\right)$ (3)

天气聚类边界点到起点向量：

$SW=w_i-S_k=\left(x_i-s_{kx},y_i-s_{ky}\right)$ (4)

×为向量叉积，$\Vert ST\Vert$ 为航段向量的模长。通过叉积符号判断$w_i$ 位于航段e_k的左侧或右侧(叉积为正则在左侧，为负则在右侧)，分别在两侧中选取垂直距离最大的点，即左侧最大距离点a_k和右侧最大距离点b_k，作为绕飞路径中间必经点。

Figure 6. Selection of the midpoint for rerouting flight

图6. 绕飞中间点的选择

4. 绕飞路径规划

4.1. 绕飞航班流的定义

对于给定的绕飞范围，把计划航路在该绕飞范围内完全重叠的航班归为同一航班流。因此，在确定绕飞范围后，便可统计出本区域内不同的绕飞航班流。本文针对一条航班流进行算法设计。

4.2. 基于A*算法的单个航段绕飞路径规划

A*算法是典型的路径优化算法，通常根据综合评价函数进行寻优，如式(5)所示。

$f\left(n\right)=g\left(n\right)+h\left(n\right)$ (5)

$g\left(n\right)$ 表示实际代价函数，体现了从起点S到当前网格位置n的累计移动代价，且$g\left(S\right)=0$ 。由于本文采用四邻域连接模型，即当前网格可以向上、下、左、右四个相邻网格移动，因此从当前节点current到邻节点neigbor的实际代价更新公式为：

$g\left(\text{neigbor}\right)=g\left(\text{current}\right)+1$ (6)

$h\left(n\right)$ 是启发式函数，表示当前节点到终点的预估代价，本文采用曼哈顿距离作为启发式函数。

$h\left(n\right)=\left|x_E-x_n\right|+\left|y_E-y_n\right|$ (7)

其中，$\left(x_E,y_E\right)$ 为终点坐标，$\left(x_n,y_n\right)$ 为当前网格节点坐标。

4.3. 基于视距缩减方法的航路优化

根据A*算法，每个绕飞航段能够得到两条绕飞路径。若整个计划航路可划分为k个若干航段，那么最多能够得到$2^k$ 条相应数量的绕飞路径。

针对每一条绕飞路径，本文运用视距缩减方法进行优化。具体方法如下：对于A*算法得出的每条绕飞路径，从第一个点开始，将其记为起始点；确定起始点到其后第i个点的连线所经过的像素点中危险天气网格的数量[12]，若该数量大于预设数量阈值，则将第i个点设为新的起始点，重复上述操作，直至这条绕飞路径的最后一个点；最后，将所有的起始点依次连接，即可得到优化后的路径。

通过视距优化处理，能够在保证路径有效性的前提下，减少A*算法中临域连接所产生的路径直角拐点，使规划路径更贴合实际飞行轨迹，降低飞行员的操作复杂度。同时，优化后的路径在长度上更接近理论最短路径，有助于提升航班运行效率。

4.4. 绕飞航路的平行拓展

4.4.1. 同胚路径簇和异构路径簇的定义

本文借鉴拓扑学中的同胚概念，不考虑绕飞路径的形态与长度，仅考量不同绕飞路径与天气之间的位置关系，对二维平面上的不同绕飞路径进行定义。针对起止点相同的绕飞路径，若将它们首尾相连所形成的所有封闭曲线内部不存在危险天气像素点，则将这一类绕飞路径定义为同胚路径簇；反之，则将其定义为异构路径簇。依据该定义可得，本文借助A*算法所获取的规划路径均归属于异构路径簇。

4.4.2. 平行拓展算法

在雷雨天气条件下，为了降低航班流之间的飞行冲突，本文提出平行拓展策略对现有的异构路径簇加以拓展，如图7所示，构建出多条同胚路径簇，从而丰富最优绕飞路径的解集合，用于考虑冲突指标的航班流综合规划，具体算法如下：

记原始航路点序列为$P={\left\{\left(x_i,y_i\right)\right\}}_{i=1}^N$ ，d为平移偏移距离(可正可负，正值表示左偏移，负值表示右偏移，可依据实际空域条件和航班流需求来确定)，平移后的航路点序列为$P^{\prime }={\left\{\left({x^{\prime }}_i,{y^{\prime }}_i\right)\right\}}_{i=1}^N$ ，$n_i$ 为点i处的单位法向量。对于航路中的某一个段向量$V=\left(v_x,v_y\right)$ ，其单位法向量为：

$n=\frac{\left(-v_y,v_x\right)}{\Vert V\Vert }$ (8)

对于航路中间转弯点的偏移向量(求法向平均)：

$n_{avg}=\frac{n_{prev}+n_{next}}{\Vert n_{prev}+n_{next}\Vert }$ (9)

得到偏移后的点$\left({x^{\prime }}_i,{y^{\prime }}_i\right)=\left(x_i,y_i\right)+d\ast n_{avg}$ ，对于序列端点则使用开始和最后航段的法向量计算：

$\left({x^{\prime }}_1,{y^{\prime }}_1\right)=\left(x_1,y_1\right)+d\ast n_{start}$ (10)

$\left({x^{\prime }}_N,{y^{\prime }}_N\right)=\left(x_N,y_N\right)+d\ast n_{start}$ (11)

在平移的过程中，可能出现平移后的点为危险天气像素点的情况，这些点就使用原来的点；如果平移后的某个航段与天气相交，进入天气的航段都使用平移前的航段；绕飞中间点的算法与航路分段中的算法相同。

$\left({x^{\prime }}_K,{y^{\prime }}_K\right)=\left(x_K,y_K\right)$ (12)

平行拓展算法是一种简单实用的方法，通过本算法构造出满足民航间隔的平行航路，能够有效降低区域内航班流的冲突指数，特别适用于扇区交接点和走廊口的进出港航班流规划。

Figure 7. Parallel extension of rerouting flight paths

图7. 绕飞路径平行拓展示意图

4.4.3. 整体算法流程

整体算法流程如图8所示。

Figure 8. Overall algorithm flowchart of rerouting route generation for flight stream

图8. 航班流绕飞路径生成整体算法流程图

5. 算法验证

5.1. 历史航迹拟合处理

通过对航班流历史航迹进行拟合，能够清晰掌握历史航迹绕飞的大致走向。再通过计算规划航迹与历史拟合航迹的偏离程度，可以初步评估规划航迹的有效性。本文运用Jolliffe等人提出的主成分分析(PCA)对点集进行排序，能够通过主方向提取实现点集的一维参数化[13]；Reinsch提出的平滑样条模型可利用正则化项控制曲线的平滑性[14]，经Carl de Boor等人优化后形成了实用的csaps算法[11]；Tukey提出的biweight权重函数以及Huber、Rousseeuw等人发展的鲁棒统计方法，为抑制离群点干扰提供了理论依据[12] [15] [16]。本文将上述算法进行融合，采用“主方向参数化—鲁棒平滑拟合—采样输出”三步法，生成航班流历史轨迹的拟合航迹。

5.2. 实例分析

选取气象部门提供的中南地区2023年6月14日14:54的天气图片以及FlightAware网站获取的14:35~15:5时间区间的ADS-B历史数据进行实例验证。其中天气雷达的经纬度覆盖范围为[105, 125, 18, 43]，像素尺寸为1388 * 1111 (不考虑投影失真变形的情况下，每个像素代表2 * 2 KM的范围)。ADS-B历史数据选取海南岛前往华东方向的航班历史航迹，主用航路的航路点为：“GIVIV P101 GYA POU SHL LMN XEBUL EGEDA PLT SAGON”，使用本算法进行绕飞路径生成验证。天气雷达图与历史航迹的融合图以及历史轨迹拟合如图9所示。从图中可以看出，大部分航空器都是沿着天气的空白区域飞行，偶尔会有少部分轨迹穿越天气区域，主要原因是天气雷达回波在不同高度层的强度不同、不同航空器对于天气绕飞的尺度存在差异。

参考部分航空公司的雷雨绕飞标准，考虑距离危险天气最少20 NM前开始执行绕飞，将分段阈值设定为20；在处理天气雷达图像时，为最大限度保留天气形状，确保天气团之间水平和斜向均不临接，将天气聚类阈值为3；依据《民用航空空中交通管理规则》(CCAR-93TM-R6)，区域雷达管制的水平间隔标准为5 NM，本算例将平行拓展阈值设定为5。利用本算法得到的各个绕飞航段路径如图10所示。

Figure 9. Weather radar map and historical track fusion map

图9. 天气雷达图和历史航迹的融合图

Figure 10. Comprehensive solution results diagram

图10. 综合的求解结果图

通过绕飞航段路径排列组合以及视距优化，得到多个可用绕飞路径组合。如图11所示，共得到32组绕飞路径，图左侧显示的是第25组绕飞路径结果。

Figure 11. Combined rerouting flight path results diagram

图11. 组合绕飞路径结果图

对32组绕飞路径进行指标计算(取规划航路与拟合航迹平均距离较小的前16组)，具体结果如表1所示。

Table 1. Circumventing flight route indicator data

表1. 绕飞路径指标数据

规划路径组合	规划路径与拟合航迹最大距离(pixel)	规划路径与拟合航迹最小距离(pixel)	规划路径与拟合航迹平均距离(pixel)
组合1	93.9	0	13.4
组合2	93.9	0	14
组合3	53.1	0	14
组合4	79.9	0	15.6
组合5	93.9	0	19.8
组合6	70.2	0	20.9
组合7	93.9	0	21.2
组合8	93.9	0	21.8
组合9	55.7	0	21.8
组合10	79.9	0	23.5
组合11	87.5	0	23.7
组合12	93.9	0	25.5
组合13	70.2	0	28.7
组合14	93.9	0	29.6
组合15	87.5	0	31.6
组合16	93.9	0	33.3

从表1中能够看出，拟合的航班流历史轨迹与算法生成的规划路径之间的平均距离偏差最小值为13.4 pixel (约27 KM)，表明算法生成的路径与实际偏差不大，也就说明算法能够找出有效的路径。从数据和图片中可以清晰地发现，不同绕飞规划路径长度存在显著差异。但在实际优化过程中，并非始终选择绕飞路径最短的路线，而是需要综合考量空域限制、流量分布、冲突复杂度等诸多因素。

5.3. 平行拓展算法验证

为验证平行拓展算法的有效性，选取同一日期14:00~15:55时段内的历史ADS-B航迹数据。在该时段，广州终端区北向进出港航班流受天气影响，易形成对头飞行冲突。因此，针对从广州起飞前往华北方向的交通流，进行绕飞路径规划并做平行拓展。选取平行拓展距离为10像素(对应区域管制间隔20 KM)，历史拟合航迹、规划路径和平行拓展路径如图12所示。

Figure 12. Parallel expansion result diagram

图12. 平行拓展后结果图

初始规划绕飞路径与平行拓展路径与历史拟合航迹之间的距离值见表2。

Table 2. Parallel expansion result diagram

表2. 平行拓展指标结果

	最大距离(pixel)	最小距离(pixel)	平均距离(pixel)
初始规划路径与拟合航迹	37.5	9.2	24.9
左侧平行拓展路径与拟合航迹	18.8	0.4	8.2
右侧平行拓展路径与拟合航迹	49.2	27.2	37.9

从表2的结果来看，左侧平行拓展路径比初始规划路径更加符合实际运行情况，表明平行拓展路径规划的算法对于解决空管运行中的飞行冲突有一定的现实意义。

6. 结论

根据主观判断，航空器的历史轨迹是较为理想的绕飞结果。在实际指挥过程中，管制员会结合各空管运行部门的决策和机组的意图进行指挥，但由于缺乏绕飞路径辅助决策工具，空管部门基于安全和工作负荷考虑，会降低通行能力并采取相应流量管理措施。本文的主要目的在于构建绕飞路径集合，确保这些路径具备较高的可执行性，为后续的绕飞路径规划应用打好基础。通过对比图9和图11能够发现，所搜索到的解与历史轨迹的重合度较高，表明本文的绕航路径规划算法具有有效性，图12进一步验证了平行路径算法的有效性。至于如何定量分析历史绕飞路径与规划路径的关系，可考虑规划路径与实际历史轨迹之间同胚和异构的比例，因篇幅限制，本文未作阐述。只有在保证每个航班流的绕飞解集合有效的基础上，对空中整体航班流进行全局规划才具有意义，并将其应用于实际的规划决策。

本文针对现有雷雨条件下航班路径规划算法在应用上的不足，提出了结合实际运行状况的绕飞路径生成与拓展方法。通过对天气雷达图片进行处理、确定绕飞起止点和中间点、运用A*算法、优化航路视距以及拓展同胚航路等一系列操作，能够生成多条符合实际需求的绕飞路径，为空中交通航班流的整体规划提供较为合理的基础路径集合。基于这些路径集合，可以开展雷雨条件下空中航班流的多目标优化规划研究。未来，为进一步提升规划路径的实用性，在天气雷达处理(基于15分钟或30分钟的临近时间内历史轨迹的天气雷达图片处理)和同胚航路拓展(基于侧向偏置的航路拓展是解决航班流冲突的有效手段)方面，仍有诸多可改进和研究之处。