基于禁忌搜索算法的傳染病樣本收集無(wú)人機(jī)調(diào)度方法

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

(1.成都信息工程大學(xué) 軟件工程學(xué)院，四川 成都 610225；2.四川數(shù)辰科技有限公司，四川 成都 610095；3.成都攜恩科技有限公司，四川 成都 610041；4.四川天奧空天信息技術(shù)有限公司，四川 成都 611731)

0 引言

當(dāng)前，世界各地引入了各種檢測(cè)診所、網(wǎng)站、快出式診所和機(jī)制，以獲取有關(guān)新冠肺炎的信息,決策出有效的防控措施[1]。各個(gè)國(guó)家也同時(shí)鼓勵(lì)科研人員研發(fā)新技術(shù)和新方法，幫助政府有效管控新冠肺炎的傳播，將傳播病例降至最低。為了實(shí)現(xiàn)這一目標(biāo)，相關(guān)工作提出借助人工智能技術(shù)控制無(wú)人機(jī)來(lái)檢測(cè)、監(jiān)控和控制疫情[2]。

近年來(lái)，無(wú)人機(jī)廣泛用于氣候監(jiān)測(cè)、環(huán)境研究、救援和搜索行動(dòng)以及天氣預(yù)報(bào)等多種領(lǐng)域。這是因?yàn)闊o(wú)人機(jī)具有很高的機(jī)動(dòng)性、便攜性、可擴(kuò)展性和靈活性，可以預(yù)見(jiàn)以后無(wú)人機(jī)的應(yīng)用將會(huì)越來(lái)越廣泛[3]。最新研究建議將無(wú)人機(jī)運(yùn)用到傳染病疫情防控中，以此作為向智能醫(yī)療轉(zhuǎn)型的手段[4]。

路徑規(guī)劃是無(wú)人機(jī)應(yīng)用要探索的重要問(wèn)題之一。目前，無(wú)人機(jī)路徑規(guī)劃的難點(diǎn)在于，因?yàn)闊o(wú)人機(jī)的高機(jī)動(dòng)性存在一些目標(biāo)定位和識(shí)別的問(wèn)題。想要解決無(wú)人機(jī)路徑規(guī)劃問(wèn)題，就要根據(jù)無(wú)人機(jī)的任務(wù)分配情況，選擇合適的算法，規(guī)劃出最好的路徑，這就需要任務(wù)環(huán)境的地理位置信息支撐，并清楚任務(wù)環(huán)境中障礙物的分布，然后根據(jù)無(wú)人機(jī)自身的限制條件和飛行特性，規(guī)劃合理的路徑，使無(wú)人機(jī)能夠順利通過(guò)障礙物到達(dá)目的地[5]。

無(wú)人機(jī)的路徑規(guī)劃就是一個(gè)在任務(wù)環(huán)境和無(wú)人機(jī)自身多方面約束條件下，求解出最好路徑的問(wèn)題[6]。根據(jù)表達(dá)技術(shù)，可以將解決無(wú)人機(jī)路徑規(guī)劃問(wèn)題的方法分為2類(lèi)：第1類(lèi)是基于單元分解、勢(shì)場(chǎng)和Voronoi圖的空間表達(dá)技術(shù)；第2類(lèi)是以坐標(biāo)和非坐標(biāo)技術(shù)為代表的算法，如蟻群算法、生物啟發(fā)模型[7]、模擬退火法[8]和魚(yú)群算法[9]等。各種方法的優(yōu)勢(shì)和劣勢(shì)不同，評(píng)估算法好壞的標(biāo)準(zhǔn)是算法的時(shí)間和空間復(fù)雜度，以及求得解集的質(zhì)量好壞。

蟻群算法用于路徑規(guī)劃時(shí)的缺點(diǎn)是由于規(guī)劃求解時(shí)容易受到蟻群繁雜信息素的影響，造成收斂速度慢，容易陷入混亂狀態(tài)，全局的搜索能力受到影響。但是，若信息素量太少，會(huì)導(dǎo)致多樣性降低、正反饋過(guò)強(qiáng)，出現(xiàn)僵化現(xiàn)象，蟻群尋找路徑的能力會(huì)變得不靈活。禁忌算法因自身禁忌表和解禁策略的特征，能夠避免陷入局部最好解狀態(tài)，其缺點(diǎn)是無(wú)法保證得到全局最好解。本文在蟻群算法和禁忌算法各自?xún)?yōu)勢(shì)和劣勢(shì)的基礎(chǔ)上，提出了一種改進(jìn)的基于禁忌搜索的蟻群算法(Improved Taboo Ant Colony Algorithm，ITAC)，其優(yōu)點(diǎn)在于引入了禁忌搜索算法的特性，如能夠通過(guò)利用禁忌表和解禁策略跳出局部最好結(jié)果的狀態(tài)，可以彌補(bǔ)基本蟻群算法的缺點(diǎn)，即避免由于多樣性過(guò)剩導(dǎo)致找不到最好解集，陷入搜索混亂的狀態(tài)。反過(guò)來(lái)，基本蟻群算法能夠通過(guò)信息素的更新原則找到最好的初始解，將最好的初始解當(dāng)作禁忌算法尋優(yōu)的初始解，能夠改進(jìn)禁忌算法過(guò)于依賴(lài)初始解集好壞的特性，減少算法的運(yùn)算時(shí)間，提升ITAC在路徑規(guī)劃中的尋優(yōu)能力。

最后通過(guò)仿真實(shí)驗(yàn)，驗(yàn)證本文所提的ITAC在無(wú)人機(jī)路徑規(guī)劃和調(diào)度上的性能優(yōu)勢(shì)，對(duì)比算法有禁忌搜索算法、蟻群算法和Dijkstra算法。實(shí)驗(yàn)?zāi)M對(duì)3類(lèi)不同患者數(shù)量(30，50，100例)的案例，分別初始化無(wú)人機(jī)數(shù)量(10，20，30，50，100架)來(lái)測(cè)試算法在實(shí)際應(yīng)用中無(wú)人機(jī)的使用數(shù)量、計(jì)算運(yùn)行時(shí)間和優(yōu)化距離方面的性能。結(jié)果表明，4類(lèi)算法均優(yōu)化了3類(lèi)案例中無(wú)人機(jī)的使用數(shù)量，其中ITAC表現(xiàn)最佳，在提供最佳路徑的同時(shí)縮減了計(jì)算時(shí)間。

