基于动态扇区的空域与飞行流量两阶段协同规划模型及算法

姚頔, 王瑛

(1.空军工程大学 装备管理与安全工程学院, 陕西 西安　710051; 2.国家飞行流量监控中心, 北京　100094)



基于动态扇区的空域与飞行流量两阶段协同规划模型及算法

姚頔1,2, 王瑛1

(1.空军工程大学 装备管理与安全工程学院, 陕西 西安710051; 2.国家飞行流量监控中心, 北京100094)

摘要：针对管制扇区动态规划与飞行流量时空调配的耦合问题，考虑运行容量、效率等目标，建立了两阶段协同规划模型及求解框架。第一阶段根据自然航路点和流量分布，结合Voronoi图与图论模型构建有限元加权图拓扑抽象，以均衡管制负荷和减少协调移交负荷为目标，基于遗传算法适应性生成扇区结构；第二阶段综合等待和改航策略，以缓解区域总延误和该区域造成的区域外延误为目标，同时兼顾均摊延误和减少延误架次，在区域内容量约束和其他区域对该区域的流控约束下，基于NSGA-II进行流量时空优化。按照优先级顺序实施策略流程，为缓解空中交通拥堵探索综合施策框架。仿真结果表明，所提出的模型算法可为提升空管运行品质提供辅助决策支持。

关键词：飞行流量管理；空域管理；空域动态配置；动态扇区；两阶段协同规划

航空器在空域飞行形成空中交通，空管以保障航空运行安全高效和空域使用科学精益为目标，空中交通需求为基本输入，服务容量为约束，符合间隔标准的有序交通流为输出，在管制服务基础上逐渐衍生出了空域管理和飞行流量管理功能，推动空管从战术性或被动反应式系统向战略性或前摄式系统发展。为应对日益突出的飞行效率与空域资源配置矛盾，欧美空管系统在流量管理(air traffic flow management,ATFM)实践的同时，不断探索空域动态配置(dynamic airspace configuration,DAC)，占据着运行概念与技术应用的制高点。国际空管一体化趋势与无缝运行刚性需求与日俱增，对我国运行方式与效能提出更高要求，研究DAC和ATFM的协同规划框架方法，对空管运行实践具有重要指导意义。

1相关研究

DAC方面，欧美强调空域结构动态调整以适应具体交通流的运行理念，并进一步设想在未来“自由飞行”条件下仅在不能满足动态航迹需求的区域建立固定航路结构[1]。在不区分军民航空域属性的一体化统筹统配模式下，管制扇区的动态规划是DAC的核心，现有研究主要集中在模型选择上，包括基于区域元胞(region model/cell model)[2-3]、计算几何Voronoi图(Voronoi diagram model)[4-5]、图论(graph model)[6-7]和轨迹(flight trajectory model)[8]等建模方法。区域建模将空域均匀分割为一组多边形元胞(如文献[2-3]采用正六边形)并进行管制负荷或空域复杂度测度，通过聚类算法[2]、生长算法[3]等将元胞网格组合成负荷相对均衡的扇区。与之类似，Voronoi图建模也以平衡负荷为目标，随机生成节点[4]或继承导航台等航路点位置先验[5]作为空间目标簇，以空间目标的Voronoi多边形为初始拓扑，基于遗传算法[4]、模拟退火算法[5]等组合生成扇区。图论建模以机场、航路点为节点，航段为边，管制负荷为点、边权重构建加权图模型，基于遗传算法[6]、谱聚类算法[7]等切分形成扇区边界。轨迹建模比较典型的是以动态密度为性能测度，通过k均值算法聚类航迹实现空域剖分[8]。Li Jinhua结合区域元胞和图论建模[9]，将矩形元胞覆盖航路，在继承航路结构同时，显著降低了计算复杂度。

