基于改进桶结构轮盘算法的混合航线网络仿真

赵得存， 赖 欣

(中国民用航空飞行学院 空中交通管理学院， 四川 广汉 618307)

中国的航线网络分为固定(ATS)航线网络和临时航线网络，相应的其他国家或者组织也存在类似航线网络布局，例如欧洲区域的航线网络除了ATS航线网络还有CDR航线网络和DCT航线网络。由两种或者两种以上的航线网络组成的航线网络称为混合航线网络。航线网络是航空公司进行航班走向规划的基础。固定航线作为空中交通运输主要路线，连接各飞行情报区，承担着绝大部分的运输任务，临时航线主要分在限制区域、枢纽机场附近，作为固定航线的补充。固定航线和临时航线使用有较大区别，固定航线可作为航空公司的长期航班运行的走向规划基础，而临时航线的使用需要航空公司临时提出申请，并获得相关管理部门的批准，但临时航线具有距离短、绕飞区域少的优势，使用临时航线可为航空公司节省燃油消耗、提高运行效率。例如2019年，共有37.3万架次航班使用临时航路，缩短飞行距离1 570万km。在航路图中查询临时航线由于存在大量的固定航线以及图幅问题，在查询过程需要反复对航路图逐步放大查询，十分浪费时间，对公司进行航线规划产生障碍。因此可见构建能够对固定航线网络和临时航线网络可视化的航线网络极为重要。

1 相关理论

1.1 基于复杂网络理论的航线网络分析

从复杂网络[1-3]的角度来分析航线网络[4-12]，每一种航线网络都有一定的小世界性和无标度性[13-15]，节点度的分布符合幂律分布。每一种航线网络都能够由图论中的以下部分组成：

1)网络的节点。无论固定航线网络或是临时航线网还是其他航线网络，均以航路点为节点。

2)节点度。不同的航线网络，节点有不同的连接方式，但节点的度都符合幂律分布。

3)网络的边。组成航线的航段为网络的边,且两节点之间有且仅有一条边。

4)无向网络。多数情况下，两航路点之间是双向的，即航路点A可以到达航路点B，那么航路点B也可以到达航路点A，即网络是双向的。因此，在进行航线网络构建时，可以将双向网络抽象为无向网络。

以中国固定航线网络和临时航线网络为例，节点度分布见表1，混合航线网络节点和边数量统计分析见表2。

根据表1可知，在临时航线网络中度数为1或2的节点数量占据总节点数量的85%。在固定航线网络和混合航线网络中度数为2、3、4、5的节点数量分别占据各自总节点数量的89%，符合幂律分布(二八定律)。

表1 混合航线网络节点度统计

表2 混合航线网络节点和边数量统计

1.2 桶结构的轮盘算法

根据上文对航线网络的分析，航线网络是典型的无标度网络，而生成无标度网络的经典算法主要有简单轮盘算法、随机选择算法、基于桶结构的轮盘算法等。使用简单轮盘算法构建无标度网络会出现拒绝式抽样导致无法正确连边问题。使用随机选择算法在构建无标度网络时，需要花费较长的时间遍历图中所有节点来进行增长。基于桶结构的轮盘算法以分桶的方式既避免了拒绝式抽样问题又解决了在节点数量较大时，图增长过慢的问题。

基于桶结构的轮盘算法(roulette wheel bucket，RW-bucket)是赌轮盘算法和桶排序结合形成一种算法，将相同性质或相同属性的个体归在一个桶内，进行统一操作，其操作准则为：各个个体被选中的概率与其适应度大小成正比。进而在使用该算法进行航线网络构建时需要归类的个体即为节点；划分依据为节点度相同归为同一个桶内；个体适应度即为节点度的大小，节点度越大则被选中的概率越大；算法的核心为构建网络图时的选点和连边。

基于桶结构的轮盘算法的传统步骤如下：

1)初始生成一个无向图G0，节点集为{v1,v2,…，vm}，边集为{e1,e2,…，em}。

2)随机产生一个节点vk+1和随机数r。