本文首先介紹了傳染病樣本收集檢測(cè)模式和無(wú)人機(jī)用于樣本收集和醫(yī)療領(lǐng)域中的應(yīng)用現(xiàn)狀，以及無(wú)人機(jī)路徑規(guī)劃等研究現(xiàn)狀；然后介紹了無(wú)人機(jī)的調(diào)度問(wèn)題以及提出的傳染病檢測(cè)樣本收集的無(wú)人機(jī)調(diào)度問(wèn)題，還介紹了實(shí)際的應(yīng)用案例；其次介紹了無(wú)人機(jī)調(diào)度問(wèn)題的求解算法，以及本文提出的基于禁忌搜索的蟻群改進(jìn)算法ITAC；仿真實(shí)驗(yàn)對(duì)比并分析了4種算法在路徑優(yōu)化中的結(jié)果；最后，對(duì)研究進(jìn)行了總結(jié)和展望。

1 相關(guān)工作

無(wú)人機(jī)是現(xiàn)代廣泛應(yīng)用的新興技術(shù)之一，由于無(wú)人機(jī)體積小、飛行能力強(qiáng)、機(jī)械復(fù)雜，可以廣泛應(yīng)用于農(nóng)業(yè)、體育、娛樂(lè)、包裹遞送、災(zāi)害管理、搜救、緊急醫(yī)療和醫(yī)療保健等不同領(lǐng)域。無(wú)人機(jī)在醫(yī)療保健領(lǐng)域的應(yīng)用尤為重要，尤其是無(wú)接觸投放藥物。因?yàn)獒t(yī)療保健迫切需要將物品運(yùn)送到道路難以到達(dá)的地點(diǎn)，以及當(dāng)運(yùn)輸血液、疫苗、急救箱和其他藥物等與醫(yī)療緊急情況有關(guān)物品時(shí)作用更突出[10]。在醫(yī)藥和醫(yī)療保健方面，無(wú)人機(jī)技術(shù)的出現(xiàn)帶來(lái)了一場(chǎng)革命，Saeed等人[11]將無(wú)人機(jī)在醫(yī)療保健領(lǐng)域的應(yīng)用分為3類(lèi)：

① 院前急救。救助院外心臟驟停患者時(shí)使用無(wú)人機(jī)，大大縮短了反應(yīng)時(shí)間，從而提高了存活率。

② 加快實(shí)驗(yàn)室診斷檢測(cè)。居住在農(nóng)村社區(qū)的人往往得不到適當(dāng)?shù)尼t(yī)療保健，這可能是由于缺乏道路基礎(chǔ)設(shè)施和交通不便造成的。在這種情況下，無(wú)人機(jī)在運(yùn)送疫苗或從患者身上收集樣本方面是高效和廉價(jià)的。

③ 醫(yī)療保健和執(zhí)法方面監(jiān)控。如今，無(wú)人機(jī)配備了高科技攝像頭，執(zhí)法機(jī)構(gòu)可以使用這些攝像頭進(jìn)行監(jiān)控，海灘上的救生員也可以識(shí)別溺水者的身份。

由于醫(yī)療保健的作用對(duì)人類(lèi)至關(guān)重要，無(wú)人機(jī)技術(shù)在這一領(lǐng)域的研究受到高度重視。例如，西班牙警方使用配備擴(kuò)音器的無(wú)人機(jī)向公民傳達(dá)封鎖措施；包括中國(guó)和美國(guó)在內(nèi)的其他國(guó)家則部署無(wú)人機(jī)進(jìn)行空中消毒和運(yùn)送醫(yī)療樣本；加納使用無(wú)人機(jī)運(yùn)輸新冠肺炎測(cè)試樣本[12]，研究表明，空運(yùn)或無(wú)人機(jī)技術(shù)可以通過(guò)加快大規(guī)模檢測(cè)，成為對(duì)抗冠狀病毒的可靠工具。除了運(yùn)送新冠肺炎檢測(cè)樣本外，無(wú)人機(jī)還參與將未使用的檢測(cè)工具包、醫(yī)療用品和藥品送到最需要的偏遠(yuǎn)農(nóng)村和山區(qū)。

無(wú)人機(jī)技術(shù)已運(yùn)用到疫情防控工作中，但是，無(wú)人機(jī)要順利完成不同場(chǎng)景的任務(wù)，關(guān)鍵是要解決無(wú)人機(jī)的路徑規(guī)劃問(wèn)題。目前，運(yùn)用了很多計(jì)算機(jī)技術(shù)和各類(lèi)算法來(lái)求解無(wú)人機(jī)路徑規(guī)劃問(wèn)題，其中求解算法主要分為2類(lèi)：第1類(lèi)是利用地理位置信息和地圖的算法，包括洪范填充算法、路線(xiàn)圖法、單元分解法和Floyd算法；第2類(lèi)是根據(jù)動(dòng)物群體尋找路徑的啟發(fā)式算法，需要實(shí)時(shí)的環(huán)境變動(dòng)信息來(lái)規(guī)劃路徑，如魚(yú)群算法、蟻群算法和遺傳算法等。

目前世界各地研究人員已經(jīng)探索了多種方法從感染者身上收集潛在的新冠肺炎樣本，其中廣泛使用的3種方法為：在專(zhuān)門(mén)的醫(yī)院或快出式診所收集樣本、驅(qū)車(chē)到診所或患者在家中自助收集樣本。這些方法的優(yōu)點(diǎn)、風(fēng)險(xiǎn)和限制如表1所示。

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

基于上述研究現(xiàn)狀，潛在患者可以向服務(wù)臺(tái)請(qǐng)求獲得檢測(cè)試劑盒，可以將無(wú)人機(jī)運(yùn)用到新型冠狀病毒抗原檢測(cè)試劑盒的運(yùn)輸，控制臺(tái)就派遣無(wú)人機(jī)到潛在患者的住處，進(jìn)行檢測(cè)樣本的收集并返回醫(yī)院或者檢測(cè)中心，其優(yōu)勢(shì)在于無(wú)需和患者接觸或不用長(zhǎng)期與患者共處同一空間，新型冠狀病毒傳播風(fēng)險(xiǎn)顯著降低。此外，具有收集速度比較快以及減少碳足跡和空氣污染的優(yōu)勢(shì)。在此基礎(chǔ)上，本文針對(duì)無(wú)人機(jī)的路徑規(guī)劃問(wèn)題和提高無(wú)人機(jī)運(yùn)輸檢測(cè)樣本的效率和安全性，提出了一種基于禁忌搜索算法的傳染病樣本收集無(wú)人機(jī)調(diào)度方法。

2 無(wú)人機(jī)調(diào)度問(wèn)題