ATFM方面，按主要发展轨迹分为单机场地面等待模型(single airport ground holding problem, SAGHP)[10]、多机场地面等待模型(multi-airport ground holding problem, MAGHP)[11]和(使用改航策略的)流量网络优化模型(air traffic flow network optimization problem,ATFNOP/air traffic flow network optimization with rerouting problem,ATFNORP)[12-15]。早期聚焦机场交通拥堵，Odoni首先系统阐释了SAGHP；Bertsimas和Odoni考虑机场间运行关联性和延误传播效应，建立了MAGHP[11]。随着研究从以机场为核心向空域全网演进，Bertsimas和Stock将空域抽象为以机场、扇区为节点的扇区网络，在机场和扇区容量约束下，优化航班起降时间[12]，并对改航问题建立了动态多任务网络流模型[13]。Bertsimas、Lulli和Odoni进一步提出了BLO模型[14]，以延误代价最小构造超线性目标函数实现延误公平分配，综合地面等待、空中等待、改航、调速等运行策略，并在约束中引入3类不等式，强化模型松弛的多面体结构。受其启发，Alonso等提出混合0-1整数规划模型[15]，将扇区网络变为航路网络，使之更贴近于实际。此外，Dell′Olmo和Lulli针对航路网络设计了一种层次迭代模型[16]，上下2层分别用于航路流量“粗粒度”分配和航路上具体航班四维航迹“细粒度”优化。Daniel等考虑缓解空域拥堵程度与航班延误双目标相互冲突，提出了最小化管制负荷和均匀降低延误的多目标优化模型[17]。上述模型解法涵盖线性规划方法[10]、拉格朗日松弛算法[11-15]、启发式算法[16]和进化算法[17]。

总体看，两方面研究自成体系，统筹耦合研究较少。本文主要研究扇区动态调整与流量时空分配的协同规划模型算法。

2问题描述与建模

2.1基本思想

DAC与ATFM以流量需求与空域容量的动态协调平衡为纽带，DAC负责科学设计并动态调整空域容量，ATFM负责充分利用空域容量、优化调配流量需求。

前瞻借鉴国际空管运行理念，结合我国运行实际，为降低求解难度，本文认为协同规划应分阶段实施，其策略手段具有以下优先级：①空域是空管职能载体与核心资源，改变以固定划分、静态使用为特征的空域管理模式成为必然趋势。静态扇区结构难以有效适配时变的飞行流分布，造成管制席位忙闲不均，制约了容量潜力挖掘，空管应以适应飞行流动态调整扇区构形为首要手段，尽量减少对航班运行的控制与调整。因此，设定根据初始飞行计划实施DAC的优先级高于ATFM。②时空资源的相关性，决定了ATFM时隙路径联动分配难分解。但在实际运行中，改航受到严格控制；此外，除遇恶劣天气、军事活动、突发事件等造成空域容量骤降，一般空域用户希望按照原定计划路径飞行，改航可能导致绕飞，带来额外飞行成本。因此，先以初始飞行计划使用等待策略进行时隙调整，如可改航再同时使用改航策略和等待策略。

2.2协同规划框架

按照“模块化分解”和“两阶段协同”思路，设计规划基本流程示意如图1所示。第一阶段，根据目标区域基础数据建立以机场与导航台等自然航路点为节点、航段为边的无向图，以无向图节点为空间目标簇生成Voronoi图；将Voronoi有限元内与有限元间管制负荷作为点、边权重，构建约简加权图；以均衡各扇区内管制负荷和减少扇区间协调移交负荷为目标，对有限元进行组合优化，适应性生成扇区。考虑时变扇区缺乏历史数据，无法基于管制负荷历史峰值的拟合准确测度容量上限，利用国家飞行流量监控中心系统空域仿真与评估子系统对第一阶段生成扇区按间隔标准进行航迹仿真，输出扇区内航段容量。第二阶段在新扇区拓扑下，以缓解区域总延误和该区域造成的区域外延误为根本目的，综合均摊延误和控制延误架次2种常用目标策略，以机场、航路容量和其他区域对该区域施加的限流措施为约束，基于“时空分治”思想，按照时隙调整先于路径调整的原则，首先调整初始飞行计划的起降时隙，如容量骤降需避让相关空域则启动改航调整路径与起降时隙，对于改航触发的流量时空分布变化，返回第一阶段重新生成扇区划分，吸收消解因容量不足导致的延误。新扇区生成后，按间隔标准及受限航路限流标准仿真输出各扇区航段容量，进而重新分配起降时隙。

