基于禁忌搜索算法的传染病样本收集无人机调度方法

UAV Scheduling Method for Infectious Disease Sample Collection Based on Taboo Search Algorithm

路径规划和调度问题对无人机完成特定任务具有重要意义。针对蚁群算法容易陷入局部最优、迭代次数多和稳定性低等问题,提出了一种改进的基于禁忌搜索的蚁群算法(Improved Taboo Ant Colony Algorithm,ITAC),利用禁忌搜索算法的思想进行优势互补,旨在提高算法运行效率,增强全局搜索能力,更能适应解决更大规模的无人机调度问题,最大程度地节省配送成本,有助于高效地控制疫情的蔓延。实验针对3类不同患者数量(30,50和100例)的案例,分别使用10,20,30,50,100架无人机,进行了路径优化仿真。以无人机的使用数量、飞行总距离和算法运行时间为评估指标,将ITAC算法和3种常用路径规划算法(禁忌搜索算法、蚁群算法和Dijkstra算法)进行对比实验和分析,结果表明,4类算法均优化了3类案例中无人机的使用数量,其中ITAC算法表现最佳,在提供最佳路径的同时缩减了运算时间。

Path planning and scheduling problems are of great significance for the UAV to complete specific tasks.For ant colony algorithm is easy to fall into local optimality,many iterations and low stability,an Improved Taboo Ant Colony Algorithm(ITAC)is proposed.Using the taboo search algorithm for complementary advantages aims to improve the operation efficiency of the algorithm,to enhance the global search ability,to better adapt to solve the scheduling problem of a large scale of UAVs,to save the distribution cost to the greatest extent,and to help to effectively control the spread of the epidemic.The experiments are conducted on three kinds of patients(30,50 and 100 cases)to simulate the phase of path planning by using 10,20,30,50 and 100 UAVs.The number of UAVs,total flight distance,algorithm running time are viewed as the evaluation indexes,the ITAC algorithm and three commonly-used path planning algorithms(taboo search algorithm,ant algorithm and Dijkstra algorithm)are compared in experiments and the results are discussed,and the results show that the number of UAVs of these four types of algorithms are optimized in three kinds of cases,the ITAC algorithm obtains the best performance,while providing the optimal path as well as reducing the calculation time.