無(wú)人機(jī)應(yīng)用的挑戰(zhàn)之一是獲得無(wú)人機(jī)部署的時(shí)間表。無(wú)人機(jī)部署涉及從資源分配到路由的各種調(diào)度問(wèn)題，是一個(gè)比較難的問(wèn)題。無(wú)人機(jī)能耗的非線(xiàn)性特征、其他無(wú)人機(jī)的干擾以及與無(wú)人機(jī)操作相關(guān)的其他約束，無(wú)人機(jī)的最大負(fù)荷重量、最大飛行距離，使得問(wèn)題的解決變得更加困難。

由于無(wú)人機(jī)是一種電池驅(qū)動(dòng)的設(shè)備，電池可能在持續(xù)特定的時(shí)間后失效。因此，無(wú)人機(jī)需要在能耗限制內(nèi)完成規(guī)定任務(wù)。對(duì)于大多數(shù)商用無(wú)人機(jī)，飛行時(shí)間在45 min～2 h，普遍能滿(mǎn)足研究需求。大多數(shù)可用于類(lèi)似目標(biāo)的商用無(wú)人機(jī)具有如表2所示的特性。

表2給出了6種可用于交付傳染病檢測(cè)試劑盒的商用無(wú)人機(jī)。無(wú)人機(jī)的電池容量有限，因此無(wú)人機(jī)需要在電池耗盡前完成飛行并返回基點(diǎn)。這就需要解決無(wú)人機(jī)的調(diào)度問(wèn)題，以便在盡可能短的時(shí)間內(nèi)完成任務(wù)，并找到最短的路徑來(lái)調(diào)度和攜帶樣品?；谏鲜鲅芯?，本文使用了提出的ITAC和3種常用路徑規(guī)劃算法(禁忌搜索算法、蟻群算法和Dijkstra算法)來(lái)解決無(wú)人機(jī)的路徑規(guī)劃問(wèn)題。本文采用的傳染病樣本無(wú)人機(jī)調(diào)度方法的總體流程如圖1所示，給出了呼叫無(wú)人機(jī)調(diào)度團(tuán)隊(duì)、收集患者坐標(biāo)、啟動(dòng)路徑規(guī)劃算法、交付套件、收集樣本和返回基地的關(guān)鍵操作。

表2 商用遞送包裹的無(wú)人機(jī)Tab.2 UAVs commercially available for delivering packages

圖1 無(wú)人機(jī)調(diào)度方法流程Fig.1 Flowchart of UAV-based scheduling method

2.1 無(wú)人機(jī)調(diào)度流程

優(yōu)化無(wú)人機(jī)路徑的總體框架如圖2所示，以確保及時(shí)向患者交付和收集傳染病自檢測(cè)套件，實(shí)現(xiàn)智能醫(yī)療。無(wú)人機(jī)路徑優(yōu)化框架主要包含5個(gè)步驟，基于這一框架，潛在的患者發(fā)起樣本收集請(qǐng)求，派遣無(wú)人機(jī)并收集樣本。

圖2 無(wú)人機(jī)路徑優(yōu)化框架Fig.2 Framework of UAV path optimization

在步驟①中，潛在患者發(fā)起請(qǐng)求，要求提供自檢測(cè)新型冠狀病毒抗原檢測(cè)試劑盒，需立即會(huì)診或填寫(xiě)問(wèn)卷。如果確定患者有資格享受該服務(wù)，則向無(wú)人機(jī)調(diào)度部門(mén)發(fā)送服務(wù)啟動(dòng)請(qǐng)求。派遣部門(mén)的人員確保無(wú)人機(jī)、樣本采集箱和自檢試劑盒在發(fā)送給患者之前經(jīng)過(guò)消毒，以確保無(wú)人機(jī)不會(huì)攜帶病毒，從而不會(huì)將病毒傳播給社區(qū)。

在步驟②中，通過(guò)訪(fǎng)問(wèn)存儲(chǔ)在醫(yī)院記錄中的患者數(shù)據(jù)庫(kù)，由調(diào)度團(tuán)隊(duì)獲取患者位置的詳細(xì)信息。一旦獲得位置記錄，就會(huì)運(yùn)行路徑優(yōu)化算法，生成將試劑盒送到患者位置，并將樣本帶回醫(yī)院的最佳可能和最短的路徑。

在步驟③中，使用路徑規(guī)劃算法對(duì)運(yùn)動(dòng)軌跡進(jìn)行規(guī)劃后，將最佳路徑的GPS坐標(biāo)反饋給無(wú)人機(jī)。一個(gè)自檢套件被添加到無(wú)人機(jī)上的密封盒中，并確保箱子是密封的，在通過(guò)無(wú)人機(jī)運(yùn)輸時(shí)不會(huì)受到環(huán)境的影響。還要將有關(guān)自行采集樣本書(shū)面指導(dǎo)信息添加到盒子中，啟動(dòng)無(wú)人機(jī)并進(jìn)行發(fā)射檢查，以將其發(fā)送到目標(biāo)區(qū)域。最后，向患者發(fā)送一條短信，通知他們工具箱已經(jīng)到達(dá)，這樣就可以從無(wú)人機(jī)上取走套件。

在步驟④中，無(wú)人機(jī)降落在一個(gè)安全的位置，放下盒子，等待患者收集樣本，收集完成后將盒子放回?zé)o人機(jī)上。無(wú)人機(jī)還配備了攝像頭和麥克風(fēng)，可以與患者交互。一旦樣本準(zhǔn)備就緒，無(wú)人機(jī)就會(huì)在盒子上噴灑消毒液，并將其運(yùn)往醫(yī)院。在此過(guò)程中，如果無(wú)人機(jī)電池電量不足，它會(huì)向其他無(wú)人機(jī)發(fā)送信號(hào)，讓其代替自己進(jìn)行當(dāng)前操作，并且電量不足的無(wú)人機(jī)可以安全返回，無(wú)需等待很長(zhǎng)時(shí)間。在這種情況下，無(wú)人機(jī)保留了一個(gè)安全系數(shù)，在電池耗盡之前一段時(shí)間，無(wú)人機(jī)就會(huì)提前通知機(jī)群中的其他無(wú)人機(jī)。

在步驟⑤中，無(wú)人機(jī)根據(jù)其電池狀態(tài)和容納能力，請(qǐng)求允許返回醫(yī)院或收集其他樣本。在機(jī)群中，無(wú)人機(jī)需要相互協(xié)助，所以機(jī)群中的無(wú)人機(jī)需要具備多個(gè)樣本采集的能力，避免樣本間的交叉感染并需要具備對(duì)單獨(dú)盒子消毒的能力。這一步驟結(jié)束時(shí)，無(wú)人機(jī)可以安全地返回醫(yī)院或改道到另一個(gè)位置節(jié)點(diǎn)直至完成任務(wù)。

