本文选自中国工程院院刊《Enginring》年第4期
作者：苏艺，谢可欣，王洪建，梁哲，WanprachaArtChaovalitwongs，PanosM.Pardalos
来源：AirlinDisruptionManagmnt:ARviwofModlsandSolutionMthods[J].Enginring,,7(4):-.
编者按
随着经济社会的快速发展，乘坐飞机出行成为越来越多的人们的日常选择。由于各种不可预测因素的存在，航空公司航班经常会出现延误或取消的情况，一旦无法及时实现航班恢复，乘客的出行受到影响，航空公司的经济和社会效益也面临诸多损失。不正常航班管理因此是航空公司运营管理的一大痛点。当不正常航班产生时，需采用何种方法来调整资源（包括航班时刻、飞机和机组等）的分配并重新安排旅客以实现航班计划的恢复呢？
中国工程院院刊《Enginring》年第4期刊发同济大学梁哲教授研究团队的《航空公司不正常航班管理——模型和解决方法综述》一文。文章介绍了不正常航班发生的可能场景和一系列常见的恢复手段，回顾了飞机路径恢复、机组恢复和多资源整合恢复的基本模型和相关扩展研究，旨在为航空公司实际运行中不同的恢复场景提供合适的模型和方法。具体来看，在飞机路径恢复问题方面，回顾了通用的弧模型和路径模型，并讨论了这些模型的适用场景；在机组恢复问题方面，介绍了与飞行员级别、航班延误相关的基础模型和扩展模型；在多资源整合恢复问题方面，介绍了连接不同资源的关键约束和相关算法。此外，文章还对相关课题的未来研究方向提出了建议。
图片来自网络
一、引言
航空业已经成为全球经济的重要组成部分之一。随着人们逐渐依赖飞机出行，全球的航班数量逐年增多。根据国际航空运输协会（IATA）的报告，年全球民航旅客需求增长了4.2%，而民航运力仅增长了3.4%，需求增长幅度超过了运力增长幅度，这表明航空市场仍具有很大的发展潜力。随着航空业的发展，航空公司的计划与调度问题日趋受到重视，很多航空公司都采用先进的数学优化方法来解决这些问题并从中获益。Eltoukhy等和Zhou等总结了不同航空规划问题的模型及有效的解决方案。
在各种不正常情况下，航班往往无法按计划运行。美国运输统计局（BTS）提供的数据显示，年美国约有21%的航班经历了超过15min的起飞延误。同样地，根据中国民用航空局（CAAC）《年民航业发展统计公报》，国内平均航班准点率也仅有81.43%。官方航空指南公司（OfficialAviationGuid,OAG）的有关航班准点率的报告显示，全球只有三家航空公司的准点率超过90%。航空公司航班的延误率和取消率无时无刻不在影响着旅客对航班的选择，无法及时实现航班恢复将严重损害航空公司的经济和社会效益。因此，不正常航班管理成为了航空公司运营管理的一大痛点。
航班计划和航班恢复之间有许多差异。航班计划着重于得到最优方案，而航班恢复的目标是尽快获得一系列可行且较佳（不一定最优）的解决方案。此外，根据航班不正常情况的严重程度和类型，航班恢复相较于航班计划具有更多不确定性。航班计划可以在航班正式运行前花几个月的时间来制定，但是航班恢复需要在不正常航班产生后尽快生成并实施。在本文中，我们着眼于航班恢复问题的特征，回顾了常见的模型和方法，同时在模型基础上进一步展示了不同恢复方法的特点和使用效果。航空公司可据此选择合适的恢复方法来满足不同的恢复需求。
本文接下来的内容组织如下：第2节对不正常航班管理进行了简单的介绍，包括不正常航班可能出现的原因和可用的恢复手段。第3节提供了飞机路径恢复问题的基本模型和求解方法。第4节介绍了机组恢复问题的通用模型并进行相关扩展。第5节介绍了考虑多资源的航班恢复问题。第6节对我们的工作进行了总结，并描述了未来的研究方向。
二、不正常航班管理
已有研究对不正常航班恢复的多种方法进行了总结。Clark回顾了航空公司运营控制中心在航班恢复期间的做法。Filar等研究了机场对不正常航班的处理方法。Kohl等详细论述了不正常航班管理的诸多方面，并报道了有关航空公司不正常航班管理的大规模研究。Clausn等归纳了多种航空恢复方法，并介绍了多种航班计划阶段的模型。Blobaba等在他们专著的第9章中介绍了航班恢复模型和具有鲁棒性的航班计划模型。Barnhart和Smit描述了不同资源恢复的基本模型和航空公司不正常航班的管理工具（见其专著的第6.3章）。Floudas和Pardalos也提到了航班恢复问题的数学模型及一些改进方法和相关算法。
接下来，我们将首先简要介绍导致不正常航班出现的原因及其对航空公司航班网络的下行影响。之后，我们将描述常见的航空公司的恢复手段。
（一）不正常航班出现的原因
导致不正常航班出现的原因有两类：
（1）航空公司资源（如飞机、机组）未到位。这类不正常航班出现的原因主要包括由机器故障或燃油短缺导致的计划外的飞机维修任务，以及由生病或其他紧急事务导致的机组的缺席等。
（2）外部环境影响（如天气、空中交通管制）。空中交通方式往往对天气变化十分敏感，即使是很轻微的天气变化也可能会造成航班延误，从而降低机场航班的起飞率和到达率。在恶劣的天气下，机场将会实施机场关闭、空中交通管制等强制措施，以确保旅客的人身安全和航空公司的资产安全。
航空公司通常会为每架飞机和每个机组安排满足一定衔接规则的一组连续航班任务。因此，若前序航班无法按计划起飞，将会影响后续航班，从而产生下行影响。图1展示了包含两架飞机和4个航班的航线时空网络图。在本文中，将飞机最小中转时间设置为30min，机组最小中转时间设置为45min。
图1包含4个航班（指派了两架飞机和两个机组）的网络下行影响的图示。机组1被分配给航班1和航班4，机组2被分配给航班2和航班3
假设机场A在07:00~08:30由于雷阵雨而被关闭，由于航班1在8:30前无法起飞，导致飞机2和机组1来不及中转（图2），从而使航班2和航班4受到影响。
图2当航班1不能准时起飞时对网络下行影响的图示。延误的航班1用航班1′表示。由于分配给航班1的机组1和飞机2晚点，航班4和航班2受到影响
此外，在航班恢复期间还应考虑机场和空域的容量。机场和空域需要容纳不同航空公司的飞机，且在不同时间段可提供的资源（如登机口、跑道等）数量有限。总的来说，由于各航空公司在第三方资源上的竞争，即使是很小的意外也会造成难以估量的损失。因此，及时采用不同的恢复手段来预防或减轻下行影响是非常重要的。
（二）恢复手段
此处将结合第2.1节中的例子来解释说明航班恢复的各种手段。
（1）航班延误。主动延误受到直接或间接影响的航班。如图3所示，为了让执行完航班1的飞机和机组有足够的时间在机场B中转以执飞航班2和航班4，将这两个航班的起飞时间主动延后15min。
图3主动延误航班2和航班4以减少总延误的图示
（2）航班取消。在恢复期内，如果资源始终无法到位或者可起飞时间远远超过最晚起飞时间，那么该航班就不得不被取消。鉴于航班取消所需的高昂的成本，航空公司通常不考虑这一恢复措施。
（3）资源交换。当某航班的资源无法及时到位时，同起飞机场的可用飞机或机组可以代为执飞这个航班。原所需资源在就位后也可以被安排给其他航班。例如，如图4所示，已经在机场B的飞机1被指派去执行航班2，使得航班2能够按原计划起飞。
图4交换飞机1和飞机2以减少延误的图示
（4）备用资源（飞机和机组）的使用。机场会配备一定的备用资源，且这些资源不会被提前安排任何航班任务，以便在恢复期间随时调用。
（5）置位和调机。置位指的是机组以旅客的身份被运送到另一个机场去执行任务。调机指的是指派飞机去执飞没有旅客的非计划内航班以到达指定机场。由于成本较高，航空公司很少使用调机这种恢复方式。
（6）飞机巡航速度控制。最近，很多研究将控制飞机巡航速度作为一种航班恢复手段。这种恢复手段通过调整航班飞行时间来降低意外情况造成的影响。
（7）旅客重分配。如果计划的行程受到影响，航空公司将会给旅客重新安排具有相同出发地和目的地的行程。
根据航空公司的偏好和能力，多种恢复措施可以被同步调用。考虑到问题的复杂性，航班恢复问题通常被拆分为一系列需按特定顺序解决的子问题。通常情况下，航空公司首先解决飞机路径恢复问题，其次解决机组恢复和旅客恢复问题。在接下来的三个章节中，我们将依次介绍飞机路径恢复、机组恢复、考虑旅客的多资源恢复模型以及相关算法。
三、飞机路径恢复
在不正常航班发生时，机组的恢复和旅客的重新安置都取决于飞机路径的安排。因此，合理高效的飞机路径恢复方案对于不正常航班的恢复至关重要。与飞机路径计划问题相比，飞机路径恢复问题影响的时间相对较短（几个小时到几日不等）。
飞机路径恢复问题旨在以最少的成本重新安排受不正常航班影响的飞机路径，同时确保恢复期之外的航班不受影响。此外，在恢复期结束时，飞机应到达指定航站，以执行后续的飞行计划。
飞机路径恢复问题通常被建模为一个网络问题，与其他路径问题相似，飞机路径恢复问题所采用的模型通常是基于弧或基于路径的，以下各小节将详细介绍这些模型。
（一）飞机路径恢复——弧模型（arc-basdmodl）
弧模型可以解决由于恶劣天气、安保问题、军事行动或其他因素造成的不正常航班情况（如机场关闭、空中交通管制等），此模型建立在由Han等所提出的时空网络上。时空网络是机型分配问题中常见的网络建模形式，该网络共有三种类型的节点和三种类型的弧，如图5所示。
图5飞机路径恢复流量控制场景举例
1.节点
第一类节点为供应节点（supplynod），供应节点是每个航站恢复期开始的第一个节点；
第二类节点为需求节点（dmandnod），需求节点是每个航站的最后一个节点，表示恢复期的结束。模型要求在恢复期结束的需求节点，有指定机型及数量的飞机，以便执行后续航班计划；
第三类节点为中间节点（intrmdiatnod），此类节点包含了飞机起飞事件或到达事件的时间和空间信息。
2.弧
第一类弧为航班弧（flightarc），代表了一个具有预计起飞（到达）时间与航站信息的航班；
第二类弧为飞机在航站停留的地面弧（groundarc），地面弧的数值为停留在地面的飞机数量；
第三类弧为复制航班弧（copidflightarc），表示原始航班弧的延误时间（如10min、30min或60min），复制航班弧与原始航班弧的起飞（到达）航站相同，但前者的起飞（到达）时间为后者起飞（到达）时间加上延误时间。
下文所列模型为文献总结的通用的弧模型，该模型建立在如图5所示的时空网络上，是由Thngvall等最先提出。
假设飞机路径恢复问题中的机组模型只有一种，即单机型问题，则通用的数学模型如下所述。
模型1：飞机路径恢复的基础弧模型
式中，F为航班集合；Fn+和Fn–表示进入/离开节点n的航班弧集合；N为中间节点集合；B为供应节点集合；E为需求节点集合；Fs是流量控制时段s中所涉及航班的集合（若流量控制时段s控制的是起飞流量，则Fs仅包含该时段内的起飞航班；如果流量控制时段s同时限制了起飞和降落的流量，则Fs包含时段s内的所有航班）；S表示可能由天气情况、安保需要、军事行动等任何因素引起的流量控制时段集合；I(f)是一个包含了原始航班弧f和相应复制航班弧的弧集合，而I(F)=∪fI(f)表表示所有可选航班弧的集合；参数是航班f的第t个复制航班弧的分配成本，该分配成本包含了延误成本（其中，当复制弧不表示原始航班弧时，即t0时，包含延误成本）；是航班f的取消成本；As指流量控制时段s允许通过的航班数量；Numb表示在供应节点b可用的飞机数量；Num表示需求节点要求的飞机数量；决策变量表示航班f是否选择第t个复制航班弧，若选择则值为1，否则为0；变量yn+表示节点n之后地面上的飞机数量；变量yn–表示节点n之前地面上的飞机数量；yb+表示节点b之后地面上的飞机数量；决策变量zf表示航班f是否被取消，被取消则为1，否则为0。
式（1）中的目标函数旨在最小化总分配成本、延误成本和航班取消成本；式（2）~（4）确保了飞机流量平衡，其中式（3）和式（4）表示飞机用于执行恢复期内的一系列航班并在恢复期结束时到达对应的需求节点；式（5）为航班覆盖约束，确保每个航班要么被取消，要么根据计划起飞时间或延误起飞时间执行；式（6）确保了起飞/到达航班数量受该时段的流量限制。
图5具体描述了流量控制时段流量减少的情况。如图所示，机场B在08:30~10:30进行流量控制，其中起飞航班流量从3个减少到2个，该流量控制时段内涉及航班弧1~4。复制航班弧5和6被设置在流量控制时段以外，表示流量控制导致的航班延误。
在飓风或台风等恶劣天气条件下，应将飞机移入机库，同时使用地锁固定，或将其转移至不受台风影响的机场，以确保飞机安全。此时，地面上的飞机数量受机库容量或地锁的数量约束，如式（10）所示。
式中，G是一组具有容量限制的地面弧；Ag是限制的数量；Ng表示有容量限制的地面弧g的前一节点集合，即节点g之后为有容量限制的地面弧。
可以将流量控制用于特定机场或其他需要控制的航班集合，即式（10）中涉及的航班集合可以扩展到任意出于管理目的需要限制流量的航班集。
Thngvall等将单机型问题拓展至多机型问题，机型之间的区别包括座位数、最大飞行距离以及机组资质要求等。在多机型问题中，机型之间更换飞机的决策比同一机型内更换飞机的决策的条件更为严苛。因为如果更换后的飞机座位数低于营销部门已销售的座位数量，会为航空公司带来巨大的利润损失。此外，根据机型更换决策安排合适的机组资源也是多机型决策的一大问题。
对于多机型问题建模，Thngvall等对每个子机型建立一个时空网络，组成一组平行时空网络。在单机型问题里，一个航班只能由已分配子机型的飞机执行，而在多机型问题中，可以执行某个航班的子机型有多个。如图6所示，子机型2可以执行最初安排给子机型1的航班，因此，航班2和航班3也存在于子机型2的网络。Thngvall使用IBMCPLEX求解器对模型直接求解，对于包含1~6个子机型的12个机型、个航班、24h恢复期、10h机场关闭情况的算例，模型在.4s后获得一个近似最优解。在这个求解方案中，共有81个航班更换了原始分配机型，这表明允许交换机型的恢复方案更加灵活，能够有效提高恢复方案的质量。
图6多机组模型的时空网络举例
模型1中的时空网络没有对具体飞机进行区分，导致无法直接从解中获得具体飞机路径。因此，模型1无法应对具体飞机不正常的情况（如某架飞机需要进行计划外维护）。为了解决这一问题，Vink等提出了包含具体飞机的拓展模型。他们在模型中构建了一组平行网络，其中每一个网络代表一架具体的飞机，这些网络通过航班覆盖约束关联。在模型1中，给每个变量增加索引，用于包含飞机的具体信息。
构建每架飞机的网络并求解相应的混合整数规划模型非常耗时，为了提高恢复算法的实时性，Vink等根据Vos等的建议研发了一种选择算法（slctionalgorithm）。该算法包含三个阶段，每个阶段仅选择指定数量的飞机，若根据所选飞机集合没有找到合适的解决方案，则该所选飞机集合被扩充并转入下一阶段，直到找到解决方案。采用选择算法求解一个包含架飞机、每天个航班、恢复期为16h的算例平均耗时22s，而在相同算例下，使用所有飞机的整数线性规划平均耗时10min。在Vink所测试的10个算例里，利用选择算法找到全局最优解的有7个。平均而言，选择算法的解与全局最优解之间的差距为6%。
（二）飞机路径恢复——路径模型（path-basdmodl）
飞机的不正常情况也可以使用路径模型解决，与弧模型相比，路径模型将飞机分配给已包含航班延误、飞机交换等具体恢复措施的路径。Argüllo等、Rosnbrgr等、Eggnbrg等、Wu等和Liang等的研究都基于路径模型建模。路径模型除了可以实现弧模型中所考虑的机场关闭和空中交通管制等情况，还能处理飞机计划外维修等问题。路径模型在路径生成时进行可行性检查（即保证最小中转时间），并在路径生成的过程中实现部分约束和规则，从而避免将复杂约束放入模型中。基于路径的模型描述如下。
模型2：飞机路径恢复的路径模型
式中，A表示飞机集合；Ra表示可分配给飞机a的路径集合；表示将飞机a分配给路径r的成本；参数表示路径r是否包含航班f，如包含则为1，否则为0；决策变量表示飞机a是否分配给路径r，如分配则为1，否则为0。
式（11）中的目标函数旨在最小化分配成本和航班取消成本；式（12）限制每架飞机最终执行的路径有且仅有一条，且路径r的起点和终点对应于恢复期开始和结束时飞机所在的航站；式（13）为覆盖约束，表示每个航班至多能够被一架飞机执行，若没有可用飞机，该航班将被取消。
表1对比了弧模型与路径模型的特征。与弧模型相比，路径模型约束较少，但可行路径（变量）较多。此外，由于航班取消和航班延误是不正常航班恢复中常见的控制手段，本文将对这两种控制决策做进一步分析。在弧模型和路径模型中，航班取消决策由决策变量取值决定；然而，航班延误决策有多种建模形式，具体内容将在第3.3节中讨论。
表1弧模型与路径模型特征对比
A
:numbroflmntsinthstofaircraft;
F
:numbroflmntsinthstofflights;
I(F)
:numbroflmntsinthstofallthpossiblflights;O:spac