基于飞行受限区划设的航班改航研究

蒋 昕，胡明华，张 颖，田 文（.南京航空航天大学民航学院，江苏　南京2006；2.中船重工第709研究所，湖北　武汉430074）



基于飞行受限区划设的航班改航研究

蒋 昕1，2，胡明华1，张 颖1，田 文1
（1.南京航空航天大学民航学院，江苏南京210016；2.中船重工第709研究所，湖北武汉430074）

摘要：危险天气是影响飞行安全，导致航班延误的重要原因。在对危险天气影响下的飞行受限区进行划设的基础上，采用一元线性回归预测模型和一种改进的飞行受限区边界预测方法，实现对飞行受限区的位置及边界的动态预测，并以所预测的飞行受限区作为约束，在考虑飞行性能和安全的基础上，以最短改航距离、最小转弯角、最少转弯点为优化目标建立改航路径规划模型，采用遗传算法求解。仿真结果表明：所规划出的改航路径能避让飞行受限区并满足安全、经济以及减少管制员工作负荷的目标。

关键词：飞行受限区域；位置预测；边界预测；遗传算法；改航

随着航空运输业的快速发展，航班的大量延误也随之而来，危险天气是威胁航空器安全导致航班延误的重要原因。改航作为改善空域资源的重要手段，可以避免不必要的地面等待，有效降低由于天气原因带来的航班延误。为了在危险天气下合理利用空域资源，降低航班延误，需要对改航策略进行深入研究。

改航问题的研究开始于1993年，经过20多年的发展，国内外已取得了一些具有代表性的研究成果。1993年，Dixon和Weidner建立了在网格改航环境下的改航策略[1]；2002年，宋柯等研究了基于已有航路点的A*搜索算法[3]；2009年，徐肖豪等研究了基于人工势场算法的改航路径规划方法[4]；2011年，Maritin O Nicholes等人提出了协同改航路径规划的研究[5]；2012年，Christine Taylor和Craig Wanke使用模拟退火算法规划改航路径，在考虑改航路径可操作性的前提下对航班进行路径规划，并对生成的改航路径进行评估[2]；2012年，孟令航等研究了不确定强对流天气下动态改航路径规划方法[6]。

从以上的研究成果可以看出，前期学者们着重于改航的路径规划，未充分考虑危险天气的等级和运动趋势等方面对航路的影响。借鉴前人研究，进一步对危险天气区域进行精确的划设和预测，将预测的飞行受限区作为约束，充分考虑航空器性能以及飞行安全等其他限制因素，建立改航路径规划的数学模型，并采用遗传算法对模型进行求解。

1 飞行受限区的划设和预测

飞行危险天气包括暴雨、雷暴、冰雹等，这些危险天气会给航空器飞行带来安全隐患，造成航班延误，影响空域系统的运行。为了减少危险天气下的航班延误，降低经济损失，对飞行受限区域进行准确的划设和预测就显得十分重要。

根据雷达回波图对飞行受限区进行划设，结合飞行受限区的历史数据，利用一元线性回归预测方法，对飞行受限区的移动进行精确预测，同时提出一种飞行受限区边界预测的新方法。

1.1 飞行受限区划设

文献[7]指出，当雷达回波等级≥41 dBZ时，航空器需要避让；因此，认为雷达回波等级≥41 dBZ的区域为危险天气区域。根据气象雷达回波图，通过图像处理技术分离出回波等级≥41 dBZ的危险天气区域，并采用凸多边形划设飞行受限区。对划设的飞行受限区，飞行受限区划设步骤如下：

1）提取危险天气数据。对雷达反射率图进行处理，获得每个反射率等级的RGB颜色值，并对雷达反射率图进行遍历，保存反射率等级≥41 dBZ的像素点，这些像素点构成的区域即为危险天气区域，同时根据雷达所在位置的经纬度坐标以及分辨率，确定每个危险天气像素点对应的经纬度坐标。

2）图片二值化。对危险天气区域图片进行二值化处理，凸显危险天气区域，灰度化背景。

3）轮廓检索。调用OpenCV中的cvFindCounters( )函数，在上一步得到的二值图像中检索危险天气区域轮廓；

