基于 2021 年中国研究生数学建模竞赛 F 题
问题概述
符号体系
子问题1:航班分配基本模型
子问题2:执勤模型
子问题3:排班计划模型
模型结构总览
求解策略
参考文献
完整优化问题总结
航空公司机组排班问题(Airline Crew Scheduling Problem)是运筹学中经典的组合优化问题。本问题要求在满足航空法规、安全约束和公司政策的前提下,将航班直接分配给机组人员,建立从基本分配到完整排班计划的三层递进模型。
子问题
核心内容
主要目标
子问题1
航班直接分配
最大化覆盖航班 → 最小化乘机 → 最小化替补
子问题2
引入执勤概念
最小化执勤成本 → 平衡执勤时长
子问题3
完整排班计划
最小化任务环成本 → 平衡任务环时长
航班(Flight/Leg) ──连接──→ 执勤(Duty) ──休息──→ 任务环(Pairing) ──休假──→ 排班计划(Roster)
航班 (Flight/Leg) :飞机的一次起飞和降落,具有起降机场、起降时间、最低机组配置
执勤 (Duty) :一次"上班",由一连串航段和间隔连接时间组成,同一天内开始
任务环 (Pairing) :一次"出差",从基地出发并回到基地,由一连串执勤和休息组成
排班计划 (Roster) :一个周期内的全部安排,由任务环和休假组成
符号
含义
$K$
机组人员集合,$k \in K$
$F$
航班集合,$f \in F$
$A$
机场集合,$a \in A$
$D$
排班周期内的日期集合,$d \in D$
$K_C \subseteq K$
具有正机长资格的机组人员
$K_F \subseteq K$
具有副机长资格的机组人员
$K_{C2F} \subseteq K_C$
可替补副机长的正机长
$K^{\text{base}}_a \subseteq K$
基地为机场 $a$ 的机组人员
符号
含义
$f^o$
航班 $f$ 的起飞机场
$f^d$
航班 $f$ 的到达机场
$t^{\text{dep}}_f$
航班 $f$ 的起飞时间(日期+时刻)
$t^{\text{arr}}_f$
航班 $f$ 的到达时间(日期+时刻)
$c^C_f$
航班 $f$ 所需正机长数(本题为1)
$c^F_f$
航班 $f$ 所需副机长数(本题为1)
$b_k$
机组人员 $k$ 的基地
$h^{\text{duty}}_k$
机组人员 $k$ 的单位小时执勤成本
$h^{\text{pair}}_k$
机组人员 $k$ 的单位小时任务环成本
符号
值
含义
$\text{MinCT}$
40 分钟
航段间最小连接时间
$\text{MaxBlk}$
600 分钟 (10h)
一次执勤最大飞行时长
$\text{MaxDP}$
720 分钟 (12h)
一次执勤最大时长
$\text{MinRest}$
660 分钟 (11h)
相邻执勤间最小休息时间
$\text{MaxDH}$
5
每航班最多乘机人数
$\text{MaxTAFB}$
14400 分钟 (10天)
周期内任务环总时长上限
$\text{MaxSuccOn}$
4 天
最大连续执勤天数
$\text{MinVacDay}$
2 天
两个任务环之间最少休息天数
编号
目标
所属子问题
①
尽可能多的航班满足机组配置
1
②
机组人员的总体执勤成本最低
2
③
机组人员的总体任务环成本最低
3
④
尽可能少的总体乘机次数
1
⑤
机组人员之间的执勤时长尽可能平衡
2
⑥
机组人员之间的任务环时长尽可能平衡
3
⑦
尽可能少使用替补资格
1
建立线性规划模型,直接将航班分配给机组人员。每位机组人员从基地出发,按航班顺序飞行,最终回到基地。相邻航段之间需要机场匹配且满足最小连接时间。每个航班的每种资格(正机长、副机长)必须恰好被一人覆盖。
核心约束:
每个机组人员初始从基地出发并最终回到基地
下一航段的起飞机场必须与上一航段的到达机场一致(空间连续性)
相邻两个航段之间的连接时间不小于 MinCT 分钟(时间可行性)
主变量 —— 航班衔接:
$$
x_{k,f,g} = \begin{cases}
1 & \text{机组人员 } k \text{ 在执行航班 } f \text{ 后立即执行航班 } g \\
0 & \text{否则}
\end{cases}
$$
其中 $k \in K$ ,$f, g \in F$。
辅助变量 —— 航班服务:
$$
y_{k,f}^{\text{cap}} = \begin{cases}
1 & \text{机组人员 } k \text{ 以正机长资格执行航班 } f \\
0 & \text{否则}
\end{cases}
$$
$$
y_{k,f}^{\text{fo}} = \begin{cases}
1 & \text{机组人员 } k \text{ 以副机长资格执行航班 } f \\
0 & \text{否则}
\end{cases}
$$
$$
y_{k,f}^{\text{sub}} = \begin{cases}
1 & \text{机组人员 } k \text{ 以替补资格(正机长补副机长)执行航班 } f \\
0 & \text{否则}
\end{cases}
$$
$$
y_{k,f}^{\text{dh}} = \begin{cases}
1 & \text{机组人员 } k \text{ 以乘机方式乘坐航班 } f \\
0 & \text{否则}
\end{cases}
$$
源汇虚拟变量:
$$
x_{k,0,f}^{\text{src}} = \begin{cases}
1 & \text{机组人员 } k \text{ 的第一个航班是 } f \\
0 & \text{否则}
\end{cases}
$$
$$
x_{k,f,0}^{\text{snk}} = \begin{cases}
1 & \text{机组人员 } k \text{ 的最后一个航班是 } f \\
0 & \text{否则}
\end{cases}
$$
航班覆盖变量:
$$
z_f^{\text{cap}} = \begin{cases}
1 & \text{航班 } f \text{ 的正机长需求被满足} \\
0 & \text{否则}
\end{cases}
\qquad
z_f^{\text{fo}} = \begin{cases}
1 & \text{航班 } f \text{ 的副机长需求被满足} \\
0 & \text{否则}
\end{cases}
$$
$$
u_f = \begin{cases}
1 & \text{航班 } f \text{ 的机组配置完全满足(可起飞)} \\
0 & \text{否则}
\end{cases}
$$
采用分层序列法(Lexicographic Method),按编号 ①→④→⑦ 的优先级依次求解。
第一优先级 ①:最大化满足机组配置的航班数
$$
\max \quad Z_1 = \sum_{f \in F} u_f
$$
第二优先级 ④:最小化总体乘机次数
在满足 $Z_1 = Z_1^*$ 的前提下:
$$
\min \quad Z_4 = \sum_{k \in K} \sum_{f \in F} y_{k,f}^{\text{dh}}
$$
第三优先级 ⑦:最小化替补资格使用次数
在满足 $Z_1 = Z_1^$ 和 $Z_4 = Z_4^ $ 的前提下:
$$
\min \quad Z_7 = \sum_{k \in K} \sum_{f \in F} y_{k,f}^{\text{sub}}
$$
每个机组人员 $k$ 的航线构成一条从基地出发并回到基地的路径。
源约束 —— 从基地出发:
$$
x_{k,0,f}^{\text{src}} = 1 \text{ 仅当航班 } f \text{ 从 } b_k \text{ 起飞}, \quad \sum_{f \in F} x_{k,0,f}^{\text{src}} \leq 1
$$
汇约束 —— 回到基地:
$$
x_{k,f,0}^{\text{snk}} = 1 \text{ 仅当航班 } f \text{ 到达 } b_k, \quad \sum_{f \in F} x_{k,f,0}^{\text{snk}} \leq 1
$$
流守恒 —— 中间节点:
对于每个机组人员 $k$ 和每个航班 $g$ :
$$
x_{k,0,g}^{\text{src}} + \sum_{f \in F} x_{k,f,g} = \sum_{h \in F} x_{k,g,h} + x_{k,g,0}^{\text{snk}}
$$
即:进入航班 $g$ 的流量 = 离开航班 $g$ 的流量。
航班 $f$ 后接航班 $g$ 的前提是机场匹配:
$$
x_{k,f,g} = 1 \Rightarrow f^d = g^o
$$
即:
$$
x_{k,f,g} \leq \mathbf{1}[f^d = g^o]
$$
同样:
$$
x_{k,0,f}^{\text{src}} \leq \mathbf{1}[f^o = b_k], \quad x_{k,f,0}^{\text{snk}} \leq \mathbf{1}[f^d = b_k]
$$
相邻航段间必须满足最小连接时间:
$$
x_{k,f,g} = 1 \Rightarrow t_g^{\text{dep}} - t_f^{\text{arr}} \geq \text{MinCT}
$$
即当 $f^d = g^o$ 且 $t_g^{\text{dep}} \geq t_f^{\text{arr}} + \text{MinCT}$ 时才允许 $x_{k,f,g} = 1$ 。
每个航班需要恰好 1 名正机长和 1 名副机长:
$$
z_f^{\text{cap}} = \sum_{k \in K_C} y_{k,f}^{\text{cap}} \leq 1, \quad \forall f \in F
$$
$$
z_f^{\text{fo}} = \sum_{k \in K_F} y_{k,f}^{\text{fo}} + \sum_{k \in K_{C2F}} y_{k,f}^{\text{sub}} \leq 1, \quad \forall f \in F
$$
航班完全覆盖的条件:
$$
u_f \leq z_f^{\text{cap}}, \quad u_f \leq z_f^{\text{fo}}, \quad u_f \geq z_f^{\text{cap}} + z_f^{\text{fo}} - 1
$$
或等价地:
$$
u_f = z_f^{\text{cap}} \cdot z_f^{\text{fo}}
$$
(在 ILP 中用线性化处理乘积项)
若航班未被完全覆盖,则该航班不能配置任何机组人员:
$$
z_f^{\text{cap}} = 0 \Rightarrow z_f^{\text{fo}} = 0
$$
每个机组人员执行航班时,只能以其中一种资格:
$$
y_{k,f}^{\text{cap}} + y_{k,f}^{\text{fo}} + y_{k,f}^{\text{sub}} + y_{k,f}^{\text{dh}} \leq 1, \quad \forall k, f
$$
正机长不能以副机长执行正常任务:
$$
y_{k,f}^{\text{fo}} = 0, \quad \forall k \in K_C, f \in F
$$
副机长不能替补正机长:
$$
y_{k,f}^{\text{cap}} = 0, \quad \forall k \in K_F \setminus K_C, f \in F
$$
只有 $k \in K_{C2F}$ 才能使用替补:
$$
y_{k,f}^{\text{sub}} \leq \mathbf{1}[k \in K_{C2F}]
$$
每航班最多 MaxDH 名乘机人员:
$$
\sum_{k \in K} y_{k,f}^{\text{dh}} \leq \text{MaxDH}, \quad \forall f \in F
$$
连接变量 $x_{k,f,g}$ 与服务变量必须一致:
$$
y_{k,g}^{\text{cap}} + y_{k,g}^{\text{fo}} + y_{k,g}^{\text{sub}} + y_{k,g}^{\text{dh}} = x_{k,0,g}^{\text{src}} + \sum_{f \in F} x_{k,f,g}, \quad \forall k, g
$$
即:如果机组人员 $k$ 进入了航班 $g$ ,则必须为 $g$ 提供某种服务。
$$
\boxed{\begin{aligned}
(\text{P}_{1.1})\quad
\max \quad & \sum_{f \in F} u_f \\
\text{s.t.} \quad & x_{k,0,g}^{\text{src}} + \sum_{f: (f,g)\in E} x_{k,f,g} = \sum_{h: (g,h)\in E} x_{k,g,h} + x_{k,g,0}^{\text{snk}}, && \forall k \in K, \forall g \in F \\
& \sum_{k \in K_C} y_{k,f}^{\text{cap}} = z_f^{\text{cap}} \leq 1, && \forall f \in F \\
& \sum_{k \in K_F} y_{k,f}^{\text{fo}} + \sum_{k \in K_{C2F}} y_{k,f}^{\text{sub}} = z_f^{\text{fo}} \leq 1, && \forall f \in F \\
& z_f^{\text{cap}} = z_f^{\text{fo}}, \quad u_f \leq z_f^{\text{cap}}, \quad u_f \geq z_f^{\text{cap}} + z_f^{\text{fo}} - 1, && \forall f \in F \\
& x_{k,0,f}^{\text{src}} + \sum_{g: (g,f)\in E} x_{k,g,f} = y_{k,f}^{\text{cap}} + y_{k,f}^{\text{fo}} + y_{k,f}^{\text{sub}} + y_{k,f}^{\text{dh}}, && \forall k, \forall f \\
& y_{k,f}^{\text{cap}} + y_{k,f}^{\text{fo}} + y_{k,f}^{\text{sub}} + y_{k,f}^{\text{dh}} \leq 1, && \forall k, \forall f \\
& \sum_{k \in K} y_{k,f}^{\text{dh}} \leq \text{MaxDH}, && \forall f \in F \\
& y_{k,f}^{\text{cap}} \leq \mathbf{1}[k \in K_C], \quad y_{k,f}^{\text{fo}} \leq \mathbf{1}[k \in K_F], \quad y_{k,f}^{\text{sub}} \leq \mathbf{1}[k \in K_{C2F}] \\
& \text{所有变量} \in {0,1}
\end{aligned}}
$$
记最优值为 $Z_1^*$ 。
$$
\boxed{\begin{aligned}
(\text{P}_{1.2})\quad
\min \quad & \sum_{k \in K}\sum_{f \in F} y_{k,f}^{\text{dh}} \\
\text{s.t.} \quad & (\text{P}_{1.1})\text{ 的全部约束} \\
& \sum_{f \in F} u_f = Z_1^*
\end{aligned}}
$$
记最优值为 $Z_4^*$ 。
$$
\boxed{\begin{aligned}
(\text{P}_{1.3})\quad
\min \quad & \sum_{k \in K}\sum_{f \in F} y_{k,f}^{\text{sub}} \\
\text{s.t.} \quad & (\text{P}_{1.1})\text{ 的全部约束} \\
& \sum_{f \in F} u_f = Z_1^_, \quad \sum_{k \in K}\sum_{f \in F} y_{k,f}^{\text{dh}} = Z_4^_
\end{aligned}}
$$
参数
A套数据
B套数据
航班数
206
13,954
机组人数
21
465
机场数
7
39
周期
15天
31天
变量数(约)
O(K·F²)
O(K·F²)
B套数据规模较大,需要设计高效的求解算法。
对于A套数据,可直接使用 MILP 求解器(如 Gurobi/CPLEX)求解。对于B套数据,推荐采用以下策略:
时空网络约简 :仅生成可行航班衔接边(机场匹配 + 时间可行)
列生成法 :以机组人员的完整飞行路径为列,求解集合覆盖/分割模型
启发式构造 + 局部搜索 :先构造可行解,再用邻域搜索改进
在子问题1的基础上引入**执勤(Duty)**概念。执勤由同一天内的一串航段组成,满足时间窗口约束。引入执勤成本(小时工资),要求在覆盖航班的前提下最小化总执勤成本并平衡执勤时长。
新增约束:
每个机组人员每天至多一个执勤
每次执勤的飞行时长 ≤ MaxBlk
每次执勤时长 ≤ MaxDP
跨执勤的机场连续性
相邻执勤间休息时间 ≥ MinRest
在子问题1变量的基础上,新增/扩展:
执勤标识变量:
$$
w_{k,d} = \begin{cases}
1 & \text{机组人员 } k \text{ 在第 } d \text{ 天有执勤} \\
0 & \text{否则}
\end{cases}
$$
执勤间衔接变量:
$$
v_{k,f,g}^{\text{duty}} = \begin{cases}
1 & \text{机组人员 } k \text{ 的航班 } f \text{ 和 } g \text{ 属于同一执勤,且 } f \text{ 紧接着 } g \\
0 & \text{否则}
\end{cases}
$$
执勤间连接变量:
$$
r_{k,f,g} = \begin{cases}
1 & \text{机组人员 } k \text{ 在执行完航班 } f \text{ 后(作为上一执勤的结束),} \\
& \text{下一个执勤从航班 } g \text{ 开始} \\
0 & \text{否则}
\end{cases}
$$
执勤参数变量:
$s_{k,d}$ :机组人员 $k$ 第 $d$ 天执勤的开始时间(连续变量)
$e_{k,d}$ :机组人员 $k$ 第 $d$ 天执勤的结束时间(连续变量)
$\ell_{k,d}^{\text{blk}}$ :机组人员 $k$ 第 $d$ 天执勤的飞行时长(连续变量)
$\ell_{k,d}^{\text{duty}}$ :机组人员 $k$ 第 $d$ 天执勤的总时长(连续变量)
第一优先级 ②:最小化总体执勤成本
$$
\min \quad Z_2 = \sum_{k \in K} \sum_{d \in D} h_k^{\text{duty}} \cdot \frac{\ell_{k,d}^{\text{duty}}}{60}
$$
第二优先级 ⑤:最小化执勤时长不均衡度
$$
\min \quad Z_5 = \max_{k \in K} \sum_{d \in D} \ell_{k,d}^{\text{duty}} - \min_{k \in K} \sum_{d \in D} \ell_{k,d}^{\text{duty}}
$$
或使用方差/标准差:
$$
\min \quad Z_5 = \sum_{k \in K} \left( \sum_{d \in D} \ell_{k,d}^{\text{duty}} - \bar{\ell}^{\text{duty}} \right)^2
$$
其中 $\bar{\ell}^{\text{duty}} = \frac{1}{|K|} \sum_{k \in K} \sum_{d \in D} \ell_{k,d}^{\text{duty}}$ 。
保留子问题1的所有约束(3.4.1–3.4.7),并增加:
$$
w_{k,d} \leq 1, \quad \forall k \in K, d \in D
$$
同一执勤内的所有航班起飞日期相同:
$$
v_{k,f,g}^{\text{duty}} = 1 \Rightarrow \text{day}(f) = \text{day}(g)
$$
$$
\ell_{k,d}^{\text{blk}} \leq \text{MaxBlk}, \quad \forall k \in K, d \in D
$$
飞行时长的计算:
$$
\ell_{k,d}^{\text{blk}} = \sum_{f \in F: \text{day}(f)=d} (t_f^{\text{arr}} - t_f^{\text{dep}}) \cdot (y_{k,f}^{\text{cap}} + y_{k,f}^{\text{fo}} + y_{k,f}^{\text{sub}})
$$
注:乘机不计入飞行时间,但计入执勤时间。
$$
\ell_{k,d}^{\text{duty}} \leq \text{MaxDP}, \quad \forall k \in K, d \in D
$$
执勤总时长的计算:
$$
\ell_{k,d}^{\text{duty}} = e_{k,d} - s_{k,d}
$$
其中 $s_{k,d}$ 为当天第一个航班的起飞时间,$e_{k,d}$ 为当天最后一个航班的到达时间。
$$
r_{k,f,g} = 1 \Rightarrow t_g^{\text{dep}} - t_f^{\text{arr}} \geq \text{MinRest}
$$
$$
r_{k,f,g} = 1 \Rightarrow f^d = g^o
$$
即上一个执勤的结束机场必须与下一个执勤的起始机场一致。
航班 $f$ 后接航班 $g$ 时,要么在同一执勤内,要么跨执勤:
$$
x_{k,f,g} = v_{k,f,g}^{\text{duty}} + r_{k,f,g}, \quad \forall k, f, g
$$
记 $(\text{P}{1.1})\text{–}(\text{P} {1.3})$ 的最优值分别为 $Z_1^, Z_4^ , Z_7^*$。新增变量 $\ell_{k,d}^{\text{duty}} \in \mathbb{R}{\geq 0}$、$w {k,d}, v_{k,f,g}^{\text{duty}}, r_{k,f,g} \in {0,1}$,并令 $T_k^{\text{duty}} = \sum_{d \in D} \ell_{k,d}^{\text{duty}}$ 。
$$
\boxed{\begin{aligned}
(\text{P}_{2.1})\quad
\min \quad & \sum_{k \in K}\sum_{d \in D} h_k^{\text{duty}} \cdot \ell_{k,d}^{\text{duty}} \\
\text{s.t.} \quad & (\text{P}_{1.1})\text{ 的全部约束 (C1–C6)} \\
& \sum_{f \in F} u_f = Z_1^_, \quad \sum_{k,f} y_{k,f}^{\text{dh}} \leq Z_4^_, \quad \sum_{k,f} y_{k,f}^{\text{sub}} \leq Z_7^* \\
& w_{k,d} = \min!\Big(1,; \sum_{f: \text{day}(f)=d} \big(x_{k,0,f}^{\text{src}} + \sum_{g} x_{k,g,f}\big)\Big), && \forall k, \forall d \\
& \ell_{k,d}^{\text{blk}} = \sum_{f: \text{day}(f)=d} (t_f^{\text{arr}} - t_f^{\text{dep}}) \cdot (y_{k,f}^{\text{cap}} + y_{k,f}^{\text{fo}} + y_{k,f}^{\text{sub}}) \leq \text{MaxBlk}, && \forall k, \forall d \\
& \ell_{k,d}^{\text{duty}} = e_{k,d} - s_{k,d} \leq \text{MaxDP}, && \forall k, \forall d \\
& v_{k,f,g}^{\text{duty}} = 1 ;\Rightarrow; \text{day}(f) = \text{day}(g), && \forall k, \forall f, g \\
& r_{k,f,g} = 1 ;\Rightarrow; t_g^{\text{dep}} - t_f^{\text{arr}} \geq \text{MinRest} ;\land; f^d = g^o, && \forall k, \forall f, g \\
& x_{k,f,g} = v_{k,f,g}^{\text{duty}} + r_{k,f,g}, && \forall k, \forall f, g \\
& w_{k,d}, v_{k,f,g}^{\text{duty}}, r_{k,f,g} \in {0,1}, \quad \ell_{k,d}^{\text{blk}}, \ell_{k,d}^{\text{duty}}, s_{k,d}, e_{k,d} \geq 0
\end{aligned}}
$$
记最优值为 $Z_2^*$ 。
$$
\boxed{\begin{aligned}
(\text{P}_{2.2})\quad
\min \quad & \max_{k \in K} T_k^{\text{duty}} - \min_{k \in K} T_k^{\text{duty}} \\
\text{s.t.} \quad & (\text{P}_{2.1})\text{ 的全部约束} \\
& \sum_{k,d} h_k^{\text{duty}} \cdot \ell_{k,d}^{\text{duty}} = Z_2^*
\end{aligned}}
$$
双层优化 :首先求解子问题1获得航班分配方案,再在此基础上划分执勤
约束规划(CP) :执勤划分可用CP高效建模
时间窗预处理 :根据MaxDP/MaxBlk约简可行执勤划分
在子问题1和子问题2的基础上,引入任务环(Pairing)和排班计划(Roster) 。任务环从基地出发并回到基地,由一连串执勤组成。排班计划由任务环和休假构成,覆盖整个排班周期。
新增约束:
每个机组人员每周期任务环总时长 ≤ MaxTAFB
相邻任务环之间至少 MinVacDay 天休息
连续执勤天数 ≤ MaxSuccOn
任务环标识变量:
$$
p_{k,m} = \begin{cases}
1 & \text{机组人员 } k \text{ 的第 } m \text{ 个任务环存在} \\
0 & \text{否则}
\end{cases}
$$
任务环-执勤归属变量:
$$
q_{k,d,m} = \begin{cases}
1 & \text{机组人员 } k \text{ 第 } d \text{ 天的执勤属于第 } m \text{ 个任务环} \\
0 & \text{否则}
\end{cases}
$$
任务环参数变量:
$\tau_{k,m}^{\text{start}}$ :任务环开始日期
$\tau_{k,m}^{\text{end}}$ :任务环结束日期
$\tau_{k,m}^{\text{tafb}}$ :任务环总时长(从基地出发到回到基地)
第一优先级 ③:最小化总体任务环成本
任务环成本按任务环时长计算(不包括执勤成本,视为出差补贴):
$$
\min \quad Z_3 = \sum_{k \in K} \sum_{m} h_k^{\text{pair}} \cdot \frac{\tau_{k,m}^{\text{tafb}}}{60} \cdot p_{k,m}
$$
第二优先级 ⑥:最小化任务环时长不均衡度
$$
\min \quad Z_6 = \max_{k \in K} \sum_{m} \tau_{k,m}^{\text{tafb}} - \min_{k \in K} \sum_{m} \tau_{k,m}^{\text{tafb}}
$$
保留子问题1和2的所有约束,并增加:
$$
\sum_{m} \tau_{k,m}^{\text{tafb}} \cdot p_{k,m} \leq \text{MaxTAFB}, \quad \forall k \in K
$$
$$
\tau_{k,m+1}^{\text{start}} - \tau_{k,m}^{\text{end}} \geq \text{MinVacDay}, \quad \forall k, m
$$
即:上任务环结束日与下任务环开始日之间至少有 MinVacDay 天。
$$
\sum_{i=0}^{\text{MaxSuccOn}} w_{k,d+i} \leq \text{MaxSuccOn}, \quad \forall k, d
$$
即:任意连续 MaxSuccOn+1 天内至少有一天休息。
每个任务环的第一次执勤必须从基地出发,最后一次执勤必须回到基地:
$$
f_1^o = b_k, \quad f_{\text{last}}^d = b_k, \quad \forall \text{ 任务环}
$$
所有任务环和休假覆盖整个排班周期,初始和结束位置都在基地。
记前序问题的最优值分别为 $Z_1^, Z_4^ , Z_7^, Z_2^ , Z_5^*$。新增变量 $p_{k,m}, q_{k,d,m} \in {0,1}$ 、$\tau_{k,m}^{\text{start}}, \tau_{k,m}^{\text{end}} \in \mathbb{Z}{\geq 0}$、$\tau {k,m}^{\text{tafb}} \in \mathbb{R}{\geq 0}$,并令 $T_k^{\text{pair}} = \sum {m=1}^{M} \tau_{k,m}^{\text{tafb}}$。
$$
\boxed{\begin{aligned}
(\text{P}_{3.1})\quad
\min \quad & \sum_{k \in K}\sum_{m=1}^{M} h_k^{\text{pair}} \cdot \tau_{k,m}^{\text{tafb}} \cdot p_{k,m} \\
\text{s.t.} \quad & (\text{P}_{2.1})\text{ 的全部约束 (C1–C6, D1–D7)} \\
& \sum_{f \in F} u_f = Z_1^_, \quad \sum_{k,f} y_{k,f}^{\text{dh}} \leq Z_4^_, \quad \sum_{k,f} y_{k,f}^{\text{sub}} \leq Z_7^* \\
& \sum_{k,d} h_k^{\text{duty}} \cdot \ell_{k,d}^{\text{duty}} \leq Z_2^_, \quad T_k^{\text{duty}} \text{ 的均衡度} \leq Z_5^_ \\
& \sum_{m=1}^{M} \tau_{k,m}^{\text{tafb}} \cdot p_{k,m} \leq \text{MaxTAFB}, && \forall k \in K \\
& p_{k,m} = p_{k,m+1} = 1 ;\Rightarrow; \tau_{k,m+1}^{\text{start}} - \tau_{k,m}^{\text{end}} \geq \text{MinVacDay}, && \forall k, \forall m \\
& \sum_{i=0}^{\text{MaxSuccOn}} w_{k,d+i} \leq \text{MaxSuccOn}, && \forall k \in K, \forall d \in D \\
& w_{k,d} = 1 ;\Rightarrow; \sum_{m=1}^{M} q_{k,d,m} = 1, && \forall k, \forall d \\
& p_{k,m} = 1 ;\Rightarrow; \tau_{k,m}^{\text{start}} = \min{d \mid q_{k,d,m} = 1}, ; \tau_{k,m}^{\text{end}} = \max{d \mid q_{k,d,m} = 1}, && \forall k, \forall m \\
& p_{k,m} = 1 ;\Rightarrow; \tau_{k,m}^{\text{tafb}} = e_{k,\tau_{k,m}^{\text{end}}} - s_{k,\tau_{k,m}^{\text{start}}}, && \forall k, \forall m \\
& p_{k,m} = 1 ;\Rightarrow; \text{首执勤从 } b_k \text{ 出发,末执勤回到 } b_k, && \forall k, \forall m \\
& p_{k,m}, q_{k,d,m} \in {0,1}, \quad \tau_{k,m}^{\text{start}}, \tau_{k,m}^{\text{end}} \in \mathbb{Z}_{\geq 0}, \quad \tau_{k,m}^{\text{tafb}} \geq 0
\end{aligned}}
$$
记最优值为 $Z_3^*$ 。
$$
\boxed{\begin{aligned}
(\text{P}_{3.2})\quad
\min \quad & \max_{k \in K} T_k^{\text{pair}} - \min_{k \in K} T_k^{\text{pair}} \\
\text{s.t.} \quad & (\text{P}_{3.1})\text{ 的全部约束} \\
& \sum_{k,m} h_k^{\text{pair}} \cdot \tau_{k,m}^{\text{tafb}} \cdot p_{k,m} = Z_3^*
\end{aligned}}
$$
列生成法(推荐) :
主问题(RMP):集合覆盖/分割模型,选择任务环覆盖所有航班
子问题(Pricing):资源约束最短路径问题(RCSPP),生成新的任务环
三阶段串行求解 :任务环生成(PO)→ 任务环分配(RO)→ 局部优化
启发式方法 :
遗传算法:编码任务环序列
禁忌搜索:邻域结构包括任务环交换、拆分、合并
大邻域搜索(LNS):破坏-修复框架
子问题1(航班分配)
│
├── 新增:执勤概念
│
▼
子问题2(执勤模型)
│
├── 新增:任务环 + 排班计划
│
▼
子问题3(排班计划)
每一层都在前一层的基础上增加约束和优化目标,保持模型间的前向兼容。
约束
子问题1
子问题2
子问题3
空间连续性(机场匹配)
✓
✓
✓
时间可行性(MinCT)
✓
✓
✓
基地出发/返回
✓
✓
✓
航班覆盖(C1F1)
✓
✓
✓
资格/替补限制
✓
✓
✓
乘机限制(MaxDH)
✓
✓
✓
每天最多一个执勤
✓
✓
执勤飞行时长(MaxBlk)
✓
✓
执勤总时长(MaxDP)
✓
✓
执勤间休息(MinRest)
✓
✓
任务环总时长(MaxTAFB)
✓
任务环间休假(MinVacDay)
✓
连续执勤天数(MaxSuccOn)
✓
编号
目标
子问题1
子问题2
子问题3
①
最大化覆盖航班
✓
✓
✓
④
最小化乘机次数
✓
✓
✓
⑦
最小化替补使用
✓
✓
✓
②
最小化执勤成本
✓
✓
⑤
平衡执勤时长
✓
✓
③
最小化任务环成本
✓
⑥
平衡任务环时长
✓
采用分阶段字典序优化 + 列生成 的混合策略:
阶段1: 子问题1 —— 构建可行航班衔接网络
│
├─ Step 1.1: 机场匹配 + MinCT 构建可行衔接图
├─ Step 1.2: MILP/网络流求解最大化航班覆盖
├─ Step 1.3: 字典序优化减少乘机和替补
│
▼
阶段2: 子问题2 —— 在航班分配基础上划分执勤
│
├─ Step 2.1: 时间窗约束约简可行执勤
├─ Step 2.2: 约束满足/规划求解执勤划分
├─ Step 2.3: 字典序优化执勤成本和平衡
│
▼
阶段3: 子问题3 —— 构建任务环和排班计划
│
├─ Step 3.1: 列生成法生成候选任务环
├─ Step 3.2: 集合覆盖模型分配任务环
├─ Step 3.3: 字典序优化任务环成本和平衡
│
▼
输出: UncoveredFlights.csv + CrewRosters.csv
技术
适用场景
工具
MILP
小规模精确求解
Gurobi / CPLEX / OR-Tools
列生成
大规模组合优化
自定义 + 求解器
约束规划
复杂规则约束
OR-Tools CP-SAT
遗传算法
大规模近似求解
DEAP / 自实现
局部搜索
解改进
禁忌搜索 / 模拟退火
时间统一 :所有时间转换为相对计划周期起点的分钟数
机场编码 :机场三字码映射为整数索引
资格矩阵 :建立机组人员-航班资格可行性矩阵
衔接图构建 :构建航班间可行衔接的有向无环图(DAG)
时空索引 :按日期-机场建立航班索引以加速查询
Xiaodong Luo, Yogesh Dashora, Tina Shaw (2015). Airline Crew Augmentation: Decades of Improvements from Sabre. Interfaces , 45(5): 409-424.
Saeed Saemi, Alireza Rashidi Komijan, Reza Tavakkoli-Moghaddam, Mohammad Fallah (2021). A new mathematical model to cover crew pairing and rostering problems simultaneously. Journal of Engineering Research , 9(2): 218-233.
Mohamed Haouari, Farah Zeghal Mansour, Hanif D. Sherali (2019). A New Compact Formulation for the Daily Crew Pairing Problem. Transportation Science , 53(3): 811-828.
Cappanera, P. & Gallo, G. (2004). A Multicommodity Flow Approach to the Crew Rostering Problem. Operations Research , 52(4): 583-596.
Barnhart, C., Cohn, A.M., Johnson, E.L., Klabjan, D., Nemhauser, G.L., Vance, P.H. (2003). Airline Crew Scheduling. In Handbook of Transportation Science , 517-560.
Desaulniers, G., Desrosiers, J., Dumas, Y., Solomon, M.M., Soumis, F. (1997). Daily Aircraft Routing and Scheduling. Management Science , 43(6): 841-855.
本节将三个子问题统一表述为完整的数学规划形式,按字典序优先级给出最终的一体化模型。
$$
\begin{aligned}
x_{k,f,g} &\in {0,1} && \text{机组 } k \text{ 在执行航班 } f \text{ 后立即执行航班 } g \\
x_{k,0,f}^{\text{src}} &\in {0,1} && \text{航班 } f \text{ 是机组 } k \text{ 的第一个航班} \\
x_{k,f,0}^{\text{snk}} &\in {0,1} && \text{航班 } f \text{ 是机组 } k \text{ 的最后一个航班} \\
y_{k,f}^{\text{cap}} &\in {0,1} && \text{机组 } k \text{ 以正机长资格执行航班 } f \\
y_{k,f}^{\text{fo}} &\in {0,1} && \text{机组 } k \text{ 以副机长资格执行航班 } f \\
y_{k,f}^{\text{sub}} &\in {0,1} && \text{机组 } k \text{ 以替补资格执行航班 } f \\
y_{k,f}^{\text{dh}} &\in {0,1} && \text{机组 } k \text{ 以乘机方式乘坐航班 } f \\
z_f^{\text{cap}} &\in {0,1} && \text{航班 } f \text{ 的正机长需求被满足} \\
z_f^{\text{fo}} &\in {0,1} && \text{航班 } f \text{ 的副机长需求被满足} \\
u_f &\in {0,1} && \text{航班 } f \text{ 可起飞(完全覆盖)}
\end{aligned}
$$
$$
\begin{aligned}
w_{k,d} &\in {0,1} && \text{机组 } k \text{ 在第 } d \text{ 天有执勤} \\
v_{k,f,g}^{\text{duty}} &\in {0,1} && \text{机组 } k \text{ 的航班 } f,g \text{ 属于同一执勤,} f \text{ 紧接 } g \\
r_{k,f,g} &\in {0,1} && \text{机组 } k \text{ 的航班 } f \text{ 后结束执勤,} g \text{ 开始新执勤} \\
s_{k,d} &\in \mathbb{R}_{\geq 0} && \text{机组 } k \text{ 第 } d \text{ 天执勤开始时间} \\
e_{k,d} &\in \mathbb{R}_{\geq 0} && \text{机组 } k \text{ 第 } d \text{ 天执勤结束时间} \\
\ell_{k,d}^{\text{blk}} &\in \mathbb{R}_{\geq 0} && \text{机组 } k \text{ 第 } d \text{ 天执勤飞行时长(分钟)} \\
\ell_{k,d}^{\text{duty}} &\in \mathbb{R}_{\geq 0} && \text{机组 } k \text{ 第 } d \text{ 天执勤总时长(分钟)}
\end{aligned}
$$
$$
\begin{aligned}
p_{k,m} &\in {0,1} && \text{机组 } k \text{ 的第 } m \text{ 个任务环存在} \\
q_{k,d,m} &\in {0,1} && \text{机组 } k \text{ 第 } d \text{ 天的执勤属于第 } m \text{ 个任务环} \\
\tau_{k,m}^{\text{start}} &\in \mathbb{Z}_{\geq 0} && \text{任务环开始日} \\
\tau_{k,m}^{\text{end}} &\in \mathbb{Z}_{\geq 0} && \text{任务环结束日} \\
\tau_{k,m}^{\text{tafb}} &\in \mathbb{R}_{\geq 0} && \text{任务环总时长(分钟)}
\end{aligned}
$$
优化按以下优先级依次进行,后一阶段以前一阶段的最优值为约束。
层级
编号
目标
方向
表达式
L1
①
覆盖航班数
max
$\displaystyle Z_1 = \sum_{f \in F} u_f$
L2
④
乘机次数
min
$\displaystyle Z_4 = \sum_{k \in K} \sum_{f \in F} y_{k,f}^{\text{dh}}$
L3
⑦
替补次数
min
$\displaystyle Z_7 = \sum_{k \in K} \sum_{f \in F} y_{k,f}^{\text{sub}}$
L4
②
执勤成本
min
$\displaystyle Z_2 = \sum_{k \in K} \sum_{d \in D} h_k^{\text{duty}} \cdot \ell_{k,d}^{\text{duty}}$
L5
⑤
执勤平衡
min
$\displaystyle Z_5 = \max_{k} T_k^{\text{duty}} - \min_{k} T_k^{\text{duty}}$
L6
③
任务环成本
min
$\displaystyle Z_3 = \sum_{k \in K} \sum_{m} h_k^{\text{pair}} \cdot \tau_{k,m}^{\text{tafb}}$
L7
⑥
任务环平衡
min
$\displaystyle Z_6 = \max_{k} T_k^{\text{pair}} - \min_{k} T_k^{\text{pair}}$
其中 $T_k^{\text{duty}} = \sum_{d} \ell_{k,d}^{\text{duty}}$ , $T_k^{\text{pair}} = \sum_{m} \tau_{k,m}^{\text{tafb}}$ 。
(C1) 流守恒 —— $\forall k \in K, \forall g \in F$
$$
x_{k,0,g}^{\text{src}} + \sum_{f \in F} x_{k,f,g} = \sum_{h \in F} x_{k,g,h} + x_{k,g,0}^{\text{snk}}
$$
$$
x_{k,f,g}=1 \Rightarrow f^d = g^o; \quad x_{k,0,f}^{\text{src}}=1 \Rightarrow f^o = b_k; \quad x_{k,f,0}^{\text{snk}}=1 \Rightarrow f^d = b_k
$$
在 MILP 中通过只为可行衔接创建变量来隐式处理。
$$
x_{k,f,g}=1 \Rightarrow t_g^{\text{dep}} - t_f^{\text{arr}} \geq \text{MinCT}
$$
(C4) 航班覆盖 —— $\forall f \in F$
$$
\sum_{k \in K_C} y_{k,f}^{\text{cap}} = z_f^{\text{cap}} \leq 1, \quad
\sum_{k \in K_F} y_{k,f}^{\text{fo}} + \sum_{k \in K_{C2F}} y_{k,f}^{\text{sub}} = z_f^{\text{fo}} \leq 1
$$
$$
u_f \leq z_f^{\text{cap}}, \quad u_f \leq z_f^{\text{fo}}, \quad u_f \geq z_f^{\text{cap}} + z_f^{\text{fo}} - 1
$$
(C5) 资格与路径一致性 —— $\forall k, f$
每个机组在每个航班最多一种角色:
$$
y_{k,f}^{\text{cap}} + y_{k,f}^{\text{fo}} + y_{k,f}^{\text{sub}} + y_{k,f}^{\text{dh}} \leq 1
$$
进入航班 = 有角色:
$$
x_{k,0,f}^{\text{src}} + \sum_{g} x_{k,g,f} = y_{k,f}^{\text{cap}} + y_{k,f}^{\text{fo}} + y_{k,f}^{\text{sub}} + y_{k,f}^{\text{dh}}
$$
资格限制:
$$
y_{k,f}^{\text{cap}} \leq \mathbf{1}[k \in K_C], \quad
y_{k,f}^{\text{fo}} \leq \mathbf{1}[k \in K_F], \quad
y_{k,f}^{\text{sub}} \leq \mathbf{1}[k \in K_{C2F}]
$$
$$
\sum_{k \in K} y_{k,f}^{\text{dh}} \leq \text{MaxDH}
$$
(D1) 每天最多一个执勤 —— $\forall k, d$
$$
w_{k,d} = \min\left(1, \sum_{f: \text{day}(f)=d} \big(x_{k,0,f}^{\text{src}} + \sum_{g} x_{k,g,f}\big)\right) \leq 1
$$
(D2–D3) 执勤时长 —— $\forall k, d$
$$
\ell_{k,d}^{\text{blk}} = \sum_{f: \text{day}(f)=d} (t_f^{\text{arr}} - t_f^{\text{dep}}) \cdot (y_{k,f}^{\text{cap}} + y_{k,f}^{\text{fo}} + y_{k,f}^{\text{sub}})
$$
$$
\ell_{k,d}^{\text{blk}} \leq \text{MaxBlk}, \quad \ell_{k,d}^{\text{duty}} = e_{k,d} - s_{k,d} \leq \text{MaxDP}
$$
$$
v_{k,f,g}^{\text{duty}} = 1 \Rightarrow \text{day}(f) = \text{day}(g)
$$
$$
r_{k,f,g} = 1 \Rightarrow (t_g^{\text{dep}} - t_f^{\text{arr}} \geq \text{MinRest}) \land (f^d = g^o)
$$
$$
x_{k,f,g} = v_{k,f,g}^{\text{duty}} + r_{k,f,g}, \quad \forall k, f, g
$$
(R1) 任务环 TAFB —— $\forall k$
$$
\sum_{m} \tau_{k,m}^{\text{tafb}} \leq \text{MaxTAFB}
$$
(R2) 任务环间休假 —— $\forall k, m$
$$
\tau_{k,m+1}^{\text{start}} - \tau_{k,m}^{\text{end}} \geq \text{MinVacDay}
$$
(R3) 连续执勤天数 —— $\forall k, \forall d$
$$
\sum_{i=0}^{\text{MaxSuccOn}} w_{k,d+i} \leq \text{MaxSuccOn}
$$
每个任务环的第一次执勤从基地出发,最后一次执勤回到基地。
子问题1
子问题2
子问题3
二进制变量
$O(K \cdot
E
)$
连续变量
—
$O(K \cdot D)$
$O(K \cdot M)$
约束数
$O(K \cdot F + F)$
$O(K \cdot F + F + K \cdot D)$
$O(K \cdot F + F + K \cdot D + K \cdot M)$
A套典型规模
~10⁵变量, ~10⁴约束
~10⁵变量, ~10⁴约束
~10⁵变量, ~10⁴约束
其中 $|E|$ 为衔接图边数,$D$ 为天数,$M$ 为每人最大任务环数。
注 :本模型代码实现见 models/ 目录。精确求解器见 solver/exact/ 目录。算法接口见 solver/interfaces.py 。