图1　空域扇区与飞行流量协同规划流程

2.3扇区优化模型

Voronoi图(亦称Dirichlet剖分)作为一种以等距离原则确定邻接空间边界的图结构成为空域剖分的理想初始拓扑选择，在自然继承航路网结构基础上，利于管制负荷统计。考虑基于管制操作计时、动态密度和空中交通复杂度的负荷测度在实际应用中的操作性问题，本文使用一种以管制架次-时间测度的负荷表达。

图2给出了构建空域网络有限元加权图模型的一个示例。首先建立航路网无向图Groute=(V,E),如图2a)所示。其中,V={v1,v2,…,vNV}为机场与航路点集,|V|=NV,E={e1,e2,…,eNE}为航段集,|E|=NE。然后加载以V为空间目标簇的Voronoi图Dvoronoi={D(v1),D(v2),…,D(vNV)},其中，D(vi)={x|d(x,vi)≤d(x,vi′),∀vi′∈V},d为欧氏距离函数,D(vi)为vi的Voronoi多边形。为避免航路交叉点与扇区边界小于规定距离,以及机场与其进近导航台划分于不同扇区,对于相距过近的节点移除两点之间的Voronoi多边形边界使之合并于一个有限元内,如图2b)所示。相邻Voronoi多边形之间可能存在不止一条航段穿越,为简化图形,将穿越的多条航段合并表示为一条边,并以点表示Voronoi多边形,形成图2c)所示约简图模型。

图2　空域网络有限元加权图模型构建示意图

D(vi)抽象的点权为

(1)

相邻D(vi)与D(vi′)间边权为

(2)

设扇区集S={sj},|S|=NS(sj、NS为变量),T时段内NS可按下式确定

(3)

为方便分析,将管制负荷简化分解为监控负荷与协调移交负荷,基于上述约简加权图的点、边权重测度方法,分别定义如下:

扇区sj的监控负荷为

(4)

相邻扇区sj与sj′间的协调移交负荷为

(5)

定义指派变量xij,xij=1表示第i个Voronoi多边形属于第j个扇区,否则为0,则扇区sj监控负荷与协调移交负荷可表达为

(6)

(7)

以平衡各扇区管制负荷、最小化扇区间总协调移交负荷为目标,则目标函数为

(8)

从(8)式可明显看出,扇区间总协调移交负荷越小,J越小;对于给定扇区间总协调移交负荷,各扇区管制负荷相等时,J最小。

约束条件包括

(9)

(10)

(11)

其中,(9)式确保每个Voronoi多边形只能属于一个扇区;(10)式确保每个扇区至少由一个Voronoi多边形组成;(11)式为决策变量0-1整型约束。

此外,扇区构形须在满足几何连通性约束基础上,确保在航路方向上的凸形约束,防止同一次飞行过程中,同一架航空器2次进入相同扇区,增加不必要的协调移交负荷(凸约束可能需要在优化后进一步人工调整)。

2.4流量优化模型

对于给定区域,在上述机场、航路、扇区(点、线、面)三位一体的拓扑结构下,建立开放式流量网络优化模型,相关参数及符号约定如下:

时隙集T={ti},ti为第i个等分时隙,|T|=NT+1,并假设tNT+1消化前NT个时隙内未分配的流量需求,确保问题具有可行解;

机场集Q={qk},|Q|=NQ;

扇区集S={sj},|S|=NS;

航班集F=Fd∪Fa∪Fc,Fd为区域内出港航班集,Fa为区域内进港航班集,Fc为区域内穿越航班集,|F|=NF;联程航班对集B={(f,f′)|f,f′∈F},f为前继航班,f′为后续航班,|B|=NB;

df、af分别为初始计划的进入和离开区域时隙;

bff′为联程航班的周转时间;

Ak(t)、Dk(t)分别为机场qk在t时的进离场容量,二者相互影响,可用凸状非线性函数曲线表示,如图3所示；

图3　基于历史运行数据的机场容量曲线示意图