2.2 應(yīng)用案例分析

以巴基斯坦首都伊斯蘭堡作為仿真實(shí)驗(yàn)的區(qū)域，因?yàn)檫@個(gè)區(qū)域是為數(shù)不多的將無(wú)人機(jī)運(yùn)用到對(duì)抗新冠肺炎疫情的區(qū)域，并且該區(qū)域新冠肺炎病例的數(shù)量相對(duì)可控，政府可以通過(guò)引入復(fù)雜的樣本采集技術(shù)來(lái)保持這一狀態(tài)。

無(wú)人駕駛飛機(jī)計(jì)劃是以伊斯蘭堡一家位于區(qū)域中心的醫(yī)院為主要的發(fā)射和控制場(chǎng)所。這樣，從基地發(fā)射的無(wú)人機(jī)可以以最小距離到達(dá)伊斯蘭堡地區(qū)的所有地點(diǎn)。在目前的研究中，將中心醫(yī)院的直升機(jī)停機(jī)坪用作無(wú)人機(jī)的發(fā)射和著陸場(chǎng)。在完成任務(wù)后，無(wú)人機(jī)將降落在同一個(gè)地點(diǎn)，樣本可以被帶到中心醫(yī)院進(jìn)行檢測(cè)分析。每個(gè)提交樣本的患者居住地都被認(rèn)為是一個(gè)節(jié)點(diǎn)，連接節(jié)點(diǎn)和醫(yī)院的路徑在路徑規(guī)劃文獻(xiàn)中稱(chēng)為邊。每架無(wú)人機(jī)都遵循一條特定的路線(xiàn)，起點(diǎn)和終點(diǎn)都在同一站點(diǎn)，該路線(xiàn)由一組節(jié)點(diǎn)和邊組成。通過(guò)路徑規(guī)劃算法可以使無(wú)人機(jī)完全遵循規(guī)劃的路線(xiàn)來(lái)完成任務(wù)，并安全地到達(dá)醫(yī)院。無(wú)人機(jī)路徑規(guī)劃后的軌跡網(wǎng)絡(luò)如圖3所示，它由3條不同的路線(xiàn)組成。每條路線(xiàn)的起點(diǎn)和終點(diǎn)都在同一位置，節(jié)點(diǎn)由無(wú)人機(jī)要訪(fǎng)問(wèn)的患者位置組成。線(xiàn)條是連接不同節(jié)點(diǎn)和醫(yī)院的邊，每條邊代表無(wú)人機(jī)要行進(jìn)的特定距離。

圖3 無(wú)人機(jī)示例軌跡網(wǎng)絡(luò)Fig.3 Example of UAV route network

2.3 傳染病樣本收集的無(wú)人機(jī)調(diào)度問(wèn)題

本文提出的問(wèn)題是，利用U架無(wú)人機(jī)為n個(gè)患者運(yùn)輸并收集病毒檢測(cè)試劑盒。根據(jù)地理位置信息，可以把配送區(qū)域A規(guī)劃為m個(gè)子區(qū)域，無(wú)人機(jī)j的初始位置被記為αj,0。根據(jù)無(wú)人機(jī)的起點(diǎn)位置、目標(biāo)位置和各區(qū)域的地理特征等信息，得到每個(gè)子區(qū)域αi在時(shí)刻t是否有障礙物的概率，躲避障礙物獲得規(guī)劃路徑。假設(shè)無(wú)人機(jī)調(diào)度問(wèn)題的目標(biāo)是確定無(wú)人機(jī)uj的優(yōu)化路徑kj={(αj,1,kj,1),(αj,2,kj,2),…,(αj,m,kj,m)}(1≤i≤m)，其中{αj,1,αj,2,…,αj,m}代表無(wú)人機(jī)uj的路徑序列。

無(wú)人機(jī)群在完成新冠病毒檢測(cè)樣本收集任務(wù)后，需要控制臺(tái)對(duì)其進(jìn)行任務(wù)分配。路徑規(guī)劃需要根據(jù)任務(wù)分配情況進(jìn)行，路徑規(guī)劃結(jié)果也會(huì)反過(guò)來(lái)影響任務(wù)完成情況和成本消耗。所以可以在進(jìn)行任務(wù)分配時(shí)，將無(wú)人機(jī)完成任務(wù)的時(shí)間加入到考慮中，更好地完成任務(wù)分配。將所有收集檢測(cè)樣本任務(wù)合理分配給每架無(wú)人機(jī)，首先就需要對(duì)無(wú)人機(jī)進(jìn)行編號(hào)，這樣才能有序地給每架無(wú)人機(jī)分配任務(wù)。然后根據(jù)患者位置信息和區(qū)域建筑物和環(huán)境詳細(xì)信息，對(duì)無(wú)人機(jī)起點(diǎn)到患者位置的路徑進(jìn)行合理規(guī)劃。分配給無(wú)人機(jī)的收集任務(wù)，需要滿(mǎn)足成本消耗最低且在無(wú)人機(jī)的能耗之內(nèi)。每架無(wú)人機(jī)的電量都有一個(gè)上限值，分配無(wú)人機(jī)的任務(wù)數(shù)量不能超過(guò)無(wú)人機(jī)的能耗上限值，否則代表分配任務(wù)失敗。無(wú)人機(jī)的能耗大小主要由路徑的距離、無(wú)人機(jī)的電池容量以及躲避障礙物的風(fēng)險(xiǎn)值決定。

為了衡量任務(wù)完成時(shí)間T、任務(wù)完成成本C、無(wú)人機(jī)能耗V三個(gè)主要因素影響整體效能的程度大小，引入了3個(gè)權(quán)重系數(shù)。權(quán)重值的大小代表了影響程度的大小，權(quán)重值的確定是根據(jù)具體任務(wù)規(guī)劃和無(wú)人機(jī)的型號(hào)評(píng)估分析得出的。目標(biāo)函數(shù)如下：

式中，T，C，V前面的系數(shù)分別是它們的權(quán)重系數(shù)；X表示任務(wù)之間的關(guān)系矩陣，Xij=1表明任務(wù)i，j之間存在關(guān)聯(lián)；U表示完成任務(wù)的無(wú)人機(jī)數(shù)量；M表示任務(wù)數(shù)量。

