多跑道机场离场航班排序优化方法研究.pdf

JournalAviationUniversityofChinaFlightofCivilVol.34No.5中国民航飞行学院学报Sept.2023多跑道机场离场航班排序优化方法研究*张云鹏1沐瑶2（1上海民航华东空管工程技术有限公司上海2 0 17 0 22南京航空航天大学江苏南京211100)摘要：本文建立了以旅客总延误时间成本最小化为目标函数的多跑道机场离场航班排序优化模型，并考虑航路流控的影响，通过回溯算法求解，融合位置约束交换算法优先处理受流控影响的航班，最后采用南京禄口国际机场为例进行算例验证。与先进先出模式相比，优化后的离场模式降低航班延误时间效果显著，旅客总延误成本减少了44.8 1%，所提方法可显著提升多跑道协同运行能力，为当前多跑道机场的调度排序提供了思路与方法。关键词：航路流控独立离场模式离场排序StudyonOptimizationModel ofhtScheduinoinMulti-runwayAirportZhang Yunpeng!Mu Yao2(1 Shanghai Civil Aviation EAST China AIR Traffic CONTROL Engineering and Technology Co.Ltd,Shanghai,201702,China;2Nanjing University of Aeronautics and Astronautics,Nanjing,211100,Jiangsu,China)Abstract:This paper establishes a multi-runway airport departure flight scheduling optimizationmodel with the objective function of minimizing the total delay time cost of passengers and considers theinfluence of route flow control.The solution is solved by backtracking algorithm,and the positionconstraint exchange algorithm is integrated to prioritize the flow control.For flights,Nanjing LukouInternational Airport is used as an example to verify the calculation example.Compared with the first-in-first-out model,the optimized departure model has a significant effect on reducing flight delay time withthe total delay cost of passengers reduced by 44.81%.The proposed model can significantly improve themulti-runway collaborative operation and provides insights and methods for the current scheduling andsequencing of multi-runway airports.Keywords:Routeflow controlIndependentdeparturemodeDeparture scheduling1引言为缓解大面积、长时间的离场航班延误现状和提高多跑道机场的场面运行效率，我国目前部分机场已从单跑道转化为多跑道运行模式。因此针对多跑道运行特点，需要对多跑道机场航班排序进行优化。近年来国内外专家致力于离场航班排序优化问题做了大量研究并提出了多种解决方案，既有针对单目标优化研究，也有针对多目标优化研究。还有，离场航班在实际运行过程中并不能只考虑地面的约束，也要考虑空中的航路流控。目前这些研究都没有考虑到多跑道机场更为复杂的运行情况。因此本文在前人研究的基础*国家自然科学重点基金资助项目（7 18 7 40 8 1）上，结合回溯算法基本理论，建立了多跑道机场离场航班排序优化模型，并考虑旅客延误时间成本层级和航路流控的影响，设计回溯算法，融合了位置约束交换算法和跑道轮询的思想，寻求多跑道离场航班排序问题的最优解，最后采用南京禄口国际机场为例进行算例验证。2离场限制因素2.1起飞尾流间隔标准本文针对运行模式为独立平行离场且跑道之间相互无影响的离场航班，对离场航班排序进行优化。离场模式下，不同机型之间要保证相应的标准间隔来保证安全。根据国际民航组织（ICAO）)规定，前后不同型号的飞机(S:轻型机、M:中型Journal6AviationVol.34No.5University一FlightofChinaofCivilSept.2023飞行学院学报中国民航机、H:重型机、SH:超重型机）的最小安全时间间隔标准如表1所示，单位为分钟。表1离场航班不同机型间的最小安全间隔标准Si航班j的机型轻型中型重型轻型111航班i中型1.511的机型重型21.512.2航路与航路流控离场航班在执行离场程序时，根据目的地机场选择相应的航路。然而，随着航班量的逐年激增，在空域资源有限的前提下，终端区逐渐变得拥堵。当遇到恶劣的气象条件，或者有军航活动干扰时，空中交通管制单位会发布航路或者航路点的流量限制以应对。所以，地面放行的航班频次，会受到空中流控的影响。若某航路点在一时间段收到流控限制，空中交通管制单位会对飞至该航路点的每架次航空器有相应数量约束，故在地面出发，离场程序经过受流控影响的航路点的航班，需要按照航路流控情况才予以放行。3模型建立与算法设计假设多跑道机场某天高峰时段离场航班按照计划起飞时刻由小到大进行初始排序组成集合为=1,2,m)，起飞跑道集合为R=1,2,n)，航路四个方向东南西北分别设代号为1，2，3，4，航路集合为K=1,2,3,4)。3.1目标函数本文考虑了旅客延误时间成本层级，假设现有某时段m架航空器等待离场，以总旅客延误时间成本最小化为目标函数：111Z,=minZZAirk-Eik)Cirk(1)其中，Eirk表示航班i被分配至跑道r并飞往航路k方向的预计起飞时刻，Airk表示航班i被分配至跑道r并飞往航路k方向的实际起飞时刻，Cirk表示在跑道r上的航班i往航路k方向的乘客数量。3.2约束条件令Xirk表示飞往航路点k的航班对跑道r的0-1变量，yi表示同一条跑道上航班i对航班j的0-1变量，2 表示航班i，j 对航路的0-1变量，S表示同一起飞跑道的前后两架航班i，j 滑行的最小安全间隔，T张表示飞往同一航路点的前后两架航班需要满足的流控约束，M，表示跑道所能承受的在跑道端等待的航班容量。定义决策变量：1,航班i在跑道r起飞至航路点k；Xirk(2)0,否则;1,航班i,都分配到跑道r起飞；yir(3)0,否则;1,航班i,都飞往航路k方向；(4)0,否则;约束条件如下：irk=,(i=,2,.,m,r=1,2,k=,2,3,4)(5)T=1Ak-Ark SurJ ir,(i,j=1,2.m,j=i+1)(6)jrkAik-Airk TixZ ix(i,j=,2.m,j=i+1)(7)ik M,(i=1,.,m,r=,2,k=1,2,3,4)(8)r-1Ek Ark,(i=1,2,.m,r=1,2,k=1,2,3,4)(9)其中，条件（5）为跑道唯一性约束，表示每航班仅能够选择一条跑道离场；条件（6）表示前后两架航班i和j在同一跑道起飞时的尾流间隔要大于或等于规定的最小安全间隔标准；条件（7）表示前后两架航班和j飞向同一个航路点之间的时间间隔要满足假设的航路流控；条件（8）表示在跑道端等待离场的航班总数目应该要小于或等于该跑道该时刻的起飞容量；条件（9）表示为满足实际运行要求，所有航班皆不可能提前起飞。3.3算法设计回溯算法2-3 能够在“穷举法 的基础上，通过剪枝的操作，排除不可能的排列方式，避免无效的数据排列。原有的航班排序的思路是塔台管制员根据航班的预计起飞时刻逐次放飞。然而，由于天气、军航活动等影响因素，机场可能会受到一定时间的流量管控限制。如果依旧按照原有的“先到先服务”原则进行航班放飞，可能会出现某航路航班无法抓住关键的时间间隙进行离场的情况，放行效率会大大降低，机场离场航班，尤其是受到流控限制的航班，延误时间将会大大增加。因此，将JournalUniversityofChinaFlightofCivilAviationVol.34No.5飞行学院学报中国民航Sept.2023回溯算法应用至离场航班的调度中，捕获流控限制下的关键放行资源，为的是回溯算法在进行排序时能够根据航班运行的各类实际限制与要求、空管对于跑道放行的规定，使得搜索能够系统性地贴合实际运行，算法设计步骤如下：（1）构建时间轴考虑每个航班的预计起飞时间以及不允许航班提前，为保证每个航班的预计起飞时间都在区间左端点处，将初始航班时刻表均匀划分成多个时间区间，如0 8:0 0:0 0,0 8:0 5:0 0)。(2)初始化变量将离场排序问题视为简单的排序问题，把航班的预计起飞顺序标记为1，2，m。每个序号代表一个航班，且包含所对应的飞机机型、起飞跑道、所飞航路、乘客人数以及航班号等航班信息。(3)回溯算法排序作为算法的约束条件，融合了位置约束交换算法。考虑北航路受到10 分钟时间间隔的流控，在时间轴上应用回溯算法设计排序函数。首先输入受到流控的航路代号4和要求的间隔时间10 分钟进行排序。在航路发布流控时，若当前排序不满足航路要求，说明初始化的航班排序中受流控航班间的时间间隔较近，因此就需要加大受到流控的航班间的时间间隔，对出现在同一时间区间内受到流控约束的航班进行时间延误成本比较，将延误成本较高的航班排在时间区间起点处，其余航班向后位移两个区间，并且对排序后有受流控约束航班的区间进行标记。如果得到的结果仍然不满足要求，反复调用排序函数直到结果满足要求，然后进入下一区间继续排序，并得到第一次排序结果。时间延误成本 T计算：所在时间区间起点与受流控航班预计起飞时间之差乘以旅客人数。(4)跑道轮询在第一次排序结果的基础上，验证当前区间内除受流控航班外的所有航班是否有足够时间可以起飞。验证方式为：首先计算分均延误时间成本并对其进行排序，然后对结果轮询分配跑道，最后计算该区间内的尾流间隔之和T，若T大于该区间时间长度则将越位航班分配到下一区间，然后进入下一时间区间进行排序，直到所有航班能够在所在时间区间内起飞。分均延误时间成本计算：该航班在当前区间内所有可能起飞时间点所产生的时间延误成本均值。(5)输出最优解输出各航班的离场时刻以及总延误最少的航班排列顺序及总延误时间成本大小。绘制算法流程图如图1所示：开始构建时间轴及时间区间初始化变量并设计排序函数计算当前区间内受流进入下一区间控航班时间延误成本是航班排在时间区间延误成本最高？起点处后位移两个区间，并且对排序后有受流控约束航班的区间进行标记计算当前区间内未受流控约束航班分均延误时间成本并排序输出最优解结束图1算法流程图4算例验证4.1算例数据本文选取了南京禄口机场某天早上8 点到8 点25分早高峰时段的离场航班数据，在早高峰大量JournalAviation8Vol.34No.5UniversityFlightofChinaofCivilSept.2023中国国民航飞行学院学报始发航班离场运行时使用独立离场模式，相邻跑道之间离场互不影响，并且东、南、西、北4个方向均具备离场程序可供航空器离场时使用。由于本文考虑到了旅客延误成本层级，故本文查阅了各航班机型的座位情况并假设某天客座率为9 0%进行分析。原始离场航班计划表如表2。表2 离场航班计划表序号航班号预计离场时刻航路机型旅客人数1DKH171708:00:004M1582DKH178508:00:002M1583CCA732408:00:004L2814DKH169708:05:002M1585CES288308:05:003M1226CSZ569808:05:002M1587CSN387208:10:003M1228CES270308:10:002M1589CES281108:10:004M17810CES285308:10:002M15811HX22108:15:003M28312DKH173308:15:002L15813CES289108:15:003M15814CDG492108:20:003M16815CSZ871608:25:004M17816CES979708:25:004M17817CCA15708:25:003M2814.2结果分析现假设由于空中管制对于流量的管制，北航路点4受到要求时间间隔为10 分钟的流量时间间隔管控，并且该机场跑道容量为42 架次/小时，即每小时放飞的航空器数量不能超过42 架次。依照原有的“FCFS先到先服务原则，先抵达跑道端的航班优先离场，根据预计离场时间的顺序与跑道的使用情况，来进行离场航班的调度。离场航班遵循实际起飞时间不大于预计离场起飞时间原则，得到排序情况如表3所示。表3“FCFS先到先服务排序FCFS实际旅客总延误时间序号航班号跑道号误时间(min)离场时刻(min)1DKH17170608:00:00002DKH17850708:00:0000.3CCA73240608:10:001028104DKH16970608:05:00005CES28830708:05:00006CSZ56980608:06:0011587CSN38720708:10:00008CES27030608:11:301.52379CES28110608:20:0010178010CES28530708:11:00115811HX2210608:21:006169812DKH17330608:22:0071106JournalAviation9ofChinaUniversityFlightofCivilVol.34No.5飞行学院学报中国民航Sept.202313CES28910708:15:000014CDG49210708:20:000015CSZ87160608:30:00589016CES97970608:40:0015267017CCA1570608:41:00164496根据以上的航班离场数据与放行约束条件，在离场放行模型的基础上，寻找南京禄口机场早高峰8:0 0:0 0-8:2 5:0 0 离离场航班排序的最优解。通过算法设计，输出最优排序结果，并将算法结果与先到先服务排序结果进行对比与分析，最后得到的基于回溯算法排序优化如表4所示。表4回溯算法排序实际起飞旅客总延误时间序号航班号跑道号延误时间(min)时刻(min)1DKH17170608:00:00002DKH17850708:00:00003CCA73240608:10:001028104DKH16970708:05:00005CES28830608:06:301.51836CSZ56980608:05:00007CSN38720608:11:301.51838CES27030708:10:00009CES28110608:20:0010178010CES28530708:11:00115811HX2210608:15:000012DKH17330708:15:000013CES28910608:16:00115814CDG49210708:20:000015CSZ87160608:30:00589016CES97970608:40:0015267017CCA1570608:25:0000通过对单个航班延误时间和旅客总延误时间求和，得到FCFS排序的航班总延误时间为72.5min，旅客总延误时间成本为16 0 0 3min。用回溯算法得到的航班总延误时间为45min，相比减少了37.9 3%，旅客总延误时间成本为8 8 32 min，相比减少了44.8 1%。在较短的放行时间中，无论是先到先服务原则排序还是回溯算法排序，在满足尾流间隔的要求下，对于跑道的利用率都是很高的。但是，在流控条件的约束之下，单靠管制员主观判断，可能无法很好地利用流控中有限的放行资源，抓住关键的放行时刻。由表4可知，在流控限制的影响下，先到先服务缺乏合理的排序，导致了航路点4被限制的航班发生了较长时间的延误，并且延误时间会继续累计叠加下来，对于后续的航班的影响会越来越大。在先到先服务的排序队列中，虽然时间段08:00:00-08:25:00之中，放行航班数量与回溯算法排序队列数量相同，然而受到流控影响的航班没有在关键的时刻放行，导致了序号17 的航班发生了严重掉队的延误情况。将先到先服务排序原则与回溯算法优化排序所得到的两个序列中的航班实际离场时刻，与航班原始预计离场时刻进行对比，得到所有航班起飞时刻对比图如图2 所示。（下转第15页）上接第9 页）JournalAviationUniversityofCivilofChinaFlightVol.34No.515中国民航飞行学院学报Sept.20233）5S标准化管理的体系养成5S标准化管理项目实施完成后，项目组成员应对5S标准化成果进行汇总，以便下次对目标或流程修订时进行快速修订。具体文件资料汇总包含各区域“标准指引、各岗位“工作标准”。参考文献1】中华人民共和国交通运输部.大型飞机公共航空运输承运人运行合格审定规则（CCAR-121R7）08:40:00预计超飞时割先到先服务实际起飞时刻回湖算法实际起飞时刻08:30:0008:20:0008:10.0008:00:00航班号图2 起飞时刻结果分析图分析图2 可知，在进行始发航班的离场调度中，基于回溯算法的优化排序相比于先到先服务排序，所得的航班离场时刻曲线与预计离场时刻曲线更符合，表明相比于“FCFS排序原则，利用回溯算法所求旅客总延误时间最小序列，在减小航班总延误时间问题上更加合理和有效。5结论（1）首先建立了最小化旅客延误时间成本的数学模型，考虑了离场航空器之间必要的尾流间隔和旅客延误时间成本层级，接着阐述了回溯算法运行的流程和参数设计。（2）选取南京禄口机场离场航班数据进行算例验证。首先考虑实际运行过程中存在的流控S.2021.32中国民用航空总局.民用航空器维修单位合格审定规则（CCAR-145R3）S 2 0 2 2.23中国民用航空总局.民用航空器维修培训机构合格审定规则(CCAR-147R1)S2 0 2 2.24程爱学.质量总监M.北京：北京大学出版2005.45芮福宏，申奕.现场管理与5S活动实训教程M.天津：天津大学，2 0 13.9约束对航班时刻表进行排序，再运用回溯算法融合位置约束算法进行相对应的离场航空器排序优化，并与实际管制运行中的FCFS算法进行比较，表明了优化后的离场航班顺序大大减少了离场航班延误的总时间，证明了回溯算法进行离场航空器排序优化时的适应性和可行性。（3）本文从离场航班尾流间隔和航路点流控方面建立了离场航班排序优化模型，但是由于时间和精力的不足，仍存在一定的欠缺：本文在建立离场航班排序优化模型时没有考虑进场航班的影响，可能会导致结果不够准确。本文建立的模型没考虑相邻跑道干扰、滑行路径等因素对航空器离场过程的影响。因此，如何考虑相邻跑道干扰的离场航班排序优化是一个未来值得研究的工作方向。参考文献1 ICAO.Rules of the air and air trafficservices(DOC4444)S.19962王岩冰，郑明春，刘弘.回溯算法的形式模型J.计算机研究与发展，2 0 0 1(9):10 6 6-10 7 93 Mihelie Jurij,Cibej Uros.An experimentalevaluation of refinement techniques for the subgraphisomorphism backtracking algorithmsJ.OpenComputer Science,2020(1)