Huo Lisu, Zhu Jianghan, Wu Guohua, Li Zhimeng
College of Systems Engineering, National University of Defense Technology, Changsha 410073, China.
School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China.
Sensors (Basel). 2020 Aug 24;20(17):4769. doi: 10.3390/s20174769.
The unmanned aerial vehicle (UAV) has drawn increasing attention in recent years, especially in executing tasks such as natural disaster rescue and detection, and battlefield cooperative operations. Task assignment and path planning for multiple UAVs in the above scenarios are essential for successful mission execution. But, effectively balancing tasks to better excavate the potential of UAVs remains a challenge, as well as efficiently generating feasible solutions from the current one in constrained explosive solution spaces with the increase in the scale of optimization problems. This paper proposes an efficient approach for task assignment and path planning with the objective of balancing the tasks among UAVs and achieving satisfactory temporal resolutions. To be specific, we add virtual nodes according to the number of UAVs to the original model of the vehicle routing problem (VRP), thus make it easier to form a solution suitable for heuristic algorithms. Besides, the concept of the universal distance matrix is proposed to transform the temporal constraints to spatial constraints and simplify the programming model. Then, a Swap-and-Judge Simulated Annealing (SJSA) algorithm is therefore proposed to improve the efficiency of generating feasible neighboring solutions. Extensive experimental and comparative studies on different scenarios demonstrate the efficiency of the proposed algorithm compared with the exact algorithm and meta-heuristic algorithms. The results also inspire us about the characteristics of a population-based algorithm in solving combinatorial discrete optimization problems.
近年来，无人机（UAV）越来越受到关注，特别是在执行自然灾害救援与探测以及战场协同作战等任务方面。在上述场景中，多架无人机的任务分配和路径规划对于任务的成功执行至关重要。但是，有效平衡任务以更好地挖掘无人机的潜力仍然是一个挑战，并且随着优化问题规模的增加，在受限的爆炸式解空间中从当前解高效生成可行解也是一个挑战。本文提出了一种高效的任务分配和路径规划方法，目标是在无人机之间平衡任务并实现令人满意的时间分辨率。具体而言，我们根据无人机的数量向车辆路径问题（VRP）的原始模型中添加虚拟节点，从而更易于形成适合启发式算法的解。此外，提出了通用距离矩阵的概念，将时间约束转换为空间约束并简化规划模型。然后，提出了一种交换判断模拟退火（SJSA）算法来提高生成可行邻域解的效率。在不同场景下进行的广泛实验和对比研究表明，与精确算法和元启发式算法相比，所提算法具有高效性。这些结果也让我们了解了基于种群的算法在解决组合离散优化问题时的特点。
