(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210762184.X (22)申请日 2022.06.30 (71)申请人 中南大学 地址 410083 湖南省长 沙市岳麓区麓山 南 路932号 (72)发明人 伍国华　程佳淇　 (74)专利代理 机构 长沙国科天河知识产权代理 有限公司 432 25 专利代理师 赵小龙 (51)Int.Cl. G06F 30/20(2020.01) G06F 17/18(2006.01) G06Q 50/26(2012.01) G08G 1/123(2006.01) G06F 111/04(2020.01)G06F 111/06(2020.01) G06F 111/08(2020.01) G06F 111/10(2020.01) (54)发明名称 一种单车辆与多无人机协同弧路由调度方 法 (57)摘要 本发明公开了一种单车辆与多无人机协同 弧路由调度方法， 包括： 以完成所有巡逻任务且 车辆与无人机全部回到停车场的完成时间最小 为优化目标； 在满足约束条件的前提下， 通过启 发式算法生产巡逻路径规划策略的初始解； 采用 基于模拟退火与大范围邻域搜索混合的优化方 法对巡逻路径 规划策略进行迭代 寻优， 得到车辆 和无人机最优的巡逻路径规划策略。 本发明应用 于任务规划调度领域， 考虑路网不对称， 面向巡 逻任务对车机协同建立了混合整数规划模型， 并 考虑实际巡逻需求， 在中等以及大规模下， 构建 符合问题特征的邻域破坏算子， 在邻域破坏算子 的基础上， 建立基于结合模拟退火的大范围邻域 搜索框架的优化方法， 对车与无人机弧路由问题 进行协同规划。 权利要求书2页 说明书16页 附图7页 CN 115062486 A 2022.09.16 CN 115062486 A 1.一种单 车辆与多无 人机协同弧路由调度方法， 其特 征在于， 包括如下步骤： 步骤1， 以完成所有巡逻任务且车辆与无人机全部回到停车场的完成时间最小为优化 目标， 构建目标函数， 为： 式中， f(s)为车辆和无人机的巡逻路径规划策略为s时 的目标函数值， tPC为车辆和无人 机的巡逻路径规划策略为s时车辆回到停车场的完成时间， 为车辆和无人机的巡逻路径 规划策略为s时最后一架无 人机回到停车场的完成时间； 步骤2， 在满足约束条件的前提下， 通过启发式算法生产巡 逻路径规划策略的初始解； 步骤3， 采用基于模拟退火与大范围邻域搜索混合的优化方法对巡逻路径规划策略进 行迭代寻优， 得到车辆和无 人机最优的巡 逻路径规划策略。 2.根据权利要求1所述的单车辆与多无人机协同弧路由调度方法， 其特征在于， 步骤2 中， 所述约束条件 包括： 车辆路径约束， 用于保障车辆路径的连续性， 确保车辆从停车场出发， 并最终回到停车 场； 无人机路径约束， 包括： 无人机的每 个飞行路径只有一个放飞节点和一个回收节点； 放飞和回收无人机的节点一定是车辆路径中的节点， 即无人机与车辆之间的协同关系 依靠放飞和回收无 人机的节点相关联； 当车辆到达放飞点时， 只有在车辆上的无人机能够被放飞， 当车辆到达回收点时， 只有 不在车辆上的无 人机能够被回收； 无人机性能约束， 包括： 同一时间内最多 有d架无人机在飞行途中； 每架无人机在一次飞行 过程中都有最大飞行时间的限制； 时间约束以及任务约束， 用于确保车辆和无人机最早到达每个节点的时间， 以及确保 每一个任务都被无 人机或者车辆 至少访问一次。 3.根据权利要求2所述的单车辆与多无人机协同弧路由调度方法， 其特征在于， 步骤2 中， 所述通过启发式算法生产巡 逻路径规划策略的初始解， 具体为： 在满足约束的情况下将弧段任务分配给无人机或者车辆执行， 并确定每条弧段任务的 执行方向， 对于每条由无 人机访问的任务 边， 找到满足无 人机航程约束的起降点对； 根据无人机起降点顺序生成车辆路径， 并将所有由车辆访问的任务边插入车辆路径 中， 即形成巡 逻路径规划策略的初始解。 4.根据权利要求3所述的单车辆与多无人机协同弧路由调度方法， 其特征在于， 步骤3 具体包括： 步骤3.1， 获取初始温度T0、 终止温度Tmin、 最大迭代次数Imax、 退火速率γ与巡逻路径规 划策略的初始解s0； 步骤3.2， 令s＝s0、 s′＝s0、 T←T0、 i＝1， 其中， s为巡逻路径规划策略的最优解， s ′为巡 逻路径规划策略的当前解， T为当前温度， i 为迭代次数； 步骤3.3， 采用破坏算子对巡逻路径规划策略的当前解s ′进行随机破坏， 并采用修复算权　利　要　求　书 1/2 页 2 CN 115062486 A 2子对破坏后的当前解进行修复， 筛 选出修复后的中间解s*； 步骤3.4， 判断f(s*)＜f(s′)是否成立： 若是， 则令s ′＝s*， 并进入步骤3.6； 否则， 进入步骤3.5； 步骤3.5， 令Δf1＝(f(s′)‑f(s*))/f(s′)、 并获取0～1的随机变量ζ， 判 断Δf2＞ζ 是否成立： 若是， 则令s ′＝s*， 并进入步骤3.7； 否则， 进入步骤3.7； 步骤3.6， 判断f(s*)＜f(s)是否成立： 若是， 则令s＝s*， 并进入步骤3.7； 否则， 进入步骤3.7； 步骤3.7， 判断i＜Imax且T＞Tmin是否成立： 若是， 则令i ＝i+1、 T＝γT， 并返回步骤3.3； 否则， 输出当前的s， 作为车辆和无 人机最优的巡 逻路径规划策略。 5.根据权利要求4所述的单车辆与多无人机协同弧路由调度方法， 其特征在于， 步骤 3.3中， 所述采用破坏算子对巡 逻路径规划策略的当前解s ′进行随机破坏， 具体为： 随机选择s′中一个由无 人机访问的任务 边， 改变其任务方向； 或 随机选择s ′中一个由无人机访 问的任务边， 删除其起降点对， 重新挑选该任务的起降 点对； 或 随机选择s ′中一个任务， 若该任务为无人机任务， 则从车辆路径中删除该任务的起降 点对； 若该任务 为车辆任务， 则从车辆路径中删除该任务的两个端点； 或 随机改变s ′中一个任务边， 将其由无人机访问改为由车辆访问， 或将其由车辆访问改 为由无人机访问； 随机选择s ′中的两个不属于同一连结任务的无人机任务边， 将这两个无人机任务边中 的所有任务 边连结起来形成一个连 结任务； 或 随机选择s ′中的两个无人机任务边， 将其破坏重组为三个无人机任务边， 并为三个新 的无人机任务 边分配新的起降点对。 6.根据权利要求4所述的单车辆与多无人机协同弧路由调度方法， 其特征在于， 步骤 3.3中， 所述采用修复算子对 破坏后的当前解进行修复， 筛 选出修复后的中间解s*， 具体为： 将破坏算子操作后的任务在符合约束的条件下， 重新插入车辆路径中， 得到一个巡逻 路径规划策略的中间解。权　利　要　求　书 2/2 页 3 CN 115062486 A 3