本文来自微信公众号：中国工程院院刊（ID：CAE-Engineering），作者：苏艺，谢可欣，王洪建，梁哲，头图来自：视觉中国
随着经济社会的快速发展，乘坐飞机出行成为越来越多的人们的日常选择。由于各种不可预测因素的存在，航空公司航班经常会出现延误或取消的情况，一旦无法及时实现航班恢复，乘客的出行受到影响，航空公司的经济和社会效益也面临诸多损失。不正常航班管理因此是航空公司运营管理的一大痛点。当不正常航班产生时，需采用何种方法来调整资源（包括航班时刻、飞机和机组等）的分配并重新安排旅客以实现航班计划的恢复呢？
中国工程院院刊《Engineering》2021年第4期刊发同济大学梁哲教授研究团队的《航空公司不正常航班管理——模型和解决方法综述》一文。文章介绍了不正常航班发生的可能场景和一系列常见的恢复手段，回顾了飞机路径恢复、机组恢复和多资源整合恢复的基本模型和相关扩展研究，旨在为航空公司实际运行中不同的恢复场景提供合适的模型和方法。
具体来看，在飞机路径恢复问题方面，回顾了通用的弧模型和路径模型，并讨论了这些模型的适用场景；在机组恢复问题方面，介绍了与飞行员级别、航班延误相关的基础模型和扩展模型；在多资源整合恢复问题方面，介绍了连接不同资源的关键约束和相关算法。此外，文章还对相关课题的未来研究方向提出了建议。
一、引言
航空业已经成为全球经济的重要组成部分之一。随着人们逐渐依赖飞机出行，全球的航班数量逐年增多。根据国际航空运输协会（IATA）的报告，2019年全球民航旅客需求增长了4.2%，而民航运力仅增长了 3.4%，需求增长幅度超过了运力增长幅度，这表明航空市场仍具有很大的发展潜力。随着航空业的发展，航空公司的计划与调度问题日趋受到重视，很多航空公司都采用先进的数学优化方法来解决这些问题并从中获益。Eltoukhy等和Zhou等总结了不同航空规划问题的模型及有效的解决方案。
在各种不正常情况下，航班往往无法按计划运行。美国运输统计局（BTS）提供的数据显示，2019年美国约有21%的航班经历了超过15 min的起飞延误。同样地，根据中国民用航空局（CAAC）《2019年民航业发展统计公报》，国内平均航班准点率也仅有81.43%。官方航空指南公司（Official Aviation Guide, OAG）的有关航班准点率的报告显示，全球只有三家航空公司的准点率超过90%。航空公司航班的延误率和取消率无时无刻不在影响着旅客对航班的选择，无法及时实现航班恢复将严重损害航空公司的经济和社会效益。因此，不正常航班管理成为了航空公司运营管理的一大痛点。
航班计划和航班恢复之间有许多差异。航班计划着重于得到最优方案，而航班恢复的目标是尽快获得一系列可行且较佳（不一定最优）的解决方案。此外，根据航班不正常情况的严重程度和类型，航班恢复相较于航班计划具有更多不确定性。航班计划可以在航班正式运行前花几个月的时间来制定，但是航班恢复需要在不正常航班产生后尽快生成并实施。在本文中，我们着眼于航班恢复问题的特征，回顾了常见的模型和方法，同时在模型基础上进一步展示了不同恢复方法的特点和使用效果。航空公司可据此选择合适的恢复方法来满足不同的恢复需求。
本文接下来的内容组织如下：第2节对不正常航班管理进行了简单的介绍，包括不正常航班可能出现的原因和可用的恢复手段。第3节提供了飞机路径恢复问题的基本模型和求解方法。第4节介绍了机组恢复问题的通用模型并进行相关扩展。第5节介绍了考虑多资源的航班恢复问题。第6节对我们的工作进行了总结，并描述了未来的研究方向。
二、不正常航班管理
已有研究对不正常航班恢复的多种方法进行了总结。Clarke回顾了航空公司运营控制中心在航班恢复期间的做法。Filar等研究了机场对不正常航班的处理方法。Kohl等详细论述了不正常航班管理的诸多方面，并报道了有关航空公司不正常航班管理的大规模研究。Clausen等归纳了多种航空恢复方法，并介绍了多种航班计划阶段的模型。Belobaba等在他们专著的第9章中介绍了航班恢复模型和具有鲁棒性的航班计划模型。Barnhart和Smit描述了不同资源恢复的基本模型和航空公司不正常航班的管理工具（见其专著的第6.3章）。Floudas和Pardalos也提到了航班恢复问题的数学模型及一些改进方法和相关算法。
接下来，我们将首先简要介绍导致不正常航班出现的原因及其对航空公司航班网络的下行影响。之后，我们将描述常见的航空公司的恢复手段。
（一）不正常航班出现的原因
导致不正常航班出现的原因有两类：
（1）航空公司资源（如飞机、机组）未到位。这类不正常航班出现的原因主要包括由机器故障或燃油短缺导致的计划外的飞机维修任务，以及由生病或其他紧急事务导致的机组的缺席等。
（2）外部环境影响（如天气、空中交通管制）。空中交通方式往往对天气变化十分敏感，即使是很轻微的天气变化也可能会造成航班延误，从而降低机场航班的起飞率和到达率。在恶劣的天气下，机场将会实施机场关闭、空中交通管制等强制措施，以确保旅客的人身安全和航空公司的资产安全。
航空公司通常会为每架飞机和每个机组安排满足一定衔接规则的一组连续航班任务。因此，若前序航班无法按计划起飞，将会影响后续航班，从而产生下行影响。图1展示了包含两架飞机和4个航班的航线时空网络图。在本文中，将飞机最小中转时间设置为30 min，机组最小中转时间设置为45 min。
图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，将这两个航班的起飞时间主动延后15 min。
图3 主动延误航班2和航班4以减少总延误的图示
（2）航班取消。在恢复期内，如果资源始终无法到位或者可起飞时间远远超过最晚起飞时间，那么该航班就不得不被取消。鉴于航班取消所需的高昂的成本，航空公司通常不考虑这一恢复措施。
（3）资源交换。当某航班的资源无法及时到位时，同起飞机场的可用飞机或机组可以代为执飞这个航班。原所需资源在就位后也可以被安排给其他航班。例如，如图4所示，已经在机场B的飞机1被指派去执行航班2，使得航班2能够按原计划起飞。
图4 交换飞机1和飞机2以减少延误的图示
（4）备用资源（飞机和机组）的使用。机场会配备一定的备用资源，且这些资源不会被提前安排任何航班任务，以便在恢复期间随时调用。
（5）置位和调机。置位指的是机组以旅客的身份被运送到另一个机场去执行任务。调机指的是指派飞机去执飞没有旅客的非计划内航班以到达指定机场。由于成本较高，航空公司很少使用调机这种恢复方式。
（6）飞机巡航速度控制。最近，很多研究将控制飞机巡航速度作为一种航班恢复手段。这种恢复手段通过调整航班飞行时间来降低意外情况造成的影响。
（7）旅客重分配。如果计划的行程受到影响，航空公司将会给旅客重新安排具有相同出发地和目的地的行程。
根据航空公司的偏好和能力，多种恢复措施可以被同步调用。考虑到问题的复杂性，航班恢复问题通常被拆分为一系列需按特定顺序解决的子问题。通常情况下，航空公司首先解决飞机路径恢复问题，其次解决机组恢复和旅客恢复问题。在接下来的三个章节中，我们将依次介绍飞机路径恢复、机组恢复、考虑旅客的多资源恢复模型以及相关算法。
三、飞机路径恢复
在不正常航班发生时，机组的恢复和旅客的重新安置都取决于飞机路径的安排。因此，合理高效的飞机路径恢复方案对于不正常航班的恢复至关重要。与飞机路径计划问题相比，飞机路径恢复问题影响的时间相对较短（几个小时到几日不等）。
飞机路径恢复问题旨在以最少的成本重新安排受不正常航班影响的飞机路径，同时确保恢复期之外的航班不受影响。此外，在恢复期结束时，飞机应到达指定航站，以执行后续的飞行计划。
飞机路径恢复问题通常被建模为一个网络问题，与其他路径问题相似，飞机路径恢复问题所采用的模型通常是基于弧或基于路径的，以下各小节将详细介绍这些模型。
（一）飞机路径恢复——弧模型（arc-based model）
弧模型可以解决由于恶劣天气、安保问题、军事行动或其他因素造成的不正常航班情况（如机场关闭、空中交通管制等），此模型建立在由Hane等所提出的时空网络上。时空网络是机型分配问题中常见的网络建模形式，该网络共有三种类型的节点和三种类型的弧，如图5所示。
图5 飞机路径恢复流量控制场景举例
1. 节点
第一类节点为供应节点（supply node），供应节点是每个航站恢复期开始的第一个节点；
第二类节点为需求节点（demand node），需求节点是每个航站的最后一个节点，表示恢复期的结束。模型要求在恢复期结束的需求节点，有指定机型及数量的飞机，以便执行后续航班计划；
第三类节点为中间节点（intermediate node），此类节点包含了飞机起飞事件或到达事件的时间和空间信息。
2. 弧
第一类弧为航班弧（flight arc），代表了一个具有预计起飞（到达）时间与航站信息的航班；
第二类弧为飞机在航站停留的地面弧（ground arc），地面弧的数值为停留在地面的飞机数量；
第三类弧为复制航班弧（copied flight arc），表示原始航班弧的延误时间（如10 min、 30 min或60 min），复制航班弧与原始航班弧的起飞（到达）航站相同，但前者的起飞（到达）时间为后者起飞（到达）时间加上延误时间。
下文所列模型为文献总结的通用的弧模型，该模型建立在如图5所示的时空网络上，是由Thengvall 等最先提出。
假设飞机路径恢复问题中的机组模型只有一种，即单机型问题，则通用的数学模型如下所述。
模型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个复制航班弧的分配成本，该分配成本包含了延误成本（其中，当复制弧不表示原始航班弧时，即t > 0时，
包含延误成本）；是航班f 的取消成本；As指流量控制时段s 允许通过的航班数量；Numb表示在供应节点b可用的飞机数量；Nume表示需求节点e要求的飞机数量；决策变量
表示航班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）中涉及的航班集合可以扩展到任意出于管理目的需要限制流量的航班集。
Thengvall等将单机型问题拓展至多机型问题，机型之间的区别包括座位数、最大飞行距离以及机组资质要求等。在多机型问题中，机型之间更换飞机的决策比同一机型内更换飞机的决策的条件更为严苛。因为如果更换后的飞机座位数低于营销部门已销售的座位数量，会为航空公司带来巨大的利润损失。此外，根据机型更换决策安排合适的机组资源也是多机型决策的一大问题。
对于多机型问题建模，Thengvall等对每个子机型建立一个时空网络，组成一组平行时空网络。在单机型问题里，一个航班只能由已分配子机型的飞机执行，而在多机型问题中，可以执行某个航班的子机型有多个。如图6所示，子机型2可以执行最初安排给子机型1 的航班，因此，航班2和航班3也存在于子机型2的网络。Thengvall使用IBM CPLEX求解器对模型直接求解，对于包含1~6个子机型的12个机型、1434个航班、24 h恢复期、10 h机场关闭情况的算例，模型在1838.4 s后获得一个近似最优解。在这个求解方案中，共有81个航班更换了原始分配机型，这表明允许交换机型的恢复方案更加灵活，能够有效提高恢复方案的质量。
图6 多机组模型的时空网络举例
模型1中的时空网络没有对具体飞机进行区分，导致无法直接从解中获得具体飞机路径。因此，模型1无法应对具体飞机不正常的情况（如某架飞机需要进行计划外维护）。为了解决这一问题，Vink等提出了包含具体飞机的拓展模型。他们在模型中构建了一组平行网络，其中每一个网络代表一架具体的飞机，这些网络通过航班覆盖约束关联。在模型1中，给每个变量增加索引，用于包含飞机的具体信息。
构建每架飞机的网络并求解相应的混合整数规划模型非常耗时，为了提高恢复算法的实时性，Vink等根据Vos等的建议研发了一种选择算法（selection algorithm）。该算法包含三个阶段，每个阶段仅选择指定数量的飞机，若根据所选飞机集合没有找到合适的解决方案，则该所选飞机集合被扩充并转入下一阶段，直到找到解决方案。采用选择算法求解一个包含100架飞机、每天600个航班、恢复期为16 h的算例平均耗时22 s，而在相同算例下，使用所有飞机的整数线性规划平均耗时10 min。在Vink所测试的10个算例里，利用选择算法找到全局最优解的有7个。平均而言，选择算法的解与全局最优解之间的差距为6%。
（二）飞机路径恢复——路径模型（path-based model）
飞机的不正常情况也可以使用路径模型解决，与弧模型相比，路径模型将飞机分配给已包含航班延误、飞机交换等具体恢复措施的路径。Argüello等、 Rosenberger等、Eggenberg等、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|: number of elements in the set of aircraft; |F|: number of elements in the set of flights; |I(F)|: number of elements in the set of all the possible flights;O(): space complexity, a measure of the amount of working storage an algorithm needs.
（三）考虑延误的飞机路径恢复
航班延误是不正常航班管理中一项重要的管理决策，轻微的航班延误可以被航班之间的缓冲时间吸收，并不影响航班的正常连接。因此，当轻微的不正常航班情况发生时，采用航班延误的措施是较为有效的。
在飞机路径恢复问题中，最常见的延误表达方式为模型1中所提到的，即使用复制航班弧表示航班延误，通过一组预先设定的离散延误时间集表示延误时间。 Thengvall等、Eggenberg等、Vos等和 Vink等在其建模中都采用了复制航班弧这一方法。然而，离散的延误时间存在一些缺陷：①延误时间可能被高估。例如，某个航班的实际延误时间是12 min，但可用的、偏差最小的延误时间为20 min，产生了多余的 8 min延误，从而带来不必要的延误成本。②为了防止高估延误时间，可以设置更小的时间间隔（如每延误一分钟设置一个选项），但这种做法亦会导致计算时间变长。
另外，航班的起飞和到达时间也可以作为决策变量。Aktürk等在飞机路径恢复中采取了飞机航班交换、航班延误和巡航速度调整等措施，其中将航班延误时间和巡航时间作为决策变量进行建模，具体见下文。
图7展示了该模型中飞机航班交换、航班延误和巡航速度调整三种情况。其中，情况I表示航班f 及后续航班N( f )的原始航班计划。情况II增加了巡航时间调整决策及航班延误决策。航班f 和后续航班N( f )的时间关系如式（16）所示：
式中，N( f )为原计划飞机在执行航班f 后需执行的下一个航班；rf 为航班f 的计划到达时间；
为航班f 的原计划巡航时间；TAf 为航班f 的计划中转时间；df为航班f 的计划起飞时间；lf为航班f 的延误时间；tf 为航班f 调整后的巡航时间；dN(f) 表示航班N( f )的计划起飞时间；lN( f )表示航班N( f )的延误时间。
图7 飞机航班交换情况示意图。I. 原始航班计划，航班N( f )紧跟着航班f；II. 考虑航班延误和巡航时间减少的航班计划；III. 考虑航班延误、巡航时间减少以及航班交换的航班计划，其中航班f 与航班j 进行交换；df ：航班f 的预计起飞时间；rf ：航班f 的预计到达时间；TAf ：航班f的预计中转时间；lf：航班f的起飞延误时间；lj ：航班j 的起飞延误时间；：航班f 的原始巡航时间；tf：航班f 调整后的巡航时间；N( f )：原计划飞机在执行航班f后需执行的下一个航班；dN(f )：航班N( f )的计划起飞时间；lN( f )：航班N( f )的延误时间
式（16）表示，若航班f 和航班j 没有交换，那么航班N( f )的实际起飞时间取决于航班f 的实际到达时间；若航班f 和航班j 交换，则航班N( f )紧随航班j（见图7中的情况III）。航班N( f )的实际起飞时间由式（17）给出，表示航班N( f )要么紧随航班j，要么紧随航班f。Aktürk 等在此基础上建立了一个二次混合整数规划，并用 IBM CPLEX求解器求解了一个包含207个航班、60架飞机、恢复期为1 d的算例，平均用时196 s。
式中，S( f )表示可与航班f 交换的航班集；决策变量xf,j表示航班f 是否和航班j 交换，如交换则为1，否则为0。
Liang等提出了一种在机场流量控制场景下自适应延误的方法，即在流量控制时段限制指定机场的出发或到达的最大架次。该方法可以通过在路径模型中引入以下约束实现。
式中，参数表示路径r 在流量控制时段s 中的架次数。
Liang等使用列生成框架解决该问题，在子问题中使用多标签最短路径算法，考虑了成本和延误时间两个标签。为了保证子问题的最优性，模型在每个流量控制时段的开始处和结束处复制了直接受流量控制影响的航班。模型在一个超过2 h空中交通管制和超过8 h飞机计划外维修的航班恢复情景下进行了算例效果验证，其中问题规模最大的算例（包含638个航班和44架飞机）在356 s内求得最优方案。
（四）考虑维修任务的飞机路径恢复
在飞机路径恢复期内，维修任务通常被视为无法更改的固定事件。Eggenberg等将维修任务的指标变化视为一种资源消耗和更新的过程，利用资源受限的最短路径算法生成具备维护可行性的路径。该研究在 3603 s内求解了一个包含16架飞机、242个航班、恢复期超过7 d的算例。
Liang等建立了基于连接网络的路径模型。除了 Eggenberg等使用的资源消耗概念外，他们还考虑了维修任务可以更换时间地点执行的情况，即当两架飞机属于同一机型并且资源限制都能满足时，这些飞机的维修任务的时间或地点可以互换。维修任务的可互换性提高了航班恢复的灵活性，从而可能获得更优的恢复方案。该模型同样采用资源受限的多标签最短路径算法。除了成本标签外，作者还考虑了三个额外的标签，即总飞行时间、总起降架次和总日历日时长。最终结果表明，相对于固定的维修计划，灵活可换的维修计划能够将恢复成本降低61.47%。
Vink等提出了考虑维修任务的弧模型。该模型考虑了两种类型的维修任务：一种是计划性的维修任务，此类任务很难再更换时间或地点（如当两次维修任务之间的日历日时长接近规定日历日时长），必须按原计划执行；另一种维修任务拥有多个时间和空间选择方案，至少选择一种算法来满足该飞机路径的维修要求。
表2 总结了飞机路径恢复问题中的不同研究特点和求解方法。
表2 飞机路径恢复问题的特点及求解方法
GRASP: greedy randomized adaptive search procedure.
四、机组恢复
介绍机组恢复之前，首先需要简要地了解机组排班（crew scheduling）。机组排班是指将某段时间内（如15 d 或30 d）的航班任务指派给飞行员，使航班计划中的每一个航班都能够由一个或多个飞行员执行。只有具备机型执飞资格的飞行员才能执飞相应机型，因此，航空公司往往根据机型将航班分为不同集合，分别求解不同机型的机组排班问题。与此同时，机组排班还需要遵循空管局和航空公司的规定，以确保飞行安全性和排班方案的可操作性。
与机组排班相比，机组恢复所涉及的航站相对较少，恢复时间相对较短，这使得问题规模显著降低。为了充分利用小规模的特点，恢复期不涉及的航班通常被视为固定事件。机组恢复旨在寻找一种成本最低的解决方案，在保证恢复期前后原航班计划被执行的情况下，将可用机组人员分配给不正常航班。
与机组排班类似，机组恢复问题通常建立在单一机型网络上，并且排班的法规要求在机组恢复中同样适用。此外，如果恢复期内包含预先指定的活动（如休假和培训等），则应同样被视为固定事件。
Teodorovic和Stojkovic最先提出解决机组恢复的机制，他们采用两种方法——“先进先出”（first-infirst-out, FIFO）法与动态规划法（以最小化机组的地面停留时间）——来构建机组值勤日计划，但此方法只能获得机组恢复的可行解而不能得到最优解。在之后的研究中，越来越多的学者采用最优化方法来解决机组恢复问题。下面，我们将介绍一个通用的机组恢复模型及其相应的拓展。
（一）机组恢复的基础模型
Wei等、Stojković等、Lettovský等、Yu 等和Guo等使用集分割模型（set partitioning model）来解决机组恢复问题。本文围绕Lettovský等提出的模型展开介绍。
模型3：机组恢复基础模型
式中，K表示机组集合；P表示任务环（pairing）集合；表示将机组k 分配给任务环p 的成本；
表示将航班f 作为置位（表示机组作为乘客搭乘本航司或外航司航班前往指定位置执行下一段飞行任务或回到基地）的成本；qk 表示机组k 空闲的成本；参数
表示任务环p是否包含航班f，如包含则为 1，否则为0；决策变量
表示是否将机组k分配给任务环p，如分配则为1，否则为0；决策变量vk 表示机组k 是否有任务，如没有则为1，否则为0；sf表示了航班f 作为置位使用的次数。
此模型包含了覆盖约束和分配约束。式（19）中的目标函数旨在最小化任务环成本、航班取消成本、置位成本和空闲机组的成本；式（20）表示一个航班可以被多次覆盖，超出1次的覆盖次数表示航班f 用作置位的次数，若航班f 无法被覆盖，则取消变量zf 的值为1，并会产生相应的取消成本；式（21）表示一个机组至多只能执行一个任务环。
Wei等使用启发式算法求解上述模型，在时空网络上利用最短路径算法生成任务环。此算法通过对航班弧设置不同成本以找到一个与原计划偏差最小的可行机组计划。该研究测试了包含6个机场、51个航班和18 个任务环、恢复期为2 d的算例，求解时间为1~6 s。
此外，机组恢复还需要考虑具体机组人员的配置。机组人员大体上分为三个级别：机长、副驾驶和第二副驾驶。为了获得实用的解决方案，Medard和Sawhney研究了包含多级别机组人员的拓展模型，将式（20）修改为式（25）：
式中，Q表示级别集合；Qf表示航班f 所需的机组人员级别集合；nf,q 表示航班f 所需的级别为q 的最低机组人员数量；决策变量表示是否将级别q 的机组人员k 分配给任务环p，如分配则为1，否则为0。
式（25）增加了级别q的信息，从而确保能够满足不同级别的最少机组人员数量。
（二）机组恢复的拓展
机组恢复也会产生航班延误，Stojković和Soumis在构造可行任务环时考虑了航班延误，并在主问题中增加了一组保护旅客连接（passenger connection）的约束。
式中，表示在任务环p中，由机组k执行的航班j 的起飞时间；
表示在任务环p中，由机组k执行的航班w的起飞时间；W表示任务环中的连续航班对(w, j)，该航班对要么包含于某一飞机路径中，要么包含于重要的旅客连接中。
若弧(w, j)位于飞机路径中，则dw,j = blw + gw，表示轮挡时间（blw）加上飞机中转时间（gw）。若弧(w, j) 上有重要的旅客连接，则dw,j = blw+ cw,j ，表示轮挡时间（blw）加上旅客中转时间（cw,j）。式（26）通过限制任务环中连续航班起飞时间之间的间隔来保护飞机的航班连接和旅客连接。
Stojković和Soumis通过添加一组一致性约束，提出了一个多级别模型。该模型将原始航班复制为一系列任务以表示不同的级别要求，Stojković和Soumis在模型中增加了式（27）。
式中，af是航班f 最早起飞时间；Tf是航班f 的延误时间；是机组k 执行的任务u 的起飞时间；Nf表示从航班f 复制的一系列任务。
式（27）确保从航班f 复制的每个任务都与原航班有相同的起飞时间。该模型采用列生成算法求解，将一致性约束添加至主问题。式（27）被重写为下式：
该模型采用美国国内航班的数据进行测试，以190个航班为例，其中有46个航班的起飞时间可以灵活变动，每个航班需要5名机组人员，机组总人数为97名，该算例在1237 s获得解决方案。
图8 机组恢复滚动求解框架
Abdelghany等使用迭代贪婪启发式算法求解机组恢复问题。如图8所示，不正常航班被划分至不同的阶段进行求解，划分的依据为同一阶段的航班之间资源独立（资源独立表示同一阶段的航班不共享同一机组资源）。模型在每次迭代中求解一个混合整数模型，将资源相互独立的航班分配给可用机组。
式中，df 为航班f 的计划起飞时间；blf表示航班f 的轮挡时间；ak表示机组k 开始可用的时间；mk是机组k达到最大值勤时间的时间点；若机组人员k分配至航班f 的级别为q，则决策变量xk, f,q值为1；dtf 是航班f 的实际起飞时间；atf 是航班f 的实际到达时间。
式（29）和式（30）确保每个航班都被覆盖以及确保每个机组人员至多有一个级别；式（31）和式（32）确保所有航班的实际起飞时间既不应早于航班的计划起飞时间，也不应早于机组的最早可用时间；式（33）确保所有航班的到达时间不会超过机组的日最大值勤时间；式（34）表示航班出发时间和到达时间之间的关系。该模型从美国主要航空公司获取测试算例，用1.85 s解决了一个恢复期为8 h、包含121名机组人员的算例。虽然这种滚动求解方式无法获得全局最优解，但所得求解方案是可用的。
为了限制模型规模，加快求解速度，Lettovský等将恢复期的部分任务环划分为若干片段（segment）。图9展示了一个任务环的部分，值勤2中的航班被分成由一个或多个航班组成的片段。因此，在模型中被覆盖的元素由航班变成了片段，从而减少了覆盖约束的数量。与此同时，生成的任务环数量也相应减少，从而减少了计算时间。
图9 片段示意图。片段1仅包含一个航班（航班2），片段2包含两个航班（航班3与航班4）
（三）机组恢复问题的求解办法
机组恢复的通用模型包含的约束较少，但生成的变量数量庞大。因此，大多数机组恢复都采用列生成算法求解。列生成算法可以在无需枚举出所有变量的情况下保持线性松弛的最优性。在列生成算法里，机组k的路径在子问题中生成并传递至主问题，主问题通过求解线性松弛模型获取当前轮次最优的恢复路径集合。参考文献都使用列生成算法解决，但构建网络的元素却不大相同，表3总结了不同机组恢复问题的特点和求解方法。
表3 机组恢复问题的特点及求解方法
B&B: branch and bound.
五、多资源航班恢复
这一节将介绍考虑多种资源的航班恢复问题的特征和相应的建模方法。
（一）飞机和机组资源的整合恢复
在航班恢复期内，飞机和机组资源的调度非常重要，能够提供更优的恢复方案。然而由于复杂的业务限制、较大的问题规模，这类整合恢复问题的建模和求解较为困难。
1. 基本连接
已有研究将航班取消和延误决策作为整合飞机路径恢复和机组恢复问题的基本连接。正如第3节和第4节所述，飞机路径恢复和机组恢复的基础模型都使用公共变量zf来表示航班取消决策。
Maher构建了包含飞机路径与机组任务环的连接网络模型，并且在该网络中构建了一组复制航班弧来表示不同的航班延误决策。该研究使用延误一致性约束将基于路径的飞机路径恢复和机组恢复模型进行整合，具体如式（35）所示。
式中，Uf表示航班f 复制弧的集合，用v 表示；Dk 表示可以被安排给机组k 的值勤日计划集合；参数表示飞机a 的路径 r 是否包含航班f 的复制弧v，如包含则为1，否则为0；类似地，参数
表示机组k 的值勤日计划p是否包含航班f 的复制弧v，如包含则为1，否则为0；决策变量
表示航班f 的复制弧v上的机组置位次数。
式（35）中的约束保证了飞机和机组计划中，相同航班延误决策的一致性。此外，延误一致性约束的数量取决于模型中包含的飞机可选路径和机组可选值勤日计划的数量。
2. 飞机与机组之间的资质匹配
在将飞行员指派给具体航班时，需要考虑其是否具备驾驶该航班的能力。因此，飞机与机组之间的资质匹配问题是航班恢复决策必须考虑的因素。Abdelghany等和Arıkan等构建了包含资质匹配约束的弧模型，具体如下式所示：
式中，参数ζk,a表示机组k是否有驾驶飞机a的资质，如有则为1，否则为0；决策变量表示是否将资源o安排给航班f，如安排则为1，否则为0；决策变量
和
分别表示飞机和机组的指派决策。
式（36）确保了将资质匹配的飞机和机组安排给同一个航班。除了该约束，Abdelghany等提出的模型还包含了飞机和机组的覆盖约束，以及确保延误时间可行性的其他约束等。该研究使用迭代贪婪启发式算法求解，在36s内求解了一个包含522架飞机、1360名飞行员、2040名乘务员、1100个航班（其中10个航班受到影响）的恢复场景。
Arıkan等构建了一个特殊航班网络模型。模型包含4种节点，分别为计划航班节点、源节点、汇节点和必须访问的节点，这些节点代表了飞机维修或者机组休息等事件。该研究在此网络基础上建立了弧模型，其中资质匹配约束如下式所示：
式中，Conn表示节点f 和g 之间的连接弧集合，每个连接弧用(f, g)表示；Ak表示机组k 可以驾驶的飞机集合；决策变量表示是否将资源o分配给弧(f, g)，如分配则为1，否则为0。飞机资源相关决策变量用
表示，机组资源相关决策变量用
表示。
除了上述资质匹配约束，本研究还考虑了控制巡航速度等恢复手段。为了提高求解效率，研究采用了规模控制算法（size control algorithm）和旅客聚合（passenger aggregation）的预处理方法，将一个包含1254个航班和 402架飞机的航班网络算例的总求解时间减少至12 min 以内。
值得注意的是，弧模型很难考虑机组执勤日计划和机组任务环所需的复杂合法性约束。
3. 连接可行性
不同的资源（如飞机、机组和旅客）具有不同的中转时间要求。因此，在航班恢复中，通过航班延误来控制衔接航班的时间间隔，在一定程度上有助于生成合理且高效的任务路径。很多关于航班恢复的研究在不同资源的任务路径构建中考虑了该资源的航班连接可行性，从而不需要在模型中添加相关约束。
Arıkan等提出的模型包含了连接可行性约束，见式（38）。如果将资源分配给某段弧，则该弧所连接的前一航班到达和后一航班起飞之间的时间差应满足该资源所需的最小中转时间。
式中，CCo 表示间隔时间小于资源o最小中转时间的弧的集合；Res表示包含飞机和机组的所有资源（用o表示）的集合；表示将资源o指派给弧(f, g)需要满足的最小连接时间；
表示航班f 的最晚到达时间。
由于整合模型的求解存在一定的计算难度，Zhang 等构建了两阶段启发式算法，将整合模型分解为两个阶段，分别解决飞机和机组恢复问题。这两个阶段通过飞机和机组连续航班之间的连接可行性联系在一起。
当机组的两个连续航班被指派给同一架飞机时，可以忽略机组中转时间限制。我们把机组的这类连接称为短连接。短连接可以增加解决方案的灵活性。Maher在模型中考虑了短连接约束，如式（39）所示。该约束确保了如果机组被指派给包含某个短连接的任务环，那么该短连接的两个前后航班必须由同一架飞机执飞。
式中，SC表示短连接集合，每个短连接由(f, g)表示，短连接的连接时间小于机组最小中转时间，但满足飞机的中转时间；参数表示连接(f, g)是否包含在机组k 的任务环p中，如包含则为1，否则为0；类似地，参数
表示连接(f, g)是否包含在飞机a 的路径r 中，如包含则为1，否则为0。
以上模型考虑了飞机和机组恢复计划的关联，然而要实现飞机和机组恢复计划的完全同步仍然具有一定的难度。
（二）考虑旅客的飞机路径恢复问题
原航班计划无法顺利执行可能会对旅客行程产生不利影响。对于航空公司而言，旅客行程的恢复十分重要。在极端情况下，旅客甚至无法再乘坐原航空公司的任何航班到达目的地。此时，航空公司可能不得不退票或给受影响旅客安排其他航空公司的航班，从而造成无法估量的信誉损失，无形之中影响了旅客未来的出行选择。因此，迅速合理地恢复受影响的旅客行程能够大幅提高航空公司的市场竞争力。
1. 基于行程的旅客恢复
大多数整合飞机路径恢复和旅客恢复问题的研究都是基于旅客行程来构建的。这类研究通常采用二元变量来判断旅客行程是否受到影响。造成旅客行程中断的原因一般为航班取消或者旅客中转时间不足。该二元变量及相关约束如下所示：
式中，Itin(i)表示行程i 包含的航班集合；IT表示行程的集合；表示衔接航班对中，后序航班2的计划起飞时间和前序航班1的计划到达时间之差；
表示航班f 在路径r 中实际起飞时间的延误时长；
表示航班f 在路径r 中实际到达时间的延误时长；TminC表示旅客最小中转时间；M是一个大数；Itin(i,l)表示行程i 中的第l 个航班；决策变量αi表示行程i 是否被破坏，如被破坏则为1，否则为0。
式（40）表示如果一个航班被取消，则包含该航班的行程被破坏。式（41）表示如果某行程的旅客中转时间过短，则该行程被破坏。Arıkan等提出的模型目标函数中包含了与旅客有关的成本，由延误成本和溢出成本（spill cost）组成。其中旅客溢出（spill）是指由于恢复期间重新被指派给这个航班的飞机座位数不足，部分旅客被迫滞留机场，无法登机。除此以外，燃油成本也以与巡航时间相关的非线性函数的形式包含在目标函数中。该研究将问题转化为一个具有线性目标函数和圆锥二次约束的模型来解决。受模型复杂性的限制，文献中的公式没有考虑旅客再分配决策。
许多研究在多资源整合模型中考虑了旅客行程的重新安排决策，相关约束如下所示。
式中，Γ(i)表示行程i 的备选行程集合（包含行程i）；PNi 表示行程i的初始旅客数量；参数表示行程m是否包含航班f，如包含则为1，否则为0；Capa表示飞机a的座位数；决策变量hi表示原行程i 受不正常航班情况影响被退票或选择其他航空公司产品的旅客数量；决策变量
表示将行程i 安排给行程m的旅客数量。
式（42）确保任何行程的旅客要么被成功运送到目的地，要么被退票。式（43）确保每个航班的旅客数量不超过指派给航班的飞机座位数。式（44）确保旅客不会被重新分配给受影响的行程。式（45）确保行程未受影响的旅客能够保持原计划，不会被分配给可替代行程。
虽然有不少研究考虑了旅客再分配决策，但受问题规模和计算时间的限制，部分学者更倾向于采用近似的方法考虑旅客相关因素。这些研究在模型中不考虑旅客再分配决策，仅在目标函数中对受影响的行程数量进行惩罚。Marla等使用了一种“航班计划”（flight planning）机制，允许在长途飞行中调整飞行速度。与文献中的方法不同，Marla等没有将巡航时间作为一个变量，而是将巡航时间的动态选择离散化，并在此基础上构建了精确模型和近似模型。由于精确模型的求解非常耗时，该研究采用了近似模型进行实例分析。类似地，Bratu和Barnhart也提出了两个模型，分别被称为中断旅客度量模型（DPM）和旅客延误度量模型（PDM）。后者支持旅客行程的重新安排，因此可以更准确地计算出旅客延误的成本。然而正如前文所说，不考虑旅客重新安排的模型求解效率更高。在一个涉及 80 000多名旅客的恢复算例中，PDM模型的平均计算时间大约是DPM模型的25倍。
2. 基于航班的旅客恢复
除了基于行程的旅客恢复方式外，已有研究提出了其他建模方法。Arıkan、Gürel和Aktürk构建的模型将所有资源（包括飞机、机组和旅客）都视为等价实体，在模型中确保航班网络中各个实体被指派的航班连接可行性约束和流平衡约束。由于该类建模方法的网络规模较大，研究提出使用实体聚合法能够在不失最优性的情况下尽可能减少实体的数量。Hu等构建了基于时间带网络（time-band network）模型，并提出了一种基于航班的旅客中转机制，具体为生成具有相同出发和到达机场的可替代航班集合，以安排给行程被破坏的旅客。Maher建立了一个用于解决点对点航线网络（其中所有旅客行程仅包含一个航班）的基于航班的旅客恢复模型。该模型在文献的模型基础上进一步考虑了旅客恢复。
3. 启发式算法
很多启发式算法在解决飞机和旅客整合恢复问题中展现了不错的效果。
Bisaillon等提出了一种大规模邻域搜索启发式算法。该算法分为构建、修复和改进三个阶段。前两个阶段用于产生一个可行的解决方案。第三个阶段在确保可行性的基础上，尝试通过一些较大的调整来改进已有解的质量。该算法在第三个阶段解的基础上再次执行构建步骤。该算法提供了高质量的解决方案且能够实时处理大规模恢复问题。Sinclair等在参考文献中提及的算法基础上为每个阶段增加了额外步骤以提高性能。实验结果表明，在第三个阶段中加入破坏和生成步骤对改善解质量效果最好。
Sinclair等还提出了一种列生成后优化启发式算法。该算法首先基于时空网络模型建立了线性规划模型。然后使用文献[58]中的算法以获得初始解并构造出受限主问题（RMP）的约束。最后，通过求解相应的列生成子问题生成合理的旅客重新安排方案。
Jozefowiez等提出了一种新的航班连接启发式算法。这是一种基于最短路径算法的三阶段启发式算法。第一阶段根据预设的恢复场景更新已有航班计划；第二阶段通过求解相应的最短路径问题，为行程受影响的旅客分配可替代的备选行程；第三阶段在现有飞机任务环中插入一个新的子环，用来安排额外的旅客。
Hu等使用贪婪随机自适应搜索（GRASP）算法对飞机和旅客进行恢复。在每次迭代中，模型通过使用GRASP算法生成基于新的飞机路径的旅客重新安排方案，直到满足特定的迭代停止条件。
（三）一体化多资源航班恢复问题
到目前为止，很少有研究能够完全解决多资源航班恢复问题。Bratu和Barnhart是解决该问题的首批尝试者之一。但在机组恢复部分，他们仅考虑使用备用机组来恢复航班计划。Arıkan等为了在较短时间内解得恢复方案，设计了两种预处理方法来减少约束和变量的数量，同时设计了算法来限制航班恢复的范围。
Petersen等整合了航班计划恢复、飞机路径恢复、机组恢复、行程恢复和旅客重新调度这5个子问题，设计了一种Benders分解框架求解该整合问题。然后他们对一个包含800个航班和2个机型的算例，分别使用整合求解和无整合逐阶段求解方式来获得恢复方案。虽然前者得到的恢复方案质量更高，但如果想要在半小时内解决大规模航班恢复问题，整合求解的算法还需要进一步优化。
Maher使用了行列生成法来求解多资源恢复模型，该研究通过求解基于最短路径算法的列生成子问题来获得备选的机组值勤日计划和飞机路径。该列生成子问题中的旅客调度方案可以通过背包问题来解决。模型通过迭代的方式逐步加入行约束，具体包括旅客再分配约束和延误一致性约束。Maher测试了包含262个航班的点到点网络的恢复场景和包含441个航班的轮辐网络的恢复场景，分别能够在427 s和400 s内完成求解。
表4总结了现有整合恢复模型的一些特点。
表4 整合恢复模型的方法汇总
ACP: aircraft, crew, and passengers; AP: aircraft and passengers; AC: aircraft and crew; AB: arc-based; PB: path-based.
六、结论与未来展望
本研究总结了飞机和机组恢复的基础模型和扩展，并介绍了考虑旅客因素的多资源整合恢复问题。关于飞机路径恢复问题，本文回顾了通用的弧模型和路径模型，并讨论了这些模型的适用场景。此外，本文还总结了飞机路径恢复中关于航班延误、维修因素的拓展研究。关于机组恢复问题，本文介绍了与飞行员级别、航班延误相关的基础模型和扩展模型。关于多资源整合恢复问题，本文介绍了连接不同资源的关键约束和相关算法。
在回顾不正常航班管理的研究之后，本文对未来的研究提出了以下建议：第一，飞机路径恢复或机组恢复研究可以引入更多现实因素使得解决方案更具实用性，如在建模中考虑不同机型之间的飞机交换等。第二，多阶段整合的问题十分复杂，按照现在的算力，求解仍然极具挑战性。未来的研究重点可以侧重于多阶段集成和优化方法设计等方面。例如，可以通过数据预处理（如分解方法）来缩小问题规模，降低模型复杂度。最后，不正常航班造成的损失主要来自旅客，因此以旅客为主的恢复研究是一个十分有潜力的研究课题。例如，如何将旅客偏好纳入恢复的研究以提高服务水平，以及如何通过数据挖掘评估旅客信息等，以此带来更精准的优化结果。
改编原文：
Yi Su, Kexin Xie, Hongjian Wang, Zhe Liang, Wanpracha Art Chaovalitwongse, Panos M. Pardalos.Airline Disruption Management: A Review of Models and Solution Methods[J].Engineering,2021,7(4):435-447.
本文来自微信公众号：中国工程院院刊（ID：CAE-Engineering），作者：苏艺，谢可欣，王洪建，梁哲
原创文章，作者：kepupublish，如若转载，请注明出处：https://blog.ytso.com/111510.html