3)计算节点的度，按照度相同原则分成桶。

4)计算桶的概率密度函数p(Bi)和累积分布函数P(Bi)满足

(1)

(2)

5)逐个判定每个桶是否满足P(Bi)≤r≤P(Bi+1)条件，若不满足返回步4)，若满足则在满足的桶Bi内随机选择一个节点vm与vk+1进行相连；与新节点相连的概率p(vm)满足

(3)

6)将度变化的节点重新分配对应的桶内。

7)统计节点个数和边数。

8)判定网络图G中节点和边数是否满足要求，若满足则停止，不满足则转步骤2)。

从上述传统桶结构的轮盘算法流程可以得出，桶结构的轮盘算法生成网络的节点数量随着网络的增长而越来越多；度相同的节点数量也越来越多，网络中节点的度随着网络增长变得越来越大；网络中边数也越来越多。总的来说基于传统的桶结构的轮盘算法生成的网络是没有边界限制的。然而混合航线网络却是在节点数量、边数量、相同节点数量、最大节点度方面有着严格的限制。根据上述分析可见，虽然两者在结构上具有相似性，但在具体网络生成的数量和生成规则具有差异性，因此无法直接利用RW-bucket进行混合航线网络的构建。所以需要在传统算法的基础之上对传统算的构建网络的增长，连边进行约束改进，以满足构建混合航线网络的要求，此外还需要对边赋予标签，进行边分类模拟混合航线网络中固定航线和临时航线共存的现象，并能够进行其可视化。

2 桶结构的轮盘算法改进

根据上文分析，为了更好地进行混合航线构建，从固定参数、节点来源、连边限制3个方面对原算法进行改进，使构建出的网络符合混合航线网络结构的特征。对边赋予标签，通过辨别边标签，实现对混合航线网络中的固定航线和临时航线进行模拟和可视化。基于上述思想，改进算法执行步骤如下：

步骤1：通过设定节数、边数和最大节点度给出一个待增长的初始网络图和生长上限。设定|N|=a、|B|=b和deg(vj)max=c，a、b、c为常数。

步骤2：通过从已有的节点中随机选取一个节点当作增长节点。同时在(0，1)内产生一个随机数为连边做依据。

步骤3：通过桶结构将众多的节点统一划分进行归类处理。以便于为连边做准备加快网络生长速度。

步骤4：计算桶的概率密度函数和累积分布函数。通过计算桶的概率密度函数和累积分布函数来避开逐个计算每个节点的概率密度函数和累积分布函数以此提高算法速度，并为连边提供数据支撑。所用公式为

(4)

(5)

步骤5：判定随机数是否满足不等式P(Bi)≤r≤P(Bi+1)，决定增长节点的连接对象。

步骤6：重新划分桶和判定网络成熟度。统计Bi和|Bi|；判定是否满足i=c，若满足，则对应的Bi桶内的节点不允许与其他节点相连，不满足进行下一步；判定是否满足|Bi|=b，若满足，则Bi桶锁定不进行任何操作，且Bi-1桶内节点不允许与其他节点相连，不满足则进行下一步；统计|N|，判定是否满足|N|=a，若满足则停止，不满足则转步骤2。

步骤7：对已成熟的网络中的节点赋予坐标，边赋予标签，并根据标签进行着色，以此来模拟混合网络中包含固定航线和临时航线的情况。

算法执行步骤中所用符号与意义见表3。改进算法的执行流程如图1所示。

表3 所用符号和意义

图1 改进的RW-bucket算法流程

3 基于改进算法的混合航线网络仿真

为验证改进RW-bucket算法对构建混合航线网络的可行性，采用Python软件对改进RW-bucket算法进行编程，并对两个情报区内的航线结构数据进行统计。根据统计结果，对相应情报区的混合航线网络进行构建，实现混合航线网络的方针，同时实现固定航线和临时航线的可视化。

验证飞行情报区1的航段数和节点度分布统计数据见表4、表5。

表4 飞行情报区1节点和边数量统计

