基于空中交通特征的空域扇区动态划分方法

摘要

本发明属于空中交通管理领域，公布了一种基于空域交通特征的扇区动态划分方法，其目标在于根据管制空域中交通情况的变化确定与之相适应的扇区划分，以达到优化利用空域资源目的。该方法包括空域信息提取、空域建模和扇区优化划分算法设计三个方面。首先，基于空域静态结构信息和空域动态信息建立空域拓扑结构等数据库；然后将关键点作为节点，航路作为边，用复杂网络模型描述空域结构；再由空域动态信息计算复杂网络模型中相关联节点的相似度，建立加权复杂网络，利用基于加权复杂网络的K-Means聚类算法建立空域凸胞模型；最后，将空域凸胞模型与混合编码遗传算法相结合，得到最终的扇区划分结果。本发明普遍适用于实际空域。

说明书

技术领域

本发明属于空中交通管理技术领域，涉及一种利用空域交通信息提取交通特征并基于交通特征对空域扇区结构进行划分调整的方法。

背景技术

当前空中交通管制中的重要手段是将空域划分成若干个扇区，每个扇区分别由一个或多个管制员进行管制。空域扇区划分直接决定了各个管制员的工作负荷，合理的扇区划分是保证交通安全和效率的关键。

空域扇区划分就是在确保管制安全和飞行安全的基础上，将空域划分为若干管制区，均衡分配各扇区管制员的工作负荷，保证每个扇区的工作负荷在合理的阈值内。空域动态划分是基于不同时段内空中交通的变化采用不同的、与之相适应的扇区划分，以提高空域资源的利用率、增加空域容量和优化人员配置。

当前，主要的扇区划分方法是由有经验的管制人员根据经验，基于交通流量的实际变化，对扇区结构进行调整，做出扇区划分和扇区合并、拆分决策。但是由于这种方法与管制人员的素质密切相关，主观性太强，不能保证得到最优的扇区划分方案。因此，基于空域信息，将数学模型结合优化算法的空域扇区动态划分方法有很重要的实际意义。

目前，空域扇区动态划分方法已经取得一些研究成果。2004年Yousefi等人基于网格模型，将扇区规划分问题转换为整数规划问题。2009年Xue等人基于Voronoi图模型划分扇区，先利用遗传算法优化中心点位置，然后利用Voronoi图算法直接生成扇区边界。2009年Basu等人基于航迹，得到带有时间标识的动态航迹段，据此进行扇区划分。2010年Li等人将加权图模型与谱二分法相结合，确定扇区边界。2012年Tang等人仿真对比以上几种模型（除航迹模型），并提出一种基于元胞的改进模型。将该模型与遗传算法相结合，形成完整的扇区划分方法。上述方法普遍存在问题是，没有充分利用空中交通信息，尤其是空域的动态交通特征。在大多数扇区划分方法中，基于空域静态信息建立空域模型，而空域动态信息仅用于量化管制员工作负荷。同时扇区约束条件及管制的安全性考虑不够充分，部分研究中扇区划分结果存在锯齿形边界，或者航路在某个扇区内穿越时间过短等问题。

发明内容

针对上述问题，本发明提出一种基于空中交通特征的动态扇区划分方法，在保证管制安全的前提下，能够根据空中交通的变换情况确定与之相适应的扇区划分。为了达到上述目的，本空域扇区动态划分方法包括以下四部分：

空域静态结构信息提取。基于机场、航路点、冲突点等关键点位置和航路拓扑结构，建立关键点坐标数据库、航路拓扑结构数据库等能反映重要空域结构特征的数据库。

空域动态信息分析处理。该部分主要包括以下四个方面：

（1）历史飞行计划处理。统计全天航班的飞行信息，预测空域的交通流量分布情况和变化情况。

（2）雷达数据统计。以雷达数据的更新时间为采样周期，统计每个采样时刻雷达点迹的位置，修正（1）中预测的交通特征，得到空域实际的交通流量分布情况和变化情况。

（3）飞行状态统计。以航段为统计单位，根据管制员与飞行员的交互信息，统计每个采样时刻各架飞机的飞行状态。

（4）管制员工作负荷计算。以飞机数量化管制员工作负荷。

空域模型建立。该部分主要包括以下三个方面：

（1）基于空域静态结构信息建立复杂网络；

（2）基于空域动态信息建立加权复杂网络；

（3）利用基于加权复杂网络的K-Means聚类算法建立空域凸胞模型。

空域扇区优化划分。该部分主要包括以下两个方面：

（1）扇区划分。基于整数编码遗传算法确定扇区的初始边界；

（2）扇区边界优化。基于浮点数编码遗传算法调整扇区边界，使得扇区负荷更加均衡。

本发明的空域扇区划分方法包括以下步骤：

