電力巡檢中的無(wú)人機(jī)群路徑規(guī)劃算法①

李曉輝,張 路,劉傳水,趙 毅,董 媛

1(長(zhǎng)安大學(xué) 電子與控制工程學(xué)院,西安 710064)

2(渤海裝備 華油鋼管有限公司,滄州 062658)

無(wú)人機(jī)作為一種現(xiàn)代航空設(shè)備,不僅作業(yè)速度快,成本低,還具有卓越的靈活性和時(shí)效性.常用于完成那些繁冗、危險(xiǎn)、對(duì)靈活性要求較高、作業(yè)范圍較大的任務(wù),比如航空拍攝、農(nóng)藥噴灑、邊防檢查、電力檢測(cè)、防汛扛旱等領(lǐng)域[1].隨著技術(shù)的發(fā)展,將無(wú)人機(jī)獨(dú)特的優(yōu)勢(shì)和不同的行業(yè)技術(shù)相結(jié)合,可以應(yīng)用到不同的行業(yè).比如,無(wú)人機(jī)搭載成像傳感器,可以組成一種可以捕獲目標(biāo)圖像的新型監(jiān)視設(shè)備[2].目前,許多國(guó)家都在積極拓展無(wú)人機(jī)與工業(yè)應(yīng)用相結(jié)合的技術(shù),因此無(wú)人機(jī)應(yīng)用的研究一直備受關(guān)注.

穩(wěn)定的用電需求是當(dāng)今社會(huì)的基礎(chǔ)需求,因此,輸電線路檢測(cè)在電力行業(yè)顯得尤為重要.輸電線路檢測(cè)的主要工作是工人利用眼睛、望遠(yuǎn)鏡以及其他工具和手段觀察并檢測(cè)輸電設(shè)備,跟蹤設(shè)備的運(yùn)行狀況,發(fā)現(xiàn)威脅輸電設(shè)備和輸電安全的缺陷和問(wèn)題.輸電線路分布很廣,通常跨越高山、海域、平原及交通要道,且很大部分是露天下的高壓或超高壓傳輸,這使得輸電線路的檢測(cè)更加危險(xiǎn)和困難.據(jù)統(tǒng)計(jì),我國(guó)現(xiàn)有總長(zhǎng)達(dá)68.8 萬(wàn)千米的220 千伏及以上的輸電線路,相當(dāng)于繞地球17 圈[3].目前電力巡檢依舊是以傳統(tǒng)的人工巡檢為主,人工巡檢不僅耗費(fèi)大量的人力、物力、效率低、作業(yè)局限性大、還存在安全隱患.而無(wú)人機(jī)憑借其獨(dú)特的優(yōu)勢(shì)和性能,能使這一問(wèn)題的解決更加高效、簡(jiǎn)單和安全,因此無(wú)人機(jī)巡檢是未來(lái)電力巡檢的重要方式之一[4].

無(wú)人機(jī)路徑規(guī)劃是保證無(wú)人機(jī)作業(yè)的關(guān)鍵步驟.典型的路徑規(guī)劃問(wèn)題有車輛路徑問(wèn)題(vehicle routing problem,VRP)、帶有多車場(chǎng)的車輛路徑問(wèn)題(multidepot vehicle routing problem,MDVRP)[5]和多旅行推銷員問(wèn)題 (multiple travelling salesman problem,MTSP)[6].無(wú)人機(jī)路徑規(guī)劃問(wèn)題(unmanned aerial vehicle routing problem,UAVRP)是VRP 衍生出來(lái)的問(wèn)題.相對(duì)于地面作業(yè)而言,無(wú)人機(jī)作業(yè)有著以下特點(diǎn):(1)續(xù)航時(shí)間有限,需及時(shí)補(bǔ)充能耗;(2)單站點(diǎn)時(shí)作業(yè)里程受限,對(duì)于大規(guī)模問(wèn)題無(wú)法高效解決;(3)負(fù)載能力有限且續(xù)航時(shí)間與負(fù)載能力有關(guān)[5].通常供無(wú)人機(jī)搭載的圖像傳感器體積和重量都很小,所以用于巡檢或監(jiān)視的無(wú)人機(jī)可以不考慮負(fù)載[2].在現(xiàn)有無(wú)人機(jī)路徑規(guī)劃的研究中,有要求無(wú)人機(jī)必須離開(kāi)并返回一個(gè)倉(cāng)庫(kù)的[1,7],有允許無(wú)人機(jī)在不同倉(cāng)庫(kù)起飛和降落的,但是一次只能服務(wù)一個(gè)客戶的[5];有無(wú)人機(jī)和地面車輛合作才能完成任務(wù)的[7,8].而本文考慮的無(wú)人機(jī)群巡檢系統(tǒng)具有以下特點(diǎn):(1)帶有多個(gè)站點(diǎn),可以有效解決無(wú)人機(jī)續(xù)航受限的問(wèn)題;(2)無(wú)人機(jī)群協(xié)同作業(yè),能更快速地完成任務(wù);(3)允許無(wú)人機(jī)在不同的站點(diǎn)起飛和降落,可以提高無(wú)人機(jī)自身的工作效率與工作范圍,結(jié)合(1)和(2)可以有效解決覆蓋范圍較大的任務(wù);(4)同時(shí)包含點(diǎn)和線兩種類型的巡檢任務(wù),可以用于更復(fù)雜的巡檢系統(tǒng),擴(kuò)大其應(yīng)用范圍.

