CTS2025 算法大赛获奖队伍算法总结

总体观察

CTS2025 的机组排班问题本质是一个带大量业务规则的组合优化问题：航班必须尽量覆盖，机组必须满足资质、时间、地点衔接、休息和值勤周期规则，同时还要控制置位、外站过夜、新增过夜机场和违规扣分。获奖队伍的方案虽然实现路径不同，但可以归纳出四个共同判断：

  1. 直接做全量整数规划很难。 航班、机长、占位任务、可过夜机场和大巴/飞行置位组合后，变量规模会迅速膨胀。
  2. 图模型是共同底座。 有的队把节点设为航班，有的队把节点设为机场-时间状态，有的队把弧升级为完整 FDP。
  3. 高质量初始解决定上限。 贪心、DFS、反向推演等方法用于快速构造可行解，避免后续算法从过差的解开始。
  4. 后处理负责补质量。 列生成、ALNS、遗传算法、模拟退火、Diving 取整等方法用于改进覆盖、飞时、置位和过夜。

iLorD：列生成 + 迭代分批释放

iLorD 队的主线是“基于列生成的迭代分批与释放算法”。该方案更接近运筹优化中的精确建模路线：先构造航班/占位/过夜节点组成的时空网络，再把每个机长的一条完整排班路径作为主问题中的一个列。

iLorD 分批释放流程

建模方式

主问题中的核心变量是 x_pk：是否把机长 k 的路径 p 选入方案。航班和占位任务如果没有被任何路径覆盖，则用取消变量表示并计入惩罚。约束包括：

  • 每个航班要么被一条机长路径覆盖，要么记为未覆盖；
  • 每个占位任务要么被路径覆盖，要么记为未覆盖；
  • 每个机长最多选择一条路径；
  • 路径内部已经通过子问题保证资质、时间、地点、休息、置位和值勤周期可行。

算法流程

列生成直接在全体机长上跑会非常重，因此 iLorD 引入“分批 Batch + 释放 Release”：

  • 分批策略：优先选择值勤/休息占位任务多、可执飞航班多的未排班机长，让难度较高的资源先进入优化。
  • 释放策略：当仍有未覆盖航班时，释放能覆盖这些航班的已排班机长；当方案利用率低时，优先释放日均飞时低的机长。
  • 子问题：使用多标签最短路生成新路径，标签记录成本、值勤日内任务数、飞行时间、总飞行时间、休息时间、周期日历天数、置位位置等状态。
  • 支配规则：如果一个标签在成本、任务数量、飞行时间、休息和周期状态上都不劣于另一个标签，就删除劣势标签，压缩搜索空间。
  • Diving 取整：RMP 线性松弛产生大量非整数变量时，选取接近 1 的变量临时取整并重新求解，逐步得到整数方案。

该路线的优势是质量高、约束表达完整，适合追求全局质量；代价是实现复杂，依赖高效子问题、并行和求解器。

NJUORLAB：启发式初解 + FDP 网络列生成

NJUORLAB 的方案是“启发式与精确算法融合”。它不是直接在航班网络上做列生成，而是先生成合法 FDP，再把搜索粒度提升到 FDP 网络。

NJUORLAB 列生成框架

两阶段框架

第一阶段用启发式方法构造可行初解：

  • 为每个机组创建 CrewSchedule；
  • 用 DFS 搜索候选任务序列；
  • 每加入航班或大巴任务，都检查时间衔接、值勤日状态、飞行周期和置位合法性；
  • 用破坏重建和模拟退火做局部优化；
  • 在最后阶段扩大 DFS 分支数，提高覆盖航班数。

第二阶段进入列生成：

  • 离线生成所有合法 FDP；
  • 对每个机组按资质、基地、初始位置和占位任务过滤可执行 FDP；
  • 构建个性化 FDP 时空网络并序列化到磁盘；
  • 在线列生成时读取网络，根据主问题对偶价动态更新弧收益；
  • 使用 Beam Search 在 FDP 网络中找高检验数路径。