如果根據(jù)經(jīng)驗(yàn)來(lái)確定上面的權(quán)重系數(shù)的值，目標(biāo)函數(shù)產(chǎn)生的結(jié)果有很大的不確定性，不具備客觀(guān)性，并且如果單個(gè)子目標(biāo)之間存在執(zhí)行沖突時(shí)，也不能表達(dá)出來(lái)，不能解決沖突問(wèn)題。可以根據(jù)多任務(wù)劃分來(lái)解決該問(wèn)題，產(chǎn)生良好的解集從而獲得更多的詳細(xì)信息，對(duì)整體目標(biāo)任務(wù)的分配策劃出更多的規(guī)劃方案。

3 無(wú)人機(jī)調(diào)度問(wèn)題的求解算法

無(wú)人機(jī)調(diào)度問(wèn)題是以有效利用可用無(wú)人機(jī)數(shù)量的方式，將任務(wù)分配給無(wú)人機(jī)，屬于NP難問(wèn)題，自提出以來(lái)就引起諸多學(xué)者的關(guān)注。求解此問(wèn)題的方法主要有2類(lèi)：?jiǎn)l(fā)式算法和精確算法。精確算法主要是通過(guò)有限的計(jì)算得出最好解，當(dāng)問(wèn)題較為復(fù)雜、規(guī)模較大時(shí)，計(jì)算量會(huì)變得非常龐大，因此對(duì)于無(wú)人機(jī)調(diào)度問(wèn)題，該算法就不再適用。而啟發(fā)式算法則可以彌補(bǔ)這一不足，在求解調(diào)度類(lèi)問(wèn)題時(shí)有很大的優(yōu)勢(shì)。

3.1 調(diào)度算法介紹

啟發(fā)式算法應(yīng)用到無(wú)人機(jī)調(diào)度問(wèn)題的基本思想是：首先產(chǎn)生一個(gè)無(wú)人機(jī)調(diào)度問(wèn)題的初始解，然后通過(guò)優(yōu)化策略不斷進(jìn)行局部擾動(dòng)，找到更好的解，最后經(jīng)過(guò)有限迭代，直到找到全局滿(mǎn)意的解為止。目前，用于求解無(wú)人機(jī)調(diào)度問(wèn)題的啟發(fā)式算法主要包括差分演進(jìn)算法、人工蜂群、遺傳算法、粒子群算法和閃電搜索算法[13]。

其中，蟻群算法源于對(duì)蟻群覓食生物行為的研究，模擬了基于蟻群間相互合作的仿生智能優(yōu)化算法。螞蟻在覓食過(guò)程中會(huì)留下源激素，其他螞蟻可以識(shí)別信息激素的濃度，螞蟻會(huì)朝著信息素濃度更高的方向移動(dòng)，稱(chēng)為蟻群算法的正反饋現(xiàn)象。蟻群能夠在較短時(shí)間內(nèi)找到食物位置，得益于信息素的反饋情況[14]。通過(guò)上述信息交換的正反饋機(jī)制最終得到一條最好路徑。由此，可將蟻群覓食行為的協(xié)作本質(zhì)概括為：

① 協(xié)同機(jī)制：螞蟻釋放信息素標(biāo)記已遍歷的路徑，感知路徑上已有信息素含量做出路徑?jīng)Q策，利用信息素完成個(gè)體之間的信息傳遞；

② 路徑概率決策機(jī)制：螞蟻有更大的機(jī)率選擇信息素強(qiáng)的路徑，在經(jīng)過(guò)該路徑時(shí)又會(huì)留下新的信息素，增強(qiáng)了濃度；

③ 信息素更新機(jī)制：路徑越短時(shí)，單位時(shí)間內(nèi)通過(guò)的螞蟻越多，路徑上積累的信息素越多。

蟻群算法在前期，信息素還沒(méi)有覆蓋到任務(wù)環(huán)境中，需要等待一定的時(shí)間讓信息素完全分布到環(huán)境中，產(chǎn)生一個(gè)參照；在后期，因?yàn)橄伻核惴ǖ膮f(xié)作機(jī)制，使得算法容易陷入混沌和局部最好情況，得不到全局最好解。

禁忌算法是一種將記憶功能結(jié)構(gòu)結(jié)合到了局部搜索策略中的一種元啟發(fā)式算法[15]。禁忌搜索的基本思想是在形成路徑規(guī)劃解過(guò)程中，禁止訪(fǎng)問(wèn)先前已訪(fǎng)問(wèn)過(guò)的節(jié)點(diǎn)，還利用了禁忌表和解禁策略的特性和靈活的記憶功能，增強(qiáng)了該算法對(duì)質(zhì)量較差解的容納度，具有較強(qiáng)的爬升能力，能夠避免陷入局部最小值，具有避免早熟的能力[16]。但是，全局搜索能力較弱，其最終解的質(zhì)量受初始解的影響較大。

Dijkstra算法的目的是解決起點(diǎn)A和目的地點(diǎn)B之間的最短路徑問(wèn)題，即從所有解中找出成本最低的一條路徑[17]。該算法能夠系統(tǒng)地評(píng)估和丟棄不利的子軌跡，直到找到最優(yōu)的路徑。在無(wú)人機(jī)路徑規(guī)劃中，能夠?qū)o(wú)人機(jī)的轉(zhuǎn)彎角度、出發(fā)和到達(dá)目的地的方向約束都考慮到，按路徑點(diǎn)距離的依次增加，找到起點(diǎn)到目的點(diǎn)之間的最短軌跡，算法總的時(shí)間復(fù)雜度為(n2)。

3.2 基于禁忌搜索的蟻群改進(jìn)算法

針對(duì)蟻群算法和禁忌搜索算法進(jìn)行研究，提出了ITAC的改進(jìn)思想、工作原理和算法步驟。通過(guò)仿真實(shí)驗(yàn)，比較分析了ITAC和禁忌算法、蟻群算法、Dijkstra算法的執(zhí)行結(jié)果，驗(yàn)證改進(jìn)算法的有效性。

3.2.1 算法原理

針對(duì)蟻群算法和禁忌算法各自的優(yōu)缺點(diǎn)，發(fā)現(xiàn)蟻群算法隨著搜索過(guò)程中局部最佳路徑上信息素的大量積累，易出現(xiàn)局部最佳甚至停滯的現(xiàn)象。而禁忌搜索算法的優(yōu)點(diǎn)是對(duì)次優(yōu)解有很好的接受能力，能夠幫助蟻群算法擴(kuò)大搜索空間，提高解的多樣性，搜索得到更高性能的全局最好解。

此外，蟻群算法具有分布式并行的優(yōu)點(diǎn)，每只螞蟻完成一次迭代搜索就可以獲得一個(gè)可行解，即蟻群算法每完成一次全局搜索都將產(chǎn)生等同于螞蟻數(shù)量的解[18]。因此，蟻群算法具有較大的機(jī)會(huì)搜索出性能較優(yōu)的解，將最好解集作為禁忌算法的初始解集，可以改善禁忌算法最終解的質(zhì)量過(guò)于依賴(lài)初始解的好壞情況。具有禁忌搜索能力的ITAC思想如下：

