华为杯F题思路

2021年华为杯F题思路梳理，包括机组人员、排班问题、问题假设、赛题、数据说明、提交要求等，非常清晰，需要的自取。

F题

• 机组人员
  • 飞行员
  • 乘务员
  • 空警
• 排班问题
  • 特定时间段的机组日程安排
    • 每个机组人员在何时何地哪个航班执行任务
      • 劳逸平衡
      • 机组偏好
      • 组员同行
      • 培训
      • 时近性
      • 休假
  • 通常做法
    • 机组分别求解
    • 飞行员：按机型分别求解
  • 方法：
    • 以满足规范和节约成本为主要目的任务环生成
      • Pairing Optimization（PO）
    • 以满足公平合理为主要目的任务环分配
      • Roster Optimization（RO）
    • 建立网络流模型（Network Flow） 然后列生成法（Column Generation）求解
      • 列生成法易于处理各种复杂的约束条件，优化模型比较简单，在计算性能上有很大的优势，对解决分配问题非常有效，虽然算法效果的好坏也取决于子问题及算法部件的局部处理方法。
    • 缺陷如：
      • 不能很好地处理这样的不完整任务环问题
        • 实际排班过程中需要具备人工预排班功能
        • 一个机组人员可能会乘坐指定航班到某地但回程却由系统安排
      • 两阶段解法缩小了优化空间，所谓的最优解其实是次优解
      • 对列生成法而言，各种规章约束参数主要是在列生成过程中考虑，优化模型本身缺乏这些约束参数的显性表达，通常的参数敏感性分析手段不能采用，因而难以对业务规则的制订起到指导作用
• 本题目的：建立线性优化模型，明确表达飞行时间、执勤时间、休息时间等约束，把航班直接分配给机组人员
• 背景
• 问题假设：机组排班问题假设航班规划阶段已经完成，机型分配已经结束，对机组人员数量及资格的需求已经明确，而且可用机组人员也已经确定
  • 时间
  • 机场
  • 机组人员
    • 基地
    • 资格
      • 主要资格
      • 替补资格
  • 任务
    • 飞行任务
    • 乘机任务
  • 航班
  • 执勤
    • 到达出发一致
    • 最短时间约束
    • 每个航段在同一天起飞
  • 任务环
    • 基地出发回到基地，一连串执勤休息组成
      • 结束机场与其实机场一致
      • 相邻执勤满足最少休息时间
      • 第一次执勤出发、最后一次执勤到达都在基地
  • 排班计划&排班周期
    • 排班计划：由一系列任务环和休假组成
    • 排班周期：两星期或一个月
    • 排版周期初始和中止都在基地
  • 问题描述
• 赛题：三个字问题，向前兼容
  • 假设
    • 1.机组人员之间可以任意组合
    • 2.允许存在因为无法满足最低机组资格配置而不能起飞的航班
    • 3.不满足最低机组资格配置的航班不能配置任何机组人员
    • 4.机组人员可以乘机摆渡，即实际机组配置可以超过最低配置要求，乘机机组人员的航段时间计入执勤时间，但不计入飞行时间
  • 问题1：要求建立线性规划模型给航班分配机组人员（或者说给机组人员分配航班），依编号次序满足目标
    • 目标
      • 1尽可能多的航班满足机组配置
      • 4尽可能少的总体乘机次数
      • 7尽可能少使用替补资格
    • 约束
      • 1.每个机组人员初始从基地出发并最终回到基地
      • 2.每个机组人员的下一航段的起飞机场必须和上一航段的到达机场一致
      • 3.每个机组人员相邻两个航段之间的连接时间不小于 MinCT分钟
  • 问题2：引进执勤概念。假定每个机组人员 的每单位小时执勤成本给定（可以设想为小时工资）。本子问题除了需要满足子问题1的所有目标外，还需满足如下目标（依编号次序）
    • 目标
      • 2.机组人员的总体执勤成本最低
      • 5.机组人员之间的执勤时长尽可能平衡
    • 约束
      • 1.每个机组人员每天至多只能执行一个执勤
      • 2.每次执勤的飞行时间最多不超过MaxBlk分钟
      • 3.每次执勤的时长最多不超过 MaxDP分钟
      • 4.每个机组人员下一执勤的起始机场必须和上一执勤的结束机场一致
      • 5.每个机组人员的相邻两个执勤之间的休息时间不小于 MinRest分钟
  • 问题3：编制排班计划。假定每个机组人员 的每单位小时任务环成本给定（注：不包括执勤成本，可以设想为出差补贴）。本子问题除了需要满足子问题1和2的所有目标外，还需满足如下目标（依编号次序）
    • 目标
      • 3.机组人员的总体任务环成本最低
      • 6.机组人员之间的任务环时长尽可能平衡
    • 约束
      • 1.每个机组人员每个排班周期的任务环总时长不超过 MaxTAFB 分钟
      • 2.每个机组人员相邻两个任务环之间至少有MinVacDay天休息
      • 3每个机组人员连续执勤天数不超过MaxSuccOn天
  • 赛题
• 数据说明
  • 两套验证数据：先A后B
    • 输入参数
    • 航班计划数据格式
    • 机组人员数据格式
• 提交要求
  • 建立完整数学模型
  • 根据模型设计求解算法
    • 模型和算法是两个独立的概念
    • 算法必须针对数学模型的特点设计
  • 编写程序算法，并使用给定数据进行实验
  • 论文
  • 数据描述
  • 程序实现的计算结果
    • a.按拟起飞日期和时间，出发和到达机场的次序，罗列没有机组配置的航班号和其最低配置需求。此结果需从Excel 表格按CSV 格式导出，数据项名称简单易懂，用文件名 “UncoveredFlights.csv” 提交。
    • b.按机组人员，按日期，按航段次序，罗列该机组人员的航班分配，需注明航班号，起飞日期时间/机场和到达日期时间/机场，任务性质（机长，副机长，替补，乘机）等。如休假日也需注明。此结果需从Excel 表格按CSV 格式导出，数据项名称简单易懂，用文件名 “CrewRosters.csv” 提交。