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

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

作　　者：陈琴 魏军平 刘洋 韩楠 吴涛 刘美琦 王鑫 乔少杰 CHEN Qin;WEI Junping;LIU Yang;HAN Nan;WU Tao;LIU Meiqi;WANG Xin;QIAO Shaojie(School of Software Engineering,Chengdu University of Information Technology,Chengdu 610225,China;Sichuan ShuChen Technology Co.,Ltd., Chengdu 610095,China;Chengdu Shine Technology Co., Ltd.,Chengdu 610041, China;Sichuan SpaceOn Aerospace Information Technology Co., Ltd., Chengdu 611731,China)

机构地区：[1]成都信息工程大学软件工程学院,四川成都610225 [2]四川数辰科技有限公司,四川成都610095 [3]成都携恩科技有限公司,四川成都610041 [4]四川天奥空天信息技术有限公司,四川成都611731

出　　处：《无线电工程》2022年第7期1238-1249,共12页Radio Engineering

基　　金：国家自然科学基金(61772091,61802035,61962006);四川省科技计划项目(2021JDJQ0021,2022YFG0186,2021YZD0009,2021ZYD0033);成都市技术创新研发项目(2021-YF05-00491-SN,2021-YF05-02414-GX,2021-YF05-02413-GX,2021-YF05-02420-GX,2021-YF05-02424-GX);成都市重大科技创新项目(2021-YF08-00156-GX,2021-YF08-00159-GX);成都市“揭榜挂帅”科技项目(2021-JB00-00025-GX)。

摘　　要：路径规划和调度问题对无人机完成特定任务具有重要意义。针对蚁群算法容易陷入局部最优、迭代次数多和稳定性低等问题,提出了一种改进的基于禁忌搜索的蚁群算法(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.

关 键 词：调度问题 路径规划 禁忌搜索算法 无人机 蚁群算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]