Crew scheduling optimization based on flight loop

ZHAO Jinfang; ZHAO Qiaoyang; ZHOU Song; YIN Aobo

doi:10.3969/j.issn.2095-1248.2023.04.006

Journal of Shenyang Aerospace University >

2023 , Vol. 40 >Issue 4: 40 - 48

DOI: https://doi.org/10.3969/j.issn.2095-1248.2023.04.006

Civil Aviation and Safety Engineering

Crew scheduling optimization based on flight loop

ZHAO Jinfang ^,^a ,
ZHAO Qiaoyang ^a ,
ZHOU Song ^b ,
YIN Aobo ^a

Expand

^a. College of Civil Aviation, Shenyang Aerospace University，Shenyang 110136，China
^b. College of Mechanical and Electrical Engineering, Shenyang Aerospace University，Shenyang 110136，China

Received date: 2023-03-12

Online published: 2023-11-09

Fold

Abstract

Crew scheduling is an important part of the operation management plan of an airline. Due to its NP-hard， it often faces combinational explosion and is difficult to be solved. Addressing the problem， a flight-loop-based optimization model was proposed. In phase one， considering the space-time connection constraint and the departure and arrival constraint for duty， a flight loop model between route segments was built； in phase two， the depth-first search （DFS） algorithm and greedy algorithm were incorporated to accomplish the solution of the model. In addition， a restricted master problem （RMP） model was proposed under the column generation algorithm， which was then used to solve the experimental validation examples.

Key words： transportation planning and management; crew scheduling optimization; flight loop; anonymous assignment method; depth-first search; restricted master problem model; greedy algorithm

Cite this article

ZHAO Jinfang , ZHAO Qiaoyang , ZHOU Song , YIN Aobo . Crew scheduling optimization based on flight loop[J]. Journal of Shenyang Aerospace University, 2023 , 40(4) : 40 -48 . DOI: 10.3969/j.issn.2095-1248.2023.04.006

航空公司机组排班问题是非确定性多项式（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由多个航班（f₁，f₂，…，f_n ）组成，每段航班为一段接续链条，机组配置由一名机长i和一名副驾驶j组成。本文用a表示有满足配置的机组和航班环匹配，其定义式如式（1）所示。用决策变量x_a 表示a是否启用，启用取1，否则取0。

∃! (i, j), p ⇒ a

（1）

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

符号	定义
$f, F$	航班索引及所有航班集合
$k, K$	机组人员索引及所有机组人员集合
$i, j$	正机长，副驾驶索引
$ε Ⅰ, ε Ⅲ$	两类机组人员的数量上限（具备机长资质、副驾驶资质）
$φ Ⅰ, φ Ⅲ$	匹配 $a$ 中两类机组人员出现的个数
$p, P$	航班环，航班环集合
$a, A$	一个可行航班环和一组机组人员构成的匹配索引及所有匹配的集合
$F a$	匹配 $a$ 中所有航班 $f$ 的集合
$x a$	0-1决策变量，若一个航班环 $p$ 与机组人员构成的匹配 $a$ 启用，则取1，否则取0
$y f$	0-1决策变量，若航班 $f$ 因无法满足最低机组资质配置不能起飞，则取1，否则取0
$b f a$	0-1参量，匹配 $a$ 中的航班环内是否包含航班f，是则取1，否则取0
$d f a$	0-1参量，匹配 $a$ 中的航班 $f$ 是否为置位航班，是则取1，否则取0
$δ f$	航班 $f$ 在航班环集 $p$ 中出现次数
$n f$	航班f为置位航班情况下的置位人数
$h, l$	前段到达及后段离港航班索引
$s h d$ ，s $l o$	前段航班的终点及后段航班的起点
$t h d, t l o$	前段航班的到达时间及后段航班离港时间
$f_m i n, f_m a x$	一条航班环中最早及最晚的航班
$s f o_m i n, s f d_m a x$	一条航班环中最早及最晚的航班的终点
$h 值勤, h 飞行$	最大飞行值勤小时数及飞行时间
$C p$	航班环 $p$ 所包含的城市数
$N p$	航班环 $p$ 所包含的航班数

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

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

m i n ∑ f ∈ F y f

（2）