步骤一，提取空域静态结构信息，方法如下：

（1）根据空域中关键点（机场、航路点、冲突点）的位置信息，建立关键点坐标数据库；

（2）根据关键点间的航路连接情况，建立航路拓扑结构数据库。

步骤二，基于历史飞行计划，预测空域交通流量分布情况和变化情况，方法如下：

（1）根据历史飞行计划，得到每架航班进出目标管制空域的时间；

（2）根据历史飞行计划，得到每架航班在目标管制空域内的飞行路径，从而得到途经的航路点及对应的时间；

（3）根据历史飞行计划和步骤二（1）、（2），规定采样时刻，计算出每个采样时刻各架航班在目标管制空域中的坐标位置，建立航班航迹预测数据库；

（4）基于航班航迹预测数据库和空域拓扑结构图，预测空域交通流量的分布情况和变化情况。

步骤三，基于雷达数据，得到实际的交通流量分布情况和变化情况，方法如下：

（1）以雷达监测设备数据更新的间隔时间作为采样时间，统计每个采样时刻各航班雷达点迹的位置坐标，建立雷达点迹数据库；

（2）根据雷达点迹数据库修正补充航班航迹预测数据库，建立航班航迹数据库；

（3）根据航班航迹数据库，得到空域交通流量的分布情况和变化情况。

步骤四，根据管制员与飞行员的交互信息，得到每个采样时刻各架飞机的飞行状态，方法如下：

（1）根据每架次航班在目标管制空域内飞行过程中，管制员与飞行员的信息交流，得到每架航班的飞行状态改变情况；

（2）基于步骤四（1），得到每个采样时刻各架航班的飞行状态，建立飞行状态数据库。

步骤五，基于飞机数量化管制员工作负荷，计算出监视负荷、协作负荷以及冲突解决负荷，建立监视负荷数据库、冲突解决负荷数据库和协作负荷数据库。

步骤六，基于步骤一～五中得到的数据库，建立空域加权复杂网络模型，方法如下：

（1）将关键点作为顶点，航路作为边，根据关键点坐标数据库和航路拓扑结构数据库建立空域复杂网络模型；

（2）提取反映主要交通特征的指标，结合飞行状态数据库，建立各关键点的复杂性因子向量；

（3）基于复杂性因子向量计算相似度，以相似度作为权值，建立加权复杂网络。

步骤七，基于加权复杂网络的K-Means聚类算法建立空域凸胞模型。

步骤八，进行扇区划分，方法如下：

（1）基于空域凸胞模型，将每个凸胞当做虚拟点，凸胞间连接的航路为边。以量化后的管制员工作负荷为权值，建立空域加权图模型；

（2）基于加权图模型进行整数编码并初始化种群；

（3）进行遗传算法迭代操作，得到最优子种群；

（4）对最优子种群进行解码，得到扇区划分。以跨越两个扇区的航路的中点作为边界点，确定初始扇区边界。

步骤九，进行扇区边界优化，方法如下：

（1）将步骤八中得到的最优子种群作为该部分遗传算法的输入，采用浮点数编码，初始化种群；

（2）进行遗传算法迭代操作，调整边界点位置，得到最优个体；

（3）对最优个体进行解码，得到最终的扇区边界。

本发明的空域扇区动态划分方法普遍适用于实际空域。发明中对空域交通特征进行了充分的分析提取，基于这些空域交通特征建立的空域凸胞模型更加准确全面地描述了空中交通特征。扇区边界优化使得划分后的扇区负荷更加均衡。通过本发明中的扇区划分方法得到的扇区划分可满足各扇区工作负荷基本均衡并在合理的阈值之内，满足扇区约束条件，且划分后的扇区边界平滑，保证管制安全。

本发明的有益效果在于：

（1）通过本发明中扇区划分方法得到的扇区划分可实现扇区内管制员负荷的均衡，并尽可能减少由于扇区划分而产生的协作负荷。增加了空域容量，提高了空域资源的利用率。

（2）通过本发明对空域扇区结构进行规划，得到的扇区划分结果满足空域管制的安全性要求，保证了管制安全和飞行安全。

附图说明

图1为空域扇区划分方法流程图；

图2为提取空域静态结构信息流程图；

图3为提取空域动态信息流程图；

图4为建立空域加权复杂网络模型流程图；

图5为建立空域加权图模型流程图；

图6为基于整数编码遗传算法的扇区划分流程图；

图7为整数编码方式示意图；

图8为基于浮点数编码遗传算法的扇区边界优化流程图；

图9为浮点数编码方式示意图；

图10为应用本发明对某日北京管制区的扇区划分结果；

图11为应用实例扇区内飞机数的概率分布图。

具体实施方式

