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

陈 琴，魏军平，刘 洋，韩 楠*，吴 涛，刘美琦，王 鑫，乔少杰

(1.成都信息工程大学 软件工程学院，四川 成都 610225；2.四川数辰科技有限公司，四川 成都 610095；3.成都携恩科技有限公司，四川 成都 610041；4.四川天奥空天信息技术有限公司，四川 成都 611731)

0 引言

当前，世界各地引入了各种检测诊所、网站、快出式诊所和机制，以获取有关新冠肺炎的信息,决策出有效的防控措施[1]。各个国家也同时鼓励科研人员研发新技术和新方法，帮助政府有效管控新冠肺炎的传播，将传播病例降至最低。为了实现这一目标，相关工作提出借助人工智能技术控制无人机来检测、监控和控制疫情[2]。

近年来，无人机广泛用于气候监测、环境研究、救援和搜索行动以及天气预报等多种领域。这是因为无人机具有很高的机动性、便携性、可扩展性和灵活性，可以预见以后无人机的应用将会越来越广泛[3]。最新研究建议将无人机运用到传染病疫情防控中，以此作为向智能医疗转型的手段[4]。

路径规划是无人机应用要探索的重要问题之一。目前，无人机路径规划的难点在于，因为无人机的高机动性存在一些目标定位和识别的问题。想要解决无人机路径规划问题，就要根据无人机的任务分配情况，选择合适的算法，规划出最好的路径，这就需要任务环境的地理位置信息支撑，并清楚任务环境中障碍物的分布，然后根据无人机自身的限制条件和飞行特性，规划合理的路径，使无人机能够顺利通过障碍物到达目的地[5]。

无人机的路径规划就是一个在任务环境和无人机自身多方面约束条件下，求解出最好路径的问题[6]。根据表达技术，可以将解决无人机路径规划问题的方法分为2类：第1类是基于单元分解、势场和Voronoi图的空间表达技术；第2类是以坐标和非坐标技术为代表的算法，如蚁群算法、生物启发模型[7]、模拟退火法[8]和鱼群算法[9]等。各种方法的优势和劣势不同，评估算法好坏的标准是算法的时间和空间复杂度，以及求得解集的质量好坏。

蚁群算法用于路径规划时的缺点是由于规划求解时容易受到蚁群繁杂信息素的影响，造成收敛速度慢，容易陷入混乱状态，全局的搜索能力受到影响。但是，若信息素量太少，会导致多样性降低、正反馈过强，出现僵化现象，蚁群寻找路径的能力会变得不灵活。禁忌算法因自身禁忌表和解禁策略的特征，能够避免陷入局部最好解状态，其缺点是无法保证得到全局最好解。本文在蚁群算法和禁忌算法各自优势和劣势的基础上，提出了一种改进的基于禁忌搜索的蚁群算法(Improved Taboo Ant Colony Algorithm，ITAC)，其优点在于引入了禁忌搜索算法的特性，如能够通过利用禁忌表和解禁策略跳出局部最好结果的状态，可以弥补基本蚁群算法的缺点，即避免由于多样性过剩导致找不到最好解集，陷入搜索混乱的状态。反过来，基本蚁群算法能够通过信息素的更新原则找到最好的初始解，将最好的初始解当作禁忌算法寻优的初始解，能够改进禁忌算法过于依赖初始解集好坏的特性，减少算法的运算时间，提升ITAC在路径规划中的寻优能力。

最后通过仿真实验，验证本文所提的ITAC在无人机路径规划和调度上的性能优势，对比算法有禁忌搜索算法、蚁群算法和Dijkstra算法。实验模拟对3类不同患者数量(30，50，100例)的案例，分别初始化无人机数量(10，20，30，50，100架)来测试算法在实际应用中无人机的使用数量、计算运行时间和优化距离方面的性能。结果表明，4类算法均优化了3类案例中无人机的使用数量，其中ITAC表现最佳，在提供最佳路径的同时缩减了计算时间。

