基于航班环的机组排班优化

2023-11-24赵晋芳赵乔洋周松殷奥博

沈阳航空航天大学学报 2023年4期

赵晋芳，赵乔洋，周松，殷奥博

（沈阳航空航天大学 a.民用航空学院，b.机电工程学院，沈阳 110136）

航空公司机组排班问题是非确定性多项式（nondeterministic polynomially，NP）的整数规划问题。在民航运输业发展初期，由于航班少、机型单一、运行软件落后等问题，通常由人工完成排班操作，从而导致机组值勤超时、航班衔接不合理、航班延误等诸多问题。随着航空公司运力规模的扩大，国内民航事业的竞争也愈发激烈，因此合理运用计算机技术进行机组排班对提升航空公司的飞行运作效益和飞行管理水平具有重要意义。

目前，国外实际应用的机组排班软件主要分为两类，即公平性系统（equitability system）和竞标系统（bidding system）。Zeghal等［1］将机组排班问题分解为机组配对问题和工作制度建设问题，采用二进制和不完全分割问题的方法简化该问题，将其转化为整数线性规划问题。Anbil等［2］针对机组排班问题设计了TRIP算法，该算法通过三阶段分层求解并重复计算的方法满足约束条件。Kornilakis等［3］针对机组排班问题采用集合覆盖公式建模，并采用遗传算法求解。Kasirzadeh等［4］将个性化问题考虑到机组排班问题中，采用列生成算法进行求解。Fahle等［5］、Jiao等［6］、Antonova 等［7］采用列生成技术解决大规模优化的机组排班问题。

国内学者亦对机组排班问题开展了一些工作。范永俊等［8］提出了基于分支定界法解决飞机排班问题的方案。李耀华等［9］将车辆路径问题模型应用到航班串排班问题上，并利用单亲遗传算子的免疫算法对模型进行求解，得出VRP模型满足优化航班串排班问题。此外，李耀华等［10］在利用遗传算法解决排班问题时，还提出了通过控制染色体交叉和变异的概率快速求得优化可行解的方法。陶世群等［11］采用编码策略以及适应度函数将非平衡指派问题转化为组合优化问题，提出了一种基于遗传算法的多级目标非平衡指派问题的求解方法。张米［12］针对机组排班问题设计了可求解大规模机组排班问题的启发式列生成算法，并通过数值实验对算法的有效性进行了验证。潘海洋［13］采用罚函数法解决了机组排班问题中无初始解的情况，探索出高质量的初始列并用启发式搜索输入给列生成法，实现了对算法求解质量的优化。李青等［14］提出了排班问题的多目标优化模型，并应用改进的基于信息熵的自适应遗传算法求解该模型的最优解。邵俊［15］、王文璨等［16］、董宇楠等［17］针对机组任务配对问题，提出利用遗传算法和启发式搜索算法，高效产生可行的机组任务配对，充分考虑到机组任务配对中的排班法规和运营成本因素。

虽然国内诸多学者对机组排班问题开展了一些研究，但我国民航排班问题复杂，排班工作量较大，直接应用国外的排班软件会与国内的运行规范产生冲突，影响机组排班效率，因此需要根据我国实际情况对机组排班问题进行简化。为解决航班和机组人员匹配所面临的大规模决策问题，本文考虑将航班聚合形成航班环，将与机组人员形成匹配的基本单位由航班转变为航班环，即实现由航班—机组人员匹配向航班环—机组人员匹配的转变，将问题的决策单元确定为航班环和机组的匹配，以降低问题的基本决策单元维度，缩减决策空间。研究可分为两个阶段：第一阶段为航班环构建阶段，该阶段以获得可行的航班环集合为目标，将一个可行航班计划的生成过程转化为满足要求的航班环的搜索过程；第二阶段为航班环—机组人员匹配阶段，该阶段的目标为将现有驻地的飞行员与可行航班环相匹配，使得当日计划航班完成率最高。

1 问题描述与假设

1.1 问题描述

航空公司排班问题即对机组人员进行航班环的指派问题，需要在满足民航规章、公司运行规范的前提下，为机组指派到合适的航班环，并尽可能少地取消航班及尽量减少置位的次数。由于航空公司实际运营管理十分复杂，本研究规定问题中机长和副驾的资质均满足航班对机长和副驾驶要求、飞机型号均满足航班需求，且已明确航班、机组机长、副驾驶数量。

1.2 问题假设

（1）每个机组人员有一个固定驻地，以所在地机场表示；

（2）机组人员还可以执行置位任务，置位任务是指机组人员乘坐正常航班从一个机场摆渡到另一机场去执行飞行任务。

2 数学模型

2.1 目标函数

主要集合、参数和变量定义如表1所示。欲建立航班环模型，将原问题简化为航班环p与机组人员k的匹配问题，简称问题Q。问题Q的具体定义为：需要将满足配置的机组与某天的航班环集合P中的航班环p匹配。其中航班环p由多个航班（f1，f2，…，fn）组成，每段航班为一段接续链条，机组配置由一名机长i和一名副驾驶j组成。本文用a表示有满足配置的机组和航班环匹配，其定义式如式（1）所示。用决策变量xa表示a是否启用，启用取1，否则取0。

