Skip to content

About

No description, website, or topics provided.

Resources

Stars

1 star

Watchers

0 watching

Forks

Latest commit

 

History

1 Commit

Folders and files

Repository files navigation

航空公司机组优化排班问题 —— 数学建模

基于 2021 年中国研究生数学建模竞赛 F 题


目录

  1. 问题概述
  2. 符号体系
  3. 子问题1:航班分配基本模型
  4. 子问题2:执勤模型
  5. 子问题3:排班计划模型
  6. 模型结构总览
  7. 求解策略
  8. 参考文献
  9. 完整优化问题总结

1. 问题概述

航空公司机组排班问题(Airline Crew Scheduling Problem)是运筹学中经典的组合优化问题。本问题要求在满足航空法规、安全约束和公司政策的前提下,将航班直接分配给机组人员,建立从基本分配到完整排班计划的三层递进模型。

1.1 问题分解

子问题 核心内容 主要目标
子问题1 航班直接分配 最大化覆盖航班 → 最小化乘机 → 最小化替补
子问题2 引入执勤概念 最小化执勤成本 → 平衡执勤时长
子问题3 完整排班计划 最小化任务环成本 → 平衡任务环时长

1.2 核心概念关系

航班(Flight/Leg) ──连接──→ 执勤(Duty) ──休息──→ 任务环(Pairing) ──休假──→ 排班计划(Roster)
  • 航班 (Flight/Leg):飞机的一次起飞和降落,具有起降机场、起降时间、最低机组配置
  • 执勤 (Duty):一次"上班",由一连串航段和间隔连接时间组成,同一天内开始
  • 任务环 (Pairing):一次"出差",从基地出发并回到基地,由一连串执勤和休息组成
  • 排班计划 (Roster):一个周期内的全部安排,由任务环和休假组成

2. 符号体系

2.1 集合与索引

符号 含义
$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$ 的机组人员

2.2 参数

符号 含义
$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$ 的单位小时任务环成本

2.3 约束参数

符号 值 含义
$\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 天 两个任务环之间最少休息天数

2.4 目标优先级

编号 目标 所属子问题
① 尽可能多的航班满足机组配置 1
② 机组人员的总体执勤成本最低 2
③ 机组人员的总体任务环成本最低 3
④ 尽可能少的总体乘机次数 1
⑤ 机组人员之间的执勤时长尽可能平衡 2
⑥ 机组人员之间的任务环时长尽可能平衡 3
⑦ 尽可能少使用替补资格 1

3. 子问题1:航班分配基本模型

3.1 问题描述

建立线性规划模型,直接将航班分配给机组人员。每位机组人员从基地出发,按航班顺序飞行,最终回到基地。相邻航段之间需要机场匹配且满足最小连接时间。每个航班的每种资格(正机长、副机长)必须恰好被一人覆盖。

核心约束:

  • 每个机组人员初始从基地出发并最终回到基地
  • 下一航段的起飞机场必须与上一航段的到达机场一致(空间连续性)
  • 相邻两个航段之间的连接时间不小于 MinCT 分钟(时间可行性)

3.2 决策变量

主变量 —— 航班衔接:

$$ 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} $$

3.3 目标函数(字典序多目标优化)

采用分层序列法(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}} $$

3.4 约束条件

3.4.1 流守恒约束(网络流模型)

每个机组人员 $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$ 的流量。

3.4.2 空间连续性约束

航班 $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] $$

3.4.3 时间可行性约束

相邻航段间必须满足最小连接时间:

$$ 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$。

3.4.4 航班覆盖约束

每个航班需要恰好 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 $$

3.4.5 资格约束

每个机组人员执行航班时,只能以其中一种资格:

$$ 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}] $$

3.4.6 乘机约束

每航班最多 MaxDH 名乘机人员:

$$ \sum_{k \in K} y_{k,f}^{\text{dh}} \leq \text{MaxDH}, \quad \forall f \in F $$

3.4.7 路径一致性约束

连接变量 $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$ 提供某种服务。

3.5 完整优化模型

第一阶段:最大化航班覆盖(目标①)

$$ \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}} $$

3.6 模型规模估计

参数 A套数据 B套数据
航班数 206 13,954
机组人数 21 465
机场数 7 39
周期 15天 31天
变量数(约) O(K·F²) O(K·F²)

B套数据规模较大,需要设计高效的求解算法。

3.7 算法策略

对于A套数据,可直接使用 MILP 求解器(如 Gurobi/CPLEX)求解。对于B套数据,推荐采用以下策略:

  1. 时空网络约简:仅生成可行航班衔接边(机场匹配 + 时间可行)
  2. 列生成法:以机组人员的完整飞行路径为列,求解集合覆盖/分割模型
  3. 启发式构造 + 局部搜索:先构造可行解,再用邻域搜索改进

