基于网络流的多管制扇区通行能力

赵嶷飞，黄婕，齐雁程

(1.中国民航大学空中交通管理学院，天津 300300；2.民航局空管局运行管理中心，北京 100020)

随着经济发展，中国的民航事业欣欣向荣，空中交通流量开始大幅度增长。空中交通流量与空管保障能力不足的矛盾相对突出。作为空中交通管理系统的基本单元，管制扇区的交通流构成并不单一，运行环境日益复杂且航班之间的冲突调配频繁，这在一定程度上成为制约空中交通流量增长的关键因素。为了缓解空域的拥堵并使航班流量合理高效地在空中交通网络中的各条航路上运行，研究管制扇区的通行能力已经成为不可忽视的问题。空域的通行能力的定义为：在特定的空域结构、管制规则、间隔标准、天气状况和航路航线网络结构等实际情况下，在单位时间内能够通过指定区域断面、剖面或者节点的最大航空器数量[1]。空域的通行能力以扇区为单位来进行评估。在不考虑各种动态因素的限制下从整体系统分析的角度来说，扇区的通行能力可以通过扇区的容量来进行评估[2]。中国民用航空局发布的《空域容量评价方法指导材料》[3](IB-TM-2006-004)将容量定义为：指定空域和机场在一特定时间内能够接受的最多数量的航空器架次。管制扇区并不是完全相互独立运行的，相邻的扇区之间存在着物理拓扑结构和交通流态势的耦合关系[4]。扇区内的运行不仅与该扇区内部航路结构等因素相关，也会被其他扇区的管制运行影响。因此，多扇区的容量并不是多个单扇区容量的简单相加。

前人针对扇区通行评估的研究多集中在以下三个方面。

(1)通过管制员的工作负荷对扇区容量进行评估。Schmidt[5]对管制员的工作负荷进行量化，并基于空域活动、管制员的工作负荷以及飞机延误的关系建立排队论模型；Tofukuji[6]利用回归模型得出交通流和空域容量的关系，并利用管制员的极限工作负荷来评估扇区的实际容量；万莉莉[7]通过对管制员的工作负荷建立模型对扇区容量进行评估。

(2)通过重要航路点、航路交叉点、雷达数据等依据交通流特性对单扇区容量进行评估。周进[8]结合空中交通具体情况对航路网络容量进行理论评估，并对航段和交叉点进行不同情况的研究；王红勇等[9]基于实际雷达数据建立一种扇区运行容量计算方法，根据交通流特性计算扇区不同交通流模式下最大的流量；王莉莉等[10]分析了机型组合、交叉角度和航路长度对于航路交叉点容量的影响，提出了改进的航路交叉点容量模型以及航路模型。

(3)对动态因素影响下的扇区容量进行评估分析。赵嶷飞[11]抽象了空中交通网络并建立了短期空中交通流量管理的动态网络流模型；田勇等[12]提出了影响扇区动态容量的因素，并结合扇区结构、管制员工作负荷以及雷达信息建立扇区动态容量评估模型。

综上所述，传统的通行能力研究通过管制员的极限工作负荷间接进行评估；或者只考虑单扇区航路点、航路网络的交叉点达到最优的情况；以及分析在各种动态因素下(如危险天气、军航活动等)单扇区通行能力的变化。但是上述研究几乎没有对多扇区的航路网络进行系统的评估与判断。空域是一个复杂的系统，因此更需要从整体的角度研究分析相互影响相互联系下的多扇区的通行能力。

对于现有的空中交通流量管理的研究，普遍采用基于数学计算模型的评估方法，以网络流理论为基础，将部分空域抽象成网络建立模型。以华北飞行情报区的部分扇区为例，将不同管制扇区转化为网络图中的节点，将连接扇区间的航路航线转化为网络图中的边，将多扇区的通行能力问题转化为网络流的最大流问题。

1 多管制扇区网络的数学描述

扇区的划分在二维空域上可以看作是对目标空域做二维几何的划分，以空中交通复杂度为依据，通过空域内关键点(导航台、航路点等)进行分割，形成一定数量并在空间上连续的多扇区单元。