优化区域的总延误时间分为因本区域容量不足造成的区域内地面等待、空中延误时间(包括改航造成的飞行延误和空中盘旋等待时间)和因本区域限流造成的区域外延误时间(包括向上游区域前推的地面等待和改航造成的飞行延误时间)2部分,具体包括:Fda内航班的区域内地面等待和空中延误时间,Fad、Fc内航班的区域外延误和区域内空中延误时间,Fd∩a内航班的区域内地面等待和空中延误时间。

对于f∈Fda∪Fd∩a,区域内地面等待时间为

(12)

对于f∈Fad∪Fc,区域外延误时间为

(13)

对于f∈Fda∪Fad∪Fd∩a∪Fc,区域内空中延误时间为

(14)

以总延误代价最小为目标,则目标函数为

(15)

加入e1、e2表示延误代价的超线性增长,目标函数将引导延误均匀分配,避免个别航班延误超长。例如,选择2个航班均摊2个时隙的地面等待时间将优于1个航班延误2个时隙。同时,由于空中延误代价高于地面等待,令e2>e1。

则目标函数为

(16)

由于飞行流系统区域流控波及效应突出,为减少对上游区域的影响,以本区域造成的区域外延误代价最小为目标,则目标函数为

(17)

同样,相对C3以执行区域外地面等待最少为目标,则目标函数为

(18)

约束条件包括

(19)

(20)

(21)

(22)

(23)

(24)

orinf,destf∈A

(25)

sj∈S,orinf,destf

(26)

sj∈S,orinf,destf

(27)

3两阶段求解方法

本文所建立的扇区与流量协同规划模型具有两阶段、多目标、非线性的特点,适于智能优化算法求解。

3.1基于Voronoi-加权图的扇区优化遗传算法

步骤1构造航路网无向图的Voronoi图,根据各有限元内航路结构及有限元邻接关系,按(1)、(2)式计算有限元内权重及相邻边权,形成约简加权图,并按(3)式确定划分扇区数m。

步骤2以m为图的子集数,随机选取m个有限元的空间目标进行1～m的整数编码形成m个子集,并将这m个空间目标的邻元归入m个子集赋以相同编码,未被编码的空间目标归入相邻子集,生成初始种群,设定种群规模及终止代数τmax,进化代数τ=0。

步骤3按(8)式取反计算种群个体适应度。

步骤4进行选择、交叉和变异,并使用精英策略。选择使用锦标赛方式。交叉算子可能破坏几何连通性,为此采用文献[6]中修复策略及基于Hamming距离的交叉选择。变异算子使负荷最小的子集夺取邻近负荷最大子集的有限元。

步骤5τ=τ+1,当τ<τmax时,跳转至步骤3,否则结束。

3.2基于NSGA-II的流量时空优化算法

步骤1预处理以下航班信息:航班编号、航班类别、起飞机场、降落机场、飞行速度、计划经过扇区与航段、备选改航扇区与航段、计划进入本区域时间、计划离开本区域时间、可行进入本区域时间、可行离开本区域时间、MINIT受控航班标志位、MINIT流量控制时间间隔、联程航班标志位、联程航班周转时间。

(28)

(29)

(30)

(31)

式中

(32)

步骤4根据个体序值与同一前端拥挤距离使用锦标赛选择,然后对f的时隙位基因使用多点交叉和随机变异算子,生成子种群。

步骤5合并父子种群,重新计算序值与同一前端拥挤距离,通过锦标赛选择修剪至种群规模。

步骤6τ=τ+1,当τ<τmax时,跳转至步骤9;否则结束。

4仿真实验

以北京飞行情报区为例,选取区内13个机场,202个导航台及报告点,71条航段构成的拓扑网络和2015年9月某日10:00～12:00区内实际运行的571架次航班为研究对象,应用上述模型算法进行优化求解。在验证DAC-ATFNOP-(航段容量下降的)ATFNORP-DAC-ATFNOP协同规划流程框架时,归并相似环节、简化实验步骤,假设在现有静态扇区拓扑下,受区域内天气及其他区域限流影响,部分航段通行能力下降,以初始飞行计划为基础实施改航操作,然后进行动态扇区生成。