4）多边形逼近。调用OpenCV中的cvApproxPoly( )函数，对上一步得到的轮廓集用指定精度的多边形逼近，并生成逼近后的简单多边形轮廓集。

5）生成凸包多边形。对上一步得到的简单多边形轮廓集中的每个简单多边形，调用MATLAB中的ConvexHull( )函数，求得每个简单多边形的凸包，这些凸多边形，即为需要避让的天气区域。

对于上述操作得到的飞行受限区，还需要进行特殊处理：

1）去噪处理。根据航空器性能数据库，取420节作为航空器飞行速度，对于尺寸小于7 mile的飞行受限区（即在飞行受限区内以420节速度飞行1 min），可以忽略不计。

2）合并处理。根据我国允许航空器绕飞的规定：在两个云体边界之间的最小距离不少于20 km的情况下，航空器可以从中间通过[8]；因此，将飞行受限区之间的距离小于20 km的飞行受限区合并成一个。

1.2 飞行受限区移动预测模型

在前期研究中，多数学者把危险天气假设成不变化的多边形，少部分学者简单考虑到危险天气线性移动情况[9]，但这些都是在假设危险天气移动速度和方向已知的情况下进行研究的，然而实际上并不能方便的得知危险天气的移动速度。本文结合历史数据，利用一元线性回归预测方法，对飞行受限区的移动进行精确预测。

利用墨卡托投影将飞行受限区的经、纬度坐标转为屏幕坐标，将飞行受限区域的质心坐标作为强对流单体云团的位置。根据不断更新的气象雷达数据，研究飞行受限区域沿x、y方向移动与时间的关系，建立飞行受限区域移动预测模型。

由于本文使用的气象雷达数据更新频率是5 min，以预报的起始时间t0为基准，将预报时间ti（i=1，2，3，…）转化为预报时刻Ti（Ti=1，2，3，…）：

根据强对流天气单体云团在过去多个时刻的质心位置，发现时间T分别与云团质心的位置x和y有着特殊的关系，可以近似表示为一条直线。采用一元线性回归分析，根据n个历史时刻Ti（i=1，2，…，n）云团质心的位置xi和yi，将x-T，y-T拟合成x=kx×T+bx，y=kyT+by两条直线，其中kx，ky为拟合直线x-T，y-T的斜率，bx，by为拟合直线x-T，y-T的截距。在未来时刻Tn+j（j=1，2，…），强对流天气单体云团的位置为

1.3 飞行受限区域边界预测

在前期研究中，多数学者认为强对流单体云团以已知的速度或加速度膨胀或收缩[9]。然而，在云团实际运动中，云团膨胀或收缩的速度或加速度很难直接获取。提出一种新的飞行受限区域边界预测方法，在未知云团膨胀或收缩的速度或加速度时，根据历史飞行受限区域边界变化预测未来飞行受限区域边界。

将飞行受限区域边界变化视为匀速，根据当前飞行受限区域Ft和前一时刻飞行受限区域Ft-1的边界，预测未来飞行受限区域Ft+j（j=1，2，…）的边界。预测步骤如下：

输入：当前时刻飞行受限区域Fα的x个顶点坐标pt1，…，ptx以及质心坐标Ot（x，y），前一时刻飞行受限区域Ft-1的顶点坐标p1t-1，…，pβt－1以及质心坐标Ot-1（x，y），未来t＋i时刻飞行受限区域Ft＋i质心位置的预测坐标O（x，y）t＋i（i=1，2，…）；

1）分别计算Ft、Ft-1的质心坐标由Ot（x，y）、Ot-1（x，y）移动到未来时刻t＋i（i=1，2，…）Ft+i的质心位置后Ot＋i（x，y），顶点pt1，…，ptnp1t-1，…，pβt－1的位置坐标，记p1t，…，pαtp1t-1，…，pβt－1，顶点p1t，…，pαtp1t-1，…，pβt－1构成经Ft、Ft-1移动后的多边形Ft、Ft-1；

2）以Ot＋i（x，y）为中心，向Ft的顶点，…，做射线Ot＋1（x，y），…，Ot＋1（x，y），射线Ot＋1（x，y），…，Ot＋1（x，y）分别与多边形Ft-1相交于点q1，…，qα；