本文首先介绍了传染病样本收集检测模式和无人机用于样本收集和医疗领域中的应用现状，以及无人机路径规划等研究现状；然后介绍了无人机的调度问题以及提出的传染病检测样本收集的无人机调度问题，还介绍了实际的应用案例；其次介绍了无人机调度问题的求解算法，以及本文提出的基于禁忌搜索的蚁群改进算法ITAC；仿真实验对比并分析了4种算法在路径优化中的结果；最后，对研究进行了总结和展望。

1 相关工作

无人机是现代广泛应用的新兴技术之一，由于无人机体积小、飞行能力强、机械复杂，可以广泛应用于农业、体育、娱乐、包裹递送、灾害管理、搜救、紧急医疗和医疗保健等不同领域。无人机在医疗保健领域的应用尤为重要，尤其是无接触投放药物。因为医疗保健迫切需要将物品运送到道路难以到达的地点，以及当运输血液、疫苗、急救箱和其他药物等与医疗紧急情况有关物品时作用更突出[10]。在医药和医疗保健方面，无人机技术的出现带来了一场革命，Saeed等人[11]将无人机在医疗保健领域的应用分为3类：

① 院前急救。救助院外心脏骤停患者时使用无人机，大大缩短了反应时间，从而提高了存活率。

② 加快实验室诊断检测。居住在农村社区的人往往得不到适当的医疗保健，这可能是由于缺乏道路基础设施和交通不便造成的。在这种情况下，无人机在运送疫苗或从患者身上收集样本方面是高效和廉价的。

③ 医疗保健和执法方面监控。如今，无人机配备了高科技摄像头，执法机构可以使用这些摄像头进行监控，海滩上的救生员也可以识别溺水者的身份。

由于医疗保健的作用对人类至关重要，无人机技术在这一领域的研究受到高度重视。例如，西班牙警方使用配备扩音器的无人机向公民传达封锁措施；包括中国和美国在内的其他国家则部署无人机进行空中消毒和运送医疗样本；加纳使用无人机运输新冠肺炎测试样本[12]，研究表明，空运或无人机技术可以通过加快大规模检测，成为对抗冠状病毒的可靠工具。除了运送新冠肺炎检测样本外，无人机还参与将未使用的检测工具包、医疗用品和药品送到最需要的偏远农村和山区。

无人机技术已运用到疫情防控工作中，但是，无人机要顺利完成不同场景的任务，关键是要解决无人机的路径规划问题。目前，运用了很多计算机技术和各类算法来求解无人机路径规划问题，其中求解算法主要分为2类：第1类是利用地理位置信息和地图的算法，包括洪范填充算法、路线图法、单元分解法和Floyd算法；第2类是根据动物群体寻找路径的启发式算法，需要实时的环境变动信息来规划路径，如鱼群算法、蚁群算法和遗传算法等。

目前世界各地研究人员已经探索了多种方法从感染者身上收集潜在的新冠肺炎样本，其中广泛使用的3种方法为：在专门的医院或快出式诊所收集样本、驱车到诊所或患者在家中自助收集样本。这些方法的优点、风险和限制如表1所示。

表1 采集新冠肺炎患者样本的方法Tab.1 Methods of collecting COVID-19 patient’s samples

基于上述研究现状，潜在患者可以向服务台请求获得检测试剂盒，可以将无人机运用到新型冠状病毒抗原检测试剂盒的运输，控制台就派遣无人机到潜在患者的住处，进行检测样本的收集并返回医院或者检测中心，其优势在于无需和患者接触或不用长期与患者共处同一空间，新型冠状病毒传播风险显著降低。此外，具有收集速度比较快以及减少碳足迹和空气污染的优势。在此基础上，本文针对无人机的路径规划问题和提高无人机运输检测样本的效率和安全性，提出了一种基于禁忌搜索算法的传染病样本收集无人机调度方法。

2 无人机调度问题

无人机应用的挑战之一是获得无人机部署的时间表。无人机部署涉及从资源分配到路由的各种调度问题，是一个比较难的问题。无人机能耗的非线性特征、其他无人机的干扰以及与无人机操作相关的其他约束，无人机的最大负荷重量、最大飞行距离，使得问题的解决变得更加困难。