NJUORLAB FDP 网络离线构建

关键创新

传统 SPPRC 子问题如果以航班为基本单元，状态会非常复杂。NJUORLAB 把弧定义为完整合法 FDP，节点是 (机场, 时间)，一条弧代表相同起终点节点之间的若干 FDP，并把弧收益设为这些 FDP 的最大收益。这样在线求解时只需要在更高层 FDP 网络中搜索，Beam Search 可以在速度和质量之间做平衡。

ORA 队：DFS 初始解 + ALNS 改进

ORA 队采用的是典型的“构造启发式 + 大邻域搜索”路线。它把问题拆成单个机长的周期规划，先用 DFS 生成初始排班，再用 ALNS 对低质量部分进行破坏和修复。

ORA ALNS 算子

初始解构造

ORA 先按“值 4 休 2”规则和地面占位任务，把每个机长在计划期内的可用时间切成多个飞行周期。对于每个周期：

  • 根据机长资质和时间安排筛选可行航班；
  • 单值勤日内从可安排航班或大巴出发做 DFS；
  • 对每条候选任务链按覆盖、飞时、置位、过夜和违规等指标评分；
  • 从 top-K 方案中随机选择一个，避免完全贪心导致路径单一；
  • 周期结束后安排置位，让机长回到基地或合适位置。

ALNS 改进

ALNS 阶段的核心是“选择部分机长，拆掉他们现有排班，再重新构造”：

  • 基于约束违反的破坏：优先破坏扣分高、违规多的机长排班；
  • 基于日均飞时的破坏：优先破坏日均飞时低的机长排班；
  • 构造修复：对被破坏机长重新调用 DFS；
  • 最优修复：每轮遍历修复候选，先固定得分最高的机长方案，再删除其使用航班，继续修复剩余机长。

这种方法工程上相对直观，适合规则复杂但需要快速迭代的场景。

前进四：航班连接图 + 边类型优先级

前进四队使用航班连接有向图建模。节点是航班，边表示两个航班在机场和时间上可衔接。算法按起飞时间遍历航班，相当于沿航班连接图的拓扑顺序做分配。

前进四 航班连接边类型

核心模型

每个航班节点包含起降机场、起降时间、尾号和飞行时间。有向边 A -> B 成立需要满足：

  • A.to == B.from；
  • A.sta + min_connect <= B.std；
  • 飞行和值勤时间不超过规则上限。

初版逐航班选择机长，容易因为过早分配导致后续航班无人可接。后续优化是给边增加类型：

  • type=0：同尾号且可直接连接；
  • type=1：普通直接连接；
  • type=2：通过飞行置位连接；
  • type=3：通过大巴置位连接。

分配当前航班后，算法优先沿 type=0 延伸，再尝试 type=1/2/3，尽量把连续高质量航段留给同一个机长。该算法复杂度低、速度快，适合作为初始解生成器；PPT 中也提到后续可接遗传算法、模拟退火或强化学习继续调优。

只会贪心：个性化任务图 + DP 剪枝 + 遗传算法

只会贪心队同样采用图模型，但它为每个机组构建个性化任务图，并在图上搜索源点到汇点的高得分路径。

只会贪心 支配规则与 DAG 动态规划

图上搜索

每个任务节点可以有双重身份：飞行任务或飞行置位。如果一个航班已经被其他机组执飞，当前机组仍可把它作为置位任务使用。这个状态切换不需要重构图，复杂度是 O(1)。

路径搜索时，算法给不同任务赋分：

  • 飞行任务加分；
  • 置位任务扣分；
  • 占位任务和回基地路径有额外处理；
  • 外站过夜、未回基地等产生惩罚。

由于任务图是 DAG，同一节点天然不会重复访问。算法用支配规则删除劣势路径：如果路径 A 在得分、开始时间、任务时间、飞行时间等维度都不劣于路径 B，则 B 不再保留。这样图上搜索接近动态规划。

遗传算法优化顺序