如图1所示，算例为华北飞行情报区中连续的5个管制扇区[13](19号扇区、12号扇区、16号扇区、17号扇区、18号扇区)分别以红色框线表示，选取的5个管制扇区覆盖北京首都、天津滨海、河北石家庄3个机场，该空域航班流量较大，且空域结构复杂，覆盖多条航路：B215、A461、A593等。

连接多扇区网络的航路航线具有一定的方向性，因此可以将扇区网络抽象为一个平面赋权连通有向图G=(V,E,C)，其中，V={vn}为扇区网络节点的集合，每一个扇区单元可以简化为一个网络节点vn；E={eij}为网络边集，表示不同扇区网络节点之间的航路航线抽象而成的边的集合。每条边(vi,vj)∈G，如图2所示。

图1中19号扇区可以看作是图2网络中的V1节点，同理12号扇区对应V2节点，16号扇区对应V3节点，17号扇区对应V4节点，18号扇区对应V5，图1中5个扇区分别与图2网络中的5个节点一一对应。e12为连接V1V2节点的航路航线对应的边，e13为连接V1V3节点，e14为连接V1V4节点，e15为连接V1V5节点，e23为连接V2V3节点，e34为连接节点的航路航线对应的边，5个管制扇区对应的节点通过图2中有向的边连接(其中，连接每个扇区的航路并不都是双向的)因此，多管制扇区就转化为了多扇区之间的网络流问题。

红色框线为管制扇区；黑色实线为多扇区网络之间的航路航线不同扇区之间通过航路航线连接来实现通行图1 选取华北情报区的管制扇区Fig.1 Selected control sectors of North China Flight Information Region

图2 多扇区网络抽象示意图Fig.2 Abstract schematic diagram of multi-sector network

2 模型建立

2.1 网络流模型建立

在多起点多终点的网络图中，可以根据图论增设虚拟的起点和终点Vs、Vt，虚拟节点Vs向选取的扇区网络流入无限的流量，扇区网络的流量最终全部汇入Vt节点。如图3所示，将虚拟的起点终点与航路网络连接起来，并且该源节点与汇节点看作为无限大容量，那么多起点多终点的航路网路就转化为一个单起点单终点的航路网络。

e12、e13、e14、e15、e23、e34双向边表示双向航路图3 加设虚拟源汇节点的网络流模型Fig.3 Network flow model with adding source and sink nodes

2.2 约束条件

2.2.1 边容量约束

在多管制扇区转化而成的网络流问题中，每条边eij通行的流量fij都应该满足非负性与边容量限制的约束条件，即

0≤fij≤cij

(1)

式(1)中：fij为节点i～j对应的航路通行的流量；cij为边eij对应的航路的容量限制条件。

2.2.2 点容量约束

每个扇区具有一定容量的限制，当不同的扇区转化为网络流中的节点后，那么这些节点也需要满足非负性与扇区容量约束的条件，即

0≤fk≤wk

(2)

式(2)中：fk为节点k对应的扇区实际流量；wk为节点k对应的扇区的容量限制条件。

2.2.3 流量平衡约束

进入多管制扇区内的交通流需要满足流量守恒的约束条件，对于连接扇区的整条航路的各个节点,流入的交通流量应等于流出的交通流量，即

(3)

式(3)中：fji为流入Vi点的流量。

对于源节点r，有

(4)

式(4)中：fri为源点流出的流量；fir为流入源点的流量；f为源点流出的净流量。

对于收节点s,有

(5)

式(5)中：fjs为流入汇点的流量；fsj为汇点流出的流量；-f为流入汇点的净流量。

2.3 求解算法

2.3.1 算法思想

上述模型将多起点多终点的航路网络视为平面有向赋权连通图，可以通过增设虚拟顶点Vs、Vt转化为单起点单终点的流量分配模型。为了求解上述模型并且满足空中交通管制的时效性要求，可以采用Ford-Folkson算法作为流量分配算法。

Ford-Fulkson算法是用于求解网络中最大流量问题的经典算法。算法通过不断增广来在路径中增加流量以此使网络达到最大流量。也就是说，只要存在从源节点i到顶点j的路径边eij具有可用容量，则可以继续给该条边分配流量。通过不断地将流量增加路径添加到已建立的流量，若无法继续找到可增广路径的时候，此时网络将达到最大流。完成以后，计算各条边各个顶点的流量，验证是否满足该模型的约束条件,若满足，则流量分配结束。