由于无人机是一种电池驱动的设备，电池可能在持续特定的时间后失效。因此，无人机需要在能耗限制内完成规定任务。对于大多数商用无人机，飞行时间在45 min～2 h，普遍能满足研究需求。大多数可用于类似目标的商用无人机具有如表2所示的特性。

表2给出了6种可用于交付传染病检测试剂盒的商用无人机。无人机的电池容量有限，因此无人机需要在电池耗尽前完成飞行并返回基点。这就需要解决无人机的调度问题，以便在尽可能短的时间内完成任务，并找到最短的路径来调度和携带样品。基于上述研究，本文使用了提出的ITAC和3种常用路径规划算法(禁忌搜索算法、蚁群算法和Dijkstra算法)来解决无人机的路径规划问题。本文采用的传染病样本无人机调度方法的总体流程如图1所示，给出了呼叫无人机调度团队、收集患者坐标、启动路径规划算法、交付套件、收集样本和返回基地的关键操作。

表2 商用递送包裹的无人机Tab.2 UAVs commercially available for delivering packages

图1 无人机调度方法流程Fig.1 Flowchart of UAV-based scheduling method

2.1 无人机调度流程

优化无人机路径的总体框架如图2所示，以确保及时向患者交付和收集传染病自检测套件，实现智能医疗。无人机路径优化框架主要包含5个步骤，基于这一框架，潜在的患者发起样本收集请求，派遣无人机并收集样本。

图2 无人机路径优化框架Fig.2 Framework of UAV path optimization

在步骤①中，潜在患者发起请求，要求提供自检测新型冠状病毒抗原检测试剂盒，需立即会诊或填写问卷。如果确定患者有资格享受该服务，则向无人机调度部门发送服务启动请求。派遣部门的人员确保无人机、样本采集箱和自检试剂盒在发送给患者之前经过消毒，以确保无人机不会携带病毒，从而不会将病毒传播给社区。

在步骤②中，通过访问存储在医院记录中的患者数据库，由调度团队获取患者位置的详细信息。一旦获得位置记录，就会运行路径优化算法，生成将试剂盒送到患者位置，并将样本带回医院的最佳可能和最短的路径。

在步骤③中，使用路径规划算法对运动轨迹进行规划后，将最佳路径的GPS坐标反馈给无人机。一个自检套件被添加到无人机上的密封盒中，并确保箱子是密封的，在通过无人机运输时不会受到环境的影响。还要将有关自行采集样本书面指导信息添加到盒子中，启动无人机并进行发射检查，以将其发送到目标区域。最后，向患者发送一条短信，通知他们工具箱已经到达，这样就可以从无人机上取走套件。

在步骤④中，无人机降落在一个安全的位置，放下盒子，等待患者收集样本，收集完成后将盒子放回无人机上。无人机还配备了摄像头和麦克风，可以与患者交互。一旦样本准备就绪，无人机就会在盒子上喷洒消毒液，并将其运往医院。在此过程中，如果无人机电池电量不足，它会向其他无人机发送信号，让其代替自己进行当前操作，并且电量不足的无人机可以安全返回，无需等待很长时间。在这种情况下，无人机保留了一个安全系数，在电池耗尽之前一段时间，无人机就会提前通知机群中的其他无人机。

在步骤⑤中，无人机根据其电池状态和容纳能力，请求允许返回医院或收集其他样本。在机群中，无人机需要相互协助，所以机群中的无人机需要具备多个样本采集的能力，避免样本间的交叉感染并需要具备对单独盒子消毒的能力。这一步骤结束时，无人机可以安全地返回医院或改道到另一个位置节点直至完成任务。

2.2 应用案例分析

以巴基斯坦首都伊斯兰堡作为仿真实验的区域，因为这个区域是为数不多的将无人机运用到对抗新冠肺炎疫情的区域，并且该区域新冠肺炎病例的数量相对可控，政府可以通过引入复杂的样本采集技术来保持这一状态。