3）计算Ft边界相对于Ft-1的变化值，xI=（x）-qI（x）（I＝1，…，α），yI=（y）-qI（y）（I＝1，…，α）其中（x）、（y）为顶点的x、y坐标值，qI（x）、qI（y）为交点的x、y坐标值；

5）顺序连接点pt+i1，…，pt+iα，即形成飞行受限区域Ft+j，如图1所示。

图1 飞行受限区域边界预测示意图Fig.1 Prediction diagram of flow constrained area boundary

采用精确度DaF和偏差度DdF对预测的飞行受限区域边界进行评估[5]。其中，精确度用来评估飞行受限区域划设的准确性，指标越大，准确性越好；偏差度用来评估飞行受限区域划设的安全性，指标越小，安全性越好。假设当前时刻为t，预测未来t+i时刻飞行受限区域为Fft+i，实际观测的飞行受限区域为Fat+i，则

1.4 固定时段内的飞行受限区

2009年，李雄在文献[10]中提出，假设航班在改航起始点的时刻为ts，改航结束点的时刻为td，则

式中：σR为实施改航后增加的航程与原计划航路航程百分比的估计值，大多数情况下是0.2；DR是改航开始点到改航结束点之间的航程；Vh是巡航速度，一般为420节，本文取800 km·h-1。

根据上式，在确定改航起始点和结束点之后，利用预估的改航时间td和1.2节的移动预测模型以及1.3节的边界预测模型，预测改航过程中飞行受限区的位置以及边界，将改航过程中由于飞行受限区移动形成的所有受限区合并，得到改航所在时段内的飞行受限区。

2 改航模型与算法

以单个航班的改航作为研究对象，进行改航路径规划，除了考虑避开飞行受限区外，还要考虑到飞行成本、飞机性能、飞行员工作负荷等因素。选取最短改航距离，最小转弯角度，最少转弯点为优化目标建立改航路径规划模型，并采用遗传算法对模型求解。

2.1 改航模型

在实际管制运行中，出于航路飞行安全因素以及飞行员操作负荷考虑，在绕飞危险天气区域时航向的改变量不应超过飞行性能所允许的最大角度，为了航空器能顺利完成2次转弯，飞行航班的转弯半径不应小于最小转弯半径，由于改航点数量决定管制指挥的次数，为了减轻管制员的工作负荷，在实施改航的过程中，尽可能地减少改航点数量[11]。因此，将改航路径长度、改航的转弯角度以及改航点数量作为约束条件，将改航路径最短，转弯点数量最少，转弯角度变化最小作为优化目标建立改航路径规划模型。为了实现对多个目标的综合处理，将各个指标值进行无量纲化处理，通过线性加权转化为单目标进行求解。由此建立的改航数学模型如下：

参数定义：CL，CT，CA分别代表距离代价，转弯角数量代价，转弯角度变化代价；ω1，ω2，ω3分别代表距离代价，转弯角数量代价，转弯角度变化代价的权重；ps，pi，pD：分别代表改航起始点，改航过程中的转弯点，改航结束点；D（pi，pi+1）Fj

两个改航点之间路径距飞行受限区域的最小距离；Dmin为允许改航路径偏离飞行受限区域的最小距离，通常取10 km；d（ps，pD）为改航起始点到改航结束点之间原航路距离；d（pi，pi+1）为改航过程中两个转弯点之间的距离；dmin为改航过程中两个转弯点之间的最短允许距离，通常取7.4 km；NT为改航路径中转弯角的个数；Nmax为改航路径中允许最大的转弯角数量，通常取8个；θ为改航过程中转弯角的大小；θmax为改航过程中允许的最大转弯角度，通常取90°；Fj为第j个飞行受限区。

目标函数（7）说明当目标函数取最小值时，可以获得改航的最优路径，式（8）～式（10）分别对距离代价、转弯角个数代价、转弯角度变化代价进行了归一化处理，并保证：CL越小，改航后的路径长度越短；CT越小，转弯点个数越少；CA越小，转弯角变化越小。

约束条件（11），（12）保证系数权重之和为1且为正值；式（13）保证改航路径安全性和可行性；式（14）～式（16）限制改航距离，最大转弯角度以及最大转弯点个数。

2.2 改航算法

