航空公司中断管理综述:模型与解决方法，航空运输新方法述评

工程7（2021）435研究航空运输新方法述评航空公司中断管理：模型与解决方法综述苏毅a，谢可欣a，王宏健b，梁哲a，王伟，Wanpracha Art Chaovalitwongsec，Panos M.帕达洛斯da同济大学经济管理学院，上海200092b厦门航空公司，中国c美国阿肯色州费耶特维尔市阿肯色大学工业工程系和高级数据分析研究所，邮编：72701d佛罗里达大学工业与系统工程系应用优化中心，Gainesville，FL 32611，USA阿提奇莱因福奥文章历史记录：收到2020年2020年6月26日修订2020年8月3日接受在线预订2021年保留字：中断管理飞机恢复问题机组恢复问题综合恢复问题A B S T R A C T飞机及航班的正常运作可能会受到各种不可预测因素影响，例如恶劣天气、机场关闭及纠正性维修，导致计划时间表中断。当发生中断时，航空公司运行控制中心执行各种操作以重新分配资源（例如，航班、飞机和机组人员）并重新分配乘客以恢复时间表，同时最小化成本。我们介绍了不同的中断源和相应的操作。然后，基本模型和最近提出的飞机恢复，机组人员恢复和综合恢复的扩展进行审查，目的是提供不同的中断情况下，在航空公司的实际实施的模型和方法。此外，我们还对这些主题的未来研究方向提出了建议。©2021 THE COUNTORS.Elsevier LTD代表中国工程院出版，高等教育出版社有限公司。这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）中找到。1. 介绍航空业已成为全球经济的主要参与者。随着人们越来越依赖航空旅行，全球定期航班的数量每年都在增长。根据国际航空运输协会（IATA）[1]的数据，2019年全球民航客运需求增长了4.2%，而运力增长了3.4%。因此，需求的增长似乎快于运力的增长，这表明航空市场具有巨大的发展潜力。随着航空业的发展，航线计划与调度问题越来越受到人们的关注，大多数航空公司都受益于先进的优化方法。正如Eltoukhy等人[2]和Zhou在等人[3]的文件。在各种情况下，例如飞机机械故障或恶劣天气条件，航班无法按计划运行。交通统计局提供的数据*通讯作者。电子邮件地址：liangzhe@tongji.edu.cn（中）Liang）。BTS的数据显示，2019年美国约有21%的航班出现了超过15分钟的抵达延误。同样，根据中国民用航空局（CAAC）二零一九年民航行业发展统计公报[4]，中国平均航班准点率为81. 43% 同样，OAG的准点联盟报告[5]显示，全球只有三家航空公司的准点率超过90%。航班延误和取消已成为影响旅客航空偏好的重要因素。因此，如果不正常的运营不能得到适当的恢复，航空公司的经济和社会效益可能会受到损害。因此，干扰管理已成为航空公司运营管理中的一个重要问题。航空公司规划和航空公司恢复之间有许多区别。规划的重点是优化，而恢复的目标是一个可行的，但可能是次优的解决方案，可以实时获得。此外，恢复可能比计划更不确定，这取决于障碍的程度和类型。与可以在运行前几个月获得的飞行计划不同，应在中断后尽快获得和实施恢复解决方案。在本文中，我们专注于恢复的特点和审查常见的模型和方法。模型的详细信息提供了https://doi.org/10.1016/j.eng.2020.08.0212095-8099/©2021 THE COMEORS.由爱思唯尔有限公司代表中国工程院和高等教育出版社有限公司出版。这是CC BY许可下的开放获取文章（http://creativecommons.org/licenses/by/4.0/）。可在ScienceDirect上获得目录列表工程杂志首页：www.elsevier.com/locate/engY. Su，K. Xie，H. Wang等人工程7（2021）435436回收方案的特点和应用，帮助航空公司选择适当的方法，以满足其具体要求。本文的其余部分组织如下。第2节介绍了中断管理，包括中断的来源和可能的恢复操作。第3节提供了飞机回收的基本模型和求解方法。第四介绍了船员恢复的一般模型和一些第5介绍了综合恢复，考虑多种资源，包括乘客。第六部分总结了我们的工作，并提出了未来工作的方向。2. 干扰管理许多研究探索了综合恢复方法，以有效地处理中断Clarke[6]回顾了航空公司运营控制中心在非常规运营期间的做法Filar等人[7]检查机场的干扰处理Kohl等人[8]提供了航空公司中断管理的许多方面的详细概述，并报告了关于航空公司中断管理的大规模研究。Clausen等人[9]回顾航空救援技术，介绍进度计划模型Belobaba等人[10]在他们的书的第9章中提出了进度恢复和稳健的计划，以减轻不规则操作的影响。Barnhart和Smith[11]描述了不同资源恢复和航空公司中断管理工具的基本模型（第6.3章）。Floudas和Pardalos[12]也提到了航空恢复问题的数学模型和其他相关方法的变化。下面，我们简要解释中断的来源和中断传播到航空公司的航班网络。然后，我们描述常见的航空公司恢复操作。2.1. 中断的来源我们将航班中断的原因分为两类：(1) 航空公司资源中断（例如，飞机、机组人员）。这种中断是由飞机机械故障和燃料短缺导致的额外维护，或机组人员因疾病或个人紧急情况而缺席(2) 外部环境破坏（例如，空中交通管制（Air Traffic Control）航空旅行对天气很敏感。即使是轻微的天气状况也可能降低机场起飞和抵达率，导致航班延误。在恶劣天气条件下，采取强制措施，如关闭机场和空中交通管制，以确保乘客和航空公司资产的安全。由于每架飞机和机组都安排了不同的连续飞行，航班中断，很可能影响后续航班，产生下线影响。图1示出了具有两个飞行器和四个航班的示例。飞机至少需要30分钟45分钟内，机组人员将完成这一任务。假设机场A在07：00至08：30因雷雨关闭。因此，1号航班要到8：30才能起飞，导致2号飞机和1号机组人员无法完成所需的转移（图1）。 2）的情况。2号和4号航班都受到影响。此外，在中断期间应考虑机场和空域的容量，因为机场和空域接受各种航空公司的飞机，但分配的资源（例如，登机口、跑道）在特定时间是有限的。总体而言，由于航空公司之间在资源分配方面存在分歧，即使是非常轻微的中断也可能造成重大损失。因此，采用恢复方法来防止或减轻下线影响非常重要。2.2. 恢复操作飞行改出主要包括以下操作，我们将参照2.1节中的例子来解释这些操作。(1) 航班延误受影响的航班和相关航班的起飞时间可能会延迟。在图3中，航班2和4的起飞延迟至少15分钟，以满足飞机和机组人员的最小过境时间。(2) 取消航班在恢复期间，如果分配给执行飞行的资源不可行，或者如果飞行可以进行，但延误将超过限制，则取消飞行。由于航班取消成本高昂，这种操作通常是航空公司最后的恢复选择。(3) 交换资源（重新路由）。当飞机或机组人员没有为下一次飞行做好准备时，同一机场的其他飞机或机组人员可以代替原来的飞机或机组人员执行飞行。然后，当可用时，将回收的飞机或机组人员重新分配到其他航班。例如，当发生分离时，飞机1和2可以在机场B中交换，以使航班2使用飞机1操作，而没有延迟，如图1所示。 四、(4) 使用储备资源（飞机和机组人员）。保留资源在机场可用，不执行任何飞行任务。(5) 空驶和摆渡。空驶意味着机组人员作为乘客被运送到另一个机场，而摆渡意味着飞机被分配到没有乘客的不定期航班。由于这些行动的成本很高，因此很少被采用。(6) 速度控制。最近的各种研究都将速度控制作为一种恢复操作，它修改飞行时间以减少中断及其相应延迟的影响。Fig. 1.下图说明了下线对一个由两架飞机和两名机组人员组成的四个航班网络的影响。机组1被分配到航班1和4，而机组2被分配到航班2和3。图二.当航班1不能准时出发时，网络的下行影响的说明。延误的航班1由航班1'表示。由于分配给航班1的机组1和飞机2的迟到，航班4和2受到影响。Y. Su，K. Xie，H. Wang等人工程7（2021）435437FX图三. 延迟航班4和航班2以减少总延误的示例。如下所述，三种类型的节点和三种类型的弧。时空网络的一个例子如图所示。 五、3.1.1. 节点供应节点是第一个节点，它指示发生中断时每个站点恢复期的开始。需求节点是指示每个站的恢复期结束的最后一个节点。例如，它表示飞机在指定机场按航班时刻表飞行。中间节点是具有表示特定航班的出发或到达的时间站信息的节点3.1.2. 弧航班弧线是表示航班及其预定出发/到达时间和站点的弧线。地面弧是表示飞机停留在地面上的弧。复制的飞行弧是表示延迟选项的弧（例如，10、30或60分钟）。每个延误选项都是指一个航班弧，其中离（抵）港时间是计划离（抵）港时间加上同一离（抵）港站的延误一个通用的基于弧的模型可以从参考文献中总结出来。[14飞机回收问题可以用时空网络来表示，如图1所示。 5;这种方法首先介绍了Thengvall等人。[18]第10段。假设一个单一的舰队问题，一般的数学模型如下所述。模型1：飞机回收见图4。 交换飞机1和2以减少总延迟的示例。minX Xct xtXc zð1Þ(7) 乘客重新分配。如果行程中断，乘客可以重新分配到具有相同起点的行程，Fff Ff2F t 2I ff 2Fs：t：Xxtyn--Xxt-yn0;8n2N2目的地可以同时采用多种恢复操作，Ff;tFf;t根据航空公司的偏好和能力。考虑到采用操作的复杂性，恢复问题通常分为一系列按顺序解决的子问题。通常情况下，首先解决的是飞机回收，其次是机组人员回收和乘客回收。在接下来的三个部分中，我们将详细介绍飞机回收、机组人员回收和考虑乘客的综合回收的具体模型和解决方案。3. 航空器回收由于机组人员的重新安排和乘客的重新安置取决于飞机的安排，有效地重新分配飞机对中断恢复至关重要。与规划相比，恢复的时间范围相对较短，从数小时到数天不等。飞机恢复旨在以最低成本重新安排受中断影响的飞机航线，同时确保恢复期后的航班不受中断影响。此外，在恢复期结束时，飞机应停在特定的站点，以便进行随后计划的飞行。飞机回收通常被建模为一个网络问题。与许多网络路由问题一样，所采用的模型通常是基于弧或基于路径的，如以下小节中的各种扩展所详述3.1. 基于圆弧的飞机回收基于弧的模型允许处理由恶劣天气、安全问题、军事行动和其他因素造成的机场关闭和空中交通管制等中断。该模型通常建立在时空网络中网络已经xtybNumb;8b2B3f;t图五. 用于飞机回收的插槽容量示例。Y. Su，K. Xie，H. Wang等人工程7（2021）435438SXx 拉斯 1/4;8f2F50fXx≤A;s2S6sXx xx xy2014年8月24日，第二季第4集，FFFtff;ttft2 I ftff;txt2 f0; 1g;8f2F;8t2If7zf2 f0; 1g;8f2Fynn n;yn->0;8n2N[B[E]9N其中，F是航班集合，其中，Fn和Fn-分别表示从节点n的航班集合Fe-是从节点e出发的航班集合;E是包括每个站点的最后节点并表示恢复期的终点的需求节点集合;Fs是时隙s中涉及的航班集合（如果时隙s是出发时隙，则Fs包含出发航班，如果时隙s限制出发和到达，则F s包含所有航班）;S是中断时隙集合，其可能由天气条件、安全问题、军事行动和其他因素引起;I（f）是包括原始航班弧f和对应的复制航班弧的集合，并且IFfIf表示所有可能的航班集合arcs;Ct是航班F的第t个副本的分配成本（如果第t个副本不是原始航班，即，t> 0）;cf是航班f的取消成本;As是限制的航班数量s插槽中允许使用的飞机;b是供应节点b; n = e是需求节点e所需的飞机; x t是决策变量，如果选择了飞行f的第t个副本，则值为1，否则值为0; y n= e 是飞机的数量节点n后的地面;yn-是地面上的飞机数量在节点n之前;yb是在节点b之后的地面上的飞行器的数量;ye是在节点e之前的地面上的飞行器的数量;以及zf是决策变量，如果航班f被取消，则值为1，否则值为0。Eq中的目标函数（1）目标是最小化总分配成本、延迟成本和取消成本。此外，飞机的流动平衡是由方程组中的约束条件来维持的（2）具体而言，在Eqs.（3）和（4）指示飞机被供应以操作一系列飞行并在恢复期结束时到达需求节点。方程中的飞行覆盖率约束（5）确保每班航机取消或按其班次/延误安排运作。在Eq. （六）规定每一时段内涉及的离港及抵港航班数目，须维持在该时段的容量以下。图5示出了时隙容量的减少，其中空中交通管制在机场B从08：30到10：30进行，其中出发时隙容量从三个减少到两个，并且涉及飞行弧1-4。复制的飞行弧5和6设置在时隙之后，以表示由于中断而延迟的航班在恶劣的天气条件下，如飓风或台风，飞机应被移入机库或由地面锁固定。否则，飞机应被转移到其他机场，以确保其安全。因此，地面上的飞机数量相对于机库容量或地面锁应该通过相应的约束来保证。在Eq. （10）限制相应槽中涉及的接地电弧的数量。yn≤Ag;n2Ng;g2G<$10<$其中G是地面弧的集合以及容量;Ag是地面弧的限制数量;Ng表示一些特殊中间节点的集合;并且在这些节点之后的地面上的飞机的数量是有限的。空中交通管制可用于特定机场和任何感兴趣的航班。因此，涉及的一组航班当量（10）可以扩展到由控制器指定的任何候选集合。Thengvall等人[19]扩展了单车队模型，以处理多车队。机队之间的主要区别在于飞机的配置，主要体现在座位数量和最大飞行距离以及对机组人员的要求上。在机队之间交换需要比在一个机队内交换更严格的条件，因为预先分配的容量的偏差可能导致大量的利润损失。多舰队模型采用一组与单机队模式一样，航班可以由预定子机队中的所有飞机运营。此外，在回收期间，一些航班可以由多个子机队操作。 如图 6，子机队2可以运行原计划到子机队1的航班;因此，航班2和3属于子机队2的网络。该模型使用IBM CPLEX Optimizer求解对于12个机队包含1-6个子机队，在24 h恢复期内有1434个航班，机场关闭10 h的实例，模型在1838.4 s的计算后提供了一个近最优解。在这个接近最佳的解决方案中，81个航班由与最初分配不同的子机队运营这表明在机群之间交换提供了更大的灵活性并提高了解决方案的质量。飞机航线不能直接从基于弧的基本模型中获得，因为时空网络中的流不能区分特定的飞机。因此，基于弧的模型不能处理诸如特定飞机的意外维护之类的中断。为了解决这个问题，Vink等人[21]扩展了基于弧的模型，以包含特定的飞机。建立了一组并行网络，每个网络代表一架飞机.这组网络由航班覆盖约束捆绑。该模型是通过为模型1中的每个变量包括额外的飞机指数来扩展的。为每架飞机构建网络并求解相应的整数线性规划可能非常耗时。为了实现实时性能，Vink et al.[21]从Vos等人的建议中开发一个选择算法[20]这是一个三阶段的过程。为了加快求解过程，每个阶段所涉及的选定飞机的数量是有限的。如果所选择的飞机没有找到解决方案，则候选飞机的集合是见图6。 多车队模型的时空网络示例Y. Su，K. Xie，H. Wang等人工程7（2021）435439Xs：t：x¼1;8a2A12ð Þð ÞRFRFRFF最小值X XcxXcf zf 11X Xdxzf¼1;8f2F13ð Þ扩展并进入下一阶段。选择算法求解一个100架飞机、600个日航班、16 h恢复期的实例平均耗时22 s，而求解一个10 min表1基于弧和路径的模型的特征。决策变量基于弧的模型（Leg）基于路径的模型（Path）对于整数线性规划，考虑整个集合。selec- tion算法在10个sce-narios中的7个中找到全局最优解平均而言，选择算法解，全局最优解为6%。许多变量一些制约因素O（|一||I（F）|）很多O（|一||F|）O（|F|）延迟的表述复制飞行弧的决策变量在路由生成期间3.2. 基于路径的飞机回收通用模型注销的提出决策变量也可以使用基于路径的模型来处理关于单个飞机的中断。与基于弧的模型相比，基于路径的模型将飞机分配到包括航班延误和飞机交换等详 细 信 息 的 航 线 。 Argüello 等 人 [22] 、 Rosenberger 等 人 [23] 、Eggenberg等人[24]、Wu等人[25]和Liang等人[26]开发了基于路径（路线）的模型。基于路径的飞机回收模型也可以处理中断，如机场关闭和空中交通管制，通过添加侧约束的模型。此外，该模型还可以处理飞机的计划外维护等情况。基于路径的模型使得能够进行可行性检查（即，保证的最小周转时间）。约束和规则可以在路线生成过程中隐含地包含，并从模型中删除。下面描述基于路径的模型模型2：飞机回收的基本路径模型a aR Ra2Ar2Raf 2FaRr2RaRaF Ra2Ar2Ra|- 飞机集合中的元素的数量;|F|：飞行集合中的元素的数量;|I（F） |O（）：空间复杂度，一个算法需要的工作存储量的度量。|:numberofelementsinthesetofallthepossibleflights;O():space complexity, a measureof the amount of working storage an algorithm needs.3.3. 延迟恢复航班延误是一项重要的恢复行动。短暂的恢复延迟有时可以通过航班之间的缓冲时间来吸收，从而保持航班连接。 因此，为较小的中断选择延迟是有效的。在飞机回收中广泛采用模型1所描述的复制航班来表示延误。延迟选项 由 一 组 离 散 的 预 定 延 迟 时 间 给 出 。 Thengvall 等 人 [18 ， 19] 、Eggenberg等人[24]、Vos等人[20]和Vink等人[21]在其公式中采用复制航班作为延误选项。然而，离散时延也存在一些缺点. ①延迟可能被高估。例如，航班的实际延误可能是12分钟，但唯一可用的选项是20分钟，因此产生了不必要的延误成本。②为了防止高估，可以设置较小的时间间隔，但这样做会增加问题的大小。航班的出发和到达时间也可以是模型中的决策变量。Aktürk等人[27]提出了考虑交换、延迟和调整巡航速度的飞机重新调度，其中起飞延迟和巡航时间是决策变量，如下所述。图7示出了该模型。情况I示出了航班f和随后的航班N f的原始时刻表。然后，在情况II中，将延迟组合巡航时间决策添加到原始调度xa2 f0; 1g;8a2A;8r2Rað14Þ航班f和航班N f的关系很容易获得，如下所示：zf2 f0; 1g;8f2F15rflftf-t0TAf≤dNflNf 16其中，N（f）是在原始飞行中运行飞行f之后的下一个飞行，其中，A是飞行器的集合;Ra是可以被分配给飞行器a的路线的集合;ca是将飞行器a分配给路线r的成本;dr是参数，如果路线r包含航班f，则该参数的值为1，否则该参数的值为0;并且xa是决策变量，如果飞行器a被分配给路线r，则该决策变量的值为1，否则该决策变量的值为0。Eq中的目标函数（11）目标是最小化分配成本和取消成本。Eq.中的资源利用约束（12）意味着每架飞机可以运行一条航线。路由r的起点和目的地对应于恢复开始和结束的站点。方程中的飞行覆盖约束。（13）注明每个航班只有一架飞机覆盖，如无飞机应取消该航班。表1总结了基于弧和基于路径的模型的特征。与基于弧的模型相比，基于路径的模型具有更少的约束条件，但更多的可能路线。由于取消和延迟是最常见的恢复操作，我们应该分析它们的公式。在基于弧和基于路径的模型中，取消由取消变量表示。然而，延迟有多种表现形式，详见第3.3。t0是航班的原始到达时间见图7。交换航班关系的插图。I.原始时刻表，其中航班N（f）在航班f之后。二.考虑航班延误和缩短巡航时间的时刻表。三.考虑延误、减少巡航时间和交换的计划，其中航班f与航班j交换。 df：航班f的预定起飞时间;rf：航班f的预定到达时间; TAf：航班f的周转时间;lf：航班f的起飞延误时间;lj：航班j的起飞延误时间;t0：运营航班f的飞机的原巡航时间;tf：运营航班f的飞机的巡航时间;tj：运营航班j的飞机的巡航时间;N（f）：原时刻表中运营航班f之后的下一个航班; dN（f）：航班N（f）的预定起飞时间;lN（f）：航班N（f）的起飞延误时间。Y. Su，K. Xie，H. Wang等人工程7（2021）435440Jð Þð ÞX X/x ≤A;8s2S≤18sSrjljtj-t0TAj飞行器操作航班f的巡航时间; TA f是航班f的周转时间; I f是航班f的出发延迟时间; T f是飞行器操作航班f的巡航时间; dN（f）是航班N（f）的预定出发时间;以及I N（f）是航班N（f）的出发延迟时间。当量（16）表示如果航班f和j不交换，则N f的实际出发时间取决于航班f的实际到达时间。否则，如图7的情况III所示，在交换之后，航班Nf跟随航班j。航班N的实际起飞时间由r jl jt j-t0TA j给出。因此，Eq。（17）表示航班N f跟随航班f或航班j。Aktürk等人提出的模型。[27]建立了一个圆锥二次混合整数规划，可以使用CPLEX求解。平均需要196秒来解决207个航班和60架飞机的实例，恢复期为一天。你好，我是说。-Xxfj！þ在每个子问题中，利用资源受限的基本最短路径来在3603 s内求解了16架飞机、242次7d飞行、飞机比为18.4的实际飞行实例。Liang等人[26]在连接网络上使用基于路径的模型来确定维护要求除了Eggenberg等人[24]使用的消耗资源概念外，计划维护操作可以互换。只有当飞机属于同一机队类型并且满足资源限制时，才能进行交换维护交换提高了恢复的灵活性，增加了找到更好恢复解决方案的可能性同样，使用了具有资源约束最短路径的列生成。三个额外的标签，即总飞行时间，起飞和降落的次数，和经过的时间被认为是sidered在多标签最短路径算法。与固定维护相比，灵活维护可回收成本F.XJj2S f;j2S fxf;j≤dNflNfð17Þ下降了61.47%。提出了一种基于弧的考虑维修的模型，Vink等人[21].考虑两种类型的维护操作。一种是计划性维护，很难更改为其中S（f）是可以与航班f和xf交换的航班的集合，j是决策变量，如果航班f和j交换，则值为1，否则值为0。Liang等人[26]提出了一种用于机场交通控制的自适应延迟方法，其中特定机场的出发或到达数量被限制在某些时隙中。这可以通过在等式中引入约束（18）基于路径的模型。r一sRa2Ar2Ra其中R是路由R使用的时隙S的数量。这个问题是解决使用列生成与多标签最短路径算法为相应的定价子问题。两个标签，指的是成本和延迟，被认为是在最短路径问题中，在搜索过程中去除支配路径。为了确保子问题的最优性，受影响的航班在每个时隙的开始和结束处重复。最大的评估情况下，空中交通管制中断超过2小时和意外维修超过8小时的638个航班和44架飞机在356 s内优化3.4. 恢复与维护在 飞 机 回 收 过 程 中 ， 维 修 通 常 被 看 作 是 一 项 固 定 的 活 动Eggenberg等人[24]将维护视为一个消耗资源和更新的过程。列生成，另一时间或电台（例如，当两个维护操作之间的最大经过时间接近达到时）。这种维护必须按计划在飞机上进行。另一种维修方式提供了多种时间和空间选择，并且至少选择一个选项来满足路线中的维修要求。表2[144. 机组恢复在介绍机组恢复之前，我们简要介绍了机组调度，以提供一些必要概念的背景。机组调度包括在给定时间段内安排一组飞行任务（例如，15或30 d），以便每次飞行可以由一个或多个船员操作。船员只有在适当合格的情况下才能操作船队。因此，航班按机队分组，机组调度分别为每个机队解决。此外，船员的日程安排应遵守管理机构和工会的规定，以确保安全性和可操作性。与机组调度相比，机组恢复涉及较少的机场和较短的调度时间，显着减少了问题的规模。为了充分利用这一小规模问题，恢复期内未涉及的飞行通常被视为固定活动。因此，船员恢复的目的是找到一个解决方案，表2飞机回收进场的特点及解决方法作者年模型延迟多舰队维护求解方法Jarrah等人[28]第二十八届1993基于弧由就绪时间没有没有网络流算法Yan等[14，15]1996年、1997年基于弧-没有没有拉格朗日松弛+次梯度Argüello等人[22日]1997基于路径在路径是的没有把握Thengvall等人[18]2000基于弧复制航班没有没有求解器Bard等[17个]2001基于弧由就绪时间没有没有求解器Thengvall等人[19，29]2001年、2003年基于弧复制航班是的没有拉格朗日松弛+次梯度Rosenberger等人[23日]2003基于路径在路径没有是的飞机选择+求解器安德森和Värbrand[6]2004基于弧由就绪时间没有没有Dantzig–Wolfe安德森[30]2006-在路径是的没有禁忌搜索和模拟退火Liu等人[三十一]2008-由就绪时间是的没有多目标遗传算法Eggenberg等人[24日]2010基于路径复制航班没有是的列生成+多标签最短路径Aktürk等人[27]2014-决策变量是的没有求解器Vos等人[20个]2015基于弧复制航班没有是的飞机选择+求解器Wu等人[25日]2017基于路径在路径没有没有分布式定点计算Liang等人[26日]2018基于路径自适应延迟没有是的列生成+多标签最短路径Vink等人[21日]2020基于弧复制航班是的是的飞机选择+求解器GRASP：贪婪随机自适应搜索程序。Y. Su，K. Xie，H. Wang等人工程7（2021）435441p;qp;qKKw;pppFupFup;q;p pFKp;;u; ppFFs： t：X Xbxzf-sf¼ 1;8f2F20XXB --x ≥dwj8j;p将可用机组重新分配到受影响航班的最低成本，而机组开始和结束于给定的固定活动[32]。与机组调度类似，机组恢复问题通常建立在一个单一的舰队网络。适用的劳动法规三个等级：船长、大副和二副。为了获得一个现实的解决方案，Medard和Sawhney[38]考虑通过修改方程来进行多秩扩展。（20）在Eq. （25）.在恢复过程中应遵守计划此外，preas-应反映已签署的活动，如休假和培训X Xbpxkk2Kp2P≥nfq;8f2F;8q2Qf<$25在康复Teodorovic和Stojkovic[33]是第一个开发机甲的人。nism以解决日常操作中的船员恢复问题。他们采用两种方法来构建船员职责，即，其中Q是等级的集合，其中Qf表示飞行f所需的等级;nf，q是飞行f的等级q所需的机组成员的最小数量;并且xk是具有值1的决策变量，如果先进先出计划和动态规划，以最大限度地减少机组人员的地面时间然而，问题的最优性随后的研究应用优化来解决机组人员的恢复问题。下面，我们提出了一个通用的船员恢复模型，以及扩展和相应的方法。4.1. 机组人员回收Weietal. [32]，Stojkovic'etal. [34]，Lettovsky'etal. [35]、Yuetal.[36]和Guo et al.[37]使用集合划分模型来解决机组人员恢复问题。下面，我们详细介绍了Lettovsky'etal.提出的公式。[35 ]第35段。模型3：机组恢复minX Xck xkXcf zfXcDsfXqvk19k2Kp2Pf2Ff2Fk2KPKF pk2Kp2PXxkvk¼1;8k2k21等级q的机组k被分配给配对p，否则值为0。由方程式现在，xk反映秩q的信息。这组约束确保满足具有不同级别的成员的最小数量。4.2. 机组人员恢复期机组人员的恢复也会影响航班延误。斯托伊科维奇和苏米斯[39]在构建可行配对时考虑航班延误。此外，一组约束，以保护乘客连接被添加到主问题。Kj; pw; pp;k2Kp2P其中b k是由机组人员k操作的航班j的起飞时间，配对p;bk是机组人员操作的航班wk; W是包含在飞机航线或乘客连接中的有序航班对（w，j）的集合。如果arc（w，j）在飞机航线中，则dw;j<$blw<$gw，indicat-即块时间（blw）加上周转时间（gw）。 如果在弧（w，j）上有一个重要的乘客连接，则d wj<$bl w<$c wj，p2Pxk2 f0; 1g;k2K;p2P22sf2;zf2 f 0; 1g;f2F23vk2 f0; 1g;k2K24其中K是机组的集合;P是配对的集合;ck是将机组k分配给配对p的成本;cD是航班f的空驶成本;qk是指示阻塞时间加上乘客连接时间（cw，j）。等式中的飞行优先约束（26）通过限制配对中的连续航班之间的时间来保护飞机连接和乘客连接。Stojkovic和Soumis[40]通过添加同步约束开发了一个多秩模型来自原始飞行的一组副本（定义为任务）表示不同的等级要求。由于这些任务属于同一飞行，Eq. （27）被添加到Stojkovic和Soumis的模型中[39]。F空闲机组的成本k;bp是具有值1的参数，如果对-ingp包含航班f，否则值为0;xk是决策Xk2KTkafTf;8f2F;8u2Nf 27如果机组k被分配给配对p，则变量值为1，否则值为0;如果机组k没有分配，则vk是决策变量，值为1，否则值为0;以及该模型考虑了覆盖约束和分配约束。Eq中的目标函数（19）旨在最小化配对成本，取消成本，空驶成本和空闲成本其中af是航班f的最早起飞时间;Tf是Tk是由机组k操作的任务u的出发时间;并且Nf表示与飞行f相关联的任务集合。当量（27）确保与航班f相关联的每个任务具有相同的出发时间。列生成用于解决多秩机组配对问题，并将同步约束添加当量（27）改写如下：船员。当量（20）表示一个航班可以覆盖超过一次，剩余覆盖率标识航班数量f用于空驶。如果f航班不能被覆盖，X Xbkk2Kp2Pxk1/2aT;8f2F;8u2Nð28Þ变量zf具有值1并且引起相应的取消成本。当量（21）表示一个机组最多只能操作一对。Wei等人。[32]使用启发式算法求解上述公式，其中使用时空网络上的最短路径算法生成一组配对该模型通过对飞行弧段设置不同的费用，以寻求一个与原计划偏差最小的可行计划。评估了两天内6个机场，51个航班和18个配对的实例。 计算时间从1秒到6秒不等此外，在行动解决方案中应考虑机组人员的结构。船员通常分为该模型适用于美国国内航班的数据。一个实例的190个航班，包括46个和20个航班的灵活和固定的出发时间，分别进行了评估。每次飞行需要5名机组人员，涉及的机组人数为97人。这一案件在1237年得到解决Abdelghany等人[41]使用贪婪启发式迭代解决机组人员恢复问题。 中断航班被分为不同的阶段，其中航班是资源独立的，如图所示。8.第八条。资源独立性是指在同一阶段中，各因此，在每次迭代中，使用以下公式将资源无关航班分配给可用机组。FY. Su，K. Xie，H. Wang等人工程7（2021）435442XXX见图8。 机组人员恢复的滚动框架。xk;f;q1;8f2F;q2Qfk2Kxk;f;q≤1;8k2K30f2F q 2Qfdtf-ak xk;f;q≥ 0;8f2F;q2Qf;k2K<$31Ωdtf-df≥ 0;8f2F32在f≤vkxk;f;q;8f2F;q2Qf;k2K<$33时在f¼dtf blf;8f2F34其中df是航班f的预定起飞时间;blf是航班f的预定轮挡时间;ak是机组k的准备时间;vk是满足机组k;xk，f，q是决策变量，如果机组人员k被分配给位置q的航班f，则决策变量的值为1; dtf是航班f的实际出发时间;以及Atf是航班f的实际到达时间。等式（29）和（30）确保航班的覆盖范围，每个机组人员最多有一个级别。方程中的约束条件（31）和（32）表示实际起飞时间不应早于预定起飞时间和机组准备就绪时间。在Eq. （33）保证到达时间不超过值班时限。在Eq. （34）表示出发和到达时间之间的关系。来自美国主要航空公司的数据，恢复时间为8小时，121名机组人员，在1分51秒内解决。虽然这种滚动框架不能检索到全局最优解，但该解是实用的，并且可以实时获得。为了限制模型大小并加快恢复速度，Lettovsky'etal.[35]将恢复期内的部分配对划分为分段。图9中示出了部分配对。任务2中的飞行被分成由一个或多个飞行段组成的段。覆盖的是分段而不是航班，从而减少了模型中的行使用分段可以减少生成的配对的数量和计算时间。4.3. 机组恢复问题的解决方法机组人员恢复的一般模型包括很少的约束条件，但大量的变量，因此，大多数恢复方法是使用列生成解决列生成是一种有效的方法，避免了显式枚举所有变量，同时保持线性规划松弛的最优性。在列生成的情况下，在子问题中生成乘员k的路径，并且在主问题中获得用于恢复的最优路径集合。虽然在Refs中的问题。[34，35，38，40-表3[325. 统筹恢复在本节中，我们将介绍集成不同资源以执行恢复的特性和注意事项5.1. 飞机和机组人员综合回收飞机和机组人员在恢复过程中发挥着重要作用，前者是航空公司最稀缺的资源。复杂的约束条件和庞大的问题规模阻碍了这两种资源的集成建模。5.1.1. 基础环节航班取消和延误决策提供了飞机和机组人员恢复问题之间的基本联系[45如第3节和第4所述，飞机和机组人员的基本模型见图9。 段的图示。段1包含一个飞行（即，段2），而段2包括两个段（即，航班3和航班4）。Y. Su，K. Xie，H. Wang等人工程7（2021）435443X≤x;8f;g2 Conn;8k 2 K37Ff;rf;pFf;g f;goo;f;gf;g表3机组回收进场的特点及解决方法作者年施工基本要素求解方法特奥多罗维奇和斯托伊科维奇[33]1995飞行先进先出与动态规划Wei等人[32个]1997飞行深度优先搜索+B BStojkovic 'et al. [34个]1998占空列生成+资源受限最短路径+B BLettovsky'etal.[35]第三十五届2000段列生成+斯托伊科维奇和苏米斯[39]2001飞行列生成+资源受限最短路径+B BYu等人[36个]2003飞行深度优先搜索+B BAbdelghany等人[41个]2004飞行滚动优化Guo等人[37个]2005飞行遗传算法+局部搜索斯托伊科维奇和苏米斯[40]2005飞行列生成+资源受限最短路径+B BNissen和Haase[43]2006占空列生成+资源受限最短路径+B B[38]第三十八话2007飞行列生成/深度优先搜索+求解器[44]第四十四话2012占空遗传算法B B：分支和绑定。回收具有公共变量zf，其表示飞行的回收。在此网络上建立了资源相容性模型，并将资源相容性约束表示为Eq.（三十七）.Maher[50]通过关注飞机和机组人员使用连接网络进行恢复。该网络使用航班副本来表示不同的延误。他为飞机整合了一个基于路径的模型Kf;g一f;ga2Ak恢复和一般模型的机组恢复通过添加延迟一致性约束。其中，Conn是节点f和g之间的弧的集合，（f，g）;Ak是机组人员k可以操作的飞机的集合;并且X Xbk;vxk-sv-X Xba;vxa¼0;8f2F;8v2Uð35ÞOf;g 是决策变量，如果资源o覆盖，则其值为1k2Kp2Dkf;ppFa2Ar2Raf;rRfarc（f，g），否则为0当资源是飞行器时该变量由xA表示。当资源是工作组时，其中Uf是由副本v索引的航班f的离散副本的集合;Dk是可以分配给船员k的职责集合;ba;v是参数，如果航线R上的航班F包含飞行器A的航班F的副本V，则该参数的值为1，否则该参数的值为0;BK;V是如果值班P上的航班F包含机组K的航班F的副本V，则该参数的值为1，否则该参数的值为0;以及SV是在航班F的副本V上的机组空驶操作的次数。在Eq.（35）确保机组人员和飞机在每次航班上的延误此外，延迟一致性约束的数量根据输入路径和