本文的目的是提出一種有效的解決方案來(lái)應(yīng)對(duì)帶有多站點(diǎn)的無(wú)人機(jī)群巡檢系統(tǒng).Kuhn 等人[9]在2020年在自適應(yīng)大鄰域搜索算法(adaptive large neighborhood search,ALNS)的框架下調(diào)用了兩個(gè)變鄰域下降搜索(variable neighborhood descent,VND)提出了一種通用ALNS (GALNS)算法,該算法用于求解具有時(shí)間窗和批量訂單要求的車輛路徑問(wèn)題,得到了較好的結(jié)果.因此,本文結(jié)合ALNS和VND 提出了一種混合式元啟發(fā)式算法用于解決本文考慮的無(wú)人機(jī)群巡檢系統(tǒng).ALNS和VND 都是路徑規(guī)劃中比較常用的方法.ALNS是大鄰域搜索算法(large neighborhood search,LNS)的擴(kuò)展,是一種基于個(gè)體解去搜索更好解的局部啟發(fā)式搜索算法,通過(guò)不同的搜索策略可擴(kuò)大搜索解空間[10].VND 常用于在相對(duì)較短的計(jì)算時(shí)間內(nèi)提升當(dāng)前解的質(zhì)量,可以有效地提高算法的收斂時(shí)間[11].

1 問(wèn)題描述

本文研究的問(wèn)題是通過(guò)算法找出無(wú)人機(jī)群在任意站點(diǎn)之間巡檢代價(jià)最小的飛行路徑.本文以輸電線路中的輸電線和電力塔桿為巡檢對(duì)象,將每個(gè)電力塔桿視為一個(gè)獨(dú)立的任務(wù)點(diǎn),兩塔桿之間的輸電線纜視為為獨(dú)立的任務(wù)線段.假設(shè)待巡檢區(qū)域有多個(gè)站點(diǎn)可供無(wú)人機(jī)充電和存放,并允許每個(gè)無(wú)人機(jī)在任意的站點(diǎn)起飛和降落;假設(shè)供巡檢的無(wú)人機(jī)均為充電式無(wú)人機(jī),單次飛行續(xù)航時(shí)間有限.為了保證完整并高效地完成巡檢任務(wù),無(wú)人機(jī)群路徑規(guī)劃是必不可少的工作.

無(wú)人機(jī)群路徑規(guī)劃要滿足以下約束:(1)每個(gè)任務(wù)服務(wù)時(shí)間不定,參與任務(wù)的無(wú)人機(jī)要在最大續(xù)航時(shí)間到達(dá)之前回到站點(diǎn);(2)規(guī)劃得到的路線應(yīng)是從任意站點(diǎn)起飛在任意站點(diǎn)降落的完整路徑;(3)任務(wù)結(jié)束后,每個(gè)倉(cāng)庫(kù)原有的無(wú)人機(jī)數(shù)量不變,保證路徑規(guī)劃方案可周期性使用.圖1給出了無(wú)人機(jī)群巡檢本問(wèn)題的示意圖.圖中的4 種顏色代表4個(gè)無(wú)人機(jī)的飛行路線,實(shí)線表示無(wú)人機(jī)正在巡檢目標(biāo)任務(wù),虛線表示無(wú)人機(jī)正飛往下一目標(biāo)的路途中.

