|
航班计划优化研究概述
Overview of Flight Planning Optimization Research
李德龙① LI De-long；徐海文② XU Hai-wen；傅强② FU Qiang
（①中国民用航空飞行学院空中交通管理学院，广汉 618307；②中国民用航空飞行学院计算机学院，广汉 618307）
（①School of Air Traffic Management，Civil Aviation Flight University of China，Guanghan 618307，China；
②School of Computer，Civil Aviation Flight University of China，Guanghan 618307，China）
摘要：从航班计划优化的不同时间阶段分析，可以将航班计划优化分为航班计划静态编排优化、基于航班延误预测的航班计划动态反馈优化和基于机场协同决策（A-CDM）的航班计划动态调整角度三类；进而从航班时刻、机型指派、航班频率等编制环节分析了航班计划静态编排优化；随后利用延误波及预测与数据挖掘预测的优化方法分析了基于航班延误预测的航班计划动态反馈优化的相关研究。最后，根据航班计划优化复杂性分析，给出了航班计划优化的发展趋势和未来研究方向。
Abstract: From the analysis of different time stages of flight planning optimization, flight planning optimization can be divided into three aspects: static flight planning optimization, flight planning dynamic feedback optimization based on flight delay prediction, and flight planning dynamic adjustment based on airport collaborative decision-making (A-CDM). Then, it analyzes the static scheduling and optimization of flight plans from the preparation links of flight schedules, aircraft type assignments, and flight frequencies; then uses the optimization method of delay spread prediction and data mining prediction to analyze the correlation of flight plan dynamic feedback optimization based on flight delay prediction the study. Finally, according to the complexity analysis of flight plan optimization, the development trend and future research directions of flight plan optimization are given.
关键词：航班计划优化；航班延误预测；深度学习；机场协同决策；监督学习
Key words: flight planning optimization；delay prediction；deep learning；airport-collaborative decision-making；supervised learning
中图分类号：TP39 文献标识码：A 文章编号：1006-4311（2021）02-0001-05
0 引言
航班计划是航空公司一切生产活动的基础和核心，其他所有生产计划都围绕航班计划来进行，因此及时科学地编排航班计划是保证飞行安全，改善服务工作，提高航空器的利用率、载运率及提高经济效益，完成运输生产任务有着重要的意义[1]。近几年航空业发展迅速，随着航班量的大幅度增加，航班延误问题也日益突出[2]，在影响航班延误的因素中，航班计划编制不合理是重要因素之一。
二十世纪七十年代就有了关于航班计划优化问题的研究，国外Wegmann H M[3]、Dachkovsky V.Z[4]等人较早开展研究，随后国内朱金福[5]、胡明华[6]等人做了大量的航班时刻与航线网络研究工作。经过几十年的发展，航班计划优化研究愈加复杂，不再是简单的考虑单一因素与模型。目前航班计划优化的研究开始利用深度学习等理论，依靠大数据分析的优势，进一步完善了航班计划优化理论。
文章从航班计划的编制、反馈调整等不同角度对航班计划优化的研究成果进行了分类总结，将研究成果分为三类：第一类是航班计划静态编排优化，涉及航班频率、航班时刻等研究；第二类是航班计划动态反馈优化，涉及航班延误预测研究；第三类是航班计划的动态调整，涉及机场协同决策（A-CDM）。以航空公司角度出发的航班计划静态编排优化，通过优化航班时刻、机型、机组等因素增加运营经济性，但如过多追求盈利，使航班串衔接过于紧密，过站时间裕度不足，一旦发生延误，延误波及不可避免，损失会更大。基于延误预测的航班计划研究以使用机器学习的相关理论为主，在提高预测精度的基础上，实现航班计划的优化调整。而基于A-CDM的航班计划动态调整优化研究，旨在实现不可控因素下航班计划的临时动态调整，减少航班延误。
文章的具体章节安排如下：首先在第1节介绍航班计划静态编排优化相关研究，具体包括航班时刻、航班频率等编制环节；随后在第2节分析了基于航班延误预测的航班计划优化，又将其分为基于数据挖掘预测与基于延误波及预测两类优化方向；在第3节讨论了基于机场协同决策（A-CDM）的航班计划动态调整；最后在第4节对文章内容进行总结，并结合当前研究现状，从航班计划优化研究复杂性出发，给出三点未来的研究展望。
1 航班计划静态编排优化
航空公司是航班计划编制的主体，航班计划是航空公司一切生产活动的中心环节。航班计划的编排步骤环环相扣，紧密相连，需不断综合考虑航空公司现有生产资源及对市场需求、收益深入分析，是一个动态变化的过程。但是航班计划编排所考虑的因素又是相对静态的，未充分考虑气象、流量控制等因素，故以航空公司角度出发的航班计划优化研究可看做航班计划编排静态优化研究。
综合航班计划编制过程，从飞行的航线和航段选择、班次和班期、机型指派、航班号、航班时刻等多个方面完成，其中关于班次、班期的研究也称作航班频率的研究。国内外学者在研究航班计划优化时，多从航班频率、机型指派、航班时刻三个方面，下面将重点介绍关于这三个方面的研究。
1.1 航班频率
航班频率的确定和优化是航班计划编制的关键环节，其涉及运力供给、可用机型、航线需求、竞争对手占有率等方面。航班频率的确定也是航班时刻和机型指派的基础。
八十年代，国外Christopher C. Findlay[7]用标准最优化模型来平衡最优票价与航班频率的关系，随后Du scaron[8]用实际起飞时间与期望起飞时间差的绝对值来衡量航班频率实现的经济效果，这种考虑单一模型和因素的方法在近几年得到改进。Sze-Wei Chang[9]在航空公司运营成本和旅客延误成本最低基础上开发出利润最大模型，但只针对特定航线，未考虑航线网络下的航班频率优化。而国内，朱金福[10]较早建立了利润最大化的航班频率优化模型；朱星辉[11]针对航空运量预测对航班频率进行了研究；姜思露[12]建立基于旅客计划延误的航班频率优化模型，考虑了多机型多航线的竞争环境对航班频率的影响，但取航班频率固定值会对进一步的求取可行解造成困扰，约束条件可进一步增加，其建立的模型数学表达公式如下：
■（1）
式（1）为总成本最小目标函数。其中，C为总成本，由旅客计划延误成本及运营成本两部分组成；L为航线集合，l∈L；K为机型组合，有k∈K；cSD为旅客延误单位成本；cl为航班运营成本；T为航班计划周期；MSt为某航司在航线l上的市场分担率；Rl为某个航班周期内，航线l的客座率；Flk为航线l上机型k的航班频率。
单一的航班频率优化模型逐渐被多约束模型取代，约束条件由利润和运营成本增加了延误等成本，将航班频率与机型指派、航线网络等结合建立一体化综合优化模型，也是下一步的研究重点方向。
1.2 机型指派
机型指派是指根据具体机型的舱位容量，收益状况、运营成本及飞机是否可用，将不同舱位容量的飞机分配给相应的航线，确定航班所使用的最佳机型，完成飞行计划[13]。它也是航班计划编排的核心环节，是机组排班等问题的基础。机型指派的好坏直接影响航空公司的运营收益，也影响机组人员配置、维修、停机位分配、后序航班衔接等问题。
国外的航空运输业发达，对机型指派问题研究较早，早期的大多数研究集中在枢纽航线网络和日航班计划，优化效果较之一般。在2006年，Barry C. Smith [14]从机场纯度角度出发，即要求某一机型涉及的机场尽量集中，以此建立鲁棒性机型指派模型。Oussama Aoun[15]则用隐马尔科夫模型基于对最可能状态的估算来实现了机组人员的最佳配置，是对机型指派后续问题的优化。国内，朱星辉[16]借鉴Barry C. Smith的理论，从航班纯度出发，建立了鲁棒性机型指派模型。另外，姜思露[17]在旅客计划延误计算研究基础之上，建立了航班频率和机型指派综合优化模型，并指出了航班频率、机型指派和航班时刻三者综合建模的可能。
机型指派优化问题在近几年得到很大发展，偏向建立综合性优化模型。随着市场需求分析、预测深入研究和机器学习相关理论方法的发展，机型指派问题研究也会得到进一步的发展。
1.3 航班时刻
在过去几十年里，已经提出较多时隙分配优化模型，从单个机场的航班时刻优化模型到基于范围网络的航班时刻优化模型，航班时刻一直是航班计划优化研究的主要对象。
传统的航班时刻资源管理中，首先考虑的因素为旅客需求，即出发与换乘；其次考虑航司的的需求，即相应的航班计划；最后考虑机场运行需求，即配套设施与空域容量限制。国内的流量管理问题特殊，受终端区、航路规划与空域限制等多因素影响，在考虑时刻优化时需考虑对空域容量的优化利用。早在2003年，胡明华[18]就在多元受限地面等待策略基础上提出了多元受限航班时刻优化模型，并用一套改进启发式算法求解，考虑将航班前推或后推至时间段来高效利用机场和空域容量。但空中交通流量的持续增长，空域容量限制影响提高，加上机场扩建的可能性是有限的，导致了大型机场的空中交通需求能力失衡及进、离港航班延误。
欧洲大型机场为了解决空中交通容需不平衡问题，实施了战略性航班时刻表。Miguel Lambelho[19]等人用基于机器学习的方法评估了有关潜在航班延误和取消的战略性航班时刻表，对机场的潜在性能瓶颈进行了探讨，且其模型具有通用性。这也是首次将机器学习方法与战略性航班时刻评估结合起来，模型的功能集还有较大的改进空间。YuFeng Tu[20]研究了用于估算空中交通拥堵预测模型所需的航班离港延迟分布，开发出战略层面的离港延误预测模型，为后续航班时刻优化提供了离港延误概率模型基础。在战略层面对航班计划的研究较少，没有系统的优化方法，其研究成果为后续研究提供了理论基础。
在2005年，Loo Hay Lee[21]就讨论了基于潜在违规行为的航班时刻表的鲁棒性，将消除潜在违规行为，如设备故障，看成一个多目标优化问题，为后续的航班时刻优化提供了思路。后续Ahmed Abdelghany[22]考虑了基于竞争的航班时刻优化模型，明确考虑了因航空公司之间的航线网络竞争而导致的乘客需求转移，对启发式搜索算法和网络竞争分析模型和资源（如机组和机型）跟踪模型进行了集成。Xi Geng[23]针对多机场系统（MAS），提出一种改进模拟退火优化模型来优化航班时刻，降低了MAS的平均位移和平均延迟。可见，在多机场、航线网络完整条件下，航班时刻优化将会更加有效，对战略层面的优化研究也就更加有力。
航班时刻一直是航班计划优化的重点对象，优化策略从战术层面到战略层面不断发展，给航班计划优化带来丰富理论基础。合理分配航班时隙将给航空公司带来巨大的营运收益，也可提高旅客出行便利。
2 基于延误预测的航班计划动态反馈优化
航班延误预测问题是近几年的研究热点，航班延误预测的研究大致分为两类，分别是基于数据挖掘的航班延误预测和基于航班延误波及的航班延误预测。研究航班延误预测，对机场航班时刻再分配、地面资源保障等有重要意义。2019年，付振宇[24]、刘博[25]等人综述了航班延误预测方法相关研究，使航班延误预测研究有了系统的理论介绍。
2.1 基于数据挖掘的航班延误预测
基于数据挖掘的航班延误预测主要使用决策树、随机森林、支持向量机、贝叶斯网络模型等经典机器学习方法，和深度神经网络、卷积神经网络等深度学习方法。经典的贝叶斯网络模型被广泛的应用在基于航班延误传播的航班延误预测中，其由两部分组成，一部分是有向无环图■为节点的集合，其中■为有向边的集合，Vi指待解决变量，ej指节点间关系；另一部分是概率分布表，其中根节点为边缘分布■，非根节点为条件概率分布。根据条件独立性，节点V的联合概率分布为：
■（2）
航班延误预测中，从考虑影响航班延误的单因素建模到多因素分析，延误预测理论逐渐丰富。王楠[26]量化了机场恶劣天气对起飞航班正常性影响的程度，建立了影响航班延误的气象因子数据库，以决策树形式对不同季节、不同气象因子等因素对航班延误的贡献度进行了分析。恶劣天气是影响航班延误的重要因素之一，气象因素的量化分析对航班延误的作用有重要意义，对后续的航班计划优化提供了理论基础。Sun Choi [27]也研究了恶劣天气对于航班延误的影响，并且对比了随机森林、决策树、集成学习方法、K最近邻（KNN）分类算法等相关监督机器学习方法对在考虑天气影响下的对航班延误预测的效果的精度，以丹佛国际机场（DEN）和夏洛特道格拉斯国际机场（CLT）之间的航班数据进行研究，其结果中分析出天气原因虽然是影响航班的重要因素，但不是唯一性元素，在研究航班延误预测时还应当考虑其他因素。使用监督机器学习方法在航班延误预测中，所选数据量要求较大，且各相关因素间的关系十分复杂或者高度非线性时，则可收到较好的预测效果。建立预测模型时，监督机器学习可将预测结果与实际结果（训练验证数据）相比较并不断调整预测模型，形成一个不断学习使结果达到预期的学习过程，训练过程如图1。
宿爱静[28]初步建立了机场的航班运行仿真模型，将输出的延误时间、飞机利用率作为评价指标，找到影响航班运行的瓶颈因素，也可预测不正常航班的出现概率。此模型可加入流控、天气等相关数据，初步建立航班延误预测综合模型，可分析航班延误传播和航班计划系统鲁棒性。针对影响航班正常的因素，建立综合预测模型分析航班的正常性与不正常航班的可控与恢复性研究也是当下的重点研究方向。
2.2 基于波及延误的航班延误预测
针对航班波及延误的研究，大多数考虑航班串（链）这一概念。航班串指的是航空公司在经济性基础上安排同一架飞机一天中连续执飞多个航班，如图2所示。当航班串中某一航班发生延误时，可能导致后续航班发生延误，这就是延误波及。
波及延误预测需要考虑多机场、多航线等因素，Dunbar, Michelle[29]在综合考虑飞机航线和机组配对的情况下计算最小的延误波及成本。CAO W D和HE G G.[30]等人将贝叶斯网络应用于连续航班间延误波及分析，以上研究分析了延误在航班环中的波及情况，但没有针对机场对航班串中延误传播的影响进行研究。而国内的Weiwei Wu[31]分析了航班到达时间会受前一起飞航班的影响，包括延误传播现象，及其他影响延误的因素在网络中传播机制。吴薇薇[32]用基于航班串的贝叶斯网络模型分析了航班延误波及，用加权马尔科夫链模型对机场整体延误状态进行预测，预测结果更加可靠，对航班计划进行调整，极大提高了航班计划运营的可靠性。当然，贝叶斯网络模型预测也具有局限性，延误预测不及时，只有得到明确计划起飞时间后才可以预测延误，对航班计划变更也只是提供数据支撑。高强[33]则考虑了延误波及下的航班过站松弛时间重新分配问题，这也是对波及延误下可控时间间隙的重新调整，但此类研究必须保证航班拥有合理的过站时间裕度。张海峰[34]建立基于延误控制的短期航班计划编排模型，较传统航班计划编排优化，考虑延误分析后的航班计划编排更可能减少延误发生。
上述延误预测都是基于航班延误对后续航班计划的变更存在影响，而周覃[35]侧重研究了与航班计划变更无关的独立延误，研究飞行路径优化模型对提高航班计划的先行鲁棒性的作用。总之，机器学习理论在航班延误预测领域应用更深，航班延误预测精度更高，则对航班计划优化更有极大的参考价值。基于延误预测的航班计划优化理论不断丰富，后续研究重点也将围绕大数据、综合性方向展开。
3 基于机场协同决策的航班计划动态调整
恶劣天气、流量控制、军事活动等不利因素影响航班正常进、离港，加上各组织间的沟通协调存在壁垒，会造成某时段机场大面积延误和大量人员滞留。因此需要一套高效的决策系统来实现不利条件下航班计划的动态调整，以减少航班延误及延误损失。
机场协同决策最先由欧洲航行安全组织[36]提出，由最早的协同决策平台CDM发展而来，且较早的运用在了瑞士苏黎世机场中，效果显著。中国民航局高度重视A-CDM的推广，截止2019年底，已有37家机场完成A-CDM建设。中国民航局发布的机场协同决策技术规范（征求意见稿）文件中指出，通过多方信息共享，打破各部门单位的沟通壁垒，减少飞行等待延误，提高突发事件预测和应急能力，实现航班计划的动态调整。建设A-CDM系统需要无障碍信息沟通，且保障共享数据的完整。数据完整是A-CDM的灵魂[37]，各单位保障完整数据的共享，在面对恶劣天气、流量控制等不利条件时，A-CDM系统可实现预判、分析延误影响程度和发展趋势。其中完整数据包括两类：①传统AODB数据、订座系统、离港系统、航旅APP系统；②空管系统、货运系统、安检系统、地面结算系统。
如果有大面积航班延误预警信息，A-CDM系统会根据相应运行限制和受影响时段，生成调整预案，并向机场相关单位发送调减比例和需调整航班等信息。通过航空公司反馈的航班取消或变更计划离港时间信息，生成并发布最终的航班调整方案。A-CDM系统可以自动跟踪需调整航班的执行情况、实时状态、前序状态和协调状态，协助机场运管委监督航空公司落实调整方案[38]，具体流程如图3所示。
针对A-CDM只能对里程碑事件进行监控和预警的不足，北京首都机场研发了基于复杂事件处理的协同决策系统CEP-CDM[39]。此系统相较于A-CDM具有实现机场主动“感知—分析—反馈”的能力，其优势在于从历史航班运行数据中学习出航班保障标准，对现行数据进行校验、管理，航班计划的动态调整效果更好。但CEP-CDM的构建需要中长期乃至长期的合理规划。
4 总结和展望
文章概述了国内外航班计划优化研究文献，从航班计划的编制过程和反馈优化角度将其分为三类，为航班计划的静态编制优化、动态反馈优化和动态调整。结合当前航班计划优化研究现状来看，因需考虑较多环境因素与多方协同，航班计划优化问题目前较为复杂，下列给出三点未来的研究展望。①航班计划涉及到航空公司收益与运营，也影响相关空管、机场单位的运行，单纯从某一角度或因素看待航班计划优化问题有着较大的局限性，需要有战略层面的统筹分析。②针对短期计划，可以看出机场协同决策A-CDM是机场未来发展的趋势，完备的A-CDM在面对航班延误时能实现动态实时调整航班计划，预测、预处理航班延误。但长期计划仍需要综合各方需求去监管和制作，A-CDM系统仍需要较长时间完善与推广。③面对当下数据量的增长，如何更合理、深入的应用深度学习等相关理论与航班计划优化研究相结合，是未来的研究热点。
参考文献：
[1]潘卫军.空中交通管理基础[M].二版.成都：西南交通大学社出版社，2013：206-207.
[2]徐海文.不正常航班计划恢复的可控性研究[D].南京航空航天大学，2018.
[3]Wegmann H M, Hasenclever S, Michel C, et al. Models to predict operational loads of flight schedules. 1985, 56(1):27-32.
[4]Dachkovsky V.Z., Pozdnyakov V.V., Yanbykh G.F.. The Decision-making Procedure in the Automated Process of Formulating a Flight Schedule. 1983, 16(20):465-470.
[5]姜涛，朱金福.航空公司航线网络构形的效益分析研究[J].工业技术经济，2006（11）：105-107.
[6]胡明华，陈爱民，徐肖豪，袁卫东.多元受限的地面等待策略问题研究[J].南京航空航天大学学报，1998（01）：3-5.
[7]Christopher C. Findlay. Optimal Air Fares and Flight Frequency and Market Results. 1983, 17(1):49-66.
[8]Du&scaron, an B. Teodorovi&cacute. Flight Frequency Determination. 1983, 109(5):747-757.
[9]Sze-Wei Chang, Paul Schonfeld. Optimized Schedules for Airline Routes. 2004, 130(4):412-418.
[10]朱金福. 航空运输规划[Ｍ]．西安：西北工业大学社出版社，2010．
[11]朱星辉．航空公司航班计划优化设计研究[Ｄ]．南京：南京航空航天大学，2007．
[12]姜思露，朱金福，孔明星，周秦炎.基于旅客计划延误的航班频率优化研究[J].武汉理工大学学报（交通科学与工程版），2019，43（01）：136-140.
[13]朱星辉，朱金福，巩在武.我国航空公司机型指派模型及算法研究[J].工业技术经济，2007（04）：75-77.
[14]Barry C. Smith, Ellis L. Johnson. Robust Airline Fleet Assignment: Imposing Station Purity Using Station Decomposition. 2006, 40(4).
[15]Oussama Aoun, Malek Sarhani, Abdellatif El Afia. Investigation of hidden markov model for the tuning of metaheuristics in airline scheduling problems. 2016, 49(3):347-352.
[16]朱星辉，朱金福，高强.基于航班纯度的鲁棒性机型指派问题研究[J].预测，2011，30（01）：71-74.
[17]姜思露.航班频率和机型指派综合优化研究[D].南京航空航天大学，2019.
[18]胡明华，朱晶波，田勇.多元受限的航班时刻优化模型与方法研究[J].南京航空航天大学学报，2003（03）：326-332.
[19]Miguel Lambelho, Mihaela Mitici, Simon Pickup, et al. Assessing strategic flight schedules at an airport using machine learning-based flight delay and cancellation predictions. 2020, 82.
[20]Yufeng Tu, Michael O Ball, Wolfgang S Jank, Estimating Flight Departure Delay Distributions—A Statistical Approach With Long-Term Trend and Short-Term Pattern[J]. Journal of the American Statistical Association, 2008, 103.
[21]Loo Hay Lee, Chul Ung Lee, Yen Ping Tan. A multi-objective genetic algorithm for robust flight scheduling using simulation. 2005, 177(3):1948-1968.
[22]Ahmed Abdelghany, Khaled Abdelghany, Farshid Azadian. Airline flight schedule planning under competition. 2017, 87:20-39.
[23]Xi Geng, Minghua Hu, Stefan Balint. Simulated Annealing Method-Based Flight Schedule Optimization in Multiairport Systems. 2020.
[24]付振宇，徐海文，傅强.航班延误预测研究概述[J].科技与创新，2020（03）：1-4.
[25]刘博，叶博嘉，田勇，杨旻昊.航班延误预测方法研究综述[J].航空计算技术，2019，49（06）：124-128.
[26]王楠，杨洪儒，周建军，曹敦波.乌鲁木齐机场恶劣天气影响起飞航班延误的量化研究[J].干旱气象，2018，36（04）：684-693.
[27]Sun Choi,Young Jin Kim,Simon Briceno,Dimitri Mavris.Prediction of weather-induced airline delays based on machine learning algorithms[A].in:IEEE，.2016 IEEE/AIAA 35th Digital Avionics Systems Conference : [Volume 1 of 2] Pages 1-657.[C].2016: 1-6.
[28]宿爱静，杨文东，张冲，孔明星.航班运行系统仿真建模分析[J].哈尔滨工业大学学报，2019，51（09）：49-55.
[29]Dunbar, Michelle,Froyland, Gary,Wu, Cheng-Lung. Robust Airline Schedule Planning: Minimizing Propagated Delay in an Integrated Routing and Crewing Framework[J]. Transportation Science,2012,46(2).
[30]CAO W D, HE G G. Bayesian networks analysis for sequence flight delay and propagation[J]. Journal of Computer Applications, 2009, 29(2): 606-610.
[31]Weiwei Wu, Cheng-Lung Wu. Enhanced delay propagation tree model with Bayesian Network for modelling flight delay propagation. 2018, 41(3):319-335.
[32]吴薇薇，孟亭婷，张皓瑜.基于机场延误预测的航班计划优化研究[J].交通运输系统工程与信息，2016，16（06）：189-195.
[33]高强，周覃，陈欣.基于波及延误的航班过站松弛时间重分配[J].华南理工大学学报，2019，10：151-156.
[34]张海峰，胡明华.航空公司短期航班计划编排模型及算法[J].南京航空航天大学学报，2015，47（04）：553-558.
[35]周覃，高强，李伟文.基于波及延误的飞机路径随机优化模型[J].交通信息与安全，2017，35（03）：117-123.
[36]欧洲空管机场协同决策实施手册（中文版）[S]．民航总局空中交通管理局，2013．
[37]郭亚惜.浅谈民航协同决策（CDM）系统发展[J].中外企业家，2020（04）：29-30.
[38]Business - Airline and Airport Management; Data from Universidade da Beira Interior Broaden Understanding of Airline and Airport Management (The airport A-CDM operational implementation description and challenges). 2020.
[39]卢敏，冯霞，徐涛.机场协同决策研究综述[J].智能建筑，2018（08）：58-61. |
