中国民航飞 行学院学报 14 Mav.2O17 VO1.28NO.3 JoumaI of Civil Aviation Flight University of China 基于改进区域生长算法的终端区扇区优化 戴福青摘 王丹 300300) (中国民航大学空中交通管理学院 天津要:针对民航业发展中空中交通流量不断增加以及空域划分不合理导致的流量分 布、管制员负荷分布不均等问题,基于空中交通管制扇区划分的思想,对终端区扇区优化算法 进行了研究。通过对终端区空域实际交通流网络进行数学描述,利用流量栅格矩阵划分空域单 元,并以航迹数据作为统计依据建立扇区优化的数学模型,实现利用流量数据代替负荷计算, 简化了扇区优化的过程。针对传统生长算法所得扇区不连续空域较多问题,提出环形生长的改 进区域生长算法得到最优的扇区划分。最终,以厦门终端区为例,通过改进区域生长算法所得 的扇区管制员负荷,经计算均小于总时间的80%,且最小负荷差为304 S,验证了所提出扇区 优化方法的合理性。 关 键 词:扇区划分 改进区域生长算法 终端区 管制员负荷 Terminal Area Sector Operation Optimization Based on Improved Region Growing Algorithm DaiFuqing WangDan (Air Trafic fManagement College,Civil Aviation University of China,Tianj in,3 003 00,China) Abstract:With increasing air trafic fflow and uneven distribution of lfow and controller work. 1oad caused by unreasonable airspace division,the air traficf control sector division has been a signiif. cant means to cope with growing demand of terminal airspace.This paper presents fl terminal sector optimization algorithm.With the description of the actual transportation network of terminal airspace, partition the airspace units in trafic fgrid matrix and track data as the statistical basement,a mathemat. ics model of sector optimization is built which simplifes sector optimization greatlyDue to the dis— .continuity of sector airspace resulted by the traditional growing algorithm,this paper proposes the im- proved region growing algorithm for optimum sector.At last,an example of Xiamen terminal sector optimum is given,which shows the reasonableness of the proposed optimization methods based on controller workload.Workload of every sector is equally less than 80%of total time and the minimum differentiation iS 304s. Keywords:Sector division troller workload Improved region growing algorithm Terminal airspace Con— 引言 关重要。 航空运输业的快速发展,飞行流量的不断 增加,在取得经济效益的同时,也对空管系统 目前,世界范围内广泛认可的空域扇区规划 和管理工作是以国际民航组织的8168.OPS/6111 和9689.AN/9532等相关文件为参考进行的,这些 原则和方法一般是根据各航空国家经验积累制定 的正常运行提出了严峻挑战。其中,终端区作 为航空飞行的重要节点,其空域规划的合理性 有利于均衡管制员负荷,提高机场吞吐量上 限。因此,均衡、有效、合理的扇区划分对于 保障飞行安全,提高飞行效率和空域利用率至 的,缺乏严格有效的量化标准。在空域扇区的理 论划设模型研究中,国内外一般采川法国学 者Daniel Dalahaye01提出的voronoi图的方式对空 MaV.2017 Vo1.28No.3 中国民航飞行学院学报 Journal of Civil Aviation Flight University of China 域进行划分,此后张明【zJ等进一步提出管制空域 结构拓扑描述的数学模型,对终端区单元进行划 分。此种划分方式由于节点数量的限制导致基本 网络过于粗糙,不能更好地满足均衡扇区的要 求,且一般着重于航路扇区优化。在数学优化模 型选择方面,一般采用韩松臣L3】等提出的管制员 负荷均衡模型。这些模型所需参数均需要通过一 定计算获得,在计算过程中存在一定偏差。在优 化算法方面,Arash Yousefi和George L.Donohue j 采用聚类算法优化扇区单元,韩松臣等利用模拟 退火算法对基于管制员负荷的最优化问题进行求 解,Dr.Alexander Klein[5J提出基于六边形栅格的中 心增长算法,但并未给出确定扇区数量的方法。 本文拟通过对终端区空域实际交通流网络进 行描述,利用流量栅格矩阵划分空域单元,并以 航迹数据作为统计依据建立扇区优化的数学模 型,应用改进的区域生长算法得到最优的扇区划 分,同时以管制员负荷作为验证依据。 1问题描述与建模 1.1空域网络描述 Klein A等L5 J提出,交通量与管制员负荷呈近 似线性关系,因此本文选用交通量作为空域划分 的依据。交通量的计算可以通过两种方式,一种 是基于飞行计划所提供的航线资料,其规定了飞 机所需要经过的导航台数据,并以经纬度的形式 给出,但此种方式数据较少,栅格间距过大;另 一种是基于雷达航迹数据,其记录了飞机在飞行 过程中的实际飞行轨迹,能够更为直观地反映交 通量的分布情况。因此,本文选用实际雷达航迹 数据代表交通量。 根据雷达数据获得依据以及终端区空域特 性,以雷达中心点( , )为原点建立笛卡尔坐标 系,某一时刻某架飞机的实际位置在二维平面内 的坐标为4 ( ,Y),a表示飞机应答机二次编 码,f表示雷达记录时刻。运用人工阈值分割方 法,根据终端区高度需要,将高度限制为某一阈 值之内,即4 (z)≤Z ,Z 表示某终端区空域高 度上限。在选定时间区段T∈(tb tc)内,将雷达数 据点对应到区域图中,就得到了实际交通流网络 分布。 1.2流量栅格单元划分 在得到雷达航迹的实际位置后,为了以交通 量为依据建立扇区优化模型,本文将终端区空域 划分为离散的矩形栅格单元,以进近管制最小雷 达间隔为依据,选择栅格单元边长s=6 km。由于 终端区边界点是以经纬度形式给出,因此在限定 空域范围时,需要将边界点投影到本文所建立的 笛卡尔坐标系中,因此,采用Martinez S等所提 出的斜轴墨卡托投影模型 】推导得到边界点坐标 吣 l+ sm × Sil l + C OS × COSOE COS × l ~ l 式中:Re为地球半径: 为边界点纬度坐标; 为边界点经度坐标; 。为雷达中心点纬度坐标; 为雷达中心点经度坐标。 以覆盖终端区空域左上角栅格单元的左上角 顶点(Xt1 Y,。)为原点建立新的笛卡尔坐标系,则各 点的新坐标为: X=x—xlt Y:Y—Y,, 在新的坐标系下,根据之前所划设的矩形栅 格单元,建立流量栅格矩阵 ,矩阵元素 ( ,J) 表示该栅格单元内航迹点个数,i表示某一栅格单 元对应的行序号, 表示该栅格单元对应的列序 号。则各航迹点对应的栅格位置可以表示为 3… :『 ], = ,2,3… 中国民航飞行学院学报 May.2017 VO】.28No.3 皇一 Q of——Civil Aviation Flight University of China 初始化栅格矩阵 为零矩阵,通过遍历所有 航迹点对应位置,每搜索到一个航迹点,则给相 况, (尼, )= 蓁 应矩阵 元素值+1,直到统计完所有航迹点,得 到最终流量栅格矩阵。假设终端区空域划分为 5 6的栅格区域,则对应的流量栅格矩阵可表 示为 35 lO l5 22 33 44 23 35 l7 66 54 45 M: 24 36 63 65 35 23 24 86 47 97 24 43 24 74 35 97 36 75 2改进的区域生长算法 区域生长是基于区域的图像分割方法的经典 算法之一,是一种根据事前定义的准则将像素或 子区域聚合成更大区域的过程,其实质就是把具 有某种相似性质的像素连通起米,从而最终构成 分割区域。本文中将区域生长算法应用到终端区 空域扇区分割,将栅格单元统计数据类比于像素 值。 实际应用区域生长算法一般需要有三个步骤 米实现: (1)确定选择一组能正确代表所需区域的起 始点种子: (2)确定在生长过程中将相邻单元包括进来 的准则: (3)确定区域生长过程停止的条件或规则 2.1种子点的获取 在终端区,管制员的主要任务包括基于航路 结构和】进离场程序的航班排序,因此导航台、航 路交叉点和扇区边界点是管制员负荷的重点区 域,且这些位置不可以作为管制移交点。考虑空 域内部扇区划设,将导航台和航路交叉点所在栅 格单元作为初始种子点,数量为 。建立位置栅 格矩阵 ,矩阵元素m (f,J)表示该栅格单元对 应的扇区编号,矩阵 与 所属元素呈一一对 应关系,囚此其f, 含义相同。建立 书1阶种子点 矩阵N,矩阵元素 (后,1)表示对应种子点生长情 (k=1,2,…, ) 以1.2中栅格区域为例,假定有两个初始种 子点,通过计算,得到导航台和航路交义点分别 位于(2,2)和(3,5)栅格单元内,则 0 0 0 0 0 0 O l O 0 0 0 初始的位置栅格矩阵M’= 0 0 0 0 2 0 O 0 0 0 O 0 O O O O O 0 种子点矩阵Ⅳ=『:] 2.2生长方式及生长准则 基于交通量(即管制员负荷)的扇区划分在 达到各扇区交通量均衡的同时,还戍保证每个扇 区内交通鼍尽量少,冈此建立如下扇 优化的数 学模型,生长准则为: C=rain∑∑m(i,J) 生长方式规则: ①确定初始种子点数目利位置。 ②寻找雷达航迹点数目m(i,J)最小栅格单元 作为生长中心,并令其对应种子点矩阵元素 (七,1)=1,遍历其周围相邻栅格单元,遵照生 准则,将其周围相邻步长为1的栅格单元并入该 种子点所属扇区,并将其对应 矩阵的 ( , ) 更新为其并入扇区的编号,同时更新此种子点对 应流量栅格矩阵m值为原种子点与并入栅格m值 之和。 ③以生长后种子点为依据,重新寻找雷达航 迹点数目m(i,J)最小栅格单元,重复②的操作。 MaV.2017 VO1.28No.3 中国民航飞行学院学报 Civil Aviation Flight University of China 17 ④若在遍历过程中,作为种子点的栅格单元 被选为待并入栅格,则允许其被并入其他种子区 域,其m‘值相应更新扇区编号,同时令其种子点 对应种子点矩阵元素 (k,1)=1。 栅格生长的终止条件为所有栅格单元均被并 入某一生长中心对应扇区,即满足下列等式: f, 木≠0 l =1 此时由于不同栅格单元的生长速度不同,交 通量集中区域生长速度较慢,则生成的扇区范围 较小,交通量稀疏的区域生长速度较快,则生成 的扇区范围较大,最终达到交通量均衡的目标。 2-3管制员负荷检验指标 本文将管制员工作负荷分为监视管制负荷、 冲突管制负荷和协调管制负荷。其中,监视管制 负荷是指管制员对管制扇区内飞机进行查看、观 察并给出相应调控指令的工作量;冲突管制负荷 是指管制员对其管制扇区内飞机的运行进行判 断,并对潜在冲突或已经出现事故征候的飞机给 出调控指令的工作量:协调管制负荷是指相邻扇 区之间的移交和信息交换负荷。 因此,管制员工作负荷 =a・ +6・ 4-c・ 其中,监视管制负荷 =。F×T×f ×{ , ×Ⅳ口,一up+ f down xNat—odw月+ ×( ×Ⅳ妒一up+asp down xN 一down十 × d×Nhd+ 7 keep×a口,keep l 式中,,表示扇区航班数量,架次;7表示 平均每架航班停留时间,S; 、 、 、 ,妇。分别表示高度、速度、航向、穿越航班对 监视管制负荷的影响系数: 、 ,down、 分别表示爬升、下降、平飞的航班比例: 一 、 down、 keep分别表示加速、减速、 速度保持的航班比例;Ⅳ 、 、Ⅳ^d分别表示 高度、速度、航向调整的航班平均调整次数; a 妇 表示穿越航班的比例。 一冲突管制负荷 W ̄s=F xT x min(,-.-ao,up,a.,down,a,,,k_.eep) +一】m in(c%_.p,aps_down. ̄( ̄p_ekep)]×(、 ,× + × × +Yhd× ×一Nhd+ ekep Xa 妇 ~) ,、 、 、 ,缸叩分别表示高度、速度、航 向、穿越航班对冲突管制负荷的影响系数。 协调管制负荷 。= ×( + )=2 × 表示单架飞机的平均协调管制负荷; 、 、F分别表示进、 出扇区、扇区内服务的航 班数量。 最小扇区数 ={int(M )+1-,Mtin ̄(iMnt)(M)M= sx 80% 3模拟计算与结果分析 本文采用JAVA9.0对厦门终端区进行了优化 分析,优化结果满足终止条件。首先分析统计了 一天内各时段交通量分布,选取小时流量最火时 段16:o0.16:59数据作为依据,进行流量栅格单 元划分,得到52 ̄49阶流量栅格矩阵M,如图1 所示。 其中,黑色区域表示流量为0栅格,由白色 至灰区域流量依次递增。采用区域生长算法,种 子点矩阵N=『1,2,…,121,对应初始栅格位置矩阵 M‘=J 书(f,J)l,其中m*(19,45):l, m (10,34)=2,m (8,32)=3,m‘(12,16)=4, m (17,18)=5,m (22,23)=6 m (12,32)=7, m (23,32)=8,m (24,26)=9 m (30,32)=10, m (28,26)=1l,m‘(35,36)=12。 中国民航飞行学院学报 18 Mav.201 7 V01.28NO.3 Journal of Civil Aviation Flight University of China 所得终端区扇区优化结果如图2所示。生长 4结论 后扇区数量为3,根据前述管制员负荷计算方法, 所得各扇区管制员负荷见表1。 在繁忙终端区,管制扇区划分是降低管制员 :l 作负荷、应对终端区交通流量不断增加的手 段。通过对终端区空域实际交通流网络进行描 述,利用流量栅格矩阵划分空域单元,并以航迹 数据作为统计依据建立扇区优化的数学模型,针 对传统生长算法所得扇区不连续空域较多问题, 提山改进的区域生K算法得到最优的扇区划分。 最终,以厦门终端区为例,管制员负荷作为依据 验证了所提出扇区优化方法的合理性。 参考文献 图1流量栅格矩阵图 [1]Delahaye D,Schoenauer M,Alliot J M.Airspace sectoring by evolutionary computation[J].Spatial evolutionary modelling,2001:203-233.[J].民航科 技,2002(5):45 [2】张明.管制扇区的最优划分方法研究[J】.南京 航空航天大学学报,2004(3):308.312 [3】张明,韩松臣.依据管制员工作负荷的扇区优 化方法[J].交通运输工程学报,2006(4):86-89 [4]Yousefi A,Donohue G L.Temporal and spatial distribution of airspace complexity for air trafic con—f troller workload—bhsed sectorization[C]//Aiaa 4th 图2扇区优化结果 aviation technology,integration and operations(atio) forum,chicago,illinois.2004 表1优化扇区管制员负荷 扇区 管制员负荷/s l 2 3 766.4 1027.2 723.2 [5】Klein A.An eficifent method for airspace analysis and partitioning based on equalized traffic 经计算各扇区管制员负荷均小于总时间的 80%,满足管制员负荷的要求。且扇区之间管制 负荷最大差为304 s,均衡度符合要求。 mass[C]//ATM Seminar,USA.2005:l一10