Problem Statement
机组排班的目的是为各航班指派飞行所需的各岗位人员，同时结合机组人员的培训、休假等占位任务，生成特定时间段的日程安排。由于航班计划的变动，人员培训、值班、休假等占位任务的调整，机组排班通常在实际运行的前一周完成，属于航空公司的短期计划问题。
硬约束（违反-10’）：
①地勤任务必须执行
②仅允许值勤日的开始或结束进行置位
③地点衔接
④有资质才能飞
⑤连接时间约束：飞行或飞行置位任务，飞机尾号不同，前序和后续任务间隔不小于3小时；大巴置位而言，与相邻飞行任务之间最小间隔时间为2小时。
⑥每个值勤日内飞行任务数量不超过4个，总任务数量不超过6个
⑦飞行值勤日开始前最小休息时间设为12小时
⑧飞行值勤日总飞行时间不超过8小时、值勤时间不超过12小时
⑨计划期内的总飞行值勤时间不得超过60小时
⑩ 值四休二：一个飞行周期最多横跨4个日历日，并且飞行周期开始前必须连续休息2个完整的日历日
情况①表示如果飞行周期中出现少于2个完整日历日的休息，则认为当前飞行周期尚未结束；如果出现2个及以上完整日历日的休息，则认为当前飞行周期已结束，可以开始新的飞行周期。
情况②③④表示飞行周期后可接置位或占位任务，此时不视为飞行周期，不参与横跨4个日历日的计算。但此后的飞行周期开始时间距离上一值勤日应保证2个完整日历日的休息，遵守则②合规，否则④违规；如果此后不包含飞行值勤日，认为不构成飞行周期，无需考虑2个完整日历日的休息。
软约束（违反-0.5’）：
①外站过夜：不在base过夜，但在layover airport过夜
②置位（大巴 or 航班）
③未覆盖航班（5’ per）
潜在约束：
①计划期要从staystation出发
②两个连续休息日前尽可能回base
否则，会产生3次外站过夜的违规
Task
- 输入：航班、机长、占位任务、大巴、资质匹配、可过夜机场等数据。
- 输出：为期7天的每位机长的个人任务排班表。
- 目标：最大化“飞行值勤日日均飞时”，同时最小化因“未覆盖航班”、“新增过夜站点”、“外站过夜天数”、“置位次数”和“违规次数”导致的扣分。
- 约束：必须遵守地点衔接、时间衔接、任务数量、飞行时长、值勤时长、休息时间、值勤周期、总工时和资质共10大类规则。
Input：
Output：
Challenge
- 计划期是一个被截断的短周期。事实上计划期开始，并不能完全假定所有飞行员都是available
尤其是启发式方法，短视，可能会带来"资源雪崩"和"波谷效应" - 可以在计划期前对部分飞行员进行提前置位。
但不知道理想置位地点 - 贪心方法会生成大量低效FDP，尽管能增加航班覆盖率，但会造成日均飞时的下降和大量的外站过夜和置位。（未解决）
必然会影响航班覆盖率，我们期待的是 尽可能多的形成高任务密度的FDP，如果仅仅是增加一个FDP去多覆盖2个航班，我们认为是效率不高的 - 以机长为中心 还是 以航班为中心 构造启发式算法
crew-focus更能考虑到机长的整个任务周期特性，但慢；flight-focus能较快的构造出一个性能还不错的初始解，但离最优的距离比较远
Methodology
贪心策略
- 资质优先 优先选择能飞航班较少的机组（“窄资质”机组）。逻辑是：这些机组的选择面很窄，先把他们能飞的、困难的任务分配掉，剩下更容易的任务可以留给“宽资质”的万能机组去解决。
- 基地优先 优先选择能让机组在模拟的“终点”回到基地的方案
- 负潜力优先 优先选择未来机会更多的方案，避免让机组飞到一个“死胡同”机场
- 等待时间优先 指两次任务间的“休息”时间。优先选择等待更短的方案，即衔接更紧凑的。
- 分层资质策略（仍可探索）
- 第一梯队：“浅资质”机长
- 定义：只能飞很少几种任务的“专才”。
- 策略：最优先派遣。
- 逻辑分析：最不灵活的资源，机会窗口窄。必须在第一时间，将那些只有他们能干的活儿分配给他们。优先解决最受限问题的策略。
- 第二梯队：“高资质”机长
- 定义：能飞很多种任务的“通才”或“万金油”。
- 策略：次优先派遣。
- 逻辑分析：最大化这些高资质机长的价值，因为这些机长通常能够形成更长的飞行任务链。避免后期无将可用：防止“通才”在后期被一些简单的任务占用，导致真正需要他们时却分身乏术。
- 第三梯队：“一般资质”机长
- 定义：资质数量居中的主力军。
- 策略：最后派遣。
- 逻辑分析：这是前两个策略执行后的自然结果。
- FDP质量贪心策略：
当一个未覆盖的航班（按时间顺序）需要被分配时，算法会为所有合格的机组生成候选的FDP方案。直接保证了生成的FDP是任务饱满、效率高的，从根本上提升了日均飞时，减少了总执勤日
但航班覆盖率捉襟见肘
主动置位
动机：计划期开始前，crew的分布极不均匀。一个合理的分布：base airport的crew适当过剩，layover airport仅有少量机长，供大于需，但是现在的数据分布是会存在一个特别的机场，其crew大大大大量聚集，远超正常的分布。
当前的数据分布极不均匀，直接用贪心算法，会有大量crew资源被限制以至于被浪费
置位回base：（PASS）
针对 部分机场 将所有crew尽可能置位回各自的base
两日闲人交集：(PASS)
- 对29日的所有航班进行一次有逻辑的预分配，这次分配至少要尊重机长的初始位置和飞行资质，确定29日的闲人集合
AA。 - 基于这个更真实的预分配结果，来确定29日结束后，每个机长的位置。
- 用这个更准确的30日初始位置数据，去计算30日的闲人集合
BB。 这样，我们得到的BB集合与AA的交集也就是该机场未来两天的“闲人”，是可以毫无顾虑的置位，以支援其他机场。
逆转时间（Accept）
一种基于动态规划 反向递推思想 的启发式方法
本质上是一种两阶段式的启发式架构。
第一阶段：将时间轴逆转，从尾到头通过贪心算法生成排班计划。
不用考虑staystation的约束，可以生成一个近似的 启发式的 理论最优解
第二阶段：
STEP1：如果第一阶段 生成的理论最优排班计划 中，存在crew的最后到达地 和 staystation一致，我们认为这些crew的staystation本身就是ideal，因此这部分的crew的排班计划可以被认为是 ideal计划。因此锁定这部分crew的排班计划。若增加一趟主动提前置位能到ideal的，只有任务链合规，也锁定排班计划。
原数据中大概有2/3的Crew的staystation和base相同，经过实验验证：大概有1/2的Crew的staystation就是ideal的 & 初步分析，对于crew而言base是ideal的可能性很大
STEP2：针对STEP1中未锁定的机长，尽可能将其置位回各自的base，实在回不去的就留在原地。更新staystation，将未锁定Crew和未覆盖航班带入正向贪心过程，生成排班计划。
STEP3：合并两阶段的排班计划，共同构成初始解。
比较研究，逆转时间的两阶段架构 和 单纯正向贪心架构的 对比如下，融合反向递推的两阶段架构能带来 航班覆盖率的大幅提升，但外站过夜和置位次数也大幅增加。
中间改进过程
贪心算法部分，我们是以航班为中心，中间改进过程，我们真的飞行任务较少的飞行员，将其打乱，以Crew为中心，进行贪心搜索
融合策略
对于正-反 两阶段可以尝试在正反阶段采用不同的贪心策略，使初始解的结构不在单一，可能会更有利于后续的优化
立-破-立策略（未实现）
LNS or ALNS的哲学思想是在初始解基础上先破后立，那么后续优化过程的好坏就非常依赖于初始解的结构。
这种 初始解-优化 范式 的解耦结构 限制了优化模块的性能
能否 参考diffusion的思路，先在不考虑 任务重叠等硬约束的情况下，仅考虑时间先后，将所有航班 都 分配给机长 先把航班覆盖率拉到100%，然后再进行破坏，按照 硬约束规则 进行破坏，使得最终解是合规的
“立破立”的策略，能够在保障覆盖率的情况下进行优化
Appendix
 |  |
|---|---|
 |  |
 |  |