图1是空域扇区划分方法流程图，具体实施方式如下：

步骤一，提取空域静态结构信息，方法如下：

（1）根据空域中关键点（机场、航路点、冲突点）的位置信息，建立关键点坐标数据库。

图2是建立空域静态结构信息流程图，图2中关键点坐标数据库中包含关键点编号及其对应的坐标，数据库中的坐标是将实际的经纬度坐标转换成的直角坐标。

（2）根据关键点间的航路连接情况，建立航路拓扑结构数据库。

图2中航路连接情况可描述为两个关键点之间是否有航路连接，若有，则航路拓扑矩阵中对应元素为1，反之为0。

图3为建立空域动态信息流程图，动态信息的提取由步骤二～四完成。

步骤二，基于历史飞行计划，预测空域交通流量分布情况和变化情况，方法如下：

（1）根据历史飞行计划，得到每架航班进入管制空域的时间以及离开管制空域（或降落在管制空域内）的时间。

（2）根据历史飞行计划中航班飞行途经的关键点及其途经时间，由关键点确定其对应连接的航段，从而得到飞行路径。

（3）与步骤三保持一致的采样时刻，基于已知的信息，预测每个采样时刻各航班的位置坐标信息，将这些坐标信息汇总，建立航班航迹预测数据库。

（4）基于航班航迹预测数据库和空域拓扑结构图，预测空域交通流量的分布情况和变化情况。

步骤三，基于雷达数据，得到实际的交通流量，方法如下：

（1）以雷达监测设备数据更新的间隔时间（一般每两分钟更新一次雷达显示）作为采样时间，记录显示的雷达点迹坐标位置，得到实际的飞行航迹数据，据此建立雷达点迹数据库。

（2）根据雷达点迹数据库修正补充航班航迹预测数据库，建立航班航迹数据库。

实际的空中交通管理中可能出现航班取消、增加临时航班、航班延误等情况，雷达监视反映了实时的交通情况。

（3）根据航班航迹数据库，得到空域交通流量的分布情况和变化情况。

步骤四，根据管制员与飞行员的交互信息，得到每个采样时刻各架飞机的飞行状态，方法如下：

（1）根据每架次航班在目标管制空域内飞行过程中管制员与飞行员的信息交流，得到每架航班的飞行状态改变情况。

管制员与飞行员的信息交流包括飞行员报告飞机位置和飞行状态信息，管制员发出改变飞行状态或解决冲突的指令等，由此可以得到航班在飞行过程中速度改变、航向改变等信息，并且可以得到每次飞行状态改变对应的时间、位置信息。

（2）基于步骤四（1），得到每个采样时刻各架航班的飞行状态，建立飞行状态数据库。

步骤五，基于飞机数量化管制员工作负荷，计算出监视负荷、协作负荷以及冲突解决负荷，建立监视负荷数据库、冲突解决负荷数据库和协作负荷数据库。

步骤六，基于步骤一～五得到的数据库，建立空域加权复杂网络模型，方法如图4所示，具体方法如下：

（1）将关键点作为顶点，航路作为边，根据关键点坐标数据库和航路拓扑结构数据库建立空域复杂网络模型。

（2）提取反映主要交通特征的指标，结合飞行状态数据库，建立各关键点的复杂性因子向量。

本发明基于空域复杂性分析空中交通特征。通过主成分分析选出的代表扇区85%复杂性的五个指标：航空器平均通过时间，总的冲突数量，航空器平均速度，航空器数量，爬升的航空器比例。定义两个主成分，分别为“密度因子”（主成分一）和“飞行态势因子”（主成分二）。通过主成分分析法得到指标的得分函数如下：

密度因子=0.247×平均通过时间+0.348×总冲突次数-0.383×平均速度-0.011×爬升航空器比例+0.413×航空器数量

飞行态势因子=-0.685×平均通过时间-0.024×总冲突次数+0.141×平均速度+0.465×爬升航空器比例-0.153×航空器数量

采用向量空间法将关键点i周围的交通特征表示成复杂性因子向量di，对于关键点i有：

d_i＝(t_1i,t_2i)

其中，t_ji表示主成分j在关键点i周围的值。

（3）根据图4所示的流程，基于复杂性因子向量计算相似度，以相似度作为权值，建立加权复杂网络。

步骤七，基于加权复杂网络的K-Means聚类算法建立空域凸胞模型，方法如下：

（1）根据原始数据集计算相似度，得到相似度矩阵。

（2）根据相似度矩阵建立加权复杂网络：以数据为节点、相似度作为数据之间连边的权值表示数据之间的连接强度。

（3）计算各个节点的加权复杂网络综合特征值。

（4）对各节点的加权复杂网络综合特征值进行排序，形成由大到小的队列。

