基于改进遗传算法的长期飞机检修规划编排

Long-Term Aircraft Maintenance Planning and Arrangement Based on Improved Genetic Algorithm

摘要: 长期飞机检修计划编排问题根据飞机的检修参数与维修能力，为机队指定3~5年内的大型检修计划。大型检修计划作为飞机维护运营计划的基础，侧重于满足各类维修资源限制并尽可能减少维修次数，有利于航空公司合理分配飞机检修时间安排，以保障航班正常运行，提高机组利用率，增加运营收入。由于时间周期较长，约束较为复杂，提出了一种遗传算法结合邻域搜索算子的启发式算法，实验结果表明，GA-NS算法在解决大规模问题方面表现出了较好的效率和准确性，为航空业提供了更科学的维修计划设计方法，有望提高服务质量，提升运营效率。

Abstract: The long-term aircraft maintenance planning problem involves specifying a comprehensive maintenance schedule for a fleet over 3~5 years, considering aircraft maintenance parameters and capabilities. This planning, as the foundation of aircraft maintenance operations, focuses on meeting various maintenance resource constraints while minimizing the number of maintenance events. It aids airlines in efficiently allocating aircraft maintenance schedules to ensure normal flight operations, enhance crew utilization, and increase operational revenue. Given the extended planning horizon and complex constraints, a heuristic algorithm combining a genetic algorithm with neighborhood search operators, GA-NS, is proposed. Experimental results demonstrate that the GA-NS algorithm exhibits high efficiency and accuracy in addressing large-scale problems. It offers the aviation industry a more scientifically informed approach to maintenance planning, with the potential to enhance service quality and operational efficiency.

1. 引言

民航业具有运营成本高、利润率低、竞争性强等特征，其运营管理问题无论从理论还是实践角度都得到了广泛关注。孙宏等的研究 [1] 显示，航空公司的总成本包括燃油/滑油成本、机场服务成本、航路成本、机组成本和飞机维修成本等。值得关注的是，飞机维修费用是航空公司的主要运营成本之一，在资产负债表中扮演着重要的角色。根据国际航空运输协会(International Air Transport Association，简称IATA)的航空公司维护成本官方报告 [2] ，2020年全球飞机检修维护费用支出约为500亿美元，占据航空公司总运营成本的10.5%。此外，根据Oliverwyman的报告 [3] ，预计全球飞机维修需求将持续增长，预计到2030年将超过1100亿美元。因此，对于航空公司来说，不断优化关于飞机维护的时间安排、降低维护运营成本可以为航空公司节省大量开支，起到增加利润的作用。随着越来越多廉价航空公司的出现，航空业价格竞争的压力日益增加，航空公司降低机组成本的重要性更是日益显著。

当前许多航空公司仍在依赖人工编制飞机维修计划。随着飞机规模和航线网络的迅猛扩张，人工排程显然已经无法满足航空公司的需求。低质量的解决方案可能导致飞机在服役期间的维修频率明显超出实际需求，从而减少飞机的可用时间。与此同时，不合理的维修间隔也可能导致维修资源得不到充分利用。飞机利用率的下降和维修成本的增加可能对航空公司的收益产生负面影响。高昂的维修成本使得航空公司迫切希望以更为高效的方式制定飞机的维修计划，以提高飞机的可用性。除了定期维护之外，更多的维修工作具有不确定性，如飞机故障难以预测，这会干扰维修工作的内容和时间安排 [4] 。根据Reményi在2014年的研究 [5] ，近50%的维修公司表示，维修工作的内容存在40%到59%的不确定性。因此，运用计算机技术和数学方法对飞机维修计划进行自动排程具有重要的研究价值和实际意义。

根据维修计划编排提前期长短，维修计划可分为长期编排、中期编排以及短期编排种类型。不同维修计划在优化目标和所受限制上有所不同。由于C检的间隔约为18到24个月，而D检通常每5至6年安排一次 [6] ，长期计划编排基本不会考虑具体的航班，侧重于在满足各类维修资源限制(人员、设备和场地容量)和维修间隔的情况下，尽可能减少维修次数以最小化成本。由于长期维修计划编排的频率低，且对制定计划的时间没有实时性要求，目前的研究主要集中于短期维护路径规划。然而，对于短期维护计划的优化会导致贪婪的策略，尽可能地将小型定检推迟到到期日。这种推迟的检查可能在接下来的一两个月内不会导致任何维护能力问题。但是随着时间的推移，后续的检查可能会堆积起来，导致未来维护需求激增。

