基于禁忌搜索算法的傳染病樣本收集無人機調度方法

陳 琴，魏軍平，劉 洋，韓 楠*，吳 濤，劉美琦，王 鑫，喬少杰

(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在優化路徑規劃中表現效果最佳。

當前研究的局限性在于，使用了路徑規劃的相關技術，而沒有考慮其他問題，如郵遞員問題。此外，針對無人機電量有限這個問題可以在未來考慮使用太陽能驅動無人機來解決。無人機不依賴于化石資源，從而減少汽車或送貨卡車產生的空氣污染，減少碳排放，對實現碳中和起到一定作用。其次，一些變量如風速和電池因熱造成的能量損失本研究沒有考慮，可以在未來工作中進行改進。同樣，在未來無人機的法律含義、用戶的安全性、無人機的防黑客攻擊能力、最小無人機的最大覆蓋區域、性能優化、無人機與患者之間的失敗合作概率、無人機的路徑出錯的概率以及無人機的衛生系統故障等，都是未來研究的重點。