无人驾驶飞机计划是以伊斯兰堡一家位于区域中心的医院为主要的发射和控制场所。这样，从基地发射的无人机可以以最小距离到达伊斯兰堡地区的所有地点。在目前的研究中，将中心医院的直升机停机坪用作无人机的发射和着陆场。在完成任务后，无人机将降落在同一个地点，样本可以被带到中心医院进行检测分析。每个提交样本的患者居住地都被认为是一个节点，连接节点和医院的路径在路径规划文献中称为边。每架无人机都遵循一条特定的路线，起点和终点都在同一站点，该路线由一组节点和边组成。通过路径规划算法可以使无人机完全遵循规划的路线来完成任务，并安全地到达医院。无人机路径规划后的轨迹网络如图3所示，它由3条不同的路线组成。每条路线的起点和终点都在同一位置，节点由无人机要访问的患者位置组成。线条是连接不同节点和医院的边，每条边代表无人机要行进的特定距离。

图3 无人机示例轨迹网络Fig.3 Example of UAV route network

2.3 传染病样本收集的无人机调度问题

本文提出的问题是，利用U架无人机为n个患者运输并收集病毒检测试剂盒。根据地理位置信息，可以把配送区域A规划为m个子区域，无人机j的初始位置被记为αj,0。根据无人机的起点位置、目标位置和各区域的地理特征等信息，得到每个子区域αi在时刻t是否有障碍物的概率，躲避障碍物获得规划路径。假设无人机调度问题的目标是确定无人机uj的优化路径kj={(αj,1,kj,1),(αj,2,kj,2),…,(αj,m,kj,m)}(1≤i≤m)，其中{αj,1,αj,2,…,αj,m}代表无人机uj的路径序列。

无人机群在完成新冠病毒检测样本收集任务后，需要控制台对其进行任务分配。路径规划需要根据任务分配情况进行，路径规划结果也会反过来影响任务完成情况和成本消耗。所以可以在进行任务分配时，将无人机完成任务的时间加入到考虑中，更好地完成任务分配。将所有收集检测样本任务合理分配给每架无人机，首先就需要对无人机进行编号，这样才能有序地给每架无人机分配任务。然后根据患者位置信息和区域建筑物和环境详细信息，对无人机起点到患者位置的路径进行合理规划。分配给无人机的收集任务，需要满足成本消耗最低且在无人机的能耗之内。每架无人机的电量都有一个上限值，分配无人机的任务数量不能超过无人机的能耗上限值，否则代表分配任务失败。无人机的能耗大小主要由路径的距离、无人机的电池容量以及躲避障碍物的风险值决定。

为了衡量任务完成时间T、任务完成成本C、无人机能耗V三个主要因素影响整体效能的程度大小，引入了3个权重系数。权重值的大小代表了影响程度的大小，权重值的确定是根据具体任务规划和无人机的型号评估分析得出的。目标函数如下：

式中，T，C，V前面的系数分别是它们的权重系数；X表示任务之间的关系矩阵，Xij=1表明任务i，j之间存在关联；U表示完成任务的无人机数量；M表示任务数量。

如果根据经验来确定上面的权重系数的值，目标函数产生的结果有很大的不确定性，不具备客观性，并且如果单个子目标之间存在执行冲突时，也不能表达出来，不能解决冲突问题。可以根据多任务划分来解决该问题，产生良好的解集从而获得更多的详细信息，对整体目标任务的分配策划出更多的规划方案。

3 无人机调度问题的求解算法

无人机调度问题是以有效利用可用无人机数量的方式，将任务分配给无人机，属于NP难问题，自提出以来就引起诸多学者的关注。求解此问题的方法主要有2类：启发式算法和精确算法。精确算法主要是通过有限的计算得出最好解，当问题较为复杂、规模较大时，计算量会变得非常庞大，因此对于无人机调度问题，该算法就不再适用。而启发式算法则可以弥补这一不足，在求解调度类问题时有很大的优势。