蟻群算法循環(huán)搜索所有配送點(diǎn)可得m條路徑，計(jì)算路徑長(zhǎng)度找到全局最佳路徑，對(duì)其進(jìn)行局部?jī)?yōu)化變換等操作后，存入禁忌表進(jìn)行限制，全局最佳路徑中的局部路徑將被拒絕訪(fǎng)問(wèn)。此外，針對(duì)蟻群算法所求得的解相似而易早熟、易陷入局部最好解的情況，應(yīng)用2-opt算法[19]對(duì)最佳路徑進(jìn)行局部?jī)?yōu)化變換，直到鄰域內(nèi)不能再改進(jìn)，以增加解的多樣性。

3.2.2 工作原理

本節(jié)對(duì)在禁忌算法基礎(chǔ)上改進(jìn)的蟻群算法，涉及的相關(guān)定義進(jìn)行介紹。

定義1：禁忌表。禁忌表是禁忌搜索算法中的基本定義。禁忌表的作用是來(lái)存儲(chǔ)算法迭代搜索一次后產(chǎn)生的所有結(jié)果中最好和最壞的路徑結(jié)果[20]。

從實(shí)際問(wèn)題出發(fā)，假設(shè)存在m個(gè)樣本配送地點(diǎn)，就令螞蟻的數(shù)量等于配送點(diǎn)數(shù)量進(jìn)行路徑規(guī)劃，對(duì)規(guī)劃算法得出的結(jié)果進(jìn)行排序，找出最好的路徑解集Rbest和最壞的解集Rworst，將二者存入禁忌表中。由于Rbest和Rworst兩個(gè)解集中的路徑數(shù)目不止一條，而且禁忌表能夠根據(jù)規(guī)則限制一些壞結(jié)果路徑點(diǎn)的選取。這說(shuō)明改進(jìn)算法不僅能在規(guī)劃路徑時(shí)高效并行，還提高了每次迭代搜索產(chǎn)生的最好路徑解集的質(zhì)量。

禁忌表中存儲(chǔ)的Rbest解集中的路徑數(shù)量設(shè)為Nbest，Rworst解集中的路徑數(shù)量設(shè)為Nworst，其中表里存儲(chǔ)的路徑數(shù)量可以調(diào)整，路徑數(shù)量設(shè)置過(guò)多會(huì)降低算法的運(yùn)算效率[21]。通常情況下，最好路徑數(shù)量設(shè)置為一條，但是，若求解的路徑優(yōu)化問(wèn)題規(guī)模比較大時(shí)，也可以根據(jù)實(shí)際情況將最好路徑數(shù)設(shè)置為多條。同時(shí)也要注意，并不是禁忌表中存儲(chǔ)的路徑數(shù)量越多越好。因?yàn)楫?dāng)禁忌表中存儲(chǔ)的路徑數(shù)量越多，就代表路徑規(guī)劃時(shí)可選擇的路徑點(diǎn)越少，甚至在限制條件較多時(shí)，會(huì)出現(xiàn)無(wú)路徑點(diǎn)可選的情況，最后導(dǎo)致算法搜索效率降低，可行空間太小搜索失去條理，無(wú)法獲得最好結(jié)果。

定義2：狀態(tài)標(biāo)識(shí)表。 狀態(tài)標(biāo)識(shí)表存儲(chǔ)的是路徑選擇狀態(tài)的標(biāo)識(shí)量，反映了路徑規(guī)劃時(shí)禁忌表對(duì)路徑選擇的限制。狀態(tài)標(biāo)識(shí)表中存儲(chǔ)的是多維矩陣，其中，矩陣的維度根據(jù)實(shí)際問(wèn)題定義。改進(jìn)算法中采用的是二維矩陣，矩陣中存儲(chǔ)著3個(gè)表示量：0，1，-1。1表示最好路徑解集中的局部路徑被禁忌訪(fǎng)問(wèn)，除非局部路徑出現(xiàn)在更好的路徑解集中時(shí)才被釋放；-1表示當(dāng)前路徑是禁忌表里Rworst解集中的路徑；0表示當(dāng)前路徑同時(shí)存在于Rworst解集和Rbest解集中。

定義3：解禁策略。禁忌表有一個(gè)禁忌周期，超過(guò)禁忌周期就需要對(duì)禁忌表中最先存入的路徑進(jìn)行釋放。改進(jìn)算法在對(duì)所有路徑節(jié)點(diǎn)迭代一次后會(huì)得出一個(gè)最好解，將該結(jié)果與當(dāng)前的路徑進(jìn)行比較。若最好解較優(yōu)將其存入禁忌表，對(duì)當(dāng)前最好路徑結(jié)果進(jìn)行解禁。在進(jìn)行路徑選擇時(shí)，找不到可選擇的下一路徑點(diǎn)時(shí)，就對(duì)禁忌表中最先存入的路徑進(jìn)行解禁。最后釋放的就是最好解，因?yàn)樵谝?guī)定的禁忌大小中，搜索過(guò)程中沒(méi)有優(yōu)于禁忌表中的結(jié)果時(shí)，表明禁忌表中的解是全局最好的解。禁忌表中的Rworst的禁忌周期沒(méi)有限制，只有當(dāng)Rworst中的局部路徑也是Rbest中的路徑時(shí)，局部路徑才能被釋放。這種策略降低了最差路徑對(duì)全局的影響，算法的效率也提高了[22]。

3.2.3 算法描述

根據(jù)以上描述，改進(jìn)蟻群算法流程如圖4所示。

圖4 結(jié)合禁忌搜索的改進(jìn)蟻群算法流程Fig.4 Flowchart of improved ant colony algorithm combined with taboo search

基于禁忌搜索的改進(jìn)蟻群算法如下：