表5 飞行情报区1节点度统计

根据统计数据执行算法，其中a=39，|B|=36，|Bi|={9,8,4,3,2,1,1}，c=7。

根据Python编程执行算法得出验证飞行情报区1的混合航线网络结构图，如图2所示。

虚线代表临时航线，实线代表固定航线图2 飞行情报区1混合航线网络模拟图

图3为图2对应的真实航路图，通过实物对比验证方法，从节点连接正确性和航线类别表达的正确性两方面来检验方法的可用性。可以清晰明确地看出图2对图3从节点连接和航线类别两方面成功地进行了模拟。图2完整模拟出图3的航线结构，并能对固定航线和临时航线进行可视化区分。

图3 飞行情报区1的真实航线结构

飞行情报区2的节点数量、边数量和节点度分布统计见表6、表7。

那么此时算法中的a=16，|B|=36，|Bi|={11,1,1,1,1,0,1}，c=7。着色边数量为8条。

表6 飞行情报区2节点和边数量统计

表7 飞行情报区2节点度统计

根据Python编程执行算法得出飞行情报区2的混合航线网络结构模拟图，如图4所示。

虚线代表临时航线；实线代表固定航线图4 飞行情报区2混合航线网络模拟图

图5为图4对应的真实航路图，通过实物对比验证方法，从节点连接正确性和航线类别表达的正确性两方面来检验方法的可用性。可以清晰明确地看出图4对图5从节点连接和航线类别两方面成功地进行了模拟。图4完整模拟出图5的航线结构，并能对固定航线和临时航线进行可视化区分。

图5 飞行情报区2的真实航线结构

以上是在小范围进行的验证，为了说明该方法也适用于大范围的航线可视化，将飞行情报区1、2所在的完整情报区的航线网络利用该方法进行可视化，如图6、图7所示。

图6 情报区1所在的完整情报区A的航线 网络结构

图7 情报区2所在的完整情报区B的航线网络结构

图6、图7中圆形区域分别对应飞行情报区1、2的航线结构，由于实际航路图图幅问题无法进行实物对比验证地展示，因此从节点数量和固定航线以及临时航线所包含的航段数量对模拟网络和实际航路图进行比较，见表8。

表8 对比验证结果

从表8中可以明确看出模拟结果与实际航路图所包含数据一致，且在与实际航路进行实物对比验证得出模拟结果的航线网络结构和连接与实际网路一致。综上和以上验证可以得出该方法能够对实际航路图进行模拟构建并对固定航线和临时航线进行可视化区分。

4 结语

研究了中国航线网络中的航线类型，介绍了固定航线和临时航线的作用，分析了固定航线和临时航线在航路图中存在的查询矛盾，提出了构建能够对固定航线网络和临时航线网络可视化的航线网络的方法。从复杂无标度网络角度对中国的航线网络进行研究，总结航线网络的特点，针对航线网络存在的特点和构建要求，对构建航线网络的算法进行比较筛选。得出使用RW-bucket算法进行航线网络，为了能够更为贴合航线网络的构建要求，对RW-bucket进行改进。从中国航空资料汇编中获得航路数据，使用改进后的方法进行模拟构建，将构建结果采用实物对比验证的方法，与实际航路图对应的部分进行从节点连接和航线类别表达两方面来评价方法的适用性。经过对比验证后，结构表明，该方法能够正确地表达节点连接问题和航线类别可视化问题。

综上，本文提出了一种构建对固定航线网络和临时航线网络可视化的航线网络的方法，该算法采用对节点先分桶后统计再连接的方法，避免了在构建航线网络出现的“拒绝式抽样问题”，并且通过桶结构存储节点，进一步降低了算法复杂度。通过对航线进行标签化，在算法实现过程中通过判定标签类型，对固定航线和临时航线进行可视化区分。该方法可助情报人员对航线类型快速判定出航线类别，其次提高临时航线在航班走向规划时的使用频率，充分发挥临时航线具有的截弯取直、节省飞行时间、降低运行成本的优势。