流量优化阶段,以Δ=5 min为一个时间片,|T|=25,e1=0.1,e2=0.3,种群大小取400,算法终止代数取500,交叉概率取0.7,变异概率取0.1,分别以C1～C4为主要目标的前端解见表1;

表1　多目标流量优化方案结果

以C1为主要目标,选取方案1进行优化调控。若按先到先服务策略(first come first serve,FCFS),共需调整航班181架次,总延误代价2 578 Δ。相较FCFS,总延误时间减少了约31%,执行地面/空中延误策略减少了约50%。

扇区优化阶段,种群大小取200,算法终止代数取200,交叉概率取0.4,变异概率取0.2,Voronoi初始拓扑与最优扇区划分结果见图4,扇区优化前后性能指标见表2。

图4　10:00～12:00最优扇区划分结果

扇区μ/%σ/(架次·min)ω/%优化前45.0458优化后24.5216 40

表2中引入总负荷平衡系数μ、标准差σ和协调移交负荷减少率ω个性能指标,测度如下

(33)

式中,Wmax、Wmin分别为扇区最大和最小负荷。

(34)

(35)

在新扇区拓扑下,按改航后的流量分布进一步调整时隙后,相较在当前扇区拓扑下启动改航策略,总延误代价减少了约11%,执行地面/空中延误策略减少了约20%。综合两阶段,运行效能得到较大改观。

5结论

本文旨在为空域与飞行流量协同规划方法层面探索综合施策框架提供初步思路,在机场、航路、扇区构成的拓扑结构下,将机场、航路容量及扇区负荷有机整合,并系统考虑区域内外影响,基于扇区动态划分与流量时空优化,构建了两阶段多目标的协同规划模型及算法,结合管制区实际运行数据验证了有效性。从飞行流运行特点和模型本身来看,本文既适用于区域性优化调控,也适用于国家尺度的全局优化。

鉴于研究侧重确定条件建模,对恶劣天气等随机因素刻画不足;同时,需考虑高度层划分,将空域结构与流量调配由2D优化向3D拓展,以便于实际应用;在求解算法的性能改进方面也尚有提升空间。这些也是下一步的研究重点。

参考文献：

[1]ICAO Doc9854-AN/458. Gloabal Air Traffic Management Operational Concept[S]. Montreal: ICAO, 2005

[2]Yousfi A, Donohue G. Temporal and Spatial Distribution of Airspace Complexity for Air Traffic Controller Workload-Based Sectorization[C]∥Proceedings of the 4thAIAA Aviation Technology, Integration and Operations Conference, 2004: 1-14

[3]Klein A. An Efficient Method for Airspace Analysis and Partitioning Based on Equalized Traffic Mess[C]∥Proceedings of the 6thUSA/Europe Air Traffic Management Research and Development, 2005: 1-10

[4]Delahaye D, Schoenauer M, Alliot J M. Airspace Sectoring by Evolutionary Computation[C]∥Proceedings of the IEEE International Conference on Evolutionary Computation, 1998: 218-223

[5]韩松臣, 张明. 依据管制工作负荷的扇区优化新方法[J]. 南京航空航天大学学报, 2004, 36(1): 91-96

Han Songchen, Zhang Ming. Optimization Method for Sector Partition Based on Control Workload[J]. Journal of Nanjing University of Aeronautics & Astronautics, 2004, 36(1): 91-96 (in Chinese)

[6]Chen Yangzhou, Bi Hong, Zhang Defu, Song Zhuoxi. Dynamic Airspace Sectorization via Improved Genetic Algorithm[J]. J Mod Transport, 2013, 21(2): 117-124

[7]Li Jinhua, Wang Tong, Savai M, Hwang I. Graph-Based Algorithm for Dynamic Airspace Configuration[J]. Journal of guidance, control, and dynamics, 2010, 33(4): 1082-1094

[8]Brinton C, Pledgie S. Airspace Partitioning Using Flight Clustering and Computational Geometry[C]∥Proceedings of the 27thDigital Avionics Systems Conference, 2008: 3-10

[9]Li Jinhua, Seah C E, Hwang I. An Algorithm for Dynamic Airspace Configuration Based on the Air Route Structure[C]∥AIAA Guidance, Navigation, and Control Conference, 2009