3.1 调度算法介绍

启发式算法应用到无人机调度问题的基本思想是：首先产生一个无人机调度问题的初始解，然后通过优化策略不断进行局部扰动，找到更好的解，最后经过有限迭代，直到找到全局满意的解为止。目前，用于求解无人机调度问题的启发式算法主要包括差分演进算法、人工蜂群、遗传算法、粒子群算法和闪电搜索算法[13]。

其中，蚁群算法源于对蚁群觅食生物行为的研究，模拟了基于蚁群间相互合作的仿生智能优化算法。蚂蚁在觅食过程中会留下源激素，其他蚂蚁可以识别信息激素的浓度，蚂蚁会朝着信息素浓度更高的方向移动，称为蚁群算法的正反馈现象。蚁群能够在较短时间内找到食物位置，得益于信息素的反馈情况[14]。通过上述信息交换的正反馈机制最终得到一条最好路径。由此，可将蚁群觅食行为的协作本质概括为：

① 协同机制：蚂蚁释放信息素标记已遍历的路径，感知路径上已有信息素含量做出路径决策，利用信息素完成个体之间的信息传递；

② 路径概率决策机制：蚂蚁有更大的机率选择信息素强的路径，在经过该路径时又会留下新的信息素，增强了浓度；

③ 信息素更新机制：路径越短时，单位时间内通过的蚂蚁越多，路径上积累的信息素越多。

蚁群算法在前期，信息素还没有覆盖到任务环境中，需要等待一定的时间让信息素完全分布到环境中，产生一个参照；在后期，因为蚁群算法的协作机制，使得算法容易陷入混沌和局部最好情况，得不到全局最好解。

禁忌算法是一种将记忆功能结构结合到了局部搜索策略中的一种元启发式算法[15]。禁忌搜索的基本思想是在形成路径规划解过程中，禁止访问先前已访问过的节点，还利用了禁忌表和解禁策略的特性和灵活的记忆功能，增强了该算法对质量较差解的容纳度，具有较强的爬升能力，能够避免陷入局部最小值，具有避免早熟的能力[16]。但是，全局搜索能力较弱，其最终解的质量受初始解的影响较大。

Dijkstra算法的目的是解决起点A和目的地点B之间的最短路径问题，即从所有解中找出成本最低的一条路径[17]。该算法能够系统地评估和丢弃不利的子轨迹，直到找到最优的路径。在无人机路径规划中，能够将无人机的转弯角度、出发和到达目的地的方向约束都考虑到，按路径点距离的依次增加，找到起点到目的点之间的最短轨迹，算法总的时间复杂度为(n2)。

3.2 基于禁忌搜索的蚁群改进算法

针对蚁群算法和禁忌搜索算法进行研究，提出了ITAC的改进思想、工作原理和算法步骤。通过仿真实验，比较分析了ITAC和禁忌算法、蚁群算法、Dijkstra算法的执行结果，验证改进算法的有效性。

3.2.1 算法原理

针对蚁群算法和禁忌算法各自的优缺点，发现蚁群算法随着搜索过程中局部最佳路径上信息素的大量积累，易出现局部最佳甚至停滞的现象。而禁忌搜索算法的优点是对次优解有很好的接受能力，能够帮助蚁群算法扩大搜索空间，提高解的多样性，搜索得到更高性能的全局最好解。

此外，蚁群算法具有分布式并行的优点，每只蚂蚁完成一次迭代搜索就可以获得一个可行解，即蚁群算法每完成一次全局搜索都将产生等同于蚂蚁数量的解[18]。因此，蚁群算法具有较大的机会搜索出性能较优的解，将最好解集作为禁忌算法的初始解集，可以改善禁忌算法最终解的质量过于依赖初始解的好坏情况。具有禁忌搜索能力的ITAC思想如下：

蚁群算法循环搜索所有配送点可得m条路径，计算路径长度找到全局最佳路径，对其进行局部优化变换等操作后，存入禁忌表进行限制，全局最佳路径中的局部路径将被拒绝访问。此外，针对蚁群算法所求得的解相似而易早熟、易陷入局部最好解的情况，应用2-opt算法[19]对最佳路径进行局部优化变换，直到邻域内不能再改进，以增加解的多样性。

