電力巡檢中的無人機群路徑規劃算法①

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

1(長安大學 電子與控制工程學院,西安 710064)

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

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

穩定的用電需求是當今社會的基礎需求,因此,輸電線路檢測在電力行業顯得尤為重要.輸電線路檢測的主要工作是工人利用眼睛、望遠鏡以及其他工具和手段觀察并檢測輸電設備,跟蹤設備的運行狀況,發現威脅輸電設備和輸電安全的缺陷和問題.輸電線路分布很廣,通?？缭礁呱健⒑Ｓ?、平原及交通要道,且很大部分是露天下的高壓或超高壓傳輸,這使得輸電線路的檢測更加危險和困難.據統計,我國現有總長達68.8 萬千米的220 千伏及以上的輸電線路,相當于繞地球17 圈[3].目前電力巡檢依舊是以傳統的人工巡檢為主,人工巡檢不僅耗費大量的人力、物力、效率低、作業局限性大、還存在安全隱患.而無人機憑借其獨特的優勢和性能,能使這一問題的解決更加高效、簡單和安全,因此無人機巡檢是未來電力巡檢的重要方式之一[4].

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

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

1 問題描述

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

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

圖1 無人機群巡檢示意圖

本文的目標函數是在滿足上述約束條件的前提下,最小化所使用的無人機數量(NV)和總巡檢時間(T).一條從站點起飛后在站點降落的路徑定義為一架無人機的飛行路徑,即使用一架無人機;一架無人機的巡檢時間從起飛開始計算直到降落,所有無人機的巡檢時間之和為總巡檢時間.為了區分優化目標的優先級,我們將無人機的數量設為本問題的主要優化目標,總巡檢時間設為次要優化目標,目標函數表達式如式(1).

其中,M為一個總是大于總飛行時間的數,即第二項的值總是介于0 到1 之間,以此保證優化目標的主次性.

2 算法設計

自適應大鄰域搜索算法是一種源于大鄰域搜索算法的元啟發式算法,能有效地解決路徑規劃問題[9].其與大鄰域搜索算法的區別在于加入了自適應機制,該機制根據破壞算子和修復算子的作用效果,動態調整權重并選擇不同的搜索算子來尋找更好的解.該方法通過設計多種破壞算子和修復算子,擴大解空間的搜索范圍,在每次迭代中,算法會根據過去的效果對各個算子進行權重和選擇的調整,表現好的算子就會得到更高的選擇權重,根據權重選擇更有效的算子組合方法來提高算法本身的尋找最優解的能力.相比同類算法,如模擬退火算法,只調用了一種鄰域,其解空間的搜索范圍很小,很容易陷入局部最優,而大鄰域搜索算法具有多種搜索算子,就能有效地避免陷入局部最優.

在小學階段，為了提升學生的興趣，課堂上往往充滿了英語歌曲學習、對話表演和游戲等環節，學生可以在輕松的氛圍下接受老師層層引導傳輸的知識點。但在初中階段，由于教學內容更多，往往會以課文學習、語法講解、課堂練習題為主，教學氣氛更加嚴肅。

變鄰域下降是一種強化版的局部改進策略,近年來該算法已經被成功用于求解不同的組合優化問題,具有算法結構簡單、魯棒性強、計算效率高、易于實現等優點,在變鄰域搜索和其他元啟發式方法中常作為下屬策略[9].

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

2.1 個體表示與初始解

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

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

2.2 破壞算子

破壞算子通過刪除任務序列的方法來破壞一個解的完整性,刪除任務序列的方法不同,構成的破壞算子不同.本算法設計了4 種破壞算子,其描述如下:

(1)隨機破壞:隨機破壞是此類算法中一種常見的破壞算子,它是從個體中隨機的刪除β個任務.

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

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

2.3 修復算子

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

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

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

(3)次優插入:這種修復方法的工作方式與最佳插入相似.但是,并不總是選擇最佳位置插入,而是隨機選擇一個相對于插入之前成本不超過10%的位置插入.這種方法和隨機插入方法一樣,在搜索時能表現出更優的多樣性,增加找到最優解的可能性[7].

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

2.4 可行性修復

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

?

2.5 變鄰域下降