其次针对目标（2），要求尽可能少的机组置位次数，因此对所有匹配a的置位航班进行求和，为此定义了

F a

即匹配a中的航班f集合，则总置位次数最小化表达如式（3）所示

m i n ∑ a ∈ A x a ∑ f ∈ F a d f a n f

（3）

考虑到

∀ f ∈ F a

，均有恒定的x_a，且

d f a n f

为常数。因此，式（2）可写为

m i n ∑ a ∈ A ∑ f ∈ F a x a d f a n f

（4）

由于问题Q为多目标函数优化问题，结合大M法理念^［18］，为两个目标函数添加加权系数

m 1 > > m 2

，将多目标问题转化为单目标优化问题。因此问题P表达如式（5）所示

m i n m 1 ∑ f ∈ F y f + m 2 ∑ a ∈ A ∑ f ∈ F a x a d f a n f

（5）

2.2 约束条件

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

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

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

∑ a ∈ A x a b f a = 1, ∀ f ∈ F

（6）

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

∑ a ∈ A x a b f a + y f = 1, ∀ f ∈ F

（7）

2.2.2 航班空间衔接约束

对于两段连续的航班

f

，将前段到达航班索引定义为

h

，后段离港航班索引定义为

l

。此外，定义前段航班到达机场时间为

s h d

，后段离港航班出发时间为

s l o

。由于航班的空间连贯关系，前段航班到达机场时间必须为后段航班离港时间。因此航班的空间衔接约束定义如式（8）所示

s h d = s l o, ∀ h, l ∈ F

（8）

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

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

定义一条航班环中最早的航班为

f_m i n

，最晚的航班为

f_m a x

。因此，该类约束表达如式（9）所示

s f_m i n o = s f_m a x d = s k b a s e, ∀ f_m i n, f_m a x ∈ F, k ∈ K

（9）

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

由于民航局对最小过站时间有所规定，在此定义该最小过站时间标准为

t C T M i n

（

t C T M i n

=50 min）。此外，为避免飞机过站时间过长造成资源浪费，定义最长过站时间

t C T M a x

（

t C T M a x

=100 min）。定义前段航班的到达时间为

t h d

，后段航班的离港时间为

t l o

。因此，航班最小过站时间约束和最长过站时间约束如式（10）和式（11）所示

x a t l o - t h d ≥ t C T M i n, ∀ h, l ∈ F a, a ∈ A

（10）

x a t l o - t h d ≤ t C T M a x, ∀ h, l ∈ F a, a ∈ A

（11）

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

由于置位情况的存在，为确保航班和机组唯一确定，定义航班

f

在航班环集

P

中出现次数为

δ f

，则航班

f

的执飞次数用置位次数表达，如式（12）所示

δ f - ∑ a ∈ A x a d f a

（12）

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

δ f - ∑ a ∈ A x a d f a = 1, ∀ f ∈ F

（13）

2.2.6 值勤时间约束

为保证航班的飞行安全，设置最大飞行值勤小时数为

h 值勤

，飞行时间为

h 飞行

，因此需引入约束如式（14）、（15）所示

h 值勤 ≤ h 值勤 m a x

（14）

h 飞行 ≤ h 飞行 m a x

（15）

2.2.7 航班约束

因最大航班受值勤小时数

h 值勤

约束，因此需引入约束如式（16）所示

1 ≤ p ≤ p m a x

（16）

2.3 模型约简

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

m i n m 1 ∑ f ∈ F y f + m 2 ∑ a ∈ A ∑ f ∈ F a x a d f a n f s . t . ∑ a ∈ A x a b f a + y f = 1, ∀ f ∈ F s h d = s l o, ∀ h, l ∈ F s f_m i n o = s f_m a x d = s k b a s e ∀ f_m i n, f_m a x ∈ F, k ∈ K t C T M a x ≥ x a t l o - t h d ≥ t C T M i n, ∀ h, l ∈ F a, a ∈ A 0 ≤ δ f - ∑ a ∈ A x a d f a ≤ 1, ∀ f ∈ F 1 ≤ p ≤ p m a x h 值勤 ≤ h 值勤 m a x h 飞行 ≤ h 飞行 m a x x a ∈ 0,1, ∀ a ∈ A y f ∈ 0,1, ∀ f ∈ F