算法1:基于禁忌搜索的改進(jìn)蟻群算法輸入:無(wú)人機(jī)起止位置αj,0,αj,m各區(qū)域地理特征信息A。輸出:無(wú)人機(jī)的優(yōu)化路徑序列kj={(αj,1,kj,1),(αj,2,kj,2),…,(αj,m,kj,m)}。步驟1:對(duì)參數(shù)進(jìn)行初始化,設(shè)置最大迭代次數(shù)Nmax,初始螞蟻數(shù)目為配送點(diǎn)數(shù)M;步驟2:導(dǎo)入位置數(shù)據(jù),計(jì)算配送位置與鄰近節(jié)點(diǎn)之間的距離,構(gòu)建信息素矩陣,將已訪(fǎng)問(wèn)節(jié)點(diǎn)和螞蟻承重量等變量值設(shè)為空;步驟3:螞蟻遍歷訪(fǎng)問(wèn)所有配送位置,對(duì)螞蟻k經(jīng)過(guò)的路徑上的信息素進(jìn)行更新;步驟4:若已經(jīng)訪(fǎng)問(wèn)完所有配送位置節(jié)點(diǎn)就執(zhí)行下一步,否者跳回上一步驟;步驟5:迭代計(jì)算找出最好路徑距離和最差路徑距離,對(duì)最好路徑長(zhǎng)度和當(dāng)前路徑長(zhǎng)度進(jìn)行比較,將較小路徑存入 Rbest;步驟6:對(duì)最好路徑Rbest的局部路徑段進(jìn)行有限次優(yōu)化,即將Rbest中的局部路徑替換為比其還短的當(dāng)前最短路徑;步驟7:更新禁忌表和狀態(tài)標(biāo)識(shí)表,按照解禁策略和局部?jī)?yōu)化對(duì)路徑進(jìn)行解禁;步驟8:若已到達(dá)最大迭代次數(shù),就輸出最好路徑結(jié)果序列,沒(méi)到達(dá)就返回步驟3。

4 仿真實(shí)驗(yàn)與分析

通過(guò)仿真實(shí)驗(yàn)，對(duì)比分析了ITAC、禁忌搜索算法、蟻群算法和Dijkstra算法，驗(yàn)證了所提ITAC在無(wú)人機(jī)的路徑規(guī)劃上的性能優(yōu)勢(shì)。本文在ArcGIS中，以巴基斯坦首都伊斯蘭堡中心醫(yī)院作為無(wú)人機(jī)的起點(diǎn)，中心醫(yī)院附近110 km以?xún)?nèi)的100個(gè)居民居住點(diǎn)作為患者住宅點(diǎn)，生成地理位置信息數(shù)據(jù)集。然后，利用計(jì)算機(jī)仿真在位置數(shù)據(jù)集中對(duì)4類(lèi)算例進(jìn)行測(cè)試，迭代次數(shù)設(shè)為50，不同算法基于無(wú)人機(jī)的路徑規(guī)劃實(shí)驗(yàn)性能對(duì)比如表3所示。

實(shí)驗(yàn)?zāi)M對(duì)于3類(lèi)患者數(shù)量(30，50，100例)的案例，分別初始化無(wú)人機(jī)數(shù)量(10，20，30，50，100架)來(lái)測(cè)試算法在實(shí)際無(wú)人機(jī)的使用數(shù)量、計(jì)算運(yùn)行時(shí)間和優(yōu)化距離方面的性能。

由表3可以看出，增加患者數(shù)量會(huì)增加要覆蓋的距離，需要更多的無(wú)人機(jī)，這也增加ITAC和禁忌搜索算法、蟻群算法和Dijkstra算法的總的運(yùn)行時(shí)間。然而，增加醫(yī)院中無(wú)人機(jī)的總數(shù)并不能保證覆蓋的距離會(huì)有顯著的不同。在所考慮的算法中，基于ITAC的無(wú)人機(jī)調(diào)度方法為所有輸入?yún)?shù)生成最佳化的解，原因在于ITAC結(jié)合了蟻群算法和禁忌搜索算法的優(yōu)點(diǎn)，在無(wú)人機(jī)路徑調(diào)度上展現(xiàn)了其優(yōu)勢(shì)。

當(dāng)患者數(shù)量遠(yuǎn)遠(yuǎn)高于可用的無(wú)人機(jī)數(shù)量時(shí)， 基于禁忌搜索算法的傳染病樣本收集無(wú)人機(jī)調(diào)度方法不能規(guī)劃出可行路徑。當(dāng)患者總數(shù)為100，而醫(yī)院中只有10架無(wú)人機(jī)時(shí)，就會(huì)觀(guān)察到?jīng)]有可行解決方案的情況，在表3中用N/A(不適用)記號(hào)表示，這也說(shuō)明了無(wú)人機(jī)的局限性。每架無(wú)人機(jī)一次不能覆蓋7名以上的患者，這是由無(wú)人機(jī)的電池容量和規(guī)定時(shí)間內(nèi)覆蓋的距離決定的。

在常規(guī)情況下，電池可用時(shí)間為1 h，無(wú)人機(jī)速度為60 km/h。此外，無(wú)人機(jī)被認(rèn)為在離地面6.096～9.144 m飛行。高層建筑、橋梁和山脈等形式的障礙物可以通過(guò)路徑規(guī)劃算法自動(dòng)避開(kāi)，基于無(wú)人機(jī)的傳染病疫情自檢套件調(diào)度方法從數(shù)據(jù)庫(kù)中提取障礙物和節(jié)點(diǎn)信息，并將它們集成到路由機(jī)制中，以構(gòu)建飛行路徑。

此外，無(wú)人機(jī)平均需要7～8 min來(lái)發(fā)送、收集和歸還檢測(cè)工具包。其他，如風(fēng)速和高溫造成的能量損失都沒(méi)有考慮。距離是使用無(wú)人機(jī)生成的值乘以單位值并除以1 000來(lái)計(jì)算的，結(jié)果換算為km。例如，在30名患者和10架無(wú)人機(jī)的情況下，距離為793個(gè)單位。在本研究中，單位距離為50 m，主要基于真實(shí)應(yīng)用的繪圖考慮。因此，793×50 m÷1 000=39.65 km。經(jīng)過(guò)上述數(shù)據(jù)處理，如果每天的患者保持在100人左右，伊斯蘭堡220 km2的總面積就可以很容易地被15架無(wú)人機(jī)覆蓋，所以實(shí)驗(yàn)中實(shí)際使用的無(wú)人機(jī)數(shù)量沒(méi)有超過(guò)15架。

4種算法運(yùn)行時(shí)間對(duì)比如圖5所示。

(a) 患者數(shù)量為30

(b) 患者數(shù)量為50

(c) 患者數(shù)量為100圖5 4種算法運(yùn)行時(shí)間對(duì)比Fig.5 Runtime comparison of four algorithms

表3 不同算法基于無(wú)人機(jī)的路徑規(guī)劃實(shí)驗(yàn)性能對(duì)比Tab.3 Experimental performance comparison of UAV-based path planning with different algorithms

由圖5可以看出，所提的ITAC在運(yùn)行時(shí)間上較其他3種算法更優(yōu)。這是因?yàn)榻伤惴?、蟻群算法和Dijkstra算法都容易因自身規(guī)則出現(xiàn)局部最好的情況，迭代次數(shù)增加。

