基于航空公司损失的不正常航班恢复研究

戴福青，张舜尧

（中国民航大学空中交通管理学院，天津 300300）

不正常航班是指由于天气、流量控制、机务维修、旅客等因素导致航班计划无法正常执行。不正常航班不仅使航空公司遭受经济损失，还会打乱旅客出行安排，进而对航空公司产生负面影响。因此，在出现不正常航班时，尽快恢复航班计划是航空公司决策者的首要任务。航班计划的恢复分为3 个步骤：飞机计划恢复、机组恢复及旅客恢复。由于飞机是航空公司时间价值最高的资源，航班恢复时优先恢复飞机计划。以下探讨的是飞机计划的恢复。

国内外对于航班恢复的研究已有很多成果。赛秋玥等[1]构造了离散时空网络，采用可行路径生成算法对不正常航班生成飞机的可行路径。上官栋栋等[2]综合考虑航班延误、飞机置换和航班取消成本，建立了航班恢复模型，并用遗传算法求解。吴刚等[3]构建了多商品流网络模型，运用一种列生成算法求解模型。Teodorovic 等[4]采用分支定界方法求解了以总的旅客延误时间达到最小为目标函数的模型。唐小卫等[5]提出一种贪婪模拟退火算法，提高了贪婪算法的收敛性，降低了问题陷入局部最优解的概率。赵秀丽等[6-7]构建了以延误成本最小或延误时间最短为目标函数的模型，并提出了旅客失望溢出成本的概念，采用启发式方法并调用匈牙利法对模型求解，此外，还通过跟踪航班延误的前进方向，设计了一种逐延误指派算法，随着航班串被重新指派而动态生成飞机路径。万俊强等[8]在协同决策环境下对不正常航班恢复策略的可行性进行有效评估，采用可拓关联函数及可拓评价方法确定模型中的指标权重，并以定量结果来确定恢复策略的可行性。Argüello等[9]将贪婪随机自适应搜索（GRASP,greedy randomized adaptive search procedures）算法应用于求解飞机路径恢复问题。刘艳红等[10]分析了航班延误的恢复调度问题，提出了一种机场大面积航班延误恢复模型，并构造了基于免疫机制的免疫遗传算法来求解模型。

现有的研究成果较多，但仍存在以下问题：①在计算航空公司不正常航班损失时考虑因素过少，影响决策的合理性；②在航班恢复过程中没有优先考虑对时间敏感度更高、能为航空公司带来更大利润的商务舱旅客，可能会导致商务舱旅客因延误时间过长而流失，对航空公司造成巨大损失；③已有的算法无法形象地描绘航班恢复路径，且易出现陷入局部最优解的情况。因此，将航空公司不正常航班损失细分为6 种，在文献[6]提出的由于航班延误导致的旅客流失基础上，进一步划分了商务舱旅客和经济舱旅客的流失。将经济学中机会成本的概念应用于航班恢复中，使损失的计算更加精细化。最终建立了以航空公司经济损失最小为目标函数的航班恢复模型，并设计了一种动态决策算法进行求解。

1 不正常航班损失种类

将不正常航班损失分为以下6 种。

1）飞机折旧

由于执行航班的飞机在航班预计起飞前就已做好起飞准备，在地面等待时会产生折旧费用，即其中：ai为飞机i每分钟的折旧费用；为飞机i在地面等待执行航班f的停场时间（航班f的计划出发时间减飞机i的就绪时间）。

2）飞机停场费用

根据中国民用航空局（简称民航局）规定，飞机停场2 h 以内免收停场费用；超过2 h，每停场24 h 按照起降费的15%计收。不足24 h 按24 h 计收。飞机停场费用表示为

式中：pi为飞机起降费用；符号[]表示向上取整。根据机场类别的不同，飞机起飞重量不同，其起降费用也不同，如表1所示，其中Ti为飞机i的最大起飞重量。

表1 飞机起降费用Tab.1 Cost of aircraft takeoff and landing

3）机会成本

机会成本的定义[12]为：企业为从事某项经营活动而放弃另一项经营活动的机会，或利用一定资源获得某种收入时所放弃的另一种收入。假设某航空公司在某机场拥有1 架飞机i，其就绪时间为t，此时该机场有两个航班f1、f2待指派，预计起飞时间分别为t1、t2，t1＜t＜t2，若该航空公司决定将飞机指派给航班f2，由于航班起飞时间只能推后不能提前，该飞机需要在地面等待的时间为t2-t。而该时间内由于无法执行航班f1会造成经济损失。该损失即为航空公司为了执行航班f2放弃执行航班f1的机会成本。

在航班恢复问题中，重新定义机会成本为：飞机的就绪时间早于航班的预计起飞时间，在地面等待起飞的时间里不能执行其他飞行任务造成的潜在损失，即，其中g为可由航空公司单位飞行时间净利润。

在航班恢复问题中考虑机会成本的优势有：①更加精细化地进行成本管理；②当决策者对航班进行分配时，可避免出现飞机在地面等待时间过长的不合理指派；③使航班恢复模型更贴近实际，得出更好的优化结果。

4）旅客失望溢出成本

参见文献[6]中提出的旅客失望溢出成本概念，给出旅客失望溢出系数，即

旅客失望溢出成本

D=p×q×u

式中：p是该航班的旅客人数；q是该航班的平均票价。

