中小型航空公司多机型机组复原问题研究

乐美龙，张 旭

（上海海事大学科学研究院，上海 201306）

飞机机械故障、恶劣天气、航空管制、机组人员生病、机场宵禁和飞机维护等原因都可能造成航空公司的航班延误甚至取消。在实际运营中，一个突发事件的发生，如某架飞机、某个机组周转出现问题，或者由于某种原因机场封闭，都将会影响航班计划的实施甚至中断。因此航空公司需要采取相应的措施，使航班能够尽快恢复正常。笔者主要讨论机组复原的恢复措施。

CLARKE［1］为航空公司开发了一个实时决策支持系统，该系统涵盖了航空公司机组复原的模块，GANG［2］介绍了美国大陆航空公司开发的“机组恢复解决方案”。然而，我国航空公司机组复原仍停留在手工复原阶段，因此建立适合我国航空公司机组复原实际需要的模型和算法显得尤为重要。WEI等［3］为机组复原问题构建了多商品网络流模型，但该模型没有将加机组和调用后备机组的策略方案表示出来，并且对机组成本的计算方法过于笼统。GUO［4］则将机组复原问题视为集合分割问题，尽管将机组不执行原排班任务的惩罚值列入了目标函数，但还是没能清晰地描述机组复原的目标函数计算方法，同时模型求解时间较长，难以满足航空公司实时有效性的需求。MEDARD［5］使用基于航班网络的深度优先搜索算法以及基于任务周期的列生成算法来求解机组复原问题，测试结果表明，这两种算法都能较快地求解机组调配问题，且运行时间只有几分钟。CYNTHIA等［6］是机组复原问题较早的研究者，其描述了单个机组延误无法正常连接后续航班任务执行的问题，并给出了单机组复原问题的数学模型和解决方案。LETTOVSKY等［7］则在此基础上提出了一种使机组复原成本最小化的方法。詹晨旭等［8］利用原时刻表，综合考虑航班时间约束、飞机维护约束、机场容量约束和飞机容量约束，并结合航空公司运行实际，建立了适合中小型航空公司复原的飞机恢复模型。乐美龙等［9］在机组复原问题上结合了一种深度优先搜索的启发式算法，考虑了原来的时间表、时间地点约束以及排班规则，并调用Gurobi 4.6.1求解，但目标函数中由于未涉及乘客复原问题，机组免费乘机的复原方案的可用性不强，且在后续算例分析中也未能体现该项措施；在模型构建方面，未涉及到多机型的资源分配问题，且文献中没有考虑机场宵禁因素以及对可调用后备机组的容量限制。笔者则在这些方面进行了弥补与加强。

1 机组复原问题

1.1 问题描述

机组复原问题是指当发生了影响机组原始排班的突发状况以后，通过采取某种具体措施改变原始排班中一些航班的起飞与降落的时间，使得该突发状况产生的影响最小［10］。多机型机组复原问题通过将航班与机组进行配对得以实现。为此，笔者构建了航班与机型配对和机型与机组配对两个矩阵进行描述。

1.2 模型构建

（1）集合定义。K为机组集，k∈K；F为航班集，f，g∈F；A 为机型集，a∈A。

（2）参数定义。Cf，k为把航班f指派给机组k的费用；Rf为把航班f指派给后备机组的费用；df为航班f延迟1 min所花费的费用；OTf为航班f原来的起飞时间；UTf为航班f实际的起飞时间；UAf为航班f实际的到达时间；Tk为机组排班的时间限制；CFAf，a为航班f与机型a的配对系数；CACa，k为机型 a 与机组 k 的配对系数；bf，k为航班 f与机组k的配对系数；m为最大延迟时间；M为一个足够大的数；N为机场宵禁时间；vf为航班f的飞行时间；ek为后备机组的最大容量；w为连续两趟相继航班之间的最小中转时间；TSf为航班f的起飞机场；ASg为航班g的到达机场。

（3）变量定义。0－1协变量:

1.3 模型优化

模型中，以成本最小化为总的目标函数，即最小化机组原始排班成本、航班延迟成本以及调用后备机组排班成本最小化。在约束条件中，式（1）是对航班排班方式的约束，即对于任何一趟航班都需要安排一种排班方式［11］；式（2）是对航班与机组配对的定义，即通过分别对航班与机型的配对以及机型与机组的分配得以实现；式（3）是对多机型资源分配的限制；式（4）是对机组工作状态的约束，即任意机组都可以存在排班或者休息两种状态；式（5）是对航班实际起飞时间的约束，即对于任意航班实际起飞时间不得早于航空公司所规定的起飞时间；式（6）是对任意机组所执行的任意航班的实际到达时间的约束，即每一个机组排班下的每一趟航班的到达时间都不得超过航空公司所规定的机组排班时间；式（7）是对航班实际到达时间与实际起飞时间逻辑关系的定义，即任意航班的实际到达时间为该航班的实际起飞时间与飞行持续时间之和；式（8）是对航班延迟时间的约束，即任意航班的延迟时间都不得超过航空公司所规定的最大延迟时间；式（9）和式（12）是对同一机组连续两趟航班的中转时间约束，即确保同一机组任意两趟连续航班之间必须在航空公司所规定的最小中转时间之内；式（10）和式（11）是对同一机组连续两趟航班的地点约束，即确保同一机组任意两趟连续航班之间必须满足前一个航班的到达机场恰好是后一个航班的起飞机场；式（13）是机场宵禁约束，即需要在航班排班时间表中剔除超出机场宵禁时间的排班；式（14）是后备机组容量约束，即当航班发生中断后能够调用的后备机组数量不得超过航空公司所规定的最大后备机组供给量。