圖1 無(wú)人機(jī)群巡檢示意圖

本文的目標(biāo)函數(shù)是在滿足上述約束條件的前提下,最小化所使用的無(wú)人機(jī)數(shù)量(NV)和總巡檢時(shí)間(T).一條從站點(diǎn)起飛后在站點(diǎn)降落的路徑定義為一架無(wú)人機(jī)的飛行路徑,即使用一架無(wú)人機(jī);一架無(wú)人機(jī)的巡檢時(shí)間從起飛開(kāi)始計(jì)算直到降落,所有無(wú)人機(jī)的巡檢時(shí)間之和為總巡檢時(shí)間.為了區(qū)分優(yōu)化目標(biāo)的優(yōu)先級(jí),我們將無(wú)人機(jī)的數(shù)量設(shè)為本問(wèn)題的主要優(yōu)化目標(biāo),總巡檢時(shí)間設(shè)為次要優(yōu)化目標(biāo),目標(biāo)函數(shù)表達(dá)式如式(1).

其中,M為一個(gè)總是大于總飛行時(shí)間的數(shù),即第二項(xiàng)的值總是介于0 到1 之間,以此保證優(yōu)化目標(biāo)的主次性.

2 算法設(shè)計(jì)

自適應(yīng)大鄰域搜索算法是一種源于大鄰域搜索算法的元啟發(fā)式算法,能有效地解決路徑規(guī)劃問(wèn)題[9].其與大鄰域搜索算法的區(qū)別在于加入了自適應(yīng)機(jī)制,該機(jī)制根據(jù)破壞算子和修復(fù)算子的作用效果,動(dòng)態(tài)調(diào)整權(quán)重并選擇不同的搜索算子來(lái)尋找更好的解.該方法通過(guò)設(shè)計(jì)多種破壞算子和修復(fù)算子,擴(kuò)大解空間的搜索范圍,在每次迭代中,算法會(huì)根據(jù)過(guò)去的效果對(duì)各個(gè)算子進(jìn)行權(quán)重和選擇的調(diào)整,表現(xiàn)好的算子就會(huì)得到更高的選擇權(quán)重,根據(jù)權(quán)重選擇更有效的算子組合方法來(lái)提高算法本身的尋找最優(yōu)解的能力.相比同類算法,如模擬退火算法,只調(diào)用了一種鄰域,其解空間的搜索范圍很小,很容易陷入局部最優(yōu),而大鄰域搜索算法具有多種搜索算子,就能有效地避免陷入局部最優(yōu).

在小學(xué)階段，為了提升學(xué)生的興趣，課堂上往往充滿了英語(yǔ)歌曲學(xué)習(xí)、對(duì)話表演和游戲等環(huán)節(jié)，學(xué)生可以在輕松的氛圍下接受老師層層引導(dǎo)傳輸?shù)闹R(shí)點(diǎn)。但在初中階段，由于教學(xué)內(nèi)容更多，往往會(huì)以課文學(xué)習(xí)、語(yǔ)法講解、課堂練習(xí)題為主，教學(xué)氣氛更加嚴(yán)肅。

變鄰域下降是一種強(qiáng)化版的局部改進(jìn)策略,近年來(lái)該算法已經(jīng)被成功用于求解不同的組合優(yōu)化問(wèn)題,具有算法結(jié)構(gòu)簡(jiǎn)單、魯棒性強(qiáng)、計(jì)算效率高、易于實(shí)現(xiàn)等優(yōu)點(diǎn),在變鄰域搜索和其他元啟發(fā)式方法中常作為下屬策略[9].

本文將變鄰域下降作為自適應(yīng)大鄰域搜索算法的下屬策略,提出一種新的元啟發(fā)式算法來(lái)解決本問(wèn)題.本算法設(shè)計(jì)了4 種破壞算子和4 種修復(fù)算子用于擴(kuò)大解空間.在變鄰域下降中,本文采用了5 種局部搜索方法增強(qiáng)局部改進(jìn),提高算法的收斂性.此外,在每次迭代中,本文采用模擬退火原則來(lái)保留進(jìn)化過(guò)程中解的多樣性[11].

2.1 個(gè)體表示與初始解

