基于延误成本的不正常航班调整策略研究_罗军.pdf

现代计算机Modern Computer第 28 卷 第 24 期2022年12月25日文章编号:1007-1423（2022）24-0042-06DOI:10.3969/j.issn.1007-1423.2022.24.007基于延误成本的不正常航班调整策略研究罗军，江林林（中国民用航空飞行学院空中交通管理学院，广汉618307）摘要：为了解决不正常航班给航空公司和旅客带来的巨大经济损失，对各类不正常航班调整的成本指标在指派模型的基础上进行研究，在Matlab中运用改进的匈牙利算法对模型进行求解。通过成本矩阵解得最小成本航班计划，并借助时空网络图对延误航班调整策略进行描述并提出合理的恢复方案。以某航空公司某日发生大片延误的实例来验证了这一模型的优越性，证明该算法在解决航班调整问题时有一定的参考价值。关键词：航班延误成本；航班恢复；指派模型；改进的匈牙利算法；时空网络0引言在当代人的远距离旅行中，航空出行扮演着举足轻重的地位，日益增长的飞机数量造成航班正常率的不断降低。天气条件、机场保障等问题都是导致飞机延误或取消的主要原因，给出行者造成了不便利的同时，航空公司和机场也承担着经济损失。但是由于航空的飞行安排已经非常严密，一旦某飞机受到影响，延误会在航班串上产生多米诺效应，导致大量飞机晚点。及时合理地恢复延误航班，确保恢复成本尽可能小，不能仅靠调度员，而采用最优化算法则可以迅速达到目标，在减少成本的同时还能将签派员的工作效率提高，为后续飞机排班提供依据。针对航班恢复问题，国内外已研究多年，也取得了相应的成果，赖俊晓1基于我国机队规模小，将限制信息融入资源指派模型，构建了最小成本的航班恢复模型。为了提高航空公司效益，创造性地将改进的贪婪随机自适应搜索算法运用于航班恢复模型中。戴福青等2将机会成本应用于航班恢复中，通过动态规划算法将延误航班损失降为原来的44%，证明了动态规划算法在解决航班恢复问题时的可行性。李琳丹等3在非正常航班成本分析与优化方面，使用了三天内可用及新开航班结合的方法实施延误航班恢复，利用LINGO对延误信息计算来减少恢复时间。姚韵4提出基于机号路径置换算法，且用匈牙利法进行边界约束求解。白凤等5在航线不足和空港封闭而导致客机非正常飞行的情形下，通过列生成算法来求解构建的多商品网络流模型。田倩南等6基于占优准则减少被恢复航线组合量，利用CPLEX实现减小成本，提出了改进的时空网络法。Teodorovi等7结合机组及飞机路线恢复，使用字典序优化技术及分层优化技术，对新的机组进行排班重算。Vos等8提出了一种新的动态建模框架，该框架可以针对飞机短缺问题解决已中断的飞机时间表。Sinclair等9在2016年整合了航班和乘客恢复问题，通过混合规划整数模型，并运用列生成算法来求解该模型。Petersen等10将飞行计划和线路、旅客等因素同时考虑，运用列生成法与Benders分解来求模型，最后得出航班调整的具体计划。1不正常航班问题描述当航空公司原因或机场因为某些突发情况封闭，飞机原计划飞行不能实施，这时要尽快调整航空公司飞行计划，安排新飞行计划。在航班计划调整方面有三种调整策略，即飞机置换、航班延误、取消航班11。由此可知，可以 42罗军等：基于延误成本的不正常航班调整策略研究第24期同时存在飞机的延误成本和置换成本。飞机置换是取消原执行该航班的飞机，将原不正常航班安排给其他飞机去执行，如图1所示。图 1飞机置换图2模型的建立2 2.1 1指派模型指派模型航班恢复问题是在短时间内调整航班计划而使延误的成本最小化。所以，这类问题可看作指派问题。指派问题概念如下：指派问题的简单定义是：有 n 个人做 n 件事，如果已知第i个人做第j件事的总成本为cij（i,j=1,2,n），需要指定人和事之间一一对应的指派方案，使做这n件事的总成本最小。设有n2个0-1变量，xij=1,若指派第i个人做第j件事0,若不指派第i个人做第j件事(i,j=1,2,n)数学模型为minS=i=1mj=1ncijxij（1）j=1nxij=ai,i=1,m（2）i=1mxij=bj,j=1,n（3）xij=0或1,i,j=1,2,n（4）2 2.2 2航班恢复最小延误成本模型航班恢复最小延误成本模型将不正常航班损失分为三种：航班取消成本、航班延误成本、飞机置换成本。其中成本指标包括：（1）飞机折旧费：飞机起飞前在地面等待时存在折旧费用，即aiBfi。ai为一小时飞机的折旧费；Bfi为当飞机i执行航班f时停场时间。（2）飞机停场费用：根据民航局规定，飞机停场 2 h 以内免收停场费用；超过 2 h，每停场24 h按照起降费的 15%计收。不足 24 h按 24 h计收。当 0Bfi2 时，bi=0。当Bfi2 时，bi=Bfi/24 pi 15%，bi为飞机停场费用，pi为起降费用，如表1所示，Gi为飞机i的最大起飞重量。表 1起降费用机场类别一类1级一类2级二类三类025 t240250250270起降费用2650 t65070070080051100 t1100+22（Gi-50）1100+23（Gi-50）1150+24（Gi-50）1300+24（Gi-50）101200 t2200+25（Gi-100）2250+25（Gi-100）2350+26（Gi-100）2500+26（Gi-100）201 t以上5000+32（Gi-200）5050+32（Gi-200）5100+33（Gi-200）5150+33（Gi-200）（3）旅客赔偿民航局规定：延误时间48 h，赔偿标准不低于200元；延误时间大于8 h，赔偿不低400元。（4）航班取消成本航班取消成本按照该航班延误大于 8 h 计算。基于指派模型，又建立了航班恢复目标函数如下：min Z=i Af FaiBfi+bi+efi(pf1+pf2)xfi+i Af Fbiyfi+f Fpfzf约束条件如下：i Axfi+i Ayfi+zf=1（5）f Fxfi 1（6）43现代计算机2022年f Fyfi 1（7）pf1i Axfivi（8）pf2i Ayfiwi（9）sai=sdi（10）xfi0,1yfi0,1zf0,1（11）注释：飞机 i执行航班 f时，令xfi=1，否则为0。飞机i执行航班f需置换时，令yfi=1，否则为0。航班f需要取消时，令zf=1，否则为0。efi代表飞机i执行航班f时的旅客赔偿费。pf为航班取消成本。pf1和pf2分别表示航班f上的经济舱和商务舱旅客订座数。qf1和qf2分别表示航班f上经济舱和商务舱的机票价格。vi,wi表示飞机i上经济舱和商务舱座位数。sai表示飞机 i执行的前序航班的到达机场；sdi表示飞机i执行的后序航班的出发机场。2 2.3 3改进的匈牙利算法改进的匈牙利算法（1）确定飞机的到达和起飞机场，筛选出从该机场起飞的航班与飞机进行匹配，判断是否满足模型约束，直至所有航班满足条件。（2）重新搜集飞机的到达和起飞机场。（3）采集航班延误旅客人数、飞机折旧费、飞机停场费、起降费、旅客赔偿费相关成本数据等。（4）计算所有航班串的调整成本，建立目标函数。（5）根据约束条件，将成本矩阵输入Matlab软件编程求解模型并绘制时空网络图。（6）得到新航班调整策略与各航班串延误成本，直至结果满足实际要求。3算例分析表2是成都某航空公司一天内成都、北京、杭州三个机场的航班计划，共包括14个航班、6架飞机、3个机场。因天气条件低于机场最低飞行标准，管理部门决定在当天的6：009：00关闭成都机场，在此时段内机场不允许任何航空器起降，而此时段前的所有航班都可以正常起飞降落，此时段后机场立即允许飞机正常起飞降落。航班f8因大雾低能见度，航班备降后机组超时而取消。根据动态规划算法，构造航班成本矩阵，计算出每个可行航班的成本，通过Matlab软件计算得到航班调整方案，为了避免太多无效航班串致使Matlab求解速度太慢，规定前序航班与紧后航班之间不得超过8 h，所有航班间隔8 h以上的匹配均无效。将各机场成本矩阵输入Matlab进行编程来求得使各个机场成本最小的最优解矩阵，最后将三个机场的最优解矩阵进行整合，得出新航班调整计划的航班串，并根据飞机起飞和到达机场、执行航班飞机的起飞表 2原航班恢复计划表航班号f1f2f3f4f5f6f7f8f9f10f11f12f13f14机型A321A320A321A320A321A321A320A321A321A320A319A321A320A319机号67181821690684706718690684702371671818216433671818216433起飞站成都北京成都成都北京杭州北京成都成都成都成都杭州北京北京计飞6：056：257：007：3010：1510：4511：2511：3014：4016：1016：3018：4519：5020：30实飞9：006：459：059：1013：1012：4513：0017：3016：2016：3221：4019：5420：33计达8：508：509：4010：0513：2513：5514：3514：1017：2018：5019：1522：0023：1523：45实达11：139：1011：1511：2616：2015：5016：0219：3918：1718：300：35：0022：4723：19到达站北京成都杭州北京成都成都成都北京杭州北京北京成都成都成都 44罗军等：基于延误成本的不正常航班调整策略研究第24期机场来整合出已有的各架飞机所执行的新航班。Matlab求解得到成都机场、北京机场和杭州机场的最优解矩阵依次见图2、见图3和图4。图 2成都机场最优解矩阵图 3北京机场最优解矩阵图 4杭州机场最优解矩阵根据成都、北京、杭州机场的最优解矩阵，得到新的航班恢复计划表，见表3。利用时空网络图对新航班计划表进行描述，绘制出调整之后的各航班串，见图5。图 5恢复后航班时空网络图表 3新航班恢复计划表航班号f1f2f3f4f5f6f7f8f9f10f11f12f13f14机型A321A320A321A320A320A321A321A321A320A321A319A320A319A321机号67181821690684708470690667186906182169066433182164336906起飞站成都北京成都成都北京杭州北京成都成都成都成都杭州北京北京计飞6：056：257：007：3010：1510：4511：2511：3014：4016：1016：3018：4519：5020：30实飞9：006：459：059：1013：1012：4513：000：5017：3016：2016：3221：4019：5420：33计达8：508：509：4010：0513：2513：5514：3514：1017：2018：5019：1522：0023：1523：45实达11：139：1011：1511：2616：2015：5016：0203：2019：3918：1718：300：3522：4723：19到达站北京成都杭州北京成都成都成都北京杭州北京北京成都成都成都 45现代计算机2022年实验结果分析：原航班恢复计划表表1中，航班串为f1f5f9f12，恢复成本10.11万元，f2f10f13恢复成本20.14万元，f3f6恢复成本 3.05，f4f7 恢复成本 3.5，f8 航班取消，成本58万元，f11f14恢复成本4.1万元，总最小成本目标函数值为95.4万元。新航班恢复计划表表2中，航班串为f1f7，恢复成本3.7万元，f2f9f12，恢 复 成 本 18.18 万 元，f3f6f10f14f8，恢复成本32.63万元，f4f5，恢复成本3.8万元，f11f13，恢复成本2.3万元，总最小成本目标函数值为60.61万元。可见新航班恢复计划成本比原航班恢复计划成本降低36.5%。4结语本文通过充分考虑航班恢复的实际背景，从不正常航班延误成本最小化的 角度出发，将可用航班的