该结论具有一定价值，但由于商务舱旅客和经济舱旅客对于时间的敏感度完全不同，而航空公司商务舱的销售收入又占据重要位置，因此，商务舱和经济舱的旅客失望溢出系数应取不同值。令经济舱的旅客失望溢出系数u1=u，商务舱的旅客失望溢出系数u2=w×u，其中w为商务舱旅客时间敏感系数，航空公司决策者可视实际情况给w赋值。

5）旅客赔偿

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

6）航班取消成本

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

2 航班恢复模型

模型以第1 节提到的6 种不正常航班损失之和最小为目标函数，同时考虑航班覆盖约束、飞机流平衡约束等约束条件。假定F为航班集合，航班f∈F；A为系统内可用飞机集合，飞机i∈A；S为机场集合，机场s∈S，建立航班恢复目标函数如下

约束条件如下

3 动态决策算法

动态决策算法相较于已有的一些算法有以下优点：①能够快速求解；②不易于陷入局部最优；③求解过程较直观。

航班恢复问题本质上就是将飞机动态地指派到符合约束条件的航班上，最后使得指派之后的航班计划成本最小，即所有飞机飞行路径的集合成本最小。因此，只需要确定所有飞机可能的飞行路径，并找出飞行路径总成本最小的方案即可。算法思路如下。

步骤1确定飞机的就绪时间及出发机场，搜索所有从该机场出发的航班，将飞机与航班进行匹配，判断是否满足模型中的式（4）和式（5），若满足，则引出1 条航班边，若不满足，则检查下个航班。直到完成所有匹配。

步骤2更新飞机的就绪时间及出发机场。就绪时间=前序航班的实际出发时间+飞行时间+过站时间，出发机场为前序航班的到达机场。

步骤3重复上述过程，直至飞机执飞的第n个航班的降落时间小于24：00，而第n+1 个航班的降落时间超过24：00。

步骤4利用步骤1、2、3 绘制飞机飞行路径图，如图1所示（方块代表飞机的到达机场及出发机场，方块之间的连线代表飞机能够执飞的航班）。

图1 可行飞行路径图Fig.1 Feasible flight path

步骤5由飞机所经机场的就绪时间及从该机场出发的可匹配航班的预计起飞时间计算飞机执行这些航班的成本。以所有飞机飞行路径总成本最小建立目标函数。

步骤6由飞行路径图写出约束条件。由于飞行路径图的绘制过程中已满足式（4）和式（5），同时通过飞行路径图可直观看到：①每架飞机在每轮指派时最多安排1 个航班任务，即在航班任务f1、f2、f3中最多执行1 个，包含式（3）；②飞机前序航班的到达机场为后续航班的出发机场，即想要执行航班f5，就必须先执行航班f1，包含式（6）。式（1）、式（2）和（7）可直接写出。

步骤7根据目标函数及约束条件编程求解模型。

随着航班量和机场数目的增加，飞机的可行路径数目会呈指数级上升，为了避免解空间过大导致求解速度达不到实际要求，规定飞机与航班之间衔接时间不得超过300 min，所有超过该时间的匹配均视为无效匹配。剪去无效匹配的航班边，重新构造所有飞机的飞行路径，将不确定的、动态指派问题转化为确定的、静态的指派问题，大大降低了求解难度。

4 算例分析

表2 是某航空公司一天内的部分航班计划，涉及10 个航班、5 架飞机、3 个机场。尾号为3982 的飞机由于机械故障当天无法执行航班任务，航班f7、f8被取消。已知B737 的折旧成本为100 元/min，最大起飞重量为78 t，A310 的折旧成本为130 元/min，最大起飞重量为138 t；商务舱旅客时间敏感系数取1.2；根据该航空公司年报计算可得机会成本为87 元/min。

表2 待恢复的航班计划表Tab.2 Flight schedule to be recovered

根据算法思路，以尾号3912 为例构建出飞机的可行飞行路径图，如图2所示。

图2 尾号3912 的飞机可行飞行路径图Fig.2 Feasible flight path diagram for aircraft with tail No.3912

图2 中：该飞机在上海机场的就绪时间为08：00，可执行的航班为f1，到达广州机场；在广州机场的就绪时间为11：00，可执行的航班有f2、f3、f5、f10，分别到达上海机场、北京机场、上海机场和上海机场，就绪时间分别为14：00，16：00，14：00，15：20。可行路径末尾的机场表示该飞机的过夜机场。

式中：xijk表示飞机i指派给第j个路径航班号为k的航班为1 时，否则为0；Cijk为飞机执飞航班的成本矩阵。由于篇幅所限，约束条件不再列出，优化结果如表3所示。

表3 恢复后的航班计划表Tab.3 Recovered flight schedule

恢复前目标函数值为254 560 元，恢复后目标函数值为112 420 元，仅为恢复前的44%，大幅降低了延误带来的损失。

5 结语

根据航班恢复问题的研究现状及目前研究成果的部分不足，提出了以下创新：①在航班恢复模型中将减少商务舱旅客的延误时间放在更重要的位置，避免因航班延误时间过长导致商务舱旅客流失；②将经济学中机会成本的概念应用于航班恢复模型中，避免了飞机在地面等待时间过长的情况；③基于构建飞机的可行路径设计了一种动态决策算法，该算法可将动态指派问题简化为静态指派问题，在合理地减小解空间之后可快速地求解问题，且不易陷入局部最优。通过给出一个航班不正常实例，建立了航空公司经济损失最小模型，并用动态指派算法求解该模型，结果表明，航班恢复后的经济损失仅为恢复前的44%，证明了模型及算法的可行性。