1977年，加拿大航空公司率先开发了一种决策支持系统，用于长期飞机维修计划，将其机队未来5年内的C检计划时间从三周缩减到数小时 [7] 。Steiner提出了一种多目标的启发式算法，该算法根据不同的机型和限制，在5到15分钟内生成可行的维修计划 [8] 。Li将维修任务的最优组合问题转化为一个聚类问题，并应用单纯形法进行求解 [9] 。Yan等人于2008年针对长期维修计划建立了一个0~1整数规划模型，综合多个优化目标使用加权法，并通过商业求解器CPLEX进行了实证研究 [10] 。Deng等人在2020年提出了一种基于动态规划的方法来解决长期飞机维修计划编排问题，该方法考虑了飞机检修约束以及特定日期的维护能力差异，其目标是最小化检查之间的飞行时间浪费，以提高飞机长期运营能力，增加收入 [11] 。在2022年，van der Weide等人提出了一种min-max场景优化模型，旨在最小化飞机大修期间尚未使用的飞行时间总和 [12] 。同年，Deng等人考虑了检修持续时间以及飞机日常使用率的不确定性，首次提出了一种混合前瞻调度策略的近似动态规划方法 [13] 。

本研究聚焦于长期飞机维修计划问题，研究在飞机检修标准中，对于各级检修之间的飞时、工作日、飞行循环具有明确限制、检修机库具有容量限制与资源限制等前提条件下，旨在研究如何妥善制定长期大型飞机维修计划，以合理分配飞机检修时间，以确保航班正常运行的同时，最大程度地减少飞机定期检查的数量，以提高机组利用率并增加运营收入。

2. 飞机维修计划编排问题

2.1. 问题描述

基于对实际业务的调研结果，本研究在长期鲁棒飞机检修计划问题中考虑了多个关键因素，包括各机型的检修参数规则、不同时间段的检修能力设定、飞机的日常运行情况，以及使用额外可用检修机库所涉及的成本等。由于长期飞机检修计划的主要目标是在最小化检修成本的同时最大化盈利，因此，本文制定了以下目标函数评价指标：

1) 最小化未使用的飞行小时：这一目标的优化有助于更有效地规划检修间隔，从而间接减少长期维护检查的次数，减少计划期间的停飞时间。这有助于最大程度地利用所有飞机，使其投入商业运营，从而提高盈利。

2) 最小化飞机违反维修约束引发停飞时间：由于飞机停飞会导致显著的商业损失，因此，重要的是确保飞机能够满足维修约束条件，以避免停飞。

3) 最小化额外机库使用数量：降低额外的检修工作分配给第三方外包企业或支付技工额外加班费用所带来的高额成本，本文的基本假设如下：① 一次C检连续占用同一个机库。② 最小步长为1个日历日。③ 不考虑机库位置影响。④ 飞行寿命到期时不允许继续飞行，增加额外机库进行检修。⑤ 仅考虑C检(D检可化为更高等级的C检进行规划)。

2.2. 模型符号

基于上述问题描述，本文提出了长期飞机检修计划的MILP (混合整数规划)模型。

数学模型的符号说明如下：

集合说明：

$I$ ：飞机集合，下标为i；

$J_i$ ：飞机i的预计C检集合，下标为j；

$T$ ：时间步长集合，下标为t；

$P$ ：飞机运行参数集合，取值为 $\left\{FH,FC,DY\right\}$ ，分别代表飞行时间，起落循环以及日历日。

参数说明：

$I_i^P$ ：飞机i的P类参数最大可允许积累阈值；

$U_{i,t}^P$ ：飞机i的P类参数在时间点t的积累量(其中 $P=DY$ 时固定为1)；

$d_{i,j}\left(t\right)$ ：飞机i在t时刻进行j次C检时，考虑节假日休息后总共需要的天数；

$L_t$ ：t时刻可用机库数量；

$C_E$ ：使用额外机库的单位惩罚；

$C_C$ ：C检一次的固定成本；

$M$ ：足够大的常数。

决策变量：

$x_{i,j,t}$ ：0~1变量，飞机i在时间t开始第j次C检则取1，否则为0；

$y_{i,t}^P$ ：连续变量，飞机i在时间t的参数P的值；

$Z_{i,j,t}^{FH}$ ：连续变量，若飞机i在时间t开始第j次C检则为 $y_{i,t}^{FH}$ ，否则为0；