表1 集合、参数和变量定义

其中，目标函数需依编号次序满足：（1）尽可能多的航班满足机组配置；（2）尽可能少的总体置位次数。由此可知，两个目标函数具有不一样的优先级，且第一优先级的目标是使尽可能多的航班满足机组配置。

首先针对目标（1），运用决策变量yf来控制不能起飞的航班，若不能起飞为1，否则取0，可用式（2）表示最小化不能起飞的航班数

其次针对目标（2），要求尽可能少的机组置位次数，因此对所有匹配a的置位航班进行求和，为此定义了Fa即匹配a中的航班f集合，则总置位次数最小化表达如式（3）所示

考虑到∀f∈Fa，均有恒定的xa，且da fnf为常数。因此，式（2）可写为

由于问题Q为多目标函数优化问题，结合大M法理念［18］，为两个目标函数添加加权系数m1＞＞m2，将多目标问题转化为单目标优化问题。因此问题P表达如式（5）所示

2.2 约束条件

机组排班问题主要分为空间与时间的衔接约束和航班与机组的属性约束。

2.2.1 航班任务未完成的松弛约束

因机组排班的核心任务是完成每个航班任务，应有约束如式（6）所示

但由于式（6）引入判断是否满足机组配置的yf，式（6）可以被松弛为式（7），同时与目标函数式（5）中第一项协同控制，使得不能起飞的航班数最小化。

2.2.2 航班空间衔接约束

对于两段连续的航班f，将前段到达航班索引定义为h，后段离港航班索引定义为l。此外，定义前段航班到达机场时间为，后段离港航班出发时间为。由于航班的空间连贯关系，前段航班到达机场时间必须为后段航班离港时间。因此航班的空间衔接约束定义如式（8）所示

2.2.3 航班始发与终点空间约束

由于每个机组人员需从初始驻地出发并最终回到初始驻地，因此，在航班环建模中，针对所有从驻地始发的航班，都需与本文构造的虚拟起点相连接；同样的，针对所有终点到达驻地的航班，都需与本文构造的虚拟终点相连接。此外，针对机组人员的虚拟起点与终点必须是同一个机场。

定义一条航班环中最早的航班为f_min，最晚的航班为f_max。因此，该类约束表达如式（9）所示

2.2.4 最小过站时间约束和最长过站时间约束

由于民航局对最小过站时间有所规定，在此定义该最小过站时间标准为50 min）。此外，为避免飞机过站时间过长造成资源浪费，定义最长过站时间=100 min）。定义前段航班的到达时间为，后段航班的离港时间为。因此，航班最小过站时间约束和最长过站时间约束如式（10）和式（11）所示

2.2.5 航班—机组人员对应唯一性约束

由于置位情况的存在，为确保航班和机组唯一确定，定义航班f在航班环集P中出现次数为δf，则航班f的执飞次数用置位次数表达，如式（12）所示

因此有唯一性约束表达如式（13）所示

2.2.6 值勤时间约束

为保证航班的飞行安全，设置最大飞行值勤小时数为h值勤，飞行时间为h飞行，因此需引入约束如式（14）、（15）所示

2.2.7 航班约束

因最大航班受值勤小时数h值勤约束，因此需引入约束如式（16）所示

2.3 模型约简

综上所述，可以将原问题Q的模型总结如式（17）所示

由于问题Q仍然是组合爆炸问题，因此，定义两类机组人员的上限分别为εI、εII，每一个匹配a中两类机组人员出现的个数分别为φI、φII，因此需引入新约束如式（18）、（19）所示

3 算例分析

3.1 算例设置

本文研究的是某民营航空分公司机组某日的排班问题，其测试算例航班如表2所示。在本算例中，共有飞行机组人员24人，其中12人为机长资质，12人为副驾驶资质。飞行机组驻地为A、B两地和C、D、E 3个过站机场。其中A驻地共有机组人员12人，其中6人为机长资质，6人为副驾驶资质。B驻地共有飞行机组人员12人，其中6人为机长资质，6人为副驾驶资质。根据CCAR121手册查询出h值勤max=14 h，h飞行max=9 h，根据h值勤max可得pmax=4。

表2 测试算例航班

首先，为获取航班环集合P，将提供的航班信息转换成一个有向图，如图1所示，其中每个节点代表不同的航班，每个节点包含有航班的起止机场与时间信息。每根连接线都代表节点与节点之间的合法连接，需要满足包括时间、地点等的约束。如图1所示，3个航班树相互连接，形成了一个航班网络结构。航班1的可合法连接航班包括1-2、1-3、1-4以及1-5，航班2的合法连接包括2-3、2-4及2-5；航班5则能够与航班6及航班3合法连接。通过搜索可从航班1的航班树连接航班5的航班树，从而派生出1-5-6和1-5-3两个合法的任务环。其余航班树同理。

图1 深度优先搜索算法网络