本問(wèn)題由n+m個(gè)任務(wù)和d個(gè)無(wú)人機(jī)站點(diǎn)組成,其中n表示電力塔桿數(shù)量,m表示輸電線段數(shù)量,每個(gè)任務(wù)必須檢查一次且只能檢查一次.本文采用二維序列編碼方法來(lái)表示一個(gè)個(gè)體,個(gè)體由多條路徑組成,每條路徑中存放一架無(wú)人機(jī)完整的飛行序列,該序列的首尾表示無(wú)人機(jī)的起降站點(diǎn),中間代表該無(wú)人機(jī)需要訪問(wèn)的任務(wù)序列.

本文的初始個(gè)體是隨機(jī)生成的.個(gè)體由若干飛行路徑組成,所以每條路徑必須保證無(wú)人機(jī)有足夠的電量安全降落,并滿足前述無(wú)人機(jī)群路徑規(guī)劃的所有約束.初始解的生成可分為以下步驟:(1)對(duì)于個(gè)體中的第一條路徑,隨機(jī)選擇兩個(gè)站點(diǎn)作為起飛點(diǎn)和降落點(diǎn),再隨機(jī)選擇任務(wù)插入到兩個(gè)站點(diǎn)中間;(2)下一條飛行路徑的降落點(diǎn)隨機(jī)選擇,起飛點(diǎn)為上一條路的降落點(diǎn),同樣隨機(jī)選擇剩余的任務(wù)插入到起飛點(diǎn)和降落點(diǎn)之間;(3)重復(fù)步驟(2),直到所有的任務(wù)被訪問(wèn)完畢;(4)判斷每個(gè)站點(diǎn)的無(wú)人機(jī)數(shù)量是否保持不變,如果不是則需要進(jìn)行調(diào)整,即為了滿足此約束可能會(huì)出現(xiàn)無(wú)人機(jī)從這個(gè)站點(diǎn)起飛不執(zhí)行任務(wù),直接降落到另一個(gè)站點(diǎn)的空飛路徑.存在空飛路徑的解也是一種可行解,所以我們是允許它存在的.

2.2 破壞算子

破壞算子通過(guò)刪除任務(wù)序列的方法來(lái)破壞一個(gè)解的完整性,刪除任務(wù)序列的方法不同,構(gòu)成的破壞算子不同.本算法設(shè)計(jì)了4 種破壞算子,其描述如下:

(1)隨機(jī)破壞:隨機(jī)破壞是此類算法中一種常見(jiàn)的破壞算子,它是從個(gè)體中隨機(jī)的刪除β個(gè)任務(wù).

(2)聚類破壞:該方法是Sacramento 等人[7]提出的一種聚類刪除方法.具體操作是隨機(jī)選擇一個(gè)任務(wù)點(diǎn),以該點(diǎn)為中心刪除一定范圍內(nèi)的所有任務(wù).

(4)刪除效率最差的路徑:將個(gè)體內(nèi)具有效率比最低的路徑刪除.效率比α的計(jì)算方法如式(2).例如,個(gè)體中有一條路徑R1,無(wú)人機(jī)完整飛行完該路徑的時(shí)間是T(R1),除去無(wú)人機(jī)在飛往目標(biāo)任務(wù)路上的飛行時(shí)間外,純用于巡檢任務(wù)的時(shí)間為p(R1),則效率比α為:

2.3 修復(fù)算子

修復(fù)算子是專門修復(fù)被破壞算子破壞后的解,通過(guò)不同修復(fù)方法,將被破壞算子刪除的任務(wù)重新插入到個(gè)體中,通過(guò)這樣的方式來(lái)生成一個(gè)新的解.本文采用了4 種修復(fù)算子,其描述如下.

(1)隨機(jī)插入:該方法是將被刪除的任務(wù)隨機(jī)插入到被破壞的解中,可以增加搜索解空間的多樣性.

(2)最佳插入:該操作將待插入的任務(wù)插入到最佳位置,即在該位置插入后增加的飛行時(shí)間最小.

(3)次優(yōu)插入:這種修復(fù)方法的工作方式與最佳插入相似.但是,并不總是選擇最佳位置插入,而是隨機(jī)選擇一個(gè)相對(duì)于插入之前成本不超過(guò)10%的位置插入.這種方法和隨機(jī)插入方法一樣,在搜索時(shí)能表現(xiàn)出更優(yōu)的多樣性,增加找到最優(yōu)解的可能性[7].