$m_{i,t}$ ：0~1变量，飞机i在时间t正在进行检修取1，否则为0；

$E_t$ ：整数变量，时间t使用的额外机库数量。

2.3. 数学模型

本文的数学模型如下：

$\min \underset{i\in I}{{\displaystyle \sum }}\underset{j\in J}{{\displaystyle \sum }}\underset{t\in T}{{\displaystyle \sum }}\left(I_i^{FH}\cdot x_{i,j,t}-Z_{i,j,t}^{FH}+C_C\cdot x_{i,j,t}\right)+\underset{t\in T}{{\displaystyle \sum }}{E}_t\cdot C_E$ (1)

Subject to：

$Z_{i,j,t}^{FH}\le x_{i,j,t}\cdot I_i^{FH}\forall i\in I,j\in J_i,t\in T$ (2)

$Z_{i,j,t}^{FH}\le y_{i,t}^{FH}\forall i\in I,j\in J_i,t\in T$ (3)

$Z_{i,j,t}^{FH}\ge \left(x_{i,j,t}-1\right)\cdot I_i^{FH}+y_{i,t}^{FH}\forall i\in I,j\in J_i,t\in T$ (4)

$y_{i,t}^P\le I_i^P\forall i\in I,t\in T,P\in \left\{FH,FC,DY\right\}$ (5)

$y_{i,t+1}^P\ge y_{i,t}^P+U_{i,t}^P-M\cdot m_{i,t}\forall i\in I,t\in \left[1,T-1\right],P\in \left\{FH,FC,DY\right\}$ (6)

$y_{i,t+1}^P\le y_{i,t}^P+U_{i,t}^P\forall i\in I,t\in \left[1,T-1\right],P\in \left\{FH,FC,DY\right\}$ (7)

$y_{i,t+1}^P\le M\left(1-m_{i,t}\right)\forall i\in I,t\in \left[1,T-1\right],P\in \left\{FH,FC,DY\right\}$ (8)

$\underset{t\in \left[t,t+d_{i,j}\left(t\right)\right)}{{\displaystyle \sum }}{m}_{i,t}\ge d_{i,j}\left(t\right)\cdot x_{i,j,t}\forall i\in I,j\in J_i,t\in T$ (9)

$m_{i,t}\le \underset{j\in J}{{\displaystyle \sum }}\underset{t\in \left[t-\underset{i,j,t}{\max }\underset{i,j,t}{\max }\left(d_{i,j}\left(t\right)\right),t\right]}{{\displaystyle \sum }}{x}_{i,j,t}\forall i\in I,t\in T$ (10)

$\underset{i\in I}{{\displaystyle \sum }}{m}_{i,t}\le L_t+E_t\forall t\in T$ (11)

$\underset{t\in T}{{\displaystyle \sum }}\left(x_{i,j+1,t}\cdot \left(t-M\right)\right)\ge \underset{t\in T}{{\displaystyle \sum }}\left(x_{i,j,t}\cdot t\right)-M\forall i\in I,j\in \left[1,J_i-1\right]$ (12)

$\underset{t\in T}{{\displaystyle \sum }}{x}_{i,j,t}\ge \underset{t\in T}{{\displaystyle \sum }}{x}_{i,j+1,t}\forall i\in I,j\in \left[1,J_i-1\right]$ (13)

$\underset{t\in T}{{\displaystyle \sum }}{x}_{i,j,t}\le 1\forall i\in I,j\in J_i$ (14)

目标函数(1)最小化所有场景下惩罚函数。目标函数分三部分，由未使用的飞时、飞机总维修次数的成本以及额外机库使用成本组成。约束(2)至(4)引入辅助变量 $Z_{i,j,t}^{FH}$ ，约束若飞机i在时间t开始第j次C检则其取值为 $y_{i,t}^{FH}$ ，否则为0，方便计算目标函数中未使用的飞时部分。约束(5)为检修参数约束，同一飞机两次检修之间的飞时、飞行周期与工作日均不能超过规定值。约束(6)至(8)为参数更新约束，若当日进行本次检修，则飞时、飞行周期与工作日清零，若正在进行检修则当日不增加飞时、飞行周期与工作日计数。约束(9)至(11)为检修机库的占用约束，飞机在检修过程中停飞，且占用一个机库。约束(12)至(13)确定了检修应按次序进行规划。约束(14)限制每次检修仅安排一次。

3. 求解算法