其次，必须构建一个启发式函数，以评估航班环的品质。该启发式函数涵盖以下考虑因素：最大值勤时间h值勤max、航班环P所包含的城市数Cp以及航班环P所包含的航班数Np。选定一个起始城市作为出发点。从起始城市出发，深度优先搜索所有可能的航班路径DFS，通过递归方式，针对每个可能的下一个航班进行以下步骤：

（1）若满足启发式函数的品质要求，则将当前航班加入航班环中；

（2）递归尝试下一个城市，持续搜索可能的航班。

每当形成一个航班环（至少包含起始城市），将其储存为一个可行解，并纳入航班环集合P之中。若无法找到适宜的下一个航班，或已经构建出航班环，将回溯至前一个城市，继续搜索其他路径。在搜索过程中，采用不同的起始城市，通过多轮迭代以找出更多的航班环。搜索完成后，输出所获得的航班环集合P。

利用匿名指派法，将NP难问题进行降维处理，根据资质要求和驻地对φI、φII、φIII名飞行机组成员区分为nc个机组。最后由于约束条件式（16）限制，其nc个机组最多可完成pmaxnc个航班，若不采用pmax航班环，其最多完成(pmax-1)nc个航班，因此若选用pmax航班环为起始点的目标函数值大于(pmax-1)nc，则不讨论选用pmax-1航班环为起始点的可行解。

本文选用pmax个航班的航班环为起始航班环，通过贪心算法进行机组排班。贪心算法本质上是一种启发式方法，它通过局部最优选择来构建解决方案。本文通过建立STn筛选算法完成模型求解，其算法流程图如图2所示。

图2 STn筛选算法流程图

STn筛选算法应用如下：创建一个空集合来存储已选择的航班环，开始时为空。对于每个航班环，计算它是否与已选航班有交集。从尚未选择的航班环中选择无交集的最大航班数的航班环，并将其添加到已选择航班环中，形成新的集合。以此类推直至选择12个航班环或没有更多航班环可供选择为止。

3.2 计算结果

由表3机组排班结果可知，该航班有3个航班未完成，其序号为5、24、34，是由飞行时长、空间和时间约束限制造成的，因此可以在做航班计划时去掉这3个航班，满足机组配置航班百分比为92.86%。飞行小时数总计79.08 h，飞行小时数利用率为73.22%，总飞行值勤时长为107.75 h，飞行值勤时长利用率为64.14%，该算例共置位一组机组从驻地A搭乘2号航班飞往驻地B完成27-20的飞行计划。由结果可知该排班结果留有一定余度，但相对于机组每月总飞行时长100 h略偏高，因此该算法更适用于航空旺季，可以合理安排机组人员使航空公司利用最大化。由于飞行机组人数不同，会引起最终航班完成程度的差异，因此进行灵敏度分析，以该航班计划表为例找到最优飞行机组人数配比。

表3 贪心算法机组排班结果

3.3 实验对比

为了验证文中算法的可靠性和高效性，本文将遗传算法与贪心算法进行比较，利用遗传算法的机组排班结果如表4所示，两种算法比较结果如表5所示。可以明显看出，在迭代次数一定的情况下，由于贪心算法易于实现并且算法高效，使得它在问题规模相对较小、计算资源有限的情况下，能够快速地找到一个可行的排班方案。并且由于贪心算法逐步地选择最优的步骤，因此可以在实时环境中快速地生成排班。这对于需要频繁更新排班的场景，如应对突发事件或变动具有优势。由于机组排班问题可能没有太多的约束条件或变数，使得遗传算法在迭代次数有限的情况下，计算结果反而没有贪心算法精确。

表4 遗传算法机组排班结果

表5 两种算法计算结果对比

3.4 灵敏度分析

灵敏度分析是研究一个模型输出项对系统参数敏感程度的方法，在建模中经常利用灵敏度分析来研究原始数据发生变化时最优解的稳定性。此外，灵敏度分析还可以度量参数对模型的影响水平。在一次执飞任务中，航班必须由飞行机组人员操作；换言之，机组人员数量是制约实飞航班数量的关键约束之一。本文选取机组人员数量作为灵敏度分析指标，对机组排班优化模型进行灵敏度分析。由于本算例中机长、副驾驶比例为1：1，可以最大限度提高机组作业效率，因此，在灵敏度分析实验中，机长、副驾驶各占总人员的50%。

结合算例情景，使机组人员总数量在［0，36］区间内等步长增加，循环调用Groubi对模型进行优化求解，输出未满足及满足配置的航班数量（实飞班次数量）如表6所示。对灵敏度分析结果进行可视化，如图3所示。随着机组人员总数量的增加，满足机组配置的航班数量由0提升至41，未满足机组配置的航班数量自42开始逐渐减少至1，之后不再变动，满足配置的航班数量增加呈现边际效应递减。在图3中标记（1）、（2）两处区域，满足机组配置的航班数增长曲线斜率出现了明显的变化。据此可将机组人员数量增加对航班数的影响过程划分为4个阶段：