（5）从队列中依次选取K个加权网络综合特征值高、与已被选作初始聚类中心的节点之间没有连边的节点作为初始聚类中心。

（6）以所选的k个节点作为初始聚类中心，采用K-means算法，根据相似度矩阵对数据集进行划分迭代，形成聚类。

通过上述算法将关键点聚成若干类，将每类最外层的点相连，形成凸胞。整个空域范围内即建立凸胞模型。

步骤八，进行扇区划分，扇区划分部分遗传算法的迭代过程如图6所示，方法如下：

（1）基于空域凸胞模型，将每个凸胞当做虚拟点，凸胞间连接的航路为边。以量化后的管制员工作负荷为权值，建立空域加权图模型，方法如图5所示。

（2）基于加权图模型进行整数编码并初始化种群。

为了保证扇区的管制安全性，扇区包含以下几点约束条件：凸约束、连通性约束、最小距离约束、最短穿越时间约束，在遗传算法的设计中将充分考虑扇区约束。所以，初始化种群中所有的个体都应满足连通性约束。图7为采取的整数编码方式。

（3）进行遗传算法迭代操作，得到最优子种群。

扇区划分有以下目标：均衡扇区内负荷(f_b)、优化扇区间协作负荷(f_c)和最大化扇区飞行时间(f_t)。将扇区划分的目标作为适应度函数f，描述如下：

f＝a₁f_b+a₂f_c-a₃f_t

其中，f_b、f_c和f_t的表达式分别为：

$>f_b=\underset{k=1}{\overset{K}{\Sigma }}\frac{|w\left(k\right)-W_T{K}^{-1}|}{W_T{K}^{-1}}$>

$>f_c=\frac{1}{W_T}\underset{k=1}{\overset{K}{\Sigma }}{\omega }_c\left(k\right)$>

$>f_t=\underset{k}{\min }\left\{\frac{S_T\left(k\right)}{N_k}\right\}$>

其中，K表示扇区数目，w(k)表示扇区内工作负荷，表示扇区间协作负荷，S_T(k)表示扇区k的飞行时间，N_k表示扇区k的飞机数。

计算每代种群中个体的适应值，然后依次进行选择、交叉、变异操作，得到下一代种群。为了保证扇区的连通性约束，在每一代交叉算子操作完成后，需要检测新生成种群中每一个个体的连通性。若不连通，则需要进行修复，使之连通。

（4）对最优子种群进行解码，得到扇区划分。以跨越两个扇区的航路的中点作为边界点，确定初始扇区边界。

得到的最优种群中每个个体有一个与之对应的扇区划分，这些扇区划分的边界点将作为下一步边界优化的输入。

步骤九，进行扇区边界优化。图8描述了扇区边界优化部分遗传算法的迭代过程，具体方法如下：

（1）将步骤八中得到的最优子种群作为该部分遗传算法的输入，采用浮点数编码，初始化种群。染色体编码中包含边界点坐标的信息如图9所示。

（2）进行遗传算法迭代操作，调整边界点位置，得到最优个体。

遗传算法迭代操作中的适应度函数与步骤八中相同。由于种群个体之间的扇区划分不同，交叉算子不适用与该部分。

变异算子通过改变某个边界点的位置实现染色体变异。为了满足扇区最小距离约束，边界点的位置坐标变化需要进行约束。具体做法如下：

为加权图中边界两侧的凸胞添加保护区，保护区边界距离凸胞边界为d_min（d_min为最小安全距离）。边界点和边界不能在保护区内，保证边界与凸胞的距离不小于最小约束距离d_min。则边界点的坐标取值范围缩小为所在边除保护区内的点之外的所有点的坐标。变异算子为基于一个随机变量将选取的边界点在边的有效范围内移动，改变染色体中对应基因对的值。

（3）对最优个体进行解码，得到最终的扇区边界。

下面给出本发明的应用一个实例。

根据2012年12月某天（天气晴朗）的实际交通数据和北京管制区的历史交通数据，应用本发明所述的扇区划分方法对北京管制区进行扇区划分，结果如图10所示。由图10可以看出：得到的扇区划分，边界平滑并且满足凸约束。将相同的数据应用于基于加权图的扇区划分方法，得到的扇区划分中，北京管制区交通高峰期（13:00～17:00）内协作负荷为4600。而基于本发明所的到的扇区划分中，协作负荷为2800，由于扇区划分而产生的协作负荷明显减少。

图11为扇区内飞机数的概率分布图。扇区内的飞机数概率表示每分钟扇区内包含k架飞机的概率。扇区内飞机数若小于管制安全上限则认为管制安全，则扇区安全概率为99.51%。表示超过99%以上的时间，各扇区内包含的飞机数满足安全要求，划分的扇区可以保证管制的安全性。