（17）

由于问题Q仍然是组合爆炸问题，因此，定义两类机组人员的上限分别为

ε I 、 ε I I

，每一个匹配

a

中两类机组人员出现的个数分别为

φ I 、 φ I I

，因此需引入新约束如式（18）、（19）所示

∑ a ∈ A x a φ I ≤ ε I

（18）

∑ a ∈ A x a φ I I ≤ ε I I

（19）

3 算例分析

3.1 算例设置

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

h 值勤 m a x

=14 h，

h 飞行 m a x

=9 h，根据

h 值勤 m a x

可得

p m a x = 4

。

表2 测试算例航班

序号	出发地	终点	出发时间	结束时间
1	E	D	12：05	14：35
2	A	B	6：25	7：55
3	B	E	7：15	9：30
4	C	B	13：45	15：55
5	B	E	7：00	8：05
6	C	B	15：45	17：25
7	E	C	11：00	12：45
8	C	B	13：45	15：35
9	B	E	8：45	10：05
10	A	C	10：30	12：45
11	E	A	16：30	17：50
12	D	C	11：30	14：25
13	E	D	14：35	16：55
14	B	D	6：45	8：15
15	B	C	6：25	8：35
16	A	C	10：35	13：15
17	C	D	13：25	14：55
18	B	A	8：15	9：35
19	D	A	16：00	18：00
20	E	A	12：00	15：30
21	D	E	13：50	14：55
22	E	C	12：40	14：35
23	D	B	18：05	19：25
24	C	E	10：45	12：20
25	C	E	10：35	13：35
26	C	A	15：35	17：20
27	B	E	8：35	10：25
28	E	D	10：30	13：25
29	A	E	12：50	14：25
30	A	D	9：35	12：55
31	A	C	10：00	12：05
32	D	B	14：20	17：15
33	D	A	15：30	16：55
34	C	A	16：25	17：35
35	B	C	6：35	9：25
36	B	E	9：00	11：05
37	C	E	14：35	15：40
38	A	D	8：25	10：15
39	E	A	15：55	17：35
40	D	E	9：25	11：35
41	E	B	15：15	16：35
42	C	A	9：30	11：55

首先，为获取航班环集合

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两个合法的任务环。其余航班树同理。

显示原图|下载原图ZIP|生成PPT

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

其次，必须构建一个启发式函数，以评估航班环的品质。该启发式函数涵盖以下考虑因素：最大值勤时间

h 值勤 m a x

、航班环P所包含的城市数

C p

以及航班环P所包含的航班数

N p

。选定一个起始城市作为出发点。从起始城市出发，深度优先搜索所有可能的航班路径DFS，通过递归方式，针对每个可能的下一个航班进行以下步骤：

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

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

每当形成一个航班环（至少包含起始城市），将其储存为一个可行解，并纳入航班环集合

P

之中。若无法找到适宜的下一个航班，或已经构建出航班环，将回溯至前一个城市，继续搜索其他路径。在搜索过程中，采用不同的起始城市，通过多轮迭代以找出更多的航班环。搜索完成后，输出所获得的航班环集合

P

。

利用匿名指派法，将NP难问题进行降维处理，根据资质要求和驻地对

φ I 、 φ I I 、 φ I I I

名飞行机组成员区分为

n c

个机组。最后由于约束条件式（16）限制，其

n c

个机组最多可完成

p m a x n c

个航班，若不采用

p m a x

航班环，其最多完成

(p m a x - 1) n c

个航班，因此若选用

p m a x

航班环为起始点的目标函数值大于

(p m a x - 1) n c

，则不讨论选用

p m a x - 1

航班环为起始点的可行解。

本文选用

p m a x

个航班的航班环为起始航班环，通过贪心算法进行机组排班。贪心算法本质上是一种启发式方法，它通过局部最优选择来构建解决方案。本文通过建立

S T n

筛选算法完成模型求解，其算法流程图如图2所示。

显示原图|下载原图ZIP|生成PPT

图2 $S T n$ 筛选算法流程图

S T n