2.3.2 算法步骤

Step 1初始化。令选取的整个扇区网络中各条航路上的流量为fij=0，并对各条边标号为(Cij，fij)，其中Cij为边容量，并将源点Vs设置为(0，+∞)。

Step 2分配流量。采用Ford-Fulkson算法对选取的整个扇区网络分配流量。从Vs出发开始寻找相邻未标号点Vi，设置标号为(Vj，q)，表示从Vj流入，流入量为q；当配流完成之后，若qij≤Cij，表示该航路分配的流量满足约束条件，其中qij为分配给边的流量。

Step 3不断寻找相邻未标号的节点，直至汇点Vt标号完毕或者无法再继续标号。

Step 4寻找增广路。计算航路网络分配之后的流量，采用追溯法确定可行流，根据调整量q对各边容量进行调整。

Step 5判断。判断航路当前的流量是否超过航路的容量，若不超过则可继续返回Step4进行增广调整；若无法继续进行标号，即网络中不存在一条从Vs到Vt的增广路径，此时该扇区网络已经达到最大流，终止算法。

3 仿真验证

3.1 算例构造

该算例选取华北飞行情报区的5个管制扇区(12号扇、16号扇、17号扇、18号扇、19号扇)。假设条件为：①不考虑飞机性能对网络通行能力的影响；②不考虑危险天气造成的延误等待的情况；③终端区内的飞行状况良好，机场航班正常起降。

不同管制扇区的航班进入的间隔并不相同，可以通过《全国民航空中交通运行态势分析报告》[14]查阅可知，华北情报区的管制扇区的航班进入间隔如图4所示。

图4 华北情报区的管制扇区航班进入间隔Fig.4 Flight entry interval in control sectors of North China Flight Information Region

通过上述不同的管制扇区航班进入间隔可以计算得出通向不同扇区的移交架次，即指向该扇区对应节点的边的容量。

(6)

式(6)中：Q为边容量；t为航班进入间隔，min。

扇区容量值可依据《民用航空空中交通流量管理运行指导材料》中国际民航组织推荐的获取区域管制扇区容量方法计算得到[15]。扇区平均飞行时间乘以1.6与18做比较取较小值，即当前扇区容量值(单位：架次/15 min)。各扇区的平均飞行时间如图5所示。

图5 华北情报区的管制扇区平均飞行时间Fig.5 Mean flight time of control sectors in North China Flight Information Region

根据各扇区的航班进入间隔、平均飞行时间计算出边容量、扇区通行能力，如表1所示。

表1 不同管制扇区的航班进入间隔、扇区通行能力、边容量Table 1 Flight entry interval,sector capacity and side capacity of different control sectors

得到边容量以及扇区通行能力后的网络流如图6所示。

图6 计算出边容量及扇区通行能力的网络图Fig.6 Calculating the sides capacity and sectors capacity network

3.2 仿真结果

3.2.1 流量分配表

对上述建立的模型进行仿真分析，工具为 MATLAB 2016a。根据2节所设计的求解算法，对将通过扇区的空中交通流量进行分配，模拟在1 h内的不同航路的分配流量情况，各个节点流入流出的流量如表2所示。

表2 各节点流量分配Table 2 Traffic distribution among nodes

各条边分配的流量均满足边容量约束条件，并且符合流量平衡的条件。通过仿真结果可知，当每条航路航线的流量和扇区内流量无法再继续增加，经过整个网络的最大流为76.7架/h。不同扇区的容量不同，其中，16扇区、17扇区、18扇区的通行能力较大，但根据仿真结果可知，选取的整个扇区网络的通行能力会受到各航路航线容量以及扇区之间耦合度的限制，因此无法达到单独扇区的通行能力的最大值。

3.2.2 边流容比

边的流容比表示的是每条边实际分配流量与容量的比值。

通过计算有效时间内平均流量与每条边容量的比值，可以反映出每条边的容量利用率，该值越大，说明边容量利用率越高，即对应的航路航线的容量利用率也就越高。