PPT 中指出机组处理顺序会显著影响结果，因此外层用遗传算法优化“机组排列”：

  • DNA 是机组处理顺序；
  • 适应度是贪心搜索后的总得分；
  • 使用精英保留；
  • 使用顺序交叉；
  • 使用交换、反转、插入等变异；
  • 多线程并行评估。

它的经验结论是：贪心可以在十几秒生成较高质量初解，遗传算法继续提高分数；但单值勤日视角仍会限制跨值勤日协调。

章鱼哥的紧箍咒：反向推演 + 两阶段抢任务 + ALNS

章鱼哥的紧箍咒队强调“计划期截断”和“初始机组分布不均”带来的路径依赖。它先从计划期末反向推演一个理论终局状态，再决定哪些机组可以锁定、哪些机组需要释放重排。

章鱼哥 反向推演与迭代优化框架

反向推演

反向推演的目标是估计每个机组更理想的初始位置：

  • 从最后降落的航班开始，按到达时间从晚到早处理；
  • 以当前航班作为“终点”，寻找前序航班，构造反向 FDP；
  • 得到每个被分配任务机组的理论最优计划；
  • 取反向计划最早出发机场作为理想初始位置。

第二阶段判断机组当前 StayStation 是否与理想初始位置一致，或者能否通过一次置位到达。如果可以，就锁定反向推演得到的任务链；否则把任务释放回任务池，交给正向贪心重排。

迭代优化

该方案后续使用三类改进：

  • 低任务量机组重构：找出任务量少、排班零散的机组，以 Crew 为中心重新构造任务链；
  • 两阶段抢任务：先 8 人小组、后 4 人小组，在小范围内重新分配任务，提高局部总分；
  • ALNS：使用随机、最差、关联、未覆盖等破坏算子，修复时采用贪心，并用模拟退火式接受准则允许少量劣解跳出局部最优。

这个方案的核心价值在于把“初始位置”纳入优化，而不是默认所有机组从计划期初自然可用。

横向比较

队伍 核心建模 初始解 改进方法 适合借鉴的点
iLorD 时空网络 + 机长路径列 DFS/VNS 初始列 列生成、分批释放、Diving 高质量全局优化、对偶价驱动
NJUORLAB FDP 时空网络 DFS + 破坏重建 列生成、Beam Search FDP 粒度子问题、离线网络缓存
ORA 单机长周期与任务链 DFS top-K ALNS 易落地的大邻域搜索框架
前进四 航班连接 DAG 拓扑顺序贪心 边类型优先级 快速初始解、连接类型建模
只会贪心 个性化任务图 图上路径搜索 遗传算法优化顺序 支配规则、DP 剪枝、状态切换
章鱼哥 反向 FDP + 正向贪心 反向推演锁定 两阶段抢任务、ALNS 初始位置修正、小组局部重排

对当前系统建设的启发

  1. 先做稳定航班环/FDP 层。 当前系统已有航班-only 组环，后续可以把“环”扩展为 FDP 或任务串，作为排班算法的上层输入。
  2. 保留人工锁定和算法补剩余。 多队方案都依赖“锁定一部分高质量结构，再释放低质量部分重排”的思路；这与当前人工预组环锁定机制一致。
  3. 后续算法可以分层演进。 第一层用贪心/DFS 快速覆盖航班，第二层用 ALNS 或两阶段抢任务做局部重排，第三层再引入列生成或对偶价。
  4. 规则检查要成为搜索状态的一部分。 iLorD 和 NJUORLAB 都把休息、值勤、置位、周期等约束编码进标签或 FDP 合法性中；否则后处理会产生大量不可修复违规。
  5. 机场位置和计划期边界要提前处理。 章鱼哥的反向推演说明，计划期开始时的机组分布会显著影响结果；后续粗排需要显式建模初始位置、基地和可置位策略。
  6. 性能工程很重要。 支配规则、哈希查询、预排序、离线网络序列化、并行求解和 Beam Search 都是把算法从可运行推到可控时间的关键。