本文提出了一种结合邻域搜索的遗传算法(GA-NS)，用来快速高效地解决长期飞机检修规划问题。该方法结合了遗传算法的多种群搜索特性以及邻域搜索的针对性设计算子的优点，可以做到准确高效地进行求解。

3.1. 编码方式

本文采用了二维数组编码方式，其中每个飞机的开始检修时间直接表示为数组元素的值。如果在求解期限内不计划安排特定次数的检修，相关位置则用−1表示。举例来说，如果飞机1的编码为[15, 656, 1008, −1]，那么这代表飞机1将在第15天、第656天和第1008天分别进行3次C检修，而在求解过程中不会安排第四次检修。

3.2. 适应值计算

适应值即为(1)式。在算法运行过程中，需要编写仿真程序来计算适应值。仿真程序通过逐日模拟飞机的使用情况和检修情况，对飞机使用参数进行实时更新。如果飞机的参数超出了事先设定的阈值，或者解中安排了该飞机的检修，那么在仿真中会对这架飞机进行检修，并记录浪费的飞行时间情况。仿真过程结束后，我们对各项统计数据进行汇总和求和，从而获得适应值。

3.3. 初始解生成

使用随机ε-贪心算法逐个生成初始解，直到种群规模达到预设参数n_population。该算法基于仿真程序运行，输入扰动参数ε (如0.9)，每次生成范围在 $\left[\epsilon ,1\right]$ 之间的随机数α。在时间点t对所有飞机依次判断，若检测到 $y_{i,t}^{FC}+U_{i,t}^{FC}\ge I_i^{FC}\times \alpha$ (FH与DY同理)，即可认为若在该时间点不安排检修，在下个时间点之前飞机有较大概率超出参数，将有停飞风险。因此，在这种情况下安排该飞机进行检修。

3.4. 选择过程

选择过程分为两个部分。第一步按照种群适应值降序进行排序，取n_Best个最优的个体直接进入下一代。第二步使用k-tournament选择方式，例如k取3，即每次从上一代种群中随机抽取3只个体，适应值最优者进入下一代的父代池，直至新生成的父代池与种群数量相同。

3.5. 交叉过程

使用均匀交叉算子，输入交叉率λ_crossover，将父代池中的个体两两配对。在 $\left(1-{\lambda }_{\text{crossover}}\right)$ 的概率下维持父代解不变，直接遗传给下一代；在λ_crossover的概率下二者均匀打乱，生成两个新子代。均匀交叉的示例如图1所示，父代1和父代2按照飞机为单位相互分配，每架飞机均有相同的概率分配给两个子代。

Figure 1. Example of uniform crossing

图1. 均匀交叉示例

3.6. 变异过程

变异过程结合了邻域搜索算法的Destroy & Repair算子，即基于现有规划，将部分飞机的检修计划删除，再利用一定的规则重新修复，可以定向在当前解的邻域内进行探索。

Destroy算子共有3种，目标均是将机队分为S_remove和S_fix两部分，S_fix中飞机的求解计划固定，而S_remove中的飞机求解计划将会被完全删除，并在repair步骤中修复。1) 随机删除。随机删除一部分飞机的所有检修规划。2) 较差删除。将不同飞机浪费飞时进行降序排列，删除浪费飞时较多的若干架飞机的所有检修规划。3) Shaw-removal删除。首先随机选择一架飞机，将其检修计划中的时间向量 $t_0$ 全部取出，对于检修时间与 $t_0$ 中的任意一项差距在nWidth以内的飞机也会进入到S_remove中。三种算子各自侧重不同，随机删除注重邻域搜索的随机性；较差删除尝试解决该求解框架下部分飞机计划的调优问题；而Shaw-removal删除则会将耦合起来的飞机检修计划完全拆解并重新进行计算，有助于跳出局部最优解。

Repair算子共有2种，分别为基于飞机优先级的回溯搜索与基于日期的贪心并行修复。

基于飞机优先级的回溯搜索修复步骤如下：

Step 1. 将S_remove中的飞机随机排序，确认修复优先级。

Step 2. 对于优先级最高的飞机i：固定S_fix中飞机的修复方案，直到S_remove为空，算法结束。

Step 3. 针对飞机i，运行参数ε设置为1的ε-贪心算法，直至寻找到需要检修的时间 $t_0$ ，若规划时间结束，将飞机i从S_remove中取出，放置到S_fix中，回到步骤2。

