一种基于改进分支限界算法的无人机路径优化方法

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