筛选算法应用如下：创建一个空集合来存储已选择的航班环，开始时为空。对于每个航班环，计算它是否与已选航班有交集。从尚未选择的航班环中选择无交集的最大航班数的航班环，并将其添加到已选择航班环中，形成新的集合。以此类推直至选择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 贪心算法机组排班结果

驻地A	航班环	驻地B	航班环
1	2-36-1-33	1	18-10-4
2	16-37-11	2	3-28-32
3	30-21-39	3	15-42-29-41
4	38-12-26	4	14-40-22-6
5	31-17-19	5	35-25-13-23
		6	9-7-8
		7	27-20

3.3 实验对比

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

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

驻地A	航班环	驻地B	航班环
1	2-9-7-26	1	15-8
2	10-17-19	2	35-25-13-23
3	16-37-11	3	3-28-32
4	38-12-34	4	5-22-6
5	30-21-39	5	18-31-4
		6	27-20
		7	29-41

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

算法

计算时间/s

未完成航班数

航班完成数

航班完成率/%

置位

次数

贪心算法

24~26

遗传算法

24~28

3.4 灵敏度分析

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

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

表6 机组排班任务灵敏度计算结果

机组人员总数量/人	未满足机组配置航班数/班次	百分比/%	满足机组配置航班数/班次	百分比/%
0	42	100	0	0
4	32	76	10	24
8	21	50	21	50
12	16	37	26	63
16	11	25	31	75
20	6	15	36	85
24	3	7	39	93
28	1	2	41	98

显示原图|下载原图ZIP|生成PPT

图3 机组排班任务灵敏度分析可视化

第一阶段：机组人员数量从0增加到8，该阶段航路基本闲置，机组人员数量是制约实飞航班数的主要因素，随着机组人员数量的增加，实飞航班数快速增长；

第二阶段：机组人员数量从8增加到20，该阶段部分航路开始出现竞争，但是由于机组人员基数较少，实飞航班数随机组人员数量增加仍有显著提升；

第三阶段：机组人员数量从20增加至28，此时航路数量开始出现较多竞争，实飞航班数增长趋势明显放缓；

第四阶段：机组人员数量自28开始继续增加。此时，航路数量取代机组人员数量，成为制约航班数的关键约束，机组开始出现一定比例的人员空闲，仅提升人员数量无法再提高实飞航班数量。

综上，机组人员数量对实飞航路数量的增长呈现边际效应递减，而机组人员数量控制在20左右是兼顾成本与实飞航班数的较好方案。

4 结论

本文通过构建航班环对飞行计划和机组排班计划进行优化处理，剔除不合理的航班，保证了航班计划的可行性，同时还降低了因置位飞行员所带来的额外成本。在满足航班连续性的约束下完成了航班计划与机组排班计划。

（1）针对航空公司的排班现状及航班环选择问题的复杂性和优化结果不满意等问题，提出基于航班环的指派思路，构建优化模型。

（2）本文通过深度优先搜索算法和贪心算法，得出局部最优航班计划。对于未完成的航班依照目标函数的权重大小进行飞行员置位处理或放弃该飞行计划处理，该值主要受加权系数

m 1

、

m 2

控制，可以通过当日实际情况更改加权系数使其选择不同的处理方法。

（3）对于没有航班环与机组匹配的航班，本文进行受限主问题模型的松弛处理，将未完成航班加入受限主问题中再次进行求解，如此迭代，直到无法寻找到可使目标函数优化的变量，得到松弛问题的最优解。

（4）本文进行了灵敏度分析，评估了模型对输入参数变化的响应程度，了解模型未完成航班

y f

如何随着机组总人数

K

的变化而变化，从而帮助决策者更好地理解系统的行为和性能，做出更准确的决策。

本文将NP多目标问题进行降维并简化，验证了其合理性，极大地提高了飞行计划和机组排班的效率。在飞行机组成员选择上，利用灵敏度分析得出机组人数最佳方案，为后续制定最终飞行计划做好基础。

References

Publishing order | Descend order by publishing year | Descend order by cited within

1	Zeghal F M， Minoux M.Modeling and solving a crew assignment problem in air transportation［J］.European Journal of Operational Research，2006，175（1）：187-209.

2	Anbil R， Gelman E， Patty B，et al.Recent advances in crew-pairing optimization at American airlines［J］.Interfaces，1991，21（1）：62-74.