(4)插入效率最差的路徑:對(duì)于每個(gè)待插入的任務(wù),選擇如式(2)所示效率比最差的一條路,插入該路徑中的最佳位置.重復(fù)該過(guò)程,直到所有的任務(wù)都包含在新的解決方案中.

2.4 可行性修復(fù)

個(gè)體在不斷進(jìn)化過(guò)程中得到的新解,并不一定總是滿足約束的,所以我們需要判斷新得到的解的可行性,如果是一個(gè)不可行的解,則需要進(jìn)行可行性修復(fù).可行解修復(fù)是在不改變當(dāng)前任務(wù)序列的情況下,將不可行解轉(zhuǎn)化為可行解.其修復(fù)算法如算法1 所示,其中第一步是從不可行解中提取一個(gè)完整的任務(wù)序;第2)-4)步是生成第一條路徑;第5)步是生成第二條及以后的飛行路徑;第6)步是使其滿足問(wèn)題描述中的約束(3).

?

2.5 變鄰域下降

本文在變鄰域下降中采用了五種鄰域搜索結(jié)構(gòu),在調(diào)用變鄰域下降的過(guò)程中,仍然需要判斷解的可行性,如果是不可行解也要進(jìn)行可行性分割.變鄰域下降算法偽代碼如算法2 所示.5 種鄰域結(jié)構(gòu)簡(jiǎn)單解釋如下.

2-opt:該方法是反轉(zhuǎn)一段任務(wù)序列后該路徑會(huì)變得更優(yōu),是一種著名的可解開(kāi)交叉的鄰域搜索結(jié)構(gòu);在本文中每一條飛行路徑都有一段任務(wù)序列,遍歷個(gè)體中的每條路徑,如果反轉(zhuǎn)i和j之間的任務(wù)序列后路徑會(huì)變得更優(yōu),則接受反轉(zhuǎn).

顛倒線段走向:本結(jié)構(gòu)是專門針對(duì)本文題中的任務(wù)線段的,線段的訪問(wèn)方向與飛行距離直接相關(guān),所以顛倒線段的訪問(wèn)方向可能會(huì)節(jié)省更多的成本.具體操作如圖2所示.

圖2 顛倒線段走向

Swap:通過(guò)刪除最差的任務(wù)方法分別從兩條路徑中選出最差的任務(wù)兩個(gè)任務(wù),交叉插入最佳位置.

