航空网络层次结构对航班延误扩散的影响.pdf

物流科技 2023 年第 19 期 10 月上收稿日期：2023-01-16作者简介：侯泽林（1995），男，河北定州人，上海工程技术大学航空运输学院硕士研究生，研究方向：交通运输规划与管理；姚红光（1978），本文通信作者，男，黑龙江哈尔滨人，上海工程技术大学航空运输学院，副教授，博士，研究方向：交通运输与物流管理。引文格式：侯泽林，姚红光.航空网络层次结构对航班延误扩散的影响J.物流科技，2023,46(19):80-84.誗交通运输誗文章编号：1002-3100 渊2023冤 19-0080-05物流科技 2023 年第 19 期 10 月上Logistics Sci-Tech October,2023（the first half）摘要：航班准点率低，航班延误班次多是我国民航业的现状，其中航班延误的扩散严重制约了航空运输业的发展。文章借助模拟航空网络和 k-core 方法分析航空网络的社团层次结构，通过仿真发现，在延误扩散过程中，初始延误节点的度值越大，所造成的延误扩散的影响也越大；且延误扩散影响最大的是在核心层，核心层节点在网络中与其他节点联系紧密，度值大，故延误扩散的影响最严重；中间层和边缘层的节点大多通过与核心层节点连接造成大范围的延误扩散。关键词：航空网络；延误扩散；社团结构；k-core中图分类号：F560文献标志码：ADOI：10.13714/ki.1002-3100.2023.19.019Abstract:The low flight punctuality rate and many delayedflights are the current situation of Chinas civil aviation.Flightdelays seriously restrict the development of air transport indus原try.In this paper,the community structure of aviation networkis analyzed by means of simulated aviation network and New原man fast algorithm.Through simulation,it is found that in theprocess of delay diffusion,the greater the degree of initialdelay node,the greater the impact,and most of the affectednodes are closely related to each other,that is,the delay dif原fusion is more likely to occur between nodes within the com原munity.Key words:aviation network;delay spread;community struc原ture;k-core航空网络层次结构对航班延误扩散的影响The Impact of Aviation Network Hierarchy on Flight Delay Spread侯泽林，姚红光（上海工程技术大学 航空运输学院，上海 201600）HOU Zelin,YAO Hongguang（School of Air Transport,Shanghai University of Engineering Science,Shanghai 201600,China）0引言民航业是我国国民经济的重要基础产业，是综合交通运输体系不可或缺的部分，其发达程度体现了国家的综合实力和现代化水平。然而，随着我国民航业的快速发展，航空延误也接踵而至。造成航班延误的因素有很多，但航班延误扩散占据一大部分，延误扩散往往会波及更多机场和航班，也就造成延误总时长越大。当一个航班或机场受到扰动，这个扰动就会迅速波及到运输网络的其他组成部分1-2。Ahmadbeygi 等提出可以采取增加航班在机场的周转时间的方式来减少延误向下游机场的传递2。Bruno Campanelli 等对比美国航空运输网络与欧洲航空运输网络分析，由于航班时刻表问题或外界干扰导致的延误传播，发现对比空中交通流量管理（Air Traffic Flow Management，ATFM）时隙优先级系统，先到先服务（First Come First Served，FCFS）的调度机制会产生更大的交通拥塞3。Welman 等计算了美国 51个机场的延误乘子，并且估计了机场容量增大时系统延误的降低4。很少有学者研究航空网络社团结构对航班延误扩散的研究，在社团方面众多学者都有研究，Newman5提出快速模块度优化 FN 算法，Blondel 等人6提出了采用贪婪方法进行局部优化的层凝聚方法 Louvain 算法，Raghavan 等人7将标签传播思想8应用于社团发现任务，提出基于标签传播的社团发现算法。从网络层次结构研究航空网络航班延误扩散，可以发现航空网络的层次结构以及层次中节点的分布状况，通过仿真分析，可以有效防治航班延误以及延误扩散的发生。1模拟航空网络的建立本文所研究的中国航空网络的数据来源于携程网（http:/）和“飞常准”网站（http:/ 241 个城市、4 074 架次直达航班。本文所研究的航空网络是将同一个城市的不同机场合并为一个并用城市名字进行命名。因此，本文把统计的 241 个城市机场作为中国航空网络节点，城市对之间的存在航线作为边，构建一个无向无权的中国航空网络模型 G1=V,E蓸蔀，其中 V 是网络中点的集合，E 是网络中边的集合。如果城市对之间存在联系，则城市对节点之间存在航线连接，否则不存在连接，即如果两个节点之间存在连接，则 eij=1；如果没有连接存在则为 0。由此可以得到城市对节点之间的航班数据的邻接矩阵，用一个241*241 的邻接矩阵 A1来表示。因为真实的航空网络数据繁杂，进行延误扩散仿真时间长，故根据真实航空网络用 Pajek 软件进行模拟，最终得到的模拟80物流科技 2023 年第 19 期 10 月上航空网络层次结构对航班延误扩散的影响航空网络如图 1 所示。从图 1 中可知模拟航空网络的连接情况，模拟网络中有 41 个节点，节点之间共有125 条航线。根据邻接矩阵可以知道航线的方向，据此可以生成 125 个航班进行后续的仿真研究。2模拟网络的社团发现2.1k-core 层次分析算法针对于网络的社团发现有很多种，但对于航空网络的复杂性以及适用于本文的航班延误扩散的社团发现首选是基于度值的社团结构发现。针对于度值的社团网络发现有很多种，如 K-派系、K-派系社团、k-core 等。其中 k-core 能够发现网络中的节点核度，能够直接基于度值了解网络中每个节点对于其他节点的连接性。再通过 K 核分解对模拟航空网络进行社团层次划分。这在研究航班延误扩散的过程中，能够直接发现社团层次对航班延误扩散的影响。k-core 算法发现模拟航空网络的社团层次具体如下：在一个网络中 k-core 指的是要反复删除那些度值小于 K 的节点之后，所剩余的节点构成的子图9。或者可以说，子图中的每个节点的度值都不小于 K。节点的核数表示包含这个节点的最深的核，即系欸但那存在与 K 核中，但是在 K+1蓸蔀核中被剔除，则这个节点的核数为K。核数的最大值就是整个网络的最大核数，也叫最高核数10。核数通常可以反映节点的连通性，在进行研究时可能出现节点度很大，但是核数很低，这说明节点的连通性低，需要进行 K 核分解剔除这些节点，从而探索网络中的核心层。K 核分解的过程是从外到内延伸扩展进行的，最小的核在最外面，最大的核在最内层。通过 K 核分解，逐层分解，揭示网络中的层次结构。其中在 K 核中被删除的节点成为 K-1蓸蔀层。在网络中反复删除度值为 1 的节点，那么删除的节点就是所谓的 0-层；然后，再把子图中度值为 2 的全部节点反复都删除掉，这时网络中的所有节点的度值都大于 2，那些删除掉的节点就是 1-层；依此类推，一直到网络中的节点不可以在删除，此时，剩余节点所构成的子图就是网络的最高层11。2.2模拟航空网络的层次网络发现将上文中模拟航空网络的 01 邻接矩阵 B1输入到 UCINET 软件中进行 k-core 分析，以便可以计算模拟航空网络的机场核心，计算结果表明，模拟航空网络的最大核度为 5。且随着核度的增加，网络中各层的节点和边缘节点的消失如表 1 所示。图 1模拟航空网络模型图表 1各层网络节点和边消亡统计核度节点数量节点消亡数量消亡节点所占比例（%）边的数量边消亡数量消亡所占比例（%）14100.0012500.02291229.27114118.832637.3210864.8419717.07852318.4513614.63592620.8根据表 1 还可以得到，最高核 5-核中的 13 个节点就是核心层。而在 1-核剔除节点变成 2-核中共剔除 12 个节点，在 2-核剔除节点变 3-核中只剔除了 3个节点，且所移除的边所占相近，因此，可以把这 15 个节点作为边缘层。中间层为 4-核和 5-核中所剔除的 13 个节点。整理成如表 2 所示。根据表 2 可以看出，在核心层中节点之间的连接最多，且中间层和边缘层中节点之间的连边数远比核心层网络中的连边数少；而且还可以看出，中间层、边缘层内部节点之间连边数之所以少，是因为中间层、边缘层的节点大多跟核心层的节点之间进行连接，通过中转到达其他节点，也就是说，中间层、边缘层内部之间的节点联系少，主要通过和核心层联系，从而达到其他节点。依据划分好的网络层次中的节点数量和每个层次中的连边数量，可以整理出每个层次的邻接矩阵，把邻接矩阵依次导入UCINET 软件中，转换成可直接读取的数据，进行数据可视化，得到结果如图 2 所示：表 2模拟航空网络层级划分网络层次核数节点数边核心层51359中间层341313边缘层12152图 2核心层、中间层、边缘层网络图（a）核心层网络（b）中间层网络（c）边缘层网络81物流科技 2023 年第 19 期 10 月上在图 2 中能够看出，核心层、中间层、边缘层三个不同层次内部节点之间的连接情况。其中核心层内部节点之间的连接最多，中间层次之，边缘层内部节点之间连接最少，节点之间几乎不存在联系。说明在模拟航空网络中核心层中的节点联系最为紧密，中间层次之；而且中间层、边缘层的连接情况少，说明中间层、边缘层的节点较多的与核心层的节点之间有连接，可以说核心层占据整个模拟航空网络的中心地位。3延误扩散仿真分析3.1航班信息的设定在实际生活中，初始航班延误是通过各类介质在包括自身机场在内的节点中影响其他航班，从而发生航班延误扩散。在关于航空网络结构对延误扩散造成怎样的影响的研究中，本文通过延误扩散的机场总数、扩散涉及的航班数量及扩散造成的延误总时长这三个指标来衡量其影响程度。所以本文首先要确定各节点机场的航班信息、初始延误信息以及机场服务能力信息等。（1）航班时刻表航班时刻表中包括序号、航班代码、始发机场、始发时间、目的机场、降落时间、飞行时间等信息，其中始发机场、始发时间是飞机起飞是否受其他延误航班影响判断的关键因素，若二者同时在延误航班的影响范围内，则该航班很有可能受到影响，使延误扩散；同理，目的机场与降落时间则是判断该航班是否在降落时受延误影响的重要条件，若受影响也就意味着该航班无法在原定时刻降落在目的机场，则必须通过推迟起飞等方式处理，从而发生延误扩散。因此，航班时刻表是进行航班延误扩散影响研究的基础信息。其具体形式如表 3 所示。表 3航班时刻表序号航班代码始发机场始发时间目的机场降落时间飞行时间说明表示航班的排列顺序航空公司二字代码及航班 4 字代码起飞机场以网络节点 Vi表示起飞时间形式如：6:35:00降落机场以网络节点 Vi表示降落时间形式如：11:05:00空 中 飞 行 时间，单位：分钟（2）航班初始延误时刻表初始延误时刻表中包含的信息除了上述航班时刻表中的信息，还包含延误时间、影响延误时间始和影响延误时间末等信息。其中初始延误航班的影响时间始末是该表中的关键信息，通过该影响区间判断航班时刻表中是否有航班会受到初始延误影响。具体的航班初始延误时刻表包含内容和形式如表 4 所示。表 4航班初始延误时间表序号航班代码始发机场始发时间目的机场降落时间飞行时间影响时间始影响时间末说明表示航班的排列顺序航空公司二字代码及航班 4 字代码起飞机场以网络节点 Vi表示起飞时间形式如：8:00:00降落机场以网络节点 Vi表示降落时间形 式 如：12:00:00空中飞行时间，单位：分钟实际降落时间实际降落时间与最小周转时间和（3）机场服务能力机场服务能力指的是机场中能提供飞机起飞和降落的能力，即在一定时间段内机场能够供给飞机正常起飞和降落的最大能力。具体表格信息如表 5 所示。表 5机场服务能力表机 场 名 称起飞能力降落能力说明以网络节点 Vi表示机场该时刻允许起飞的最大航班数量机场一定时刻内允许降落的最大航班数量在上述的三个信息表已知的情况下，通过初始延误表可以确定航班影响的机场和影响时间区间，再通过航班时刻表来查看在这一时间区间内可能受影响的航班，根据受影响机场的服务能力，确认延误扩散航班，最终输出延误航班数量、延误机场数量和延误总时间。3.2仿真系统的建立对仿真系统进行描述：（1）仿真开始时，其中的延误总时长 T=0；延误航班数量 H=0；延误机场数量 A=0。根据“延误时刻表”确定航班初始延误信息。（2）查看航班时刻表，判断延误航班对其他航班的影响是否大于 15min。输出影响时间大于或等于 15 分钟的航班数量 N；查找机场服务能力表，判断并确定受影响的航班：即 N 小于等于起飞能力时，不受影响；N 大于起飞能力时，受影响，且受影响航班为 N 减去起飞能力。将受影响航班编入延误表，更新信息。（3）判断航班降落影响：确定航班降落影响时间区间 Tc,Tm蓘蓡。判断在该时间范围内航班时刻表中是否存在目的机场与初始延误航班相同的航班，并输出符合条件的航班数量值为 N。查找机场服务能力表，比较并确定受影响的其他航班。当 N 小于等于机场降落能力时，机场其他航班不受影响；当 N 大于机场降落能力时，机场其他航班受影响，此时，受影响的航班数量=N-机场降落能力。将受影响航班编入延误表，更新信息。将受延误扩散影响的航班编入厌恶表，删除处理掉的延误航班；输出 T、H、J。（4）重复步骤（1）、（2）、（3），一直到延误表处理完毕。3.3仿真结果根据上文基于 K-核分析模拟航空网络中得出的网络层次，对核心层网络进行航班延误扩散仿真计算和结果分析。针对核航空网络层次结构对航班延误扩散的影响82物流科技 2023 年第 19 期 10 月上心层网络，在模拟航空网络中找出核心层中的 13 个节点和 59 条边；在航班时刻表中找到核心层网络所包含的航班，设置初始延误航班信息，进行延误扩散分析。假设初始航班的延误均因为天气、军事活动等条件引起的，则必会引起航班延误在网络中进行传播扩散。把初始延误航班的延误时间设置为 70 分钟，初始航班延误表如表 6 所示。表 6模拟航空网络核心层中的初始延误航班时刻表航班代码始发机场起飞时刻实际起飞目的机场降落时刻实际降落飞行时间延误时间影响时间始影响时间末MU3351V16:007:10V127:458:551:451:108:559:55FM5679V46:457:55V610:0011:103:151:1011:1011:109C8836V167:008:10V79:2510:352:251:1010:3510:35FM9006V107:108:20V58:5010:001:401:1010:0011:00FM9636V67:458:55V510:0511:152:201:1011:1512:15在航班初始延误表中，知道初始延误航班的代码、延误时间、起飞以及降落时，假设同一机场的起飞服务能力和降落服务能力均为 1，各航班根据航班顺序进行起飞和降落，且飞机不通过加减速来改变飞行时间；根据选择的初始延误航班设置延误时间（70min），在表 6 中给出影响时间的开始和影响时间末均为降落机场的影响时间；实际计算中还有起飞机场的影响时间。采用延误扩散逻辑框架图所示的步骤进行延误扩散，且根据扩散情况持续更新航班时刻表，计算出延误扩散的总时长、受影响的节点机场以及受影响的航班数量，其中受影响的一个航班可以影响两个机场节点，不把同一个受影响的机场节点总结为一个进行统计（如：初始延误航班为 MU4567，由 V1 飞向 V3，受影响的航班有两个，这两个航班分别由 V5 飞向 V3 和 V8 飞向V3，这时节点为 4，不把 V3 总结为一个机场节点进行统计）。将航班延误扩散结果整理如表 7 所示。表 7核心层仿真结果统计表初始延误机场节点初始延误时长（min）受影响的机场节点（个）受影响的航班（班）延误扩散总时长（min）V17084315V47084190V167063175V1070147415V670126300中间层和边缘层的仿真结果如表 8、表 9 所示：表 8中间层仿真计算结果初始延误节点初始延误时间（min）受影响航班数量（班）受影响节点（个）延误扩散总时长（min）V22701260V19700010V117016321 270V287036290V15701245表 9边缘层仿真计算结果初始延误节点初始延误时间（min）受影响航班数量（班）受影响节点（个）延误扩散总时长（min）V4170000V35701240V327036162V29701265V2170000将各个层级中的节点引起的延误扩散仿真结果作图，因为篇幅原因，本文只给出平均延误扩散总时长以及影响的节点数量的图，具体如图 3 所示。从图 3 可以得出，在核心层、中间层、边缘层相同的情况下，不同的节点作为初始延误节点，其所造成的影响也不相同，一般来说，相同层级中的节点的度值越大，其所对应的核度也越大，在层级中连接的节点也越多，故作为初始延误节点进行的仿真结果也就比其他节点造成的影响大。对比核心层、中间层和边缘层节点作为初始延误节点时，核心层节点造成的延误扩散要比中间层、边缘层造成的影响大；在中间层、边缘层节点造成的延误扩散几乎可以忽略不计，但在核心层因为节点度值大，几乎都会影响到其他节点。4结论通过构建中国航空网络的模拟模型，运用 k-core 方法进行网络层次分析，从而进一步通过仿真研究航班延误在网络中的扩散，最终得到如下结论：航空网络层次结构对航班延误扩散的影响83物流科技 2023 年第 19 期 10 月上（1）在核心层、中间层、边缘层相同的情况下，不同的节点作为初始延误节点，其所造成的影响也不相同。总体来说，初始延误节点的度值越大，其延误扩散的影响越严重。（2）延误扩散影响最大的是在核心层，核心层节点在网络中与其他节点联系紧密，度值大，故延误扩散的影响最严重；中间层和边缘层的节点大多通过与核心层节点连接造成大范围的延误扩散。参考文献：1BEATTY R,HSU R,BERRY L.Preliminary evaluation of flight delay propagation through an airline scheduleJ.Air TrafficControl Quarterly,1998,7(4):259-270.2AHMADBEYGI S,COHN A,GUAN Y,et al.Analysis of the potential for delay propagation in passenger airline networksJ.Journal of Air Transport Management,2008,14(5):221-236.3CAMPANELLI B,FLEURQUIN P,ARRANZ A,et al.Comparing the modeling of delay propagation in the US and Europeanair traffic networksJ.Journal of Air Transport Management,2016,56:12-18.4WELMAN S,WILLIAMS A,HECHTMAN D,et al.Calculating delay propagation multipliers for cost-benefit analysis sponsor:The federal aviation administrationZ.2010.5NEWMAN M E J.Fast algorithm for detecting community structure in networkJ.Physical E,2003,69(6):066133.6BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al.Fast unfolding of communities in large networksJ.Journal ofStatistical Mecha-nics:Theory and Experiment,2008,2008(10):10008.7RAGHAVAN U N,ALBERT R,KUMARA S R,et al.Near linear time algo-rithm to detect community structures in large-scale networksJ.Physical Review E,2007,76(3):036106.8ZHU XIAOJIN,GHAHRAMANI Z.Learning from labels and unlabeled data with label propagation,CMU-CALD-02-107R.Pittsburgh,PA:Car-negie Mellon University,2002.9Z-M REN,J-G LIU,F SHAO,et al.Analysis of the spreading influence of the nodes with minimum K-shell value in com原plex networksJ.Acta Physica Sinica,2013,62(10):108902.10M ZHANG,S GE,Y JIA,et al.Analysis of cohesive characteristics in scientific collaboration networks based on k-coreJ.Systems Engineering-Teory&Practice,2020,40:1821-1831.11L HUANG,Y-D ZHAO,L MEI.Research on multi-sided market competition of social media personal data resource-anempirical analysis based onk-core networkJ.Soft Science,2019,33:1-7.V16V1V6V10V4节点12108642（a）核心层节点延误影响的航班数量（b）中间层节点延误影响的航班数量V19V15V22V28V11节点181614121086420-2V41V21V35V29V32节点（c）边缘层节点延误影响的节点数量3.02.52.01.51.00.50（d）各层级网络节点的平均延误扩散时长核心层中间层边缘层6005004003002001000图 3仿真结果图航空网络层次结构对航班延误扩散的影响航空网络层次结构对航班延误扩散的影响84