一种基于加权图模型的空域扇区划分方法

摘要

本发明属于空中交通管理领域，提出了一种基于加权图模型的空域扇区设计方法。本发明在建立一种能够准确表示航路和空中交通量的无向图模型后，将图顶点作为Voronoi图基点把空域离散化，然后依据每个Voronoi图单元的工作负荷和航路上的交通量构建加权图模型。进而，利用融合了一般加权图切算法、负荷平衡算法和启发式算法的图划分方法，将加权图模型划分为多个子图，再由各个子图所包含的顶点映射到对应的Voronoi图单元组合形成扇区。由本方法设计的扇区不仅满足负荷平衡和协作负荷最小化约束，而且满足扇区最小距离约束、凸性约束和连通性约束。

主权项

一种基于加权图模型的空域扇区划分方法，其特征在于包括以下步骤：步骤一，建立空域加权图模型，方法如下：(1)根据给定的空域结构信息，构建无向图模型G＝G(V,E)，其中，顶点集V＝{1,2,...,n}代表机场、航路点和航路交叉点等关键点，边集合E＝{e_ij＝(i,j):i,j∈V}，e_ij表示连接顶点i和j的航路段；(2)在无向图模型基础上，以顶点集合V中的顶点作为基点建立Voronoi图D；利用D将空域划分为n个Voronoi图单元D_i，i＝1,2，...,n，其中D_i表示第i个顶点所对应的Voronoi图单元；Voronoi图单元的边界在合并单元成为扇区时将部分地成为扇区边界；这种通过Voronoi图离散空域模型形成单元的方式可以保证将单元组合形成扇区时满足扇区的凸性约束；对空域离散化后，有一些基点离单元边界很近，如果所划分的扇区边界恰好落在这条边界上，那么扇区不符合最小距离约束，将这条边界删除，将此条边界所连接的两个单元合并；合并后的单元数目为r，r≤n，通过合并措施使得这些单元在组合成扇区时能够保证最小距离约束；(3)在空域离散化的基础上，根据交通数据计算一段时间内D_i的工作负荷w_i和每条航路e_ij上的交接负荷，i＝1,2，...,r；(4)将D_i抽象成一个辅助的加权图模型，其中，D_i抽象成一个顶点，顶点权重就是D_i的工作负荷w_i；若D_i和D_j之间有航路连接，则所有航路就抽象成一条边，边的权重就是连接D_i和D_j所有航路上交接负荷之和，记为w_ij；将所构造的加权图模型记为G_w，G_w＝(w,W)，其中w为顶点权重向量，W为边的权重矩阵表示：w＝[w₁,w₂,...,w_r]^T         (1)W＝[w_ij]_r×r，w_ij＝w_ji         (2)步骤二，确定扇区数目，方法如下：根据给定空域的总负荷A_c和每个扇区的最大负荷S_c确定扇区数k，也就是确定划分加权图子图数目，扇区数k按下式计算：其中，是向上取整运算；步骤三，采用由一般加权图切算法、负荷平衡算法和启发式算法融合成的图划分方法划分加权图模型；步骤四，将每个子图所包含的顶点对应的Voronoi图单元组合形成扇区。