算法2.變鄰域下降主要偽代碼輸入:可行解X輸出:局部增強(qiáng)后的可行解X'Begin k←1 While k≤kmax do X' ← 第k 個(gè)鄰域結(jié)構(gòu)(X)if X'是不可行解 then X' ←可行性修復(fù)(X)if f(X')＜ f(X) then X←X'k←1 else k←k+1 end while返回X'end

Exchange:遍歷每條路徑,交換其中兩個(gè)任務(wù)的位置.

Migration:在兩條路徑中,將其中一條路的一個(gè)任務(wù),在可行的情況下轉(zhuǎn)移至另一條路,即轉(zhuǎn)移之后,該條路徑的飛行時(shí)間仍然滿足最大飛行時(shí)間約束.

2.6 完整算法描述

本算法主要步驟描述如下:(1)生成初始解.(2)更據(jù)各個(gè)破壞算子和修復(fù)算子的權(quán)重,輪盤(pán)賭選擇出一組破壞算子和修復(fù)算子對(duì)當(dāng)前解進(jìn)行改進(jìn)得到新解;判斷新解的可行性,如果修復(fù)后得到的新解是不可行解,則需要進(jìn)行可行性分割,保證新解是一個(gè)滿足約束的可行解.(3)變鄰域下降增強(qiáng)局部改進(jìn).(4)更新當(dāng)前最優(yōu)解,如果當(dāng)前解優(yōu)于最優(yōu)解,則無(wú)條件更新,如果當(dāng)前解不是最優(yōu)解,則根據(jù)模擬退火準(zhǔn)則接受.(5)重復(fù)(2)-(4)直到滿足算法終止條件.對(duì)應(yīng)的偽代碼如算法3 所示.

算法3.完整算法主要偽代碼輸入:相關(guān)任務(wù)信息及參數(shù)輸出:最優(yōu)解Begin生成初始解S記錄局部最優(yōu)pbest←S,全局最優(yōu)gbest←S While 終止條件為滿足 do X← pbest輪盤(pán)賭選擇一種破壞算子Destroy()和一種修復(fù)算子Repair();得到新的解X'← Repair(Destroy(X))if X'是不可行解 then X' ←可行性修復(fù)X X'← 變鄰域下降(X')

3 實(shí)驗(yàn)驗(yàn)證

我們對(duì)所設(shè)計(jì)的算法進(jìn)行了實(shí)驗(yàn)驗(yàn)證,所有的實(shí)驗(yàn)都采用C++語(yǔ)言編寫(xiě),在Microsoft Visual Studio 2019 上編譯,所用到的計(jì)算機(jī)參數(shù)為Intel (R) Core(TM) i7-8700 CPU 3.20 GHz,16.0 GB的RAM,64 位的Windows 10 操作系統(tǒng).由于本文解決的是一種同時(shí)包含點(diǎn)和線的問(wèn)題,沒(méi)有現(xiàn)存的測(cè)試數(shù)據(jù),但是本問(wèn)題又是從經(jīng)典的MDVRP 拓展過(guò)來(lái)的,所以本文的測(cè)試數(shù)據(jù)是根據(jù)Cordeau 在VRP bench mark 中給出的Multiple Depot VRP 測(cè)試實(shí)例[13]的基礎(chǔ)上修改得到的.因?yàn)镃ordeau 給出的數(shù)據(jù)中只包含了客戶的坐標(biāo)信息,該信息可對(duì)應(yīng)于本文題中的任務(wù)點(diǎn)的信息,我們隨機(jī)連接兩點(diǎn)間的直線作為任務(wù)線段信息,只要求其互不交叉,修改后的數(shù)據(jù)信息可在https://github.com/super-Sophia/Multiple-Depot-UAVRP 中找到.

3.1 參數(shù)設(shè)置

根據(jù)常用電力巡檢無(wú)人機(jī)的參數(shù),我們?cè)O(shè)置無(wú)人機(jī)勻速飛行,速度為1 500 單位每分鐘,最大飛行時(shí)間為90 分鐘,在每個(gè)任務(wù)點(diǎn)的執(zhí)行任務(wù)時(shí)間為2 分鐘,對(duì)每個(gè)任務(wù)線段的巡檢時(shí)間取決于線段的長(zhǎng)短.所測(cè)試的數(shù)據(jù)中,相鄰兩點(diǎn)間的距離放大了50 倍,其他點(diǎn)的距離按照同樣的比例縮放.本算法中隨機(jī)剔除數(shù)量β為總?cè)蝿?wù)數(shù)量的0.3 倍,即β=0.3×(n+m);對(duì)于任務(wù)點(diǎn)數(shù)量在100 及以下的M設(shè)為999,其他的M為9 999;由于本算法是在一次次迭代中尋找更優(yōu)解,隨著迭代次數(shù)的增加,找到最優(yōu)解的可能性越大,本算法設(shè)置的最大迭代次數(shù)為1 000 次.此外本文在實(shí)驗(yàn)時(shí),還設(shè)計(jì)了離散的粒子群算法(PSO)和標(biāo)準(zhǔn)文化基因算法(MA)兩個(gè)對(duì)比算法,兩個(gè)算法的種群大小為200,交叉概率為0.95,變異概率為0.2.

3.2 實(shí)驗(yàn)結(jié)果

我們根據(jù)數(shù)據(jù)集對(duì)該算法進(jìn)行了測(cè)試,實(shí)驗(yàn)結(jié)果如表1所示.表中Instance 表示被測(cè)數(shù)據(jù)的名稱;n、m和d分別表示任務(wù)點(diǎn)的數(shù)量、任務(wù)線段的數(shù)量和站點(diǎn)的數(shù)量;AVG、BEST、SD 分別表示每個(gè)數(shù)據(jù)運(yùn)行10 次后得到的平均值,最佳值和標(biāo)準(zhǔn)差;NV和T為該數(shù)據(jù)的最佳值對(duì)應(yīng)的無(wú)人機(jī)數(shù)量和總飛行時(shí)間.從表1我們可以看出,對(duì)于表中不同規(guī)模的問(wèn)題而言,本算法都能找到有效解,這表明本算法能夠求解大規(guī)模問(wèn)題;此外,隨著問(wèn)題規(guī)模的增加,算法的標(biāo)準(zhǔn)差依舊很穩(wěn)定,這表明了本算法具有很強(qiáng)的穩(wěn)定性和魯棒性.