遗传算法(Genetic Algorithm)是一类借鉴生物界的进化规律演化而来的随机化搜索方法。由于该算法不受搜索空间的限制性假设的约束，以及算法本身固有的并行性特点，采用遗传算法能有效的解决路径规划问题[12]。

当航空器飞行过程中受到危险天气影响而无法按照预定航路飞行时，采取改航策略，重新为航空器规划处一条新的航路。为了实施改航策略，我们做出如下假设：①航空器改航可以简化成一个二维平面，将航空器视为一个运动的质点；②改航的起始点和结束点已知，航空器的以恒定的巡航速度飞行；③飞行受限区在二维空间中用多边形表示；④将二维空间网格化处理建立改航环境模型，改航起始点的坐标为（0，0）。

2.2.1 遗传算法参数设置

1）路径编码：在改航环境模型中，改航路径是由一系列转弯点按照航空器运动的先后顺序连接而形成，为了直观的显示航空器位置，方便遗传算法的交叉和变异操作，将改航的路径中转弯点的坐标（xi，yi）作为遗传算法中染色体的一个基因，则一条改航路径中的所有转弯点序列（x1，y1）……（xi，yi）构成一个染色体。

2）初始种群生成：由于式（14）～式（16）中约束条件限制，为了保证初始种群中的每个个体满足最短航路长度、最大转弯点个数以及最大转弯角度限制，初始种群个体需要按如下规则生成：①随机生成转弯点个数，保证转弯点个数满足最大转弯点个数约束限制；②在搜索空间中，为每个转弯点在环境空间中随机生成位置，这些位置组成染色体的基因；③对染色体的基因利用修复算子进行修复，保证染色体满足最短航路和最大转弯角限制（修复算子详细介绍见7）。

3）适应度函数：在遗传算法中，适应度高的个体相对于适应度低的个体遗传到下一代的概率大。由于改航策略模型求解的目标函数是改航成本最小问题，因此需要对目标函数进行转换，生成遗传算法所需要的适应度函数。取目标函数的倒数作为适应度函数，计算中为了避免改航成本为0时造成适应度函数分母无意义的情况，给分母加上一个正整数1，则对于染色体x的适应度函数为

其中C（x）为染色体x的目标函数。同时，采用修复算子使改航路径满足式（14）～（16）的约束限制，为了满足式（13）的约束限制，引入罚函数。对于与飞行受限区有交点的改航路径，采用罚函数，对C（x）进行修正，修正公式如下：

上式，保证当改航路径与飞行受限区有交点时的改航成本C（x）远大于无交点时的改航成本C（x），因此，该路径染色体的适应度函数非常小，被遗传到下一代的概率几乎为0。

4）选择算子：为了满足对于选择算子的要求，采用轮盘赌和精英保留策略进行选择操作。通过轮盘赌方法选择个体进行交叉和变异操作，保证个体被选择的概率与其适应度值成正比，精英保留策略通过将每代的最优个体进行保留，直接遗传到下一代，来保证遗传算法的全局收敛性。

5）交叉算子：静态改航路径规划算法采用单点交叉的方式进行交叉操作，过程如下：对于父亲个体改航路径中的NT个转弯点，从［1，NT－1］中随机产生一个转弯点作为交叉点O1，同理从母亲个体的改航路径中随机选择一个转弯点作为交叉点O2，将父亲O1点后的路径与母亲个体O2点后的路径进行交换，形成两个新的子代个体。对生成的新个体，采用修复算子进行修复，以保证满足约束限制。

图2为两条改航路径R1和R2，对应的转弯角数量均为3，进行交叉操作：在路径R1中随机选择一个转弯作为交叉点O1＝RondomNum[1，2]，这里O1=2；在路径R2中随机选择一个转弯作为交叉点O2＝RondomNum [1，2]，这里O2=1；将路径R1的交叉点O1之后的路径与路径R2的交叉点O2之后的路径交换后，形成新的路径如图3所示。

图2 双亲个体路径示意图Fig. 2 Parents individual path diagram

图3 交叉操作后子代个体路径示意图Fig. 3 Cross operation progeny path diagram

在图2，图3中PS，PD为改航路径的起始点和结束点，细线和粗线分别代表两条改航路径。

