(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202111415694.1 (22)申请日 2021.11.25 (71)申请人 杭州优迈科思信息科技有限责任公 司 地址 310024 浙江省杭州市西湖区转塘街 道山景路7号3幢5楼5 04室 (72)发明人 郭斯琪　肖璠　谢可欣　 (74)专利代理 机构 上海百一领御专利代理事务 所(普通合伙) 31243 代理人 杨颜颜 (51)Int.Cl. G06Q 10/06(2012.01) G06Q 10/04(2012.01) G06Q 10/10(2012.01) G06Q 50/30(2012.01) (54)发明名称 一种智能飞行机组 组环的生成方法及设备 (57)摘要 本申请的目的是提供一种智能飞行机组组 环的生成方法及设备， 本申请通过根据智能飞行 机组的基础数据搜寻出所有满足规则条件的值 勤日， 得到值勤日集合； 根据所述值勤日集合构 建航班组环网络图； 基于待排航班 集合和初始任 务环集合构建航班组环模型； 使用分支定价法对 所述航班组环模 型进行主问题 求解， 得到可行任 务环； 使用多标签最短路径算法寻找所述航班组 环模型的主问题求解的优化路径， 得到优化任务 环， 根据所述各航班的可行任务环和所述优化任 务环求解所述航班组环模型， 确定智能飞行机组 的组环方案。 从而可以在有限的求解时间内保证 方案质量和鲁棒性， 具有较高的研究意义与应用 价值。 权利要求书3页 说明书11页 附图3页 CN 114037346 A 2022.02.11 CN 114037346 A 1.一种智能飞行机组 组环的生成方法， 其特 征在于， 所述方法包括： 根据智能飞行机组的基础数据搜寻出所有满足规则条件的值勤日， 得到值勤日集合， 其中， 所述 规则条件 包括民航局法规限制以及组环场景配置的规则； 根据所述 值勤日集 合构建航班组环网络图； 基于待排航班集合和初始任务环集合构建航班组环模型， 其中， 所述航班组环模型包 括模型目标函数和约束条件； 使用分支定价法对所述 航班组环模型进行主问题求 解， 得到各航班的可 行任务环； 使用多标签最短路径算法寻找所述航班组环模型的主问题求解的优化路径， 得到优化 任务环， 根据所述各航班的可行任务环和所述优化任务环求解所述航班组环模型， 确定智 能飞行机组的组环方案 。 2.根据权利要求1所述的方法， 其特征在于， 根据智能飞行机组 的基础数据搜寻出所有 满足规则条件的值勤日之前， 包括： 获取与智能飞行机组排班相关的基础数据； 根据所述基础数据确定所述组环方案的求 解偏好并配置组环场景的规则。 3.根据权利要求1所述的方法， 其特征在于， 根据所述值勤日集合构建航班组环网络 图， 包括以下步骤： 根据所述值勤日集合确定每一人员基地、 每一人员任务的计划开始日期以及计划结束 日期； 对于任一人员 基地， 根据场景配置中设置的任务环最大持续日历日数量， 分别对于从 所述计划开始日期 至计划结束日期中的每一 天， 构建持续时间为一至任务环最大持续日历 日数量的时空网络图； 按照筛选规则 筛选出所述值勤日集合中需要加入所述 时空网络图的目标值勤日， 在满 足民航局法规限制 中的地点衔接、 休息规则以及场景配置的规则的值勤日之间设置连接 弧， 以完成航班组环网络图的构建。 4.根据权利要求3所述的方法， 其特 征在于， 所述筛 选规则包括以下步骤： 若值勤日的开始时刻对应日期等于所述 时空网络图的起始日期， 则继续判断所述值勤 日的起始机场是否为对应的人员基地， 若是， 则加入所述时空网络图； 若值勤日的日期等于所述时空网络图中的中间的任一日期， 则直接加入； 若值勤日的结束时刻对应日期等于所述 时空网络图的结束日期， 则继续判断所述值勤 日的到达机场是否为对应的人员基地， 若是， 则加入。 5.根据权利要求1所述的方法， 其特征在于， 基于待排航班集合和初始任务环集合构建 航班组环模型构建航班组环模型， 包括： 确定待排 航班集合和初始任务环集 合， 并设定固定整数变量的阈值； 根据所述初始任务环集合中每一任务环的成本、 该任务环被组环方案选择的决策变量 以及计划期内所有生成的任务环集 合构建航班组环模型的模型目标函数； 根据对集 合划分的约束以及对变量取值的约束确定航班组环模型的约束条件。 6.根据权利要求5所述的方法， 其特征在于， 所述模型目标函数表示最小化组环方案的 总成本， 所述模型目标函数满足以下 条件：权　利　要　求　书 1/3 页 2 CN 114037346 A 2其中， p表示任务环， cp表示任务环p的成本， xp为0或1的决策变量， 表示该任务环p是否 在最终的组环方案中被选择， P表示计划期内所有生成的任务环集 合。 7.根据权利要求6所述的方法， 其特 征在于， 所述约束条件 满足以下 条件： 其中， L表示待排 航班集合， l表示计划航段。 8.根据权利要求5所述的方法， 其特征在于， 使用分支定价法对所述航班组环模型进行 主问题求 解， 其中， 主问题求 解包括以下步骤： 步骤1， 判断当前解是否为整数解， 如果不是执行步骤2， 否则退出， 获得新的航班组环 方案； 步骤2， 设定集合 表示最终得到的组环方案； 当满足xp≥κ1时， 将对应的xp加入集合 其中， κ1表示固定整数变量的阈值； 步骤3： 对于 设置xp下界LB(xp)＝1， 表示该任务环p被选中， 如果存在别的任 务环p′与任务环p包含同一航班l， 设置该任务环对应变量值xp′上界UB(xp′)＝0， 表示任务 环p′被淘汰； 步骤4： 求 解航班组环模型主问题的线性松弛解。 9.根据权利要求8所述的方法， 其特征在于， 使用多标签最短路算法寻找所述航班组环 模型的主问题求 解的优化路径， 得到优化任务环， 包括： 使用多标签最短路算法基于构建的航班组环网络图寻找所述航班组环模型的主问题 求解的优化路径； 若找到一组有利于主问题求解优化的任务环， 则将该组任务环添加至任务环集合中， 跳转到步骤4； 当无法找到有利于主问题求 解优化的任务环， 则跳转到步骤1。 10.根据权利要求9所述的方法， 其特征在于， 使用多标签最短路算法基于构建的航班 组环网络图寻找所述 航班组环模型的主问题求 解的优化路径， 包括以下步骤： 步骤S1， 初始化所述航班 组环网络中所有节点的标签， 其中， 所述标签包括当前部分路 径包含的值勤日集 合、 总检验数； 步骤S2， 按照拓扑排序依次遍历每一个节点， 并获得其后续节点的集合， 如果遍历完毕 则执行步骤S5， 否则执 行步骤S3； 步骤S3， 对于节点中的任一标签以及后续节点的集合中的任一节点， 按照所述规则条 件进行规则校验， 若 校验为满足规则条件则跳转到步骤S4， 若 校验为不满足规则条件， 则重 新执行步骤S3； 步骤S4， 根据满足规则条件的标签以及校验成功的后续节点的集合中的目标节点的内 容生成新的标签， 将所述新的标签与所述 目标节点中已有的所有标签进行占优判断， 若所 述目标节点中已有的任一标签的校验数小于所述新的标签， 则不保留所述新的标签， 否则，权　利　要　求　书 2/3 页 3 CN 114037346 A 3