3	Kornilakis H， Stamatopoulos P.Crew pairing optimization with genetic algorithms［M］//Methods and Applications of Artificial Intelligence.Berlin，Heidelberg：Springer Berlin Heidelberg，2002：109-120.

4	Kasirzadeh A， Saddoune M， Soumis F.Airline crew scheduling：models，algorithms，and data sets［J］.EURO Journal on Transportation and Logistics，2017，6（2）：111-137.

5	Fahle T， Junker U， Karisch S E，et al.Constraint programming based column generation for crew assignment［J］.Journal of Heuristics，2002，8（1）：59-81.

6	Jiao Y， Dong J T， Han J R，et al.Classification and causes identification of Chinese civil aviation incident reports［J］.Applied Sciences，2022，12（21）：10765.

7	Antonova V M， Balakin K A， Grechishkina N A，et al.Application of the hypergraphs theory to solve the problem of optimizing network performance in civil aviation［J］.Journal of Communications Technology and Electronics，2022，67（6）：717-721.

8	范永俊，吴东华.基于分支定界法的飞机均衡排班计划求解［J］.统计与决策，2017（20）：60-63.

9	李耀华，谭娜，郝贵和.飞机排班航班串编制模型及算法研究［J］.系统仿真学报，2008，20（3）：612-615.

10	李耀华，王磊.基于改进遗传算法的飞机排班优化方法研究［J］.系统仿真学报，2016，28（3）：620-626.

11	陶世群，蒲保兴.基于遗传算法的多级目标非平衡指派问题求解［J］.系统工程理论与实践，2004，24（8）：80-85.

12	张米.航空公司机组排班模型研究［D］.北京：清华大学，2014.

13	潘海洋.无初始解的大规模机组排班问题建模与求解优化［D］.北京：清华大学，2014.

14	李青，张军，张学军.解决排班问题的多目标优化模型及算法研究［J］.北京航空航天大学学报，2003，29（9）：821-824.

15	邵俊.基于遗传算法的机组任务配对研究［D］.南京：南京航空航天大学，2006.

16	王文璨，巩梨，刘林忠.基于混合算法求解指派问题目标规划模型［J］.计算机应用与软件，2022，39（6）：269-272，308.

17	董宇楠，梁光胜，王悦.通航机组指派模型与算法的研究［J］.计算机应用研究，2020，37（）：188-189，201.

18	董沛余.大M法在商品发运组配环节的应用［J］.物流科技，2002，25（3）：38-40.

Options

Outlines

机组人员总数量/人	未满足机组配置航班数/班次	百分比/%	满足机组配置航班数/班次	百分比/%
0	42	100	0	0
4	32	76	10	24
8	21	50	21	50
12	16	37	26	63
16	11	25	31	75
20	6	15	36	85
24	3	7	39	93
28	1	2	41	98

机组人员总数量/人	未满足机组配置航班数/班次	百分比/%	满足机组配置航班数/班次	百分比/%
0	42	100	0	0
4	32	76	10	24
8	21	50	21	50
12	16	37	26	63
16	11	25	31	75
20	6	15	36	85
24	3	7	39	93
28	1	2	41	98

模态框（Modal）标题

Abstract

Cite this article

1 问题描述与假设

1.1 问题描述

1.2 问题假设

2 数学模型

2.1 目标函数

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

2.2 约束条件

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

2.2.2 航班空间衔接约束

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

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

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

2.2.6 值勤时间约束

2.2.7 航班约束

2.3 模型约简

3 算例分析

3.1 算例设置

表2 测试算例航班

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

图2 S T n筛选算法流程图

3.2 计算结果

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

3.3 实验对比

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

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

3.4 灵敏度分析

表6 机组排班任务灵敏度计算结果

图3 机组排班任务灵敏度分析可视化

4 结论

References

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

图2 $S T n$ 筛选算法流程图

机组人员总数量/人	未满足机组配置航班数/班次	百分比/%	满足机组配置航班数/班次	百分比/%
0	42	100	0	0
4	32	76	10	24
8	21	50	21	50
12	16	37	26	63
16	11	25	31	75
20	6	15	36	85
24	3	7	39	93
28	1	2	41	98