[10] Bianco L, Odoni A R. Large-Scale Computation and Information Processing in Air Traffic Control[M]. Berlin, Springer-Verlag, 1993

[11] Vranas P B, Bertsimas D J, Odoni A R. The Multi-Airport Ground-Holding Problem in Air Traffic Control[J]. Operations Research, 1994, 42(2): 249-261

[12] Bertsimas D, Stock S. The Air Traffic Flow Management Problem with Enroute Capacities[J]. Operations Research, 1998, 46: 406-422

[13] Bertsimas D, Stock S. The Traffic Flow Management Rerouting Problem in Air Traffic Control: A Dynamic Network Flow Approach[J]. Transportation Science, 2000, 34(3): 239-255

[14] Bertsimas D, Lulli G, Odoni A R. An Integer Optimization Approach to Large-Scale Air Traffic Flow Management[J]. Operations Research, 2011, 59(1): 211-227

[15] Agustín A, Alonso-Ayuso A, Escudero L F, Pizarro C. On Air Traffic Flow Management with Rerouting. Part Ⅰ: Deterministic Case[J]. European Journal of Operational Research, 2012, 219: 156-166

[16] Dell′Olmo P, Lulli G. A New Hierarchical Architecture for Air Traffic Management: Optimisation of Airway Capacity in a Free Flight Scenario[J]. European Journal of Operational Research, 2003, 144: 179-193

[17] Daniel D, Oussedik S, Stephane P. Airspace Congestion Smoothing by Multi-Objective Genetic Algorithm[C]∥Proceedings of the 2005 ACM Symposium on Applied Computing, Santa Fe, 2005: 907-912

[18] 胡一波. 求解约束优化问题的几种智能算法[D]. 西安:西安电子科技大学, 2009

Hu Yibo. Several Intelligent Algorithms for Constrained Optimization Problems[D]. Xi′an: Xidian University, 2009 (in Chinese)

Two-Stage Model and Algorithm for Airspace and Traffic Flow Collaborative Programming Based on Dynamic Sectorization

Yao Di1,2, Wang Ying1

1.College of Equipment Management & Safety Engineering, Air Force Engineering University, Xi′an 710051, China 2.State Air Traffic Flow Management Center, Beijing 100094, China

Abstract:Aiming at the coupling interaction of dynamic airspace sectorization and the space-time allocation of air traffic flow, we establish a two-stage collaborative programming model and solution framework to maximize the operational capacity and efficiency. The first stage begins with the construction of a Voronoi cells based weighted graph model combined with Voronoi diagram and graph theory for the topological structure of given airspace and air traffic distribution. Then, the sector re-partitioning problem is solved based on genetic algorithm to balance the sector workloads and minimize the coordination workloads. In the second stage, we built air traffic flow network optimization model to reduce the total delay fairly, the ground delay out of the area fairly, the total number of delayed fights and the number of ground-delayed fights out of the area, with the airspace capacity constraint in the area and the minutes-in-trail restriction out of the area. Then, the multi-objective optimization problem is solved based on the non-dominated sorting genetic algorithm II (NSGA-II) for a combination of flow management actions, including ground holding, airborne holding, and rerouting. We explore the comprehensive framework for alleviating the traffic congestion according to the priority order of strategies described above. Simulation results show that: the proposed model can provide supporting decision-making for improving the operational quality of air traffic management.

Keywords:air traffic management; air traffic flow management; airspace management; algorithms; computer simulation; decision making; dynamic airspace configuration; dynamic airspace sectorization; efficiency; genetic algorithms; mathematical models; NSGA II (non-dominated sorting genetic algorithm II); optimization; topology; two-stage collaborative programming; Voronoi cells; Voronoi diagram

收稿日期：2015-12-01

基金项目：国家自然科学基金(71171199)与国家空管“十二五”科研专项课题(GKG201401003)资助

作者简介：姚頔(1984—)，空军工程大学博士研究生，主要从事信息系统工程与智能决策、空域与飞行流量管理的研究。

中图分类号：V355.1

文献标志码：A

文章编号:1000-2758(2016)04-0549-09