3.2.2 工作原理

本节对在禁忌算法基础上改进的蚁群算法，涉及的相关定义进行介绍。

定义1：禁忌表。禁忌表是禁忌搜索算法中的基本定义。禁忌表的作用是来存储算法迭代搜索一次后产生的所有结果中最好和最坏的路径结果[20]。

从实际问题出发，假设存在m个样本配送地点，就令蚂蚁的数量等于配送点数量进行路径规划，对规划算法得出的结果进行排序，找出最好的路径解集Rbest和最坏的解集Rworst，将二者存入禁忌表中。由于Rbest和Rworst两个解集中的路径数目不止一条，而且禁忌表能够根据规则限制一些坏结果路径点的选取。这说明改进算法不仅能在规划路径时高效并行，还提高了每次迭代搜索产生的最好路径解集的质量。

禁忌表中存储的Rbest解集中的路径数量设为Nbest，Rworst解集中的路径数量设为Nworst，其中表里存储的路径数量可以调整，路径数量设置过多会降低算法的运算效率[21]。通常情况下，最好路径数量设置为一条，但是，若求解的路径优化问题规模比较大时，也可以根据实际情况将最好路径数设置为多条。同时也要注意，并不是禁忌表中存储的路径数量越多越好。因为当禁忌表中存储的路径数量越多，就代表路径规划时可选择的路径点越少，甚至在限制条件较多时，会出现无路径点可选的情况，最后导致算法搜索效率降低，可行空间太小搜索失去条理，无法获得最好结果。

定义2：状态标识表。 状态标识表存储的是路径选择状态的标识量，反映了路径规划时禁忌表对路径选择的限制。状态标识表中存储的是多维矩阵，其中，矩阵的维度根据实际问题定义。改进算法中采用的是二维矩阵，矩阵中存储着3个表示量：0，1，-1。1表示最好路径解集中的局部路径被禁忌访问，除非局部路径出现在更好的路径解集中时才被释放；-1表示当前路径是禁忌表里Rworst解集中的路径；0表示当前路径同时存在于Rworst解集和Rbest解集中。

定义3：解禁策略。禁忌表有一个禁忌周期，超过禁忌周期就需要对禁忌表中最先存入的路径进行释放。改进算法在对所有路径节点迭代一次后会得出一个最好解，将该结果与当前的路径进行比较。若最好解较优将其存入禁忌表，对当前最好路径结果进行解禁。在进行路径选择时，找不到可选择的下一路径点时，就对禁忌表中最先存入的路径进行解禁。最后释放的就是最好解，因为在规定的禁忌大小中，搜索过程中没有优于禁忌表中的结果时，表明禁忌表中的解是全局最好的解。禁忌表中的Rworst的禁忌周期没有限制，只有当Rworst中的局部路径也是Rbest中的路径时，局部路径才能被释放。这种策略降低了最差路径对全局的影响，算法的效率也提高了[22]。

3.2.3 算法描述

根据以上描述，改进蚁群算法流程如图4所示。

图4 结合禁忌搜索的改进蚁群算法流程Fig.4 Flowchart of improved ant colony algorithm combined with taboo search

基于禁忌搜索的改进蚁群算法如下：

算法1:基于禁忌搜索的改进蚁群算法输入:无人机起止位置αj,0,αj,m各区域地理特征信息A。输出:无人机的优化路径序列kj={(αj,1,kj,1),(αj,2,kj,2),…,(αj,m,kj,m)}。步骤1:对参数进行初始化,设置最大迭代次数Nmax,初始蚂蚁数目为配送点数M;步骤2:导入位置数据,计算配送位置与邻近节点之间的距离,构建信息素矩阵,将已访问节点和蚂蚁承重量等变量值设为空;步骤3:蚂蚁遍历访问所有配送位置,对蚂蚁k经过的路径上的信息素进行更新;步骤4:若已经访问完所有配送位置节点就执行下一步,否者跳回上一步骤;步骤5:迭代计算找出最好路径距离和最差路径距离,对最好路径长度和当前路径长度进行比较,将较小路径存入 Rbest;步骤6:对最好路径Rbest的局部路径段进行有限次优化,即将Rbest中的局部路径替换为比其还短的当前最短路径;步骤7:更新禁忌表和状态标识表,按照解禁策略和局部优化对路径进行解禁;步骤8:若已到达最大迭代次数,就输出最好路径结果序列,没到达就返回步骤3。