2 算例

2.1 算例介绍

笔者采用国内一家航空公司的实际数据来测试模型的有效性。该航空公司主要运营国内航班，数据中所采用的飞机机型有4种，分别为波音737－800、767－300、757－200和 CRJ－200，以SHA为中心机场。假设连续两趟相继航班之间的最小中转时间为40 min，航班最大延迟时间为2 h。表1所示的是8个机组的原始航班时间与原始排班费用，其中每个机组负责6趟航班，一共涉及10个机场，并以7:00为起始时间点对航班的起飞时间与到达时间进行数据预处理。

表1 航班运作时间和原始排班费用

原始机组排班费用总计为74191.25美元。

模型中费用分为3个部分:机组原始排班费用和、调用后备机组费用和航班延迟费用。费用和系数如表2所示。

表2 费用和系数

2.2 算例分析

2.2.1 测试场景1

受大范围冰雪天气影响，航班FM9533到达中心机场SHA的时间延误为13:40，航班FM9354到达长春机场CGO的时间延误为16:00，航班FM9350到达厦门机场XMN的时间延误为19:30。上述航班到达时间的延误，对其后续航班FM9353和FM9349造成影响。优化结果如表3所示。

表3 测试场景1的优化结果

经过 CPLEX优化后，复原后的费用为101223.8美元。如果不采取相应的优化措施，由于连续两趟航班之间的最小中转时间为40 min，则FM9354相应地延误1.55 h，FM9353相应地延误2.50 h，FM9349相应地延误35 min。已知机组原始排班费用为74191.25美元，根据公式顺延费用=机组原始排班费用+额外延误费用，可得顺延费用为106191.3美元。因此，经优化后的复原成本可以降低4967.5美元。

2.2.2 测试场景2

受军事演习机场管制的影响，中心机场SHA于13:35～14:05之间不能起飞或者降落任何航班，因此航班 FM9354、FM9333、FM9257、FM94531和FM9348均受到了影响，其实际起飞时间都不得早于13:35。优化结果如表4所示。

表4 测试场景2优化结果

经过 CPLEX优化后，复原后的费用为115986.3美元。如果不采取相应的优化措施，则FM9354、FM9353 均延误65 min，FM9257、FM9258均延 误 45min，FM94531、FM94532 均 延 误105 min，FM9348、FM9347 均延误 25 min。由上述公式可得，顺延费用为122191.3美元。因此经优化后的复原成本可以降低6204.95美元。

3 结果分析

CPLEX在Intel（R）Core（TM）i3－2370 M CPU@2.40 GHz处理器、2.00 GB 内存和32 位操作系统的运行环境下的求解时间为8.82 s，通过有效地调用后备机组，使得航班在发生干扰后快速进行复原，不仅能够减少航班顺延的时间，而且能够为航空公司减少航班延误成本，将突发事件对航空公司正常运营的干扰降低至最小。

4 结论

笔者对多机型机组复原问题进行了深入的研究，创新点集中在以下几个方面:

（1）在多机型机组复原的问题上，通过构建航班与机型的配对矩阵、机型与机组的配对矩阵来实现航班与机组的配对；

（2）模型中对同一机组的相继航班所需满足的时间和地点作出了进一步的约束，确保了航班之间的连续。同时，模型考虑了机组的排班时间限制，并对机场进行了宵禁约束，限制了航空公司可提供的后备机组容量；

（3）模型能够较快地产生一个最优解，当实际航班发生干扰时能够较快地找到复原方案。

［1］CLARKE D M.Irregular airline operations:a review of the state of the practice in airline operations control centers［J］.Journal of Air Transport Management，1998（4）:67－76.

［2］GANG Y，ARGUELLO M.A new era for crew recovery at continental airlines［J］.Interfaces，2003，33（1）:5 －22.

［3］WEI G，GANG Y.Optimization model and algorithm for crew management during airline irregular operations［J］.Journal of Combinatorial Optimization，1997（1）:305－321.

［4］GUO Y F，LEENA S，MARKUS P T.Solving the airline crew recovery problem by a genetic algorithm with local improvement［J］.Operational Research，2005，5（2）:241－259.

［5］MEDARD S.Airline crew scheduling from planning to operations［J］.European Journal of Operational Research，2007，183（3）:1013 －1027.

［6］CYNTHIA B，ELLIS L J，GEORGE L N，et al.Branch and price:columngeneration for solving huge integer programs［J］.Operations Research，1998，46（3）:316－329.

［7］LETTOVSKY L，JOHNSON E L，NEMHAUSER G L.Airline crew recovery［J］.Transportation Science，2000，34（4）:337 －348.

［8］詹晨旭，乐美龙.非正常航班管理中的飞机恢复问题研究［J］.中国民航大学学报，2012，30（2）:45 －48.

［9］乐美龙，李贞.基于深度优先搜索算法的机组复原研究［J］.武汉理工大学学报，2012，34（9）:63 －68.

［10］NIKLAS K.Airline disruption management perspect，experience and outlook［J］.Journal of Air Transpose Management，2007，13（3）:149 －162.

［11］魏星，朱金福.航空公司一体化飞机排班研究［J］.武汉理工大学学报:信息与管理工程版，2013，35（1）:86－90.