基于延误成本的不正常航班调整策略研究

罗 军，江林林

（中国民用航空飞行学院空中交通管理学院，广汉 618307）

0 引言

在当代人的远距离旅行中，航空出行扮演着举足轻重的地位，日益增长的飞机数量造成航班正常率的不断降低。天气条件、机场保障等问题都是导致飞机延误或取消的主要原因，给出行者造成了不便利的同时，航空公司和机场也承担着经济损失。但是由于航空的飞行安排已经非常严密，一旦某飞机受到影响，延误会在航班串上产生多米诺效应，导致大量飞机晚点。及时合理地恢复延误航班，确保恢复成本尽可能小，不能仅靠调度员，而采用最优化算法则可以迅速达到目标，在减少成本的同时还能将签派员的工作效率提高，为后续飞机排班提供依据。

针对航班恢复问题，国内外已研究多年，也取得了相应的成果，赖俊晓［1］基于我国机队规模小，将限制信息融入资源指派模型，构建了最小成本的航班恢复模型。为了提高航空公司效益，创造性地将改进的贪婪随机自适应搜索算法运用于航班恢复模型中。戴福青等［2］将机会成本应用于航班恢复中，通过动态规划算法将延误航班损失降为原来的44%，证明了动态规划算法在解决航班恢复问题时的可行性。李琳丹等［3］在非正常航班成本分析与优化方面，使用了三天内可用及新开航班结合的方法实施延误航班恢复，利用LINGO 对延误信息计算来减少恢复时间。姚韵［4］提出基于机号路径置换算法，且用匈牙利法进行边界约束求解。白凤等［5］在航线不足和空港封闭而导致客机非正常飞行的情形下，通过列生成算法来求解构建的多商品网络流模型。田倩南等［6］基于占优准则减少被恢复航线组合量，利用CPLEX 实现减小成本，提出了改进的时空网络法。Teodorović等［7］结合机组及飞机路线恢复，使用字典序优化技术及分层优化技术，对新的机组进行排班重算。Vos 等［8］提出了一种新的动态建模框架，该框架可以针对飞机短缺问题解决已中断的飞机时间表。Sinclair 等［9］在2016 年整合了航班和乘客恢复问题，通过混合规划整数模型，并运用列生成算法来求解该模型。Petersen 等［10］将飞行计划和线路、旅客等因素同时考虑，运用列生成法与Benders 分解来求模型，最后得出航班调整的具体计划。

1 不正常航班问题描述

当航空公司原因或机场因为某些突发情况封闭，飞机原计划飞行不能实施，这时要尽快调整航空公司飞行计划，安排新飞行计划。在航班计划调整方面有三种调整策略，即飞机置换、航班延误、取消航班［11］。由此可知，可以同时存在飞机的延误成本和置换成本。

飞机置换是取消原执行该航班的飞机，将原不正常航班安排给其他飞机去执行，如图1所示。

图1 飞机置换图

2 模型的建立

2.1 指派模型

航班恢复问题是在短时间内调整航班计划而使延误的成本最小化。所以，这类问题可看作指派问题。指派问题概念如下：

指派问题的简单定义是：有n个人做n件事，如果已知第i个人做第j件事的总成本为cij（i,j=1,2,…,n），需要指定人和事之间一一对应的指派方案，使做这n件事的总成本最小。

设有n2个0-1变量，

数学模型为

2.2 航班恢复最小延误成本模型

将不正常航班损失分为三种：航班取消成本、航班延误成本、飞机置换成本。其中成本指标包括：

（1）飞机折旧费：飞机起飞前在地面等待时存在折旧费用，即ai。ai为一小时飞机的折旧费；为当飞机i执行航班f时停场时间。

（2）飞机停场费用：根据民航局规定，飞机停场2 h 以内免收停场费用；超过2 h，每停场24 h 按照起降费的15%计收。不足24 h 按24 h计收。当0≤≤2 时，bi=0。当＞2 时，bi=[/24]×pi× 15%，bi为飞机停场费用，pi为起降费用，如表1 所示，Gi为飞机i的最大起飞重量。

表1 起降费用

（3）旅客赔偿

民航局规定：延误时间4～8 h，赔偿标准不低于200元；延误时间大于8 h，赔偿不低400元。

（4）航班取消成本

航班取消成本按照该航班延误大于8 h 计算。

基于指派模型，又建立了航班恢复目标函数如下：

约束条件如下：