4 仿真实验与分析

通过仿真实验，对比分析了ITAC、禁忌搜索算法、蚁群算法和Dijkstra算法，验证了所提ITAC在无人机的路径规划上的性能优势。本文在ArcGIS中，以巴基斯坦首都伊斯兰堡中心医院作为无人机的起点，中心医院附近110 km以内的100个居民居住点作为患者住宅点，生成地理位置信息数据集。然后，利用计算机仿真在位置数据集中对4类算例进行测试，迭代次数设为50，不同算法基于无人机的路径规划实验性能对比如表3所示。

实验模拟对于3类患者数量(30，50，100例)的案例，分别初始化无人机数量(10，20，30，50，100架)来测试算法在实际无人机的使用数量、计算运行时间和优化距离方面的性能。

由表3可以看出，增加患者数量会增加要覆盖的距离，需要更多的无人机，这也增加ITAC和禁忌搜索算法、蚁群算法和Dijkstra算法的总的运行时间。然而，增加医院中无人机的总数并不能保证覆盖的距离会有显著的不同。在所考虑的算法中，基于ITAC的无人机调度方法为所有输入参数生成最佳化的解，原因在于ITAC结合了蚁群算法和禁忌搜索算法的优点，在无人机路径调度上展现了其优势。

当患者数量远远高于可用的无人机数量时， 基于禁忌搜索算法的传染病样本收集无人机调度方法不能规划出可行路径。当患者总数为100，而医院中只有10架无人机时，就会观察到没有可行解决方案的情况，在表3中用N/A(不适用)记号表示，这也说明了无人机的局限性。每架无人机一次不能覆盖7名以上的患者，这是由无人机的电池容量和规定时间内覆盖的距离决定的。

在常规情况下，电池可用时间为1 h，无人机速度为60 km/h。此外，无人机被认为在离地面6.096～9.144 m飞行。高层建筑、桥梁和山脉等形式的障碍物可以通过路径规划算法自动避开，基于无人机的传染病疫情自检套件调度方法从数据库中提取障碍物和节点信息，并将它们集成到路由机制中，以构建飞行路径。

此外，无人机平均需要7～8 min来发送、收集和归还检测工具包。其他，如风速和高温造成的能量损失都没有考虑。距离是使用无人机生成的值乘以单位值并除以1 000来计算的，结果换算为km。例如，在30名患者和10架无人机的情况下，距离为793个单位。在本研究中，单位距离为50 m，主要基于真实应用的绘图考虑。因此，793×50 m÷1 000=39.65 km。经过上述数据处理，如果每天的患者保持在100人左右，伊斯兰堡220 km2的总面积就可以很容易地被15架无人机覆盖，所以实验中实际使用的无人机数量没有超过15架。

4种算法运行时间对比如图5所示。

(a) 患者数量为30

(b) 患者数量为50

(c) 患者数量为100图5 4种算法运行时间对比Fig.5 Runtime comparison of four algorithms

表3 不同算法基于无人机的路径规划实验性能对比Tab.3 Experimental performance comparison of UAV-based path planning with different algorithms

由图5可以看出，所提的ITAC在运行时间上较其他3种算法更优。这是因为禁忌算法、蚁群算法和Dijkstra算法都容易因自身规则出现局部最好的情况，迭代次数增加。

