(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210884619.8 (22)申请日 2022.07.26 (71)申请人 北京航空航天大 学 地址 100191 北京市海淀区学院路37号 (72)发明人 刘虎　禹逸雄　田永亮　 (74)专利代理 机构 北京天汇航智知识产权代理 事务所(普通 合伙) 11987 专利代理师 高永 (51)Int.Cl. G06Q 10/06(2012.01) G06Q 10/04(2012.01) G06N 3/00(2006.01) G06Q 50/26(2012.01) (54)发明名称 一种异构直升机机队调度方案分层级优化 方法 (57)摘要 本发明公开了一种异构直升机机队调度方 案分层级优化方法， 包括以下步骤： S1， 归纳灾情 中的重要信息， 结构化输入任 务想定信息； S2， 构 建异构直升机机队的调度问题模 型， 包括任务分 工优化模型和路径规划问题模型两个层级； S3， 设计解的数据结构， 将任务分工矩阵作为任务分 工优化模型对应的数据结构， 直升机任务轨迹作 为路径规划问题模型对应的数据结构； S4， 结合 解的数据结构和路径规划问题模 型， 设计路径规 划的求解器； S5， 结合解的数据结构、 任务分工优 化问题模型和路径规划求解器， 设计任务分工矩 阵优化的求解器。 该方法将调度方案从文本型变 成数据型， 从实时调度变成方案制定， 能够有效 提高调度方案效率。 权利要求书3页 说明书16页 附图4页 CN 115204711 A 2022.10.18 CN 115204711 A 1.一种异构直升 机机队调度方案分层级优化方法， 其特 征在于， 包括以下步骤： S1， 归纳灾情中的重要信息， 结构化输入任务想定信息， 包括直升机机队的组成及各直 升机的性能参数， 航空应急救援任务的救援需求， 为航空应急救援任务提供资源的地点， 航 空应急救援任务所 涉及的地理位置信息； S2， 根据输入的任务想定信息， 构建异构直升机机队的调度问题模型， 所述模型包括任 务分工优化模型和路径规划问题模型两个层级； S3， 对应所述任务分工优化模型和路径规划问题模型， 设计解的数据 结构， 将任务分工 矩阵作为任务分工优化模型对应的数据结构， 直升机任务轨迹作为路径规划问题模型对应 的数据结构； S4， 结合解的数据结构和路径规划问题模型， 设计路径规划的求解器： 所述求解器采用 分支定界算法和自适应蚁群算法完成计算， 能够根据任务分工矩阵所确定的分工， 确定每 架直升机的任务轨 迹， 使得直升 机完成全部任务的总体飞行轨 迹最短； S5， 结合解的数据结构、 任务分工优化问题模型和路径规划求解器， 设计任务分工矩阵 优化的求解器： 所述求解器采用伪粒子群算法的启发式操作算子完成计算， 实现任务分工 矩阵的优化。 2.根据权利要求1所述的异构直升机机队调度方案分层级优化方法， 其特征在于， 所述 步骤S2中， 所述路径规划问题模型的优化目标函数和约束条件公式为： 其中， th为直升机h完成其被分配的所有任务的时间； 为直升机h在任务过程中作业的 时间； 为直升机h在任务过程中在路上的时间； N为需求点集合； Knh为直升机h为了需求n 而需要执行的任务清单中的任务数量； mtnhk为mnhk的作业时间； 为直升机h在任务过程中 在路上的时间； ； vh为直升机的巡航速度； H为直升机集合； 为直升机h在l时的剩余续航时 间； d0,1为地点l与基地之间的距离， 其中基地的地点编号为0； ph为直升机h的任务轨迹， 是 途径地点的集合； Ph[i]代表直升机h的任务轨迹上的第i个地点； 为直升机h的任 务轨迹上第i个地 点和第i+1个地 点之间的距离 。 3.根据权利要求2所述的异构直升机机队调度方案分层级优化方法， 其特征在于， 所述 步骤S2中， 所述任务分工优化模型的优化目标函数和约束条件公式为： Minimize t＝max(t1,t2,...,th,...)      (5) 权　利　要　求　书 1/3 页 2 CN 115204711 A 2其中， th为直升机h完成其被分配的所有任务的时间； mcnhk为mnhk的任务种类； Ch为直升 机h可以执行的任务类 集合； Knh为直升机h为了需求n而需要执行的任务清单中的任务 数量； qn为需求n的任务量； mqnhk为mnhk的任务载荷； mrnhkr， mrnhkr＝0/1,如果mnhk由r提供资源, mrnhkr＝1； cnh为直升机h执行对应需求为n的任务时的最大单次任务能力； 为直升机h的 最大续航； mtnhk为mnhk的作业时间； mpfnhk为mnhk的任务路径中的第 一个地点； mplnhk为mnhk的 任务路径中的第二个地 点。 4.根据权利要求3所述的异构直升机机队调度方案分层级优化方法， 其特征在于， 所述 步骤S3中， 所述任务分工矩阵的每一行对应一架 直升机， 每一列对应一个需求； 任务分工矩 阵中的元素为任务列表， 表示指挥中心安排第i架直升机执行的关于第j个需求的任务列 表； 任务列表中的每一个任务都具有路径、 载荷、 类型和执 行时间4个属性； 所述直升机任务轨 迹由一串数字表达， 其中每一个数字代 表一个城市。 5.根据权利要求4所述的异构直升机机队调度方案分层级优化方法， 其特征在于， 所述 步骤S4， 所述路径 规划的求解器， 在求解中使用自适应蚁群算法， 在 对最优解进 行验证时使 用分支定界算法。 6.根据权利要求5所述的异构直升机机队调度方案分层级优化方法， 其特征在于， 所述 自适应蚁群算法， 将直升机路径规划转变为蚁群的路径搜索优化问题； Ant是一个类， 其具 有的属性包括当前所在城市lh， 在当前城市的剩余续航时间 当前走过的轨迹ph， 走过的 总距离Dh， 剩余任务列表MLAnt； Ants中不同Ant的最终任务路径视作直升机h对于最佳任务 轨迹的一次探索， 是 可行的直升 机任务轨 迹； Ants进行轨迹探索的过程中， Ant首先计算MLAnt中mnhk的任务选择概盔 然后根据 轮盘赌的原则进行下一个任务的选择； 每一轮循环中， 首先初始化Ants中的全部Ant， 然后 每一只Ant根据启发规则寻找一条可行任务轨迹， 最终找到该轮循环中任务轨迹最短的个 体作为该轮迭代过程中的最优Ant。 7.根据权利要求5所述的异构直升机机队调度方案分层级优化方法， 其特征在于， 所述 分支定界算法， 搜索树的每个节点相当于是一架直升机在执行任务过程中的一个中间状 态， 具有当前节点轨迹、 当前轨迹耗时、 未完成任务列 表、 直升机剩余续航时间四个属性； 从 根节点出发， 不断进 行分枝操作生 成新一代节点， 直到有一条分支完成了全部任务， 搜索树 生成第一个端节点； 之后， 搜索树将开始剪枝操作， 停止不符合条件的中间节点的生长， 直 到新生成的子代 节点全部都是端节点， 算法结束。 8.根据权利要求5所述的异构直升机机队调度方案分层级优化方法， 其特征在于， 所述 步骤S5， 所述求解器采用伪粒子群算法的启发式操作算子完成计算， 实现任务分工矩阵的 优化， 包括以下步骤： (1)生成Psize个初始任务分工矩阵， 每 个任务分工矩阵对应一个粒子；权　利　要　求　书 2/3 页 3 CN 115204711 A 3