注释：飞机i执行航班f时，令=1，否则为0。飞机i执行航班f需置换时，令=1，否则为0。航班f需要取消时，令zf=1，否则为0。代表飞机i执行航班f时的旅客赔偿费。pf为航班取消成本。pf1和pf2分别表示航班f上的经济舱和商务舱旅客订座数。qf1和qf2分别表示航班f上经济舱和商务舱的机票价格。vi,wi表示飞机i上经济舱和商务舱座位数。表示飞机i执行的前序航班的到达机场；表示飞机i执行的后序航班的出发机场。

2.3 改进的匈牙利算法

（1）确定飞机的到达和起飞机场，筛选出从该机场起飞的航班与飞机进行匹配，判断是否满足模型约束，直至所有航班满足条件。

（2）重新搜集飞机的到达和起飞机场。

（3）采集航班延误旅客人数、飞机折旧费、飞机停场费、起降费、旅客赔偿费相关成本数据等。

（4）计算所有航班串的调整成本，建立目标函数。

（5）根据约束条件，将成本矩阵输入Matlab软件编程求解模型并绘制时空网络图。

（6）得到新航班调整策略与各航班串延误成本，直至结果满足实际要求。

3 算例分析

表2 是成都某航空公司一天内成都、北京、杭州三个机场的航班计划，共包括14个航班、6架飞机、3个机场。因天气条件低于机场最低飞行标准，管理部门决定在当天的6：00—9：00关闭成都机场，在此时段内机场不允许任何航空器起降，而此时段前的所有航班都可以正常起飞降落，此时段后机场立即允许飞机正常起飞降落。航班f8 因大雾低能见度，航班备降后机组超时而取消。

表2 原航班恢复计划表

根据动态规划算法，构造航班成本矩阵，计算出每个可行航班的成本，通过Matlab 软件计算得到航班调整方案，为了避免太多无效航班串致使Matlab 求解速度太慢，规定前序航班与紧后航班之间不得超过8 h，所有航班间隔8 h以上的匹配均无效。将各机场成本矩阵输入Matlab 进行编程来求得使各个机场成本最小的最优解矩阵，最后将三个机场的最优解矩阵进行整合，得出新航班调整计划的航班串，并根据飞机起飞和到达机场、执行航班飞机的起飞机场来整合出已有的各架飞机所执行的新航班。Matlab 求解得到成都机场、北京机场和杭州机场的最优解矩阵依次见图2、见图3和图4。

图2 成都机场最优解矩阵

图3 北京机场最优解矩阵

图4 杭州机场最优解矩阵

根据成都、北京、杭州机场的最优解矩阵，得到新的航班恢复计划表，见表3。

表3 新航班恢复计划表

利用时空网络图对新航班计划表进行描述，绘制出调整之后的各航班串，见图5。实验结果分析：原航班恢复计划表表1 中，航班串为f1—f5—f9—f12，恢复成本10.11万元，f2—f10—f13恢复成本20.14万元，f3—f6恢复成本3.05，f4—f7 恢复成本3.5，f8 航班取消，成本58 万元，f11—f14 恢复成本4.1 万元，总最小成本目标函数值为95.4 万元。新航班恢复计划表表2 中，航班串为f1—f7，恢复成本3.7 万元，f2—f9—f12，恢 复 成 本18.18 万 元，f3—f6—f10—f14—f8，恢复成本32.63 万元，f4—f5，恢复成本3.8 万元，f11—f13，恢复成本2.3 万元，总最小成本目标函数值为60.61 万元。可见新航班恢复计划成本比原航班恢复计划成本降低36.5%。

图5 恢复后航班时空网络图

4 结语

本文通过充分考虑航班恢复的实际背景，从不正常航班延误成本最小化的角度出发，将可用航班的次序进行调整等方式，在指派模型的基础上建立使不正常航班调整的成本最小化的目标函数，运用Matlab 软件求解航班最优排班，尽可能使航空公司的经济损失降到最低。本文建立的成本最小化模型及算法适应面广，在短时间内能计算出使延误成本最低的航班调整计划，模型合理，算法较为准确，能提高签派员工作效率，具有一定的研究价值和发展潜力。本文存在一定的可改进空间，也是下一步需要继续研究的地方。比如：①航班调整方面仅考虑延误成本，未考虑到旅客满意度和公平性等问题。②没有将成本指标和非成本指标赋权结合考虑，须在实践中继续研究，充分考虑实际，将非成本指标建立模糊综合评价体系。③模型进行成本最小化求解时，是将三个机场分开，分别将每个机场同时作为前序航班的到达机场和后续航班的出发机场进行各最小调整成本求解，最后将三机场最小成本求和得到最小总成本，下一步可考虑直接求解所有机场的最小调整成本。