本文所提ITAC性能優(yōu)于其他方法的原因在于：① 改進(jìn)算法引入信息素隨時(shí)間的消散程度描述，對(duì)信息素更新機(jī)制做出了改進(jìn)，消除了局部最優(yōu)的情況；② 利用禁忌算法的禁忌策略和解禁策略，降低了最差解集對(duì)ITAC的影響，使算法跳出局部最優(yōu)；③ 根據(jù)最好解集，再次對(duì)信息素分布進(jìn)行更新，降低了選錯(cuò)路徑的概率。

ITAC在路徑規(guī)劃上表現(xiàn)的性能好于禁忌算法和蟻群算法，體現(xiàn)在實(shí)驗(yàn)結(jié)果上均優(yōu)于蟻群算法和禁忌搜索算法。如ITAC在運(yùn)行時(shí)間上明顯優(yōu)于禁忌算法、蟻群算法和Dijkstra算法。以圖5(a)為例，分別高出86.7%，22.3%和33.2%。蟻群算法具有較好的全局搜索能力和躲避障礙能力，所以蟻群算法在優(yōu)化運(yùn)行時(shí)間性能上僅次于ITAC。而禁忌搜索算法容易陷入局部最佳問(wèn)題，即使引入了禁忌表，禁忌搜索仍需要多次循環(huán)，所以禁忌搜索算法在優(yōu)化運(yùn)行時(shí)間上較差。

4種算法在3種患者數(shù)量的算例中優(yōu)化路徑規(guī)劃距離的實(shí)驗(yàn)結(jié)果如圖6所示。

(a) 患者數(shù)量為30

(b) 患者數(shù)量為50

(c) 患者數(shù)量為100圖6 4種算法路徑優(yōu)化距離Fig.6 Distances of path optimization by four algorithms

由圖6(a)～(c)可以看出，3類(lèi)案例的實(shí)驗(yàn)圖中，ITAC搜索算法、禁忌算法、蟻群算法和Dijkstra算法對(duì)距離的優(yōu)化分別為一個(gè)穩(wěn)定的值，如圖6(a)所示，患者數(shù)量為30，實(shí)際利用的無(wú)人機(jī)數(shù)量為5架，ITAC算法、禁忌算法、蟻群算法和Dijkstra算法的優(yōu)化距離分別為31.85，39.65，32.2，38.05 km。這是因?yàn)?，每?lèi)案例的患者數(shù)量固定，雖然無(wú)人機(jī)的總數(shù)在變化，但是實(shí)際利用的無(wú)人機(jī)數(shù)量是不變的，每種算法在進(jìn)行路徑規(guī)劃時(shí)，分別只規(guī)劃了一條最佳路徑，所以?xún)?yōu)化的路徑距離是一個(gè)穩(wěn)定值。

隨著患者數(shù)量的增加， ITAC對(duì)距離的優(yōu)化一直表現(xiàn)最佳，以圖6(c)為例，相比于禁忌算法、蟻群算法和Dijkstra算法，ITAC在路徑距離上分別縮短了16.3%，4.5%和13.8%。ITAC表現(xiàn)最佳的原因在于：實(shí)驗(yàn)中患者數(shù)量的增加，禁忌算法、蟻群算法和Dijkstra算法規(guī)劃的路徑距離增長(zhǎng)幅度都大于ITAC，表明ITAC的穩(wěn)定性好于其他3種算法。特別是禁忌算法對(duì)初始的解集依賴(lài)性比較強(qiáng)，所以容易陷入局部最好，得不到全局最好的結(jié)果。而ITAC利用信息素更新原則，改善了禁忌算法過(guò)于依賴(lài)初始最好解的情況，擴(kuò)大了搜索解集空間。

此外，可以發(fā)現(xiàn)實(shí)際利用的無(wú)人機(jī)數(shù)量遠(yuǎn)遠(yuǎn)小于無(wú)人機(jī)總數(shù)量，這表明路徑規(guī)劃算法不僅優(yōu)化了運(yùn)行時(shí)間和距離，還提高了無(wú)人機(jī)的利用率。綜合分析，提出的基于禁忌搜索算法的傳染病樣本收集無(wú)人機(jī)調(diào)度方法，可以應(yīng)用于無(wú)人機(jī)的疫情防控中，對(duì)無(wú)人機(jī)的路徑規(guī)劃進(jìn)行優(yōu)化。

5 結(jié)束語(yǔ)

本文提出了基于禁忌搜索算法的傳染病檢測(cè)樣本收集無(wú)人機(jī)調(diào)度方法，將其應(yīng)用于疫情防控中，將新型冠狀病毒抗原檢測(cè)試劑盒遞送到潛在感染者身邊，并將樣本帶回檢測(cè)中心，最大限度地縮短遞送和接收時(shí)間。實(shí)驗(yàn)分析了禁忌算法、ITAC、蟻群算法和Dijkstra算法對(duì)無(wú)人機(jī)的路徑規(guī)劃的結(jié)果，實(shí)驗(yàn)證明4種算法均提高了無(wú)人機(jī)的利用率，但是ITAC在優(yōu)化路徑規(guī)劃中表現(xiàn)效果最佳。

當(dāng)前研究的局限性在于，使用了路徑規(guī)劃的相關(guān)技術(shù)，而沒(méi)有考慮其他問(wèn)題，如郵遞員問(wèn)題。此外，針對(duì)無(wú)人機(jī)電量有限這個(gè)問(wèn)題可以在未來(lái)考慮使用太陽(yáng)能驅(qū)動(dòng)無(wú)人機(jī)來(lái)解決。無(wú)人機(jī)不依賴(lài)于化石資源，從而減少汽車(chē)或送貨卡車(chē)產(chǎn)生的空氣污染，減少碳排放，對(duì)實(shí)現(xiàn)碳中和起到一定作用。其次，一些變量如風(fēng)速和電池因熱造成的能量損失本研究沒(méi)有考慮，可以在未來(lái)工作中進(jìn)行改進(jìn)。同樣，在未來(lái)無(wú)人機(jī)的法律含義、用戶(hù)的安全性、無(wú)人機(jī)的防黑客攻擊能力、最小無(wú)人機(jī)的最大覆蓋區(qū)域、性能優(yōu)化、無(wú)人機(jī)與患者之間的失敗合作概率、無(wú)人機(jī)的路徑出錯(cuò)的概率以及無(wú)人機(jī)的衛(wèi)生系統(tǒng)故障等，都是未來(lái)研究的重點(diǎn)。