图4 改变坐标变异操作示意图Fig. 4 Operation diagram of changing coordinate

6）变异算子：为了更好的进行变异，增加遗传算法的局部搜索能力，保证变异的多样性，采用启发式变异，通过改变某一个转弯点的坐标，删除某一个转弯点和增加一个转弯点三种方法进行变异操作。对生成的新个体，采用修复算子进行修复，以保证满足约束限制。图4，图6分别为改变转弯点坐标、增加转弯点以及删除转弯点的操作示意图：

图5 删除坐标点变异操作示意图Fig. 5 Operation diagram of deleting coordinate

图6 增加坐标点变异操作示意图Fig. 6 Operation diagram of adding coordinate

图4表示转弯点P2改变坐标变为转弯点P2′形成新的改航路径；图5表示删除转弯点P2形成新的改航路径；图6表示在转弯点P2与P3之间增加新的转弯点PNT形成新的改航路径。

7）修复操作：为了满足约束条件的限制，引入修复算子，对改航路径进行修复，确保得到可行解。每当产生新的个体时，均需要进行修复操作。修复操作如下：①对染色体中的每个转弯点（即改航路径中的每个转弯点）按照坐标x值的大小排序，保证改航路径无回路；②对排序后的染色体，判断相邻2个转弯点之间的距离，对于小于7.4 km的两个转弯点，删除其中一个，保证满足最小航段距离限制，同时对多个在同一条直线的转弯点，进行删除操作，保证每个点均为转弯点；③对染色体的转弯点个数进行判断，对于长度大于最大转弯点个数的染色体，随机删除其中的一个转弯点，保证满足最大转弯点个数的限制；④检查染色体中每个转弯点所对应的转弯角度，若存在不满足最大转弯角度限制的转弯点，则对该转弯点进行微调，使其满足最大转弯的约束限制。

3 算例分析

3.1 飞行受限区算例分析

根据某气象雷达数据显示，2015年4月2日17:37至18:22之间，东北方向有一大面积强对流天气。根据17:37至17:52之间的历史气象雷达数据，将危险天气转为飞行受限区域，其历史预报时间、飞行受限区对应的质心经纬度以及利用墨卡托投影转为屏幕坐标的位置如表1所示：

利用1.2节的模型，对该危险天气未来30 min内的位置移动进行预测，然后根据位置预测结果利用1.3节的飞行受限区域边界预测方法，对未来30 min内的飞行受限区域边界进行预测。

根据移动预测和边界预测结果生成飞行受限区域，利用1.3节中评估模型对预测生成的飞行受限区进行评估，则预测和评估结果如表2所示。从表中可以得出随着预测的时间推移，预测的精确性下降，偏差度升高的结论。因此，本文所采用的预测模型适用于短时段内的预测，为了保证改航的安全，预测模型应该应用于实时战术改航策略中。

3.2 改航算例分析

假设一架航班将预计17:40到达改航起始点，在实施该航后，预计17:58到改航结束点。利用网格法对环境建模，同时设定改航最短转弯半径不小于7.4 km，改航最大转弯角度不大于，改航最大转弯点个数不大于8个，航空器距离危险天气距离不小于10 km。

表1 历史飞行受限区中心移动位置Tab.1 Center location of history flow constrained area

表2 飞行受限区预测结果及评估结果Tab. 2 Forecast and assessment results of flow constrained area

参数设定如下：初始种群大小N=30，种群代数G=200，种群交叉概率pc=0.8，种群变异概率pm=0.1。目标函数中，距离的权重ω1=0.8，转弯点权重系数ω3=0.1，转弯角权重系数ω4=0.1。

基于改航模型及算法求得的结果如图7所示，其中多边形区域为飞行受限区，实线段代表原始航路，虚线段为模型规划的改航路径。

规划结果表明，算法能够在对受到危险天气影响的航线进行约束处理后，自动绕飞飞行受限区，找到相对代价最小的改航路径。算法执行过程中，适应度值随迭代次数变化如图8所示，从中可以看出算法运行90代后自动终止，小于设定的最大进化代数，能保证结果收敛。

图7 改航路径规划结果Fig. 7 Route planning result

图8 适应度变化曲线Fig.8 Fit curve