Step 4. 在 $\left[t_0-t_{\text{search}},t_0\right]$ 的时间范围邻域内(t_search为时间邻域大小)，逐个尝试，找到不额外增加机库使用数量且浪费飞时最少的安排检修时间t_opt，回到步骤3。

基于日期的贪心并行修复步骤如下：

Step 1. 固定S_fix中飞机的修复方案。

Step 2. 针对S_remove运行参数ε设置为1的ε-贪心算法，每个时间步长t检查S_remove中飞机的参数情况，若超出阈值直接安排检修。

3.7. 终止条件

终止条件设置为算法达到最大迭代次数It_max，或者超过It_noImprove次迭代后最优解仍然不变。

4. 数值实验

4.1. 算例介绍

本文选取的实验数据来自Deng等人公布的欧洲一家航空公司的实际数据集 [11] ，包括2个在为期3年内，分别有40、45架飞机的实例。数据集包括飞机数据，即飞机型号、初始使用参数、各月平均飞时统计、C检进度情况、飞机参数C检间隔要求，也包括检修数据，即节假日/周末安排(不安排检修)、各项C检历史耗时情况等。通过限制机队规模以及可用检修机位数量，设置了16组时间步长为1周的小算例以及8组时间步长为1天的大算例。

4.2. 参数设置

由于停飞或临时调用第三方服务商的检修机库会导致较高的经济成本，因此在目标函数中，C_E设置为较高的10⁴， $C_C$ 作为正常的检修操作，成本较低，设置为100。

对本文提出的MILP模型的直接求解采用C++编程和调用Gurobi9.5.2求解器实现，并在一台搭载了AMD Ryzen 7 5800H的8核16线程处理器和Window 11操作系统的电脑上进行实验，求解器其余设置均为默认。在步长为一周的小算例下，限制最长计算时间为600秒，在步长为1天的大算例下，限制最长计算时间为7200秒。

对本文提出的启发式算法，采用C++编程在同一台机器上进行编程实现。算法采用单线程运行，每个算例运行3次取最优值。种群大小n_population设置为50；ε-贪心算法中ε取0.9；选择过程中n_Best取4，k取3；交叉率λ_crossover取0.6；每架飞机变异概率为0.1，等概率使用不同Destroy & Repair算子相结合；最大迭代次数It_max取100；提前终止条件为It_noImprove次迭代后最优解未发生改变。

4.3. 实验结果

小算例的实验结果如表1所示。其中GA-NS代表结合邻域搜索的遗传算法。表格的前三列包含了算例的基本信息，具体涵盖规划周期、机队规模以及可用机库数等。计算信息包括计算时间，最优目标函数以及求解结果与求解器提供的bound的百分比差距gap。实验数据显示，在以周为单位的小算例下，Gurobi求解器与GA-NS在绝大多数算例下可以求出最优解。但随着需要规划的机组数量提升，求解器的求解时间迅速增加，在算例4中无法在600 s的时间内求出最优解，同样，由于算例4的机库数量设置较少，GA-NS算法也只能求出次优解。而在当前的参数设置下，GA-NS可以在一分钟内解决小算例的优化求解问题，但在极端算例情况下只能求出次优解。

Table 1. Experimental results of small examples

表1. 小算例实验结果

大算例的实验结果如表2所示。在大算例下Gurobi的求解时间迅速增加，在3个30个及以上的机队规模算例求解过程中，无法在2小时内求出可行解。而当前参数下GA-NS算法求解所有算例时均可在2分钟内收敛，某些极端算例情况下的gap较大是由于Gurobi求解器的计算限制，并没有在2小时内求出可行下界，从而导致gap数值较大。数值实验结果证明了GA算法在计算效率与求解质量上的优势。

Table 2. Experimental results of big examples

表2. 大算例实验结果

5. 总结

本文针对长期飞机检修规划问题，提出了一种结合邻域搜索算子的遗传算法(GA-NS)。在充分考虑问题的结构和模型特征的基础上，本文对传统遗传算法的变异过程进行了有针对性的改进，并设计了多种专门针对问题的变异算子。这些算子在模型求解中得到了有效应用，为航空公司提供了高效的解决方案。

数值实验结果表明，当考虑了浪费飞行时间和额外机库成本时，GA-NS算法能够成功解决较大规模的问题。这不仅有助于提高航空公司的服务水平，还提升了运行效率，使航空公司能够更加科学地设计检修计划。该算法的成功应用为航空业提供了一种可行的、具有实际意义的解决方案。