每条边的流容比并不完全相同，如表3所示，边es1、es2、es3、e13、e23流容比为100%，那么其容量利用率也为100%，则代表该条边的流量分配已经达到了最大值，不难看出，这些边的流量负荷较重，在需要考虑到流量扩展的阶段应该优先考虑这些航段；e14、e21、e3t的流容比分别为87.9%、71.6%、81.5%，说明该条边流量分配并未达到该边的容量，但其容量利用率较高。边e12、e15、e31、e32、e34、e41、e43、e51、e5t的流容比为0，则表明该条边并未分配流量。

表3 各条边流容比Table 3 Flow capacity ratio of each edge

3.2.3 节点流容比

通过节点流容比可以观察到，不同节点的流容比也有很大的区别。如表4所示，V1节点的流容比最大，为97.7%，节点的流容比越大，代表该节点在单位时间内的利用率越高，那么其对应的扇区也就越繁忙。

表4 各节点流容比Table 4 Flow capacity ratio of each node

所建立的模型有效模拟了多扇区内交通流量的分配，使各航段的流量得以合理分配，以接近扇区内各主要航段的最大通行能力。根据各条边的流容比以及各个节点的流容比，可以判断出选取的整个扇区网络中各条航路以及各个扇区的容量利用率，可以反映出在一段时间内各个扇区的繁忙程度。通过这些节点与边构成的简单的网络图使整个扇区网络的通行能力变得更加具体。通过仿真结果可以观察到某些节点对整个扇区网络通行能力的限制。进而可以通过优化方法来提高整个网络的通行能力。

3.3 灵敏度分析

空中交通管制面对的并不是一成不变的空域环境[16]，危险天气、军航活动等也会给管制运行带来影响，也就会出现在限制时段进行流量控制的情况，有些扇区则无法进行正常的管制，所以研究删除个别扇区后对多扇区网络通行能力的影响也至关重要。

在上述模型仿真结果的基础上，对该扇区网络修改参数重新进行仿真。通过每次删除一个节点构成新的网络图进而求解新的网络图的最大流，可以得出每个节点对于整个扇区网络的最大流的影响也不尽相同。

如表5所示，当删除V3节点的时候，扇区网络的最大流的变化最为明显，从原来的76.7架/h降低为31.7架/h。通过对比可知，V3节点对于整个网络的最大流影响最大，如若考虑提高整个扇区网络的通行能力，V3需要作为整个网络图中的关键节点优先考虑。当删除V5节点后，扇区网络的最大流几乎没有任何的变化，则V5节点对于扇区网络的通行能力的影响较弱。当删除V1、V2、V4节点后，扇区网络最大流也都出现了不同程度的变化。

表5 删除对应节点的网络最大流Table 5 The maximum network flow with deleting corresponding node

不同的节点对于网络最大流的影响不仅仅与该节点的容量相关，也与该节点相连接的边的容量息息相关。这也在一定程度上反映了整个扇区网络的通行能力并不是多个单扇区通行能力的简单相加，不是仅与该扇区的繁忙程度相关，也与连接不同扇区的航路航线的分配的流量密不可分。那么对于多扇区网络通行能力的研究也需要从系统的角度对整个网络进行考虑和分析。

4 结论

针对现有管制扇区模型的局限性、主观性强的特点，依据有向图理论建立了全新简化的扇区网络模型，将扇区转化为网络图中的节点、航路航线转化为有向的边，将复杂的交通流问题抽象为求网络最大流的问题。利用华北情报区的管制扇区作为算例进行MATLAB仿真。得出如下结论。

(1)该多扇区网络的最大流为76.7架/h，验证了模型的有效性，以及各个节点、各条边的流容比，对比分析得出繁忙扇区、繁忙航路航线。

(2)对扇区网络进行了灵敏度分析，通过分析删除不同节点后网络最大流的变化判断出扇区网络的关键节点，明确了整个扇区网络的最大流并不仅是与单个扇区的繁忙程度相关，也与扇区间的航路航线连接密不可分。可见多扇区网络是一个复杂而又相互影响的整体。

从系统的角度建立的网络模型在一定程度上有利于对多扇区网络进行整体分析，进而可以为扇区的通行能力优化提供一定的建议和参考。在后续的研究中，可以继续优化网络模型，考虑实际运行时的影响因素，进一步提高多扇区网络的通行能力。