买专利卖专利找龙图腾，真高效！ 查专利查商标用IPTOP,全免费！专利年费监控用IP管家,真方便！

龙图腾网恭喜南京信息工程大学申请的专利一种基于改进分支限界算法的无人机路径优化方法获国家发明授权专利权，本发明授权专利权由国家知识产权局授予，授权公告号为：CN119937632B 。

龙图腾网通过国家知识产权局官网在2025-07-01发布的发明授权授权公告中获悉：该发明授权的专利申请号/专利号为：202510428511.1，技术领域涉及：G05D1/695；该发明授权一种基于改进分支限界算法的无人机路径优化方法是由奚钰靖;谢亚琴设计研发完成，并于2025-04-08向国家知识产权局提交的专利申请。

本一种基于改进分支限界算法的无人机路径优化方法在说明书摘要公布了：本发明公开了一种基于改进分支限界算法的无人机路径优化方法，首先将任务点划分为不同优先级等级，设计动态权重机制以驱动高优先级任务优先响应；其次，将全局MTSP问题转化为平面点集的聚类和局部TSP问题，通过融合K‑means聚类与分支限界算法实现协同求解；针对大规模任务场景中的计算复杂度挑战，提出一种基于空间划分的近似优化策略，采用多级优化架构平衡解精度与计算效率；相对于传统的启发式算法以及分支限界算法，本发明方法在小规模TSP实例中可以获得更优解，针对大规模任务场景，该算法计算效率得到大幅提升；并通过动态权重机制将高优先级任务节点的访问时序优化前置，使系统响应时效和系统综合QoS均得以提升。

本发明授权一种基于改进分支限界算法的无人机路径优化方法在权利要求书中公布了：1.一种基于改进分支限界算法的无人机路径优化方法，其特征在于：包括以下步骤： S1、构建无人机巡航系统；结合任务优先级以最短路径为目标，构建无人机巡航的最优路径目标函数，根据任务点分配互斥性、电池容量和任务点时序耦合构建约束函数；构建系统服务质量评估模型； S2、输入任务点集合与无人机基站位置，基于K-means算法进行任务分配，引入方差与离散度评价进行聚类筛选，输出n个互斥子任务集； S3、基于改进的分支限界法进行航迹规划，用贪心策略生成上界，根据搜索过程中节点的不同访问状态分别计算下界，根据单步和多步回溯情况进行动态剪枝； S4、通过基于空间划分的近似优化策略，结合贪心算法和分支限界法，通过对平面上的点进行划分，不断更新节点来减少分支限界法的枝，完成计算； 步骤S3中，用贪心策略生成上界具体包括以下分步骤： S3.1、从起始节点开始，选择距离当前节点最近的未访问节点作为下一个访问节点； S3.2、重复上一步骤，直至所有节点均被访问； S3.3、返回起始节点，形成完整回路； S3.4、计算该回路的总距离作为上界； 步骤S3中，根据搜索过程中节点的不同访问状态分别计算下界； 若搜索节点集合S仅包含起始节点，则考虑每个节点的进出恰好都是最短距离的情况，下界lb的计算公式为： 其中，D为距离矩阵，min1和min2分别表示矩阵行中的最小值和次小值； 若搜索节点集合S包含起始节点和部分中间节点，则下界lb的计算公式为： 其中，|S|表示已访问节点数，\表示集合差运算；表示搜索节点组中相邻节点距离的和，minD[S[1]，：]\S表示搜索节点组中的第一个节点到搜索节点组以外的其他节点的最小值，minD[S[|S|]，：]\S表示搜索节点组中的最后一个节点到搜索节点组以外的其他节点的最小值，表示距离矩阵行中搜索节点组以外的其他节点的最小的两值之和； 若搜索节点集合S中包含所有节点，则下界lb表示为完整路径长度： 步骤S3中，对当前节点是否为末端节点进行判断， 当下界大于上界，且当前节点非末端节点时，执行单步回溯；首先移除最近加入的节点vk，接着选择下一个候选节点vk+1，最后更新搜索路径[S[1]，S[2]，...，S[k-1]，vk+1]； 当下界大于上界，且当前节点为末端节点时，执行多步回溯；首先连续移除末端节点，直至遇到非末端节点vm，接着选择vm的下一个候选节点vm+1，最后更新搜索路径为[S[1]，S[2]，…，S[m-1]，vm+1]； 步骤S4中，基于空间划分的近似优化策略通过构建分层求解框架，将全局优化问题分解为多个局部最优子问题，具体包括以下分步骤： S4.1、采用贪心算法生成初始可行解，形成闭合路径P0，计算其总距离作为基准上界； S4.2、对平面上的点进行空间区域划分：首先，以起始点0为极坐标系原点，建立角度划分准则；其次，将路径P0覆盖的平面区域划分为k个扇形子区域{R1，R2，…，Rk}；最后，在每个子区域Ri内选取节点集合Vi＝{v1，v2，...，vm}； S4.3、分层优化迭代：首先，在当前层级使用步骤S3中改进的分支限界法求解子区域节点集合Vi的最优路径Pi *；其次，选取Pi *中前k-m个节点作为下一层优化的基准节点集合B＝{b1，b2，...，vk-m}；最后，将剩余节点按空间邻近性原则分配到各基准节点邻域，形成新的候选节点集Vj＝{v1，v2，...，vt}； S4.4、动态更新机制：首先，对每个候选节点集Vj执行局部分支限界优化；然后，合并各局部最优解形成全局近似解P′； S4.5、直到所有节点加入终止。

如需购买、转让、实施、许可或投资类似专利技术，可联系本专利的申请人或专利权人南京信息工程大学，其通讯地址为：210032 江苏省南京市江北新区宁六路219号；或者联系龙图腾网官方客服，联系龙图腾网可拨打电话0551-65771310或微信搜索“龙图腾网”。