对于求得的改航路径，分别从改航距离，转弯点个数以及转弯角度进行评估，评估结果如表3所示，其中改航起始点到改航结束点的原始路径长度为195 km，改航后的路径长度为212.6 km，增加了约9.2%。

由仿真结果表明，遗传算法所得的改航路径能实现改航路径最短，转弯点最少，转弯角度最小的优化目标，并且规避了飞行受限区域。

表3 改航路径评估结果Tab.3 Reroute assessment results

4 结论

本文首先对航班飞行受限区域的划设与预测进行研究，采用一元线性回归预测模型和边界预测算法对飞行受限区域进行实时准确的预测，然后将预测结果应用于危险天气下的航空器改航，以预测的飞行受限区域作为改航避让区域建立单个航班的改航模型，充分考虑航线结构、航空器性能等其他限制因素，以最短改航距离、最小转弯角、最少转弯点为优化目标建立模型。通过遗传算法对改航模型进行求解，利用罚函数以及修复算子保证生成满足约束条件的可行路径。仿真结果表明：采用该方法可以在危险天气下实时精确地规划出一条安全、经济、减轻管制员工作负荷的改航路径。

参考文献：

[1] DIXON M，WEINER G. Automated aircraft routing through weather impacted airspace [C]//IEEE International Conference on Robotics and Automation，Leuven，Belgium，1998：1725-1730.

[2] TAYLOR C，WANKE C. Dynamically generating operationally acceptable route alternatives using simulated annealing [J]. Air Traffic Control Quarterly，2012，20（1）：97.

[3]宋柯.空中交通流量管理改航策略初步研究[D].南京：南京航空航天大学，2002.

[4]徐肖豪，李成功，赵嶷飞，等.基于人工势场算法的改航路径规划[J].交通运输工程报，2009，9（6）：64-68.

[5] MARTIN O. NICHOLES, CHEN NEE CHUAH，WU S. FELIX ,et al. Inter-domain collaborative routing（IDCR）：Server selection for optimal client performance[J]. Copmuter Communications，2011，34：1798-1809.

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

[7] BOKADIA S，VALASEK J. Severe weather avoidance using informed heuristic search[C]//AIAA Guidance，Navigation and Control Conference，Montreal，Canada，2001：11-19.

[8]董襄宁.飞行的组织与实施[R].南京航空航天大学：民航学院，2003.

[9]王兴隆，徐肖豪，李慧.改航策略中雷暴飞行受限区划设方法[J].科学技术与工程，2013，13（10）：2906-2910.

[10]李雄.飞行危险天气下的航班改航路径规划研究[D].南京：南京航空航天大学，2009.

[11]林欢.航空器动态改航的自动化处理技术比较[J].中国西部科技，2011，10（29）：34-35.

[12]陈冬华.旅行商问题推广及其混合智能算法[J].华东交通大学学报，2011，28（2）：102-106.

（责任编辑 姜红贵）

Research of Flight Reroute Based on Flow Constrained Area

Jiang Xin1，2，Hu Minghua1，Zhang Ying1，Tian Wen1
（1.College of Civil Aviation, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China；2 . The 709th Research Institute , China Shipbuilding Industry Corporation , Wuhan 430074，China )

Abstract：Dangerous weather affects flight safety and is an important reason for flight delay. By establishing flow constrained area under dangerous weather, using a linear regression forecast model and proposing an improved method, this study forecasted the location and boundary of flow constrained area dynamically. Adopting the predicted low constrained area as the constraints and taking flight performance and safety into account, it established a reroute model and applied the genetic algorithm by setting the shortest path of reroute, the least turning points and minimum average turning angle as the optimization goal. The simulation results showed that the designed route can avoid flight constrained area and achieve the goals of security, economy and reduce controllers’workload.

Key words：flow constrained area；location forecast；boundary forecast；genetic algorithm；reroute

中图分类号：V355

文献标志码：A

文章编号：1005-0523（2016）03-0060-08

收稿日期：2015-11-19

基金项目：国家自然科学基金项目（71301074）

作者简介：蒋昕（1991—），女，硕士研究生，主要研究方向为空中交通流量管理。

通讯作者：胡明华（1962—）,男，教授，博士生导师，主要研究方向为交通运输规划与管理。