表1 實(shí)驗(yàn)結(jié)果

為了進(jìn)一步驗(yàn)證本文所設(shè)計(jì)的算法解決問(wèn)題的能力,我們將所設(shè)計(jì)的算法與離散的PSO和標(biāo)準(zhǔn)的MA 算法進(jìn)行了對(duì)比,其中離散的PSO和MA 都是路徑規(guī)劃相關(guān)文獻(xiàn)中常用的算法.在離散的PSO 中只采用了交叉和變異兩種鄰域,本文中的交叉方法是常見(jiàn)的Recombine,變異方法是采用的變鄰域下降里面的Swap 操作.MA 中采用同樣的Recombine和Swap 作為交叉和變異,鄰域搜索結(jié)構(gòu)用的變鄰域下降中的2-opt.因?yàn)? 種算法的執(zhí)行框架是不同的,為了保證對(duì)比結(jié)果的有效性,我們將這3 個(gè)算法放在同樣的搜索時(shí)間內(nèi)去測(cè)試,即判斷在同樣的時(shí)間內(nèi)哪個(gè)算法找到的解更優(yōu).我們?cè)O(shè)置的搜索時(shí)間為10 分鐘,同樣每個(gè)案例測(cè)10 次,得到的數(shù)據(jù)如表2所示.

表2中加粗的字體為3 個(gè)算法在同樣的尋優(yōu)時(shí)間內(nèi)找到的最佳結(jié)果,從上可看出,在同等時(shí)間內(nèi),本文所設(shè)計(jì)的算法均得到了更好的結(jié)果,這表明本文設(shè)計(jì)的算法比離散的PSO和MA 能更好地節(jié)省巡檢中使用的無(wú)人機(jī)數(shù)量成本和時(shí)間成本.進(jìn)一步分析3 個(gè)算法的標(biāo)準(zhǔn)差可看出,在解決此問(wèn)題時(shí),本文的算法比其他兩種算法具有更好的魯棒性和穩(wěn)定性,并且隨著問(wèn)題規(guī)模的增加,算法依然具有較好的穩(wěn)定性.

表2 對(duì)比實(shí)驗(yàn)結(jié)果

上述實(shí)驗(yàn)結(jié)果表明,本算法能有效地解決該問(wèn)題,能夠應(yīng)用于大規(guī)模問(wèn)題的求解;并且隨著問(wèn)題規(guī)模的增加,本算法依舊具有較好的穩(wěn)定性和魯棒性.此外,相比離散的PSO和標(biāo)準(zhǔn)的MA 來(lái)說(shuō),本算法具有更強(qiáng)的尋優(yōu)能力和穩(wěn)定性,能夠找到更優(yōu)的解.

4 結(jié)論與展望

本文考慮了一種帶有多個(gè)站點(diǎn)的無(wú)人機(jī)群巡檢系統(tǒng),該系統(tǒng)中同時(shí)包含任務(wù)點(diǎn)和任務(wù)線兩種巡檢任務(wù).本文在ALNS 算法的框架下加入VND為下屬策略,提出了一種新的混合式元啟發(fā)式算法來(lái)解決該問(wèn)題中的無(wú)人機(jī)群路徑規(guī)劃問(wèn)題.實(shí)驗(yàn)結(jié)果表明該算法成功地解決了無(wú)人機(jī)群在巡檢過(guò)程中的路徑規(guī)劃問(wèn)題,表明了算法的有效性.此外我們還同優(yōu)化算法中常見(jiàn)的離散PSO和標(biāo)準(zhǔn)的MA 算法進(jìn)行了對(duì)比實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明本算法具有更好的尋優(yōu)能力,并且隨著問(wèn)題規(guī)模的增加,本算法依舊具有較好的穩(wěn)定性和魯棒性.這表明了本算法能高效地解決該問(wèn)題.接下來(lái),我們將嘗試解決環(huán)境更復(fù)雜、規(guī)模更大的巡檢系統(tǒng)中的問(wèn)題.