本文所提ITAC性能优于其他方法的原因在于：① 改进算法引入信息素随时间的消散程度描述，对信息素更新机制做出了改进，消除了局部最优的情况；② 利用禁忌算法的禁忌策略和解禁策略，降低了最差解集对ITAC的影响，使算法跳出局部最优；③ 根据最好解集，再次对信息素分布进行更新，降低了选错路径的概率。

ITAC在路径规划上表现的性能好于禁忌算法和蚁群算法，体现在实验结果上均优于蚁群算法和禁忌搜索算法。如ITAC在运行时间上明显优于禁忌算法、蚁群算法和Dijkstra算法。以图5(a)为例，分别高出86.7%，22.3%和33.2%。蚁群算法具有较好的全局搜索能力和躲避障碍能力，所以蚁群算法在优化运行时间性能上仅次于ITAC。而禁忌搜索算法容易陷入局部最佳问题，即使引入了禁忌表，禁忌搜索仍需要多次循环，所以禁忌搜索算法在优化运行时间上较差。

4种算法在3种患者数量的算例中优化路径规划距离的实验结果如图6所示。

(a) 患者数量为30

(b) 患者数量为50

(c) 患者数量为100图6 4种算法路径优化距离Fig.6 Distances of path optimization by four algorithms

由图6(a)～(c)可以看出，3类案例的实验图中，ITAC搜索算法、禁忌算法、蚁群算法和Dijkstra算法对距离的优化分别为一个稳定的值，如图6(a)所示，患者数量为30，实际利用的无人机数量为5架，ITAC算法、禁忌算法、蚁群算法和Dijkstra算法的优化距离分别为31.85，39.65，32.2，38.05 km。这是因为，每类案例的患者数量固定，虽然无人机的总数在变化，但是实际利用的无人机数量是不变的，每种算法在进行路径规划时，分别只规划了一条最佳路径，所以优化的路径距离是一个稳定值。

随着患者数量的增加， ITAC对距离的优化一直表现最佳，以图6(c)为例，相比于禁忌算法、蚁群算法和Dijkstra算法，ITAC在路径距离上分别缩短了16.3%，4.5%和13.8%。ITAC表现最佳的原因在于：实验中患者数量的增加，禁忌算法、蚁群算法和Dijkstra算法规划的路径距离增长幅度都大于ITAC，表明ITAC的稳定性好于其他3种算法。特别是禁忌算法对初始的解集依赖性比较强，所以容易陷入局部最好，得不到全局最好的结果。而ITAC利用信息素更新原则，改善了禁忌算法过于依赖初始最好解的情况，扩大了搜索解集空间。

此外，可以发现实际利用的无人机数量远远小于无人机总数量，这表明路径规划算法不仅优化了运行时间和距离，还提高了无人机的利用率。综合分析，提出的基于禁忌搜索算法的传染病样本收集无人机调度方法，可以应用于无人机的疫情防控中，对无人机的路径规划进行优化。

5 结束语

本文提出了基于禁忌搜索算法的传染病检测样本收集无人机调度方法，将其应用于疫情防控中，将新型冠状病毒抗原检测试剂盒递送到潜在感染者身边，并将样本带回检测中心，最大限度地缩短递送和接收时间。实验分析了禁忌算法、ITAC、蚁群算法和Dijkstra算法对无人机的路径规划的结果，实验证明4种算法均提高了无人机的利用率，但是ITAC在优化路径规划中表现效果最佳。

当前研究的局限性在于，使用了路径规划的相关技术，而没有考虑其他问题，如邮递员问题。此外，针对无人机电量有限这个问题可以在未来考虑使用太阳能驱动无人机来解决。无人机不依赖于化石资源，从而减少汽车或送货卡车产生的空气污染，减少碳排放，对实现碳中和起到一定作用。其次，一些变量如风速和电池因热造成的能量损失本研究没有考虑，可以在未来工作中进行改进。同样，在未来无人机的法律含义、用户的安全性、无人机的防黑客攻击能力、最小无人机的最大覆盖区域、性能优化、无人机与患者之间的失败合作概率、无人机的路径出错的概率以及无人机的卫生系统故障等，都是未来研究的重点。