本文在變鄰域下降中采用了五種鄰域搜索結構,在調用變鄰域下降的過程中,仍然需要判斷解的可行性,如果是不可行解也要進行可行性分割.變鄰域下降算法偽代碼如算法2 所示.5 種鄰域結構簡單解釋如下.

2-opt:該方法是反轉一段任務序列后該路徑會變得更優,是一種著名的可解開交叉的鄰域搜索結構;在本文中每一條飛行路徑都有一段任務序列,遍歷個體中的每條路徑,如果反轉i和j之間的任務序列后路徑會變得更優,則接受反轉.

顛倒線段走向:本結構是專門針對本文題中的任務線段的,線段的訪問方向與飛行距離直接相關,所以顛倒線段的訪問方向可能會節省更多的成本.具體操作如圖2所示.

圖2 顛倒線段走向

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

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

Exchange:遍歷每條路徑,交換其中兩個任務的位置.

Migration:在兩條路徑中,將其中一條路的一個任務,在可行的情況下轉移至另一條路,即轉移之后,該條路徑的飛行時間仍然滿足最大飛行時間約束.

2.6 完整算法描述

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

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

3 實驗驗證

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

3.1 參數設置

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

3.2 實驗結果

我們根據數據集對該算法進行了測試,實驗結果如表1所示.表中Instance 表示被測數據的名稱;n、m和d分別表示任務點的數量、任務線段的數量和站點的數量;AVG、BEST、SD 分別表示每個數據運行10 次后得到的平均值,最佳值和標準差;NV和T為該數據的最佳值對應的無人機數量和總飛行時間.從表1我們可以看出,對于表中不同規模的問題而言,本算法都能找到有效解,這表明本算法能夠求解大規模問題;此外,隨著問題規模的增加,算法的標準差依舊很穩定,這表明了本算法具有很強的穩定性和魯棒性.

表1 實驗結果

為了進一步驗證本文所設計的算法解決問題的能力,我們將所設計的算法與離散的PSO和標準的MA 算法進行了對比,其中離散的PSO和MA 都是路徑規劃相關文獻中常用的算法.在離散的PSO 中只采用了交叉和變異兩種鄰域,本文中的交叉方法是常見的Recombine,變異方法是采用的變鄰域下降里面的Swap 操作.MA 中采用同樣的Recombine和Swap 作為交叉和變異,鄰域搜索結構用的變鄰域下降中的2-opt.因為3 種算法的執行框架是不同的,為了保證對比結果的有效性,我們將這3 個算法放在同樣的搜索時間內去測試,即判斷在同樣的時間內哪個算法找到的解更優.我們設置的搜索時間為10 分鐘,同樣每個案例測10 次,得到的數據如表2所示.

表2中加粗的字體為3 個算法在同樣的尋優時間內找到的最佳結果,從上可看出,在同等時間內,本文所設計的算法均得到了更好的結果,這表明本文設計的算法比離散的PSO和MA 能更好地節省巡檢中使用的無人機數量成本和時間成本.進一步分析3 個算法的標準差可看出,在解決此問題時,本文的算法比其他兩種算法具有更好的魯棒性和穩定性,并且隨著問題規模的增加,算法依然具有較好的穩定性.

表2 對比實驗結果

上述實驗結果表明,本算法能有效地解決該問題,能夠應用于大規模問題的求解;并且隨著問題規模的增加,本算法依舊具有較好的穩定性和魯棒性.此外,相比離散的PSO和標準的MA 來說,本算法具有更強的尋優能力和穩定性,能夠找到更優的解.

4 結論與展望

本文考慮了一種帶有多個站點的無人機群巡檢系統,該系統中同時包含任務點和任務線兩種巡檢任務.本文在ALNS 算法的框架下加入VND為下屬策略,提出了一種新的混合式元啟發式算法來解決該問題中的無人機群路徑規劃問題.實驗結果表明該算法成功地解決了無人機群在巡檢過程中的路徑規劃問題,表明了算法的有效性.此外我們還同優化算法中常見的離散PSO和標準的MA 算法進行了對比實驗,實驗結果表明本算法具有更好的尋優能力,并且隨著問題規模的增加,本算法依舊具有較好的穩定性和魯棒性.這表明了本算法能高效地解決該問題.接下來,我們將嘗試解決環境更復雜、規模更大的巡檢系統中的問題.