4. 子问题2:执勤模型

4.1 问题描述

在子问题1的基础上引入**执勤(Duty)**概念。执勤由同一天内的一串航段组成,满足时间窗口约束。引入执勤成本(小时工资),要求在覆盖航班的前提下最小化总执勤成本并平衡执勤时长。

新增约束:

  • 每个机组人员每天至多一个执勤
  • 每次执勤的飞行时长 ≤ MaxBlk
  • 每次执勤时长 ≤ MaxDP
  • 跨执勤的机场连续性
  • 相邻执勤间休息时间 ≥ MinRest

4.2 决策变量

在子问题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$ 天执勤的总时长(连续变量)

4.3 目标函数

第一优先级 ②:最小化总体执勤成本

$$ \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}}$。

4.4 约束条件

保留子问题1的所有约束(3.4.1–3.4.7),并增加:

4.4.1 每天最多一个执勤

$$ 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) $$

4.4.2 执勤飞行时长约束

$$ \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}}) $$

注:乘机不计入飞行时间,但计入执勤时间。

4.4.3 执勤总时长约束

$$ \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}$ 为当天最后一个航班的到达时间。

4.4.4 执勤间休息约束

$$ r_{k,f,g} = 1 \Rightarrow t_g^{\text{dep}} - t_f^{\text{arr}} \geq \text{MinRest} $$

4.4.5 执勤间机场连续性

$$ r_{k,f,g} = 1 \Rightarrow f^d = g^o $$

即上一个执勤的结束机场必须与下一个执勤的起始机场一致。

4.4.6 衔接类型互斥

航班 $f$ 后接航班 $g$ 时,要么在同一执勤内,要么跨执勤:

$$ x_{k,f,g} = v_{k,f,g}^{\text{duty}} + r_{k,f,g}, \quad \forall k, f, g $$

4.5 完整优化模型

记 $(\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}} $$

4.6 算法策略

  1. 双层优化:首先求解子问题1获得航班分配方案,再在此基础上划分执勤
  2. 约束规划(CP):执勤划分可用CP高效建模
  3. 时间窗预处理:根据MaxDP/MaxBlk约简可行执勤划分

5. 子问题3:排班计划模型

5.1 问题描述

在子问题1和子问题2的基础上,引入任务环(Pairing)和排班计划(Roster)。任务环从基地出发并回到基地,由一连串执勤组成。排班计划由任务环和休假构成,覆盖整个排班周期。

新增约束:

  • 每个机组人员每周期任务环总时长 ≤ MaxTAFB
  • 相邻任务环之间至少 MinVacDay 天休息
  • 连续执勤天数 ≤ MaxSuccOn

5.2 决策变量

任务环标识变量:

$$ 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}}$:任务环总时长(从基地出发到回到基地)

5.3 目标函数

第一优先级 ③:最小化总体任务环成本

任务环成本按任务环时长计算(不包括执勤成本,视为出差补贴):

$$ \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}} $$

5.4 约束条件

保留子问题1和2的所有约束,并增加:

5.4.1 任务环总时长约束

$$ \sum_{m} \tau_{k,m}^{\text{tafb}} \cdot p_{k,m} \leq \text{MaxTAFB}, \quad \forall k \in K $$

5.4.2 任务环间休假约束

$$ \tau_{k,m+1}^{\text{start}} - \tau_{k,m}^{\text{end}} \geq \text{MinVacDay}, \quad \forall k, m $$

即:上任务环结束日与下任务环开始日之间至少有 MinVacDay 天。

5.4.3 连续执勤天数约束

$$ \sum_{i=0}^{\text{MaxSuccOn}} w_{k,d+i} \leq \text{MaxSuccOn}, \quad \forall k, d $$

即:任意连续 MaxSuccOn+1 天内至少有一天休息。

5.4.4 任务环基地约束

每个任务环的第一次执勤必须从基地出发,最后一次执勤必须回到基地:

$$ f_1^o = b_k, \quad f_{\text{last}}^d = b_k, \quad \forall \text{ 任务环} $$

5.4.5 排班周期约束

所有任务环和休假覆盖整个排班周期,初始和结束位置都在基地。

5.5 完整优化模型

记前序问题的最优值分别为 $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}} $$

5.6 算法策略

  1. 列生成法(推荐):
    • 主问题(RMP):集合覆盖/分割模型,选择任务环覆盖所有航班
    • 子问题(Pricing):资源约束最短路径问题(RCSPP),生成新的任务环
  2. 三阶段串行求解:任务环生成(PO)→ 任务环分配(RO)→ 局部优化
  3. 启发式方法:
    • 遗传算法:编码任务环序列
    • 禁忌搜索:邻域结构包括任务环交换、拆分、合并
    • 大邻域搜索(LNS):破坏-修复框架

6. 模型结构总览

6.1 三层递进关系

子问题1(航班分配)
    │
    ├── 新增:执勤概念
    │
    ▼
子问题2(执勤模型)
    │
    ├── 新增:任务环 + 排班计划
    │
    ▼
子问题3(排班计划)

每一层都在前一层的基础上增加约束和优化目标,保持模型间的前向兼容。

6.2 约束继承关系

约束 子问题1 子问题2 子问题3
空间连续性(机场匹配) ✓ ✓ ✓
时间可行性(MinCT) ✓ ✓ ✓
基地出发/返回 ✓ ✓ ✓
航班覆盖(C1F1) ✓ ✓ ✓
资格/替补限制 ✓ ✓ ✓
乘机限制(MaxDH) ✓ ✓ ✓
每天最多一个执勤 ✓ ✓
执勤飞行时长(MaxBlk) ✓ ✓
执勤总时长(MaxDP) ✓ ✓
执勤间休息(MinRest) ✓ ✓
任务环总时长(MaxTAFB) ✓
任务环间休假(MinVacDay) ✓
连续执勤天数(MaxSuccOn) ✓

6.3 目标继承关系

编号 目标 子问题1 子问题2 子问题3
① 最大化覆盖航班 ✓ ✓ ✓
④ 最小化乘机次数 ✓ ✓ ✓
⑦ 最小化替补使用 ✓ ✓ ✓
② 最小化执勤成本 ✓ ✓
⑤ 平衡执勤时长 ✓ ✓
③ 最小化任务环成本 ✓
⑥ 平衡任务环时长 ✓

7. 求解策略

7.1 整体求解框架

采用分阶段字典序优化 + 列生成的混合策略:

阶段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

7.2 关键技术选择

技术 适用场景 工具
MILP 小规模精确求解 Gurobi / CPLEX / OR-Tools
列生成 大规模组合优化 自定义 + 求解器
约束规划 复杂规则约束 OR-Tools CP-SAT
遗传算法 大规模近似求解 DEAP / 自实现
局部搜索 解改进 禁忌搜索 / 模拟退火

7.3 数据预处理

  1. 时间统一:所有时间转换为相对计划周期起点的分钟数
  2. 机场编码:机场三字码映射为整数索引
  3. 资格矩阵:建立机组人员-航班资格可行性矩阵
  4. 衔接图构建:构建航班间可行衔接的有向无环图(DAG)
  5. 时空索引:按日期-机场建立航班索引以加速查询

8. 参考文献

  1. Xiaodong Luo, Yogesh Dashora, Tina Shaw (2015). Airline Crew Augmentation: Decades of Improvements from Sabre. Interfaces, 45(5): 409-424.

  2. 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.

  3. 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.

  4. Cappanera, P. & Gallo, G. (2004). A Multicommodity Flow Approach to the Crew Rostering Problem. Operations Research, 52(4): 583-596.

  5. 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.

  6. Desaulniers, G., Desrosiers, J., Dumas, Y., Solomon, M.M., Soumis, F. (1997). Daily Aircraft Routing and Scheduling. Management Science, 43(6): 841-855.


9. 完整优化问题总结

本节将三个子问题统一表述为完整的数学规划形式,按字典序优先级给出最终的一体化模型。

9.1 统一决策变量全集

航班级变量

$$ \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} $$

9.2 目标函数(字典序)

优化按以下优先级依次进行,后一阶段以前一阶段的最优值为约束。

层级 编号 目标 方向 表达式
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}}$。

9.3 完整约束体系

(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}} $$

(C2) 空间连续性

$$ 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 中通过只为可行衔接创建变量来隐式处理。

(C3) 时间可行性

$$ 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}] $$

(C6) 乘机限制 —— $\forall f$

$$ \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} $$

(D4) 执勤内同天约束

$$ v_{k,f,g}^{\text{duty}} = 1 \Rightarrow \text{day}(f) = \text{day}(g) $$

(D5–D6) 执勤间休息和连续性

$$ r_{k,f,g} = 1 \Rightarrow (t_g^{\text{dep}} - t_f^{\text{arr}} \geq \text{MinRest}) \land (f^d = g^o) $$

(D7) 衔接分类

$$ 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} $$

(R4) 任务环基地约束

每个任务环的第一次执勤从基地出发,最后一次执勤回到基地。

9.4 模型规模

子问题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。

About

No description, website, or topics provided.

Resources

Stars

1 star

Watchers

0 watching

Forks

Releases

Packages

Contributors

Languages