梁華塵，周穩(wěn)，倪旭東，胡康生，王倩倩，周智博

（1.國網安徽省電力有限公司滁州市城郊供電公司，安徽 滁州 239000；2.東南大學網絡空間安全學院，南京 210000）

0 引言

近年來，在“碳達峰碳中和”新背景下，構建以電網為樞紐的新型電力系統(tǒng)成為實現“雙碳”目標的重要途經［1］。輸電網作為電網的重要組成部分，因其在自然惡劣環(huán)境下長期運行，外部侵蝕和內部損耗等一系列問題會對自身穩(wěn)定運行帶來不利影響，所以需要定期巡視和維護預防事故的發(fā)生［2-3］。

傳統(tǒng)的輸電線路巡檢以人工巡檢方式為主，其勞動強度大，工作條件艱苦，勞動效率低［4］，已不能適應新時期輸電網發(fā)展和安全運行的需要。相較于人工巡檢方式，無人機電力巡檢具有操作靈活、巡檢成本低、巡檢效率高、顯著降低勞動強度［5-6］等特點。隨著技術的不斷發(fā)展，采用無人機電力巡檢逐漸成為輸電線路巡檢的重要手段。受限于無人機航跡規(guī)劃難、續(xù)航時間短和遠距離機動能力弱等問題［7］，現階段無人機無法勝任實際巡檢場景下較遠距離的連續(xù)巡檢任務。為了解決這一問題，巡檢車搭載無人機協(xié)同巡檢的新模式受到了有關研究者的關注，該模式實現了車與無人機優(yōu)勢互補，極大提高了無人機電力巡檢的自動化程度和巡檢效率［8］。無人機進行輸電線路的電力巡檢作業(yè)時，不同的巡檢路徑所耗費的時間和經濟成本存在較大差異性。因此，無人機電力巡檢路徑規(guī)劃問題成為無人機電力巡檢作業(yè)的核心問題。

針對上述問題，已有學者對無人機電力巡檢路徑規(guī)劃問題開展了相關研究工作。文獻［9］針對電力桿塔三維巡檢路徑提出了一種改進快速隨機搜索樹（rapid-exploration random tree，RRT）算法，克服了在狹窄空間難以找到可行路徑問題。文獻［10］構建了面向電力桿塔巡檢“無人機-旅行商”問題（travelling salesman problem with drone，TSP-D）模型，提出了奇偶分層編碼方式的遺傳算法求解該模型。文獻［11］研究了“巡檢車+無人機”協(xié)同巡檢作業(yè)模式下無人機任務分配問題和巡檢車路徑規(guī)劃問題。文獻［12］提出了一種異地起降的單車多無人機協(xié)同電力巡檢方式。但是以上文獻均未涉及到電力線路巡檢內容和無人機可懸停這一策略。文獻［13］考慮了車載無人機協(xié)同巡檢模式下對電力線路進行巡檢路徑規(guī)劃問題，運用啟發(fā)式算法和模擬退火算法求解。文獻［14］考慮了無人機電力巡檢軌跡遵循架空線跨度曲線，但未進行仿真驗證。但以上文獻均未考慮電力桿塔巡檢過程和無人機可懸停這一策略。

綜上所述，目前無人機電力巡檢領域涉及路徑規(guī)劃的研究尚不完善，仍有以下問題有待進一步研究：1）未對以電力線路和電力桿塔為聯(lián)合巡檢目標的車載無人機協(xié)同巡檢路徑規(guī)劃方法進行進一步研究。2）在車機協(xié)同巡檢過程中，未考慮實際情況下無人機可懸停等待巡檢車這一情況。3）未考慮無人機在不同階段的飛行參數的差異性。

針對以上問題，本文基于電力桿塔和電力線路為多目標聯(lián)合電力巡檢任務，對車載無人機協(xié)同巡檢路徑規(guī)劃問題開展了相關研究。本文首先在已有研究的基礎上，根據“圖論”相關理論建立了計及電力桿塔和電力線路聯(lián)合電力巡檢的車載無人機協(xié)同路徑規(guī)劃模型。其次在模型求解過程中首先根據本模型特點采用改進中國郵遞員求解最佳輸電線路巡檢路線；并提出一種離散桿塔分割弧算法應用到巡檢過程中，可求得較優(yōu)的路徑規(guī)劃方案，并分析了不同場景下不同策略對解的影響；結合模型相關特點，利用模擬退火算法對該方案進一步優(yōu)化，在該算法優(yōu)化過程中，提出了符合本模型特點的領域搜索算子以完成模型求解。最后通過算例進一步驗證的模型和算法的合理性和有效性。

1 車載無人機協(xié)同電力巡檢路徑規(guī)劃模型

1.1 問題描述

面向多目標聯(lián)合電力巡檢的車載無人機協(xié)同巡檢過程如圖1 所示，該過程是指巡檢車搭載無人機從運維站出發(fā)，沿著巡檢車?？奎c移動，在合適的?？奎c停靠并放飛無人機。無人機由?？奎c飛向輸電線路，開始對電力桿塔和電力線路協(xié)同巡檢，完成全部輸電線路巡檢任務后，巡檢車搭載無人機返回運維站。

1.2 策略分析

無人機進行某段電力巡檢過程如圖2 所示。方塊為車輛?？奎c，圓圈為電力桿塔，巡檢車行駛時間用T表示，無人機飛行時間用t表示，無人機的續(xù)航時間用θ表示。

圖2 巡檢單元示意圖Fig.2 Sketch diagram of inspection unit

1）不考慮無人機懸停等待

式（1）表示巡檢完b桿塔返回滿足約束條件，在某些極端場景下TAB≥tAa+tab+tbB，則會造成無可行解的情況。式（2）表示無人機飛出點c滿足續(xù)航要求，但由于無人機先于車輛到達?？奎c導致該桿塔飛出點為不可行解。

2）考慮無人機懸停等待

式（3）和式（4）擴大了可行解的約束范圍，使得無人機飛出點b、c均為可行解。

由上可知，考慮無人機懸停等待在不考慮無人機懸停等待的基礎上擴大了解的空間，避免了極端條件下巡檢過程中不可行解的出現，減少了無人機飛入飛出的次數，縮短了無人機的飛入飛出時間。

1.3 數學模型

計及桿塔和電力線路聯(lián)合巡檢的車載無人機協(xié)同巡檢路徑規(guī)劃問題可以用圖G(V，E)表示，V表示圖中所有點的集合，其中包括運維站點λ0，巡檢車?？奎c集合Vp={p1，p2，…，pn}，其中pn表示第n個巡檢車停靠點；以及無人機在輸電線路飛入飛出點集合Vλ={λ1，λ2，…，λm}，其中λn代表第n個無人機飛入飛出點，用數學形式可表示為V={λ0}∪Vp∪Vλ。E表示為圖中所有弧的集合，其中包括巡檢車行駛路段集合Ec={i，j|i，j∈Vp∪{λ0}}，無人機輸電線路飛行路段弧集合Eu={i，λk，λk+1，j|[i，j∈Vp∪λ0，k∈Rl]} 用數學形式可表示為E=Ec∪Eu。R表示巡檢單元集合，其中包括負載巡檢單元集合Rl={1，…，a，a+2，…，b，b+2，…，m-1}，空載巡檢單元Rnl={0，a+1，b+1，…，m}，用數學形式可表示為R=Rl∪Rnl，其中a、b、m為巡檢單元的巡檢序號。

1.3.1 目標函數

本文以車載無人機協(xié)同電力巡檢任務總用時最小作為優(yōu)化目標，構建如下目標函數。

式中：Z為車載無人機協(xié)同電力巡檢任務總用時；為第k個巡檢單元巡檢車行駛路線的決策變量；為第k個巡檢單元無人機巡檢作業(yè)的決策變量；dij為?？奎c之間的距離；分別為巡檢車停靠點與無人機飛入飛出點的距離；為第k個巡檢單元無人機巡檢輸電線路總長度；vc為巡檢車在停靠點間的平均行駛速度；vu1為無人機飛入飛出輸電網的平均飛行速度；vu2為無人機巡檢電力線路時的平均飛行速度；αk為第k個巡檢單元巡檢桿塔數量；Tg為無人機精細化巡檢桿塔耗費時長。

1.3.2 約束條件

1）巡檢車?？奎c出入度約束

2）運維站出入度約束

3）巡檢車?？课恢眉s束

4）無人機執(zhí)行巡檢任務約束

5）?？奎c訪問順序遞增約束

式中：gi∈N+（正整數集合），?i∈Vp，gi為輔助決策變量，其中分別為第k個巡檢單元的無人機的回收點序號以及起飛點序號。

6）無人機降落放飛點重合約束

7）無人機降落放飛點重合約束

8）負載巡檢單元車輛行駛時間約束

2 車載無人機協(xié)同電力巡檢路徑規(guī)劃模型求解

輸電網巡檢路線屬于弧路由問題范疇，傳統(tǒng)弧路由問題可通過中國郵遞員問題（Chinese mailman problem，CPP）來求解，本文結合電力巡檢相關特點，對CPP 作出相關改進，用于求解電力巡檢的巡檢路線。無人機飛入飛離電網點的選取屬于連續(xù)優(yōu)化問題，有無限多可行方案，為了把它作為離散優(yōu)化問題去分析，通常是把平面上的每條邊用多邊形鏈來近似［15］。本文以電力桿塔所在位置作為離散優(yōu)化的離散點，提出了離散桿塔分割弧算法。將離散桿塔分割弧算法與改進CPP 相結合，在遍歷輸電網中所有奇點后選取最優(yōu)解作為初始巡檢方案，并在求得的初始方案的基礎上結合模擬退火算法進一步優(yōu)化。求解策略如圖3所示。

圖3 模型求解策略圖Fig.3 Diagram of model solving strategy

2.1 改進中國郵遞員問題

中國郵遞員問題是：一個郵遞員每次上班，要走遍他負責送信的所有街道最后回到郵局，應怎么走才能使所走的路程最短［16］。

本文待巡檢的輸電線路網絡可抽象為無向連通圖G(V，E)，V為電力桿塔構成節(jié)點集合，E為電力線路構成邊集合，不同于傳統(tǒng)CPP，本文結合巡檢體對輸電線路協(xié)同巡檢的特點，首先巡檢體從某一奇點出發(fā)對輸電網開始巡檢，最終以某一奇點結束巡檢，即“一筆畫問題”，其次巡檢體在輸電線路某一奇點完成巡檢作業(yè)可以緊接著直接前往輸電線路下一個奇點開始巡檢作業(yè)。改進CPP 求解路線圖如圖4 所示。而改進的中國郵遞員問題尋找最短巡檢路線歸結為圖論［17］問題。

圖4 改進CPP示意圖Fig.4 Schematic diagram of improved CPP

給定無向連通圖G(V，E)，設奇點集合為V1，奇點Vi、Vj之間本身存在連接邊eij，則eij至多添加一條新邊，且=ω(eij)。奇點Vi、Vj之間本身不存在連接邊eij，則Vi、Vj之間至多添加一條新邊為Vi、Vj之間的歐式距離，得到新圖G'(V，E')，求使圖G'中保留兩個指定特殊奇點且總權值最小的歐拉通路，E'為通路集合，其中兩個指定特殊奇點為歐拉通路的起點和終點。

最后采用最小權匹配算法和Fleury 算法結合求解該問題，下面對兩算法進行介紹。

1）最小權匹配算法

CPP最早研究方法是奇偶點作業(yè)法［18］，但是對于本文比較大的輸電線路網絡等效圖，算法的時間復雜度過大。結合圖論中二分匹配［19］，通過對邊權值取反將最大權匹配問題轉換為最小權匹配問題以完成非歐拉圖向歐拉圖的轉換。

2）Fleury算法

在上述已求得最小權半歐拉圖的前提下，接下來改進CPP 需求該半歐拉圖的歐拉通路，本文采用Fleury 算法，該算法既可以用來求歐拉圖的歐拉回路也可以求本文半歐拉圖的歐拉通路。

設G'(V，E')為無向半歐拉圖，Fleury 算法求解過程參考文獻［20-21］。

2.2 離散桿塔分割弧算法

結合本文多目標巡檢特點，本文以電力桿塔作為輸電線路上的離散點來分析協(xié)同巡檢問題，提出了離散桿塔分割弧算法。該算法由于采用桿塔作為離散點相較于常規(guī)的取線路離散點方法（二分法、等距法等）更為密集，從而進一步擴大了解的可行域，可以獲得一個較優(yōu)的初始解。

2.2.1 算法原理

在執(zhí)行巡檢任務的第k個巡檢單元中，若k為空載巡檢單元，則該單元耗時為巡檢車行駛時間。若k為負載巡檢單元，則該單元內無人機需要執(zhí)行巡檢任務，設無人機在該單元飛入飛出輸電網的位置點分別為a、b，設x為輸電線路任意點，若該點為桿塔點，對應的桿塔巡檢順序值點為β(x)，若該點為線路點，對應的桿塔巡檢順序值點為[β(x)-，β(x)+]。已知巡檢車停靠點集合為Vp={p1，p1，…，pn}；Lab為a、b之間的輸電線路長度；為x到停靠點之間的距離；為?？奎cpi和pj之間的距離；Tg為無人機精細化巡檢桿塔耗費時長。構造函數H(x)，表示輸電線路上任意位置點x到離該位置點最近的巡檢車停靠點px的距離，用數學公式表示為：

采用貪心策略判斷：

1）b為桿塔點

（1）與下一待巡檢桿塔無電力線路連接

若滿足：

則無人機從b直接返航，由巡檢車運往下一負載巡檢單元。

若滿足：

則無人機不巡檢桿塔b直接返航。

（2）與下一待巡檢桿塔有電力線路連接

同式（16）及其結論。

2）b為線路點

則滿足：

2.2.2 算法求解策略

從起始桿塔開始執(zhí)行巡檢任務，針對電力線路和電力桿塔聯(lián)合巡檢的特點，結合上述貪心判斷思想，直至完成所有巡檢任務。算法流程圖如圖5所示。

圖5 離散桿塔分割弧算法流程圖Fig.5 Flow chart of discrete tower segmentation arc algorithm

2.3 優(yōu)化求解算法

上述算法已求得的較優(yōu)解仍然有優(yōu)化空間，由于模擬退火算法具有較好的全局收斂性，當溫度較高時，算法跳出局部最優(yōu)空間范圍能力強，隨著溫度下降，算法跳出局部最優(yōu)空間的能力逐漸減弱。最終算法在溫度趨向于最低臨界值時趨向于全局最優(yōu)解［22］，本文采用該算法對初始解進一步優(yōu)化，算法步驟參考文獻［23-25］。

由于本文研究的電力巡檢問題的特殊性，一些傳統(tǒng)路徑規(guī)劃算子無法適用，因此本文結合無人機巡檢的相關特點，提出了小規(guī)模組合算子。

1）鄰近桿塔交換算子

鄰近桿塔交換算子是指無人機的飛入點或飛出點與鄰近桿塔在某區(qū)間范圍內進行交換。

2）鄰近巡檢車?？奎c交換算子

鄰近巡檢車?？奎c交換算子是指改變在當前最優(yōu)條件下采取最近?？奎c的策略，調整為可以選取次最近?？奎c。

3 算例分析

算例選取某市長45 km、寬30 km 的110 kV 輸電線路運維區(qū)域，如圖6 所示。運維區(qū)域的待巡檢目標為電力線路和電力桿塔，其中電力桿塔195基。該運維區(qū)域的輸電線路抽象為圖論問題含有8個奇點，根據該運維區(qū)域實際路網圖中適合無人機放飛和回收的地點選取出35 個合適的運維車?？奎c，編號為1—35。

圖6 運維區(qū)域Fig.6 Operation and maintenance area

3.1 算例參數設置

電力巡檢相關參數如表1所示。

表1 電力巡檢參數表Tab.1 Parameters table of power inspection

3.2 不同場景下不同策略對結果的影響

為了驗證模型的合理性和有效性，本文考慮兩種策略在3 個場景下的結果對比，場景1 為惡劣山路，場景2為鄉(xiāng)間小路，場景3為平坦公路，3個場景主要對巡檢車行駛速度產生影響；策略1 為考慮無人機懸停，策略2 為不考慮無人機懸停，對比結果如表2所示。

表2 多場景不同策略方案結果對比Tab.2 Comparison of the results of different strategies for multiple scenarios

由表2 可知，場景1 采用策略2 會造成該場景下無法完成巡檢任務，即無可行解；場景2 采用策略1 相較于策略2 在巡檢總耗時和無人機飛入飛出輸電網過程耗時縮短了6.1 min，換算成距離為3.05 km。場景3 中，兩種策略對兩類耗時的影響差異可忽略不計，造成該現象的主要原因是隨著巡檢車的速度不斷提升，巡檢車提前到達?？奎c等待無人機的概率不斷增大。3 個場景在策略1 的情況下無人機飛入飛出過程耗時接近是由于無人機在巡檢中根據離散桿塔分割弧算法貪婪判斷過程中均可滿足判斷條件，導致最終終止判斷位置接近，削弱了巡檢車速度對最終解的影響；在策略2 的情況下隨著不同場景巡檢車速度的提升，開始出現可行解/可行解變小，并逐漸趨于策略1的可行解。綜合3 個場景下策略1 和策略2 對解的影響，策略1 避免了極端場景下巡檢過程中不可行解的出現，擴大了解的范圍，縮短了無人機的飛入飛出時間，進而減少了巡檢總耗時，綜上可知策略1優(yōu)于策略2。

3.3 車載無人機協(xié)同巡檢路徑規(guī)劃結果

由于篇幅有限，下文基于場景3 策略1 下協(xié)同巡檢路徑規(guī)劃結果進一步分析，并探究自然災害（暴雨、臺風）等條件下，道路損壞導致無法按照原先正常優(yōu)化路線到達下一?？奎c的情況，說明優(yōu)化算法的有效性和普適性。

假設自然災害條件下，車輛?？奎c3、15、16、19、24、25、31、34無法滿足?？恳?，需重新規(guī)劃巡檢路線?；诟倪MCPP 和離散桿塔分割弧的遞推算法的協(xié)同路徑初步規(guī)劃方案的遍歷過程對比如圖7 所示，由圖可知正常情況下最小巡檢總耗時為1 535 min，自然災害條件下最小巡檢總耗時為1 571 min，兩者對應的巡檢路徑規(guī)劃圖如圖8 所示，相比于正常條件下的路線，自然災害條件下通過調整車輛?？奎c和無人機飛入飛出點來協(xié)同優(yōu)化巡檢路線。

圖7 初步規(guī)劃方案遍歷結果圖Fig.7 Preliminary planning scheme traversal result map

圖8 協(xié)同巡檢路徑規(guī)劃圖Fig.8 Planning diagram of cooperative inspection path

為了進一步驗證模擬退火算法的有效性，下文在圖8（a）（下文稱方案1）的基礎上優(yōu)化協(xié)同巡檢路線，優(yōu)化后的路徑規(guī)劃方案稱為方案2。路徑優(yōu)化圖如圖9所示。

圖9 協(xié)同巡檢路徑優(yōu)化圖Fig.9 Cooperative inspection path optimization diagram

圖8 和圖9 中綠色箭頭代表巡檢車行駛路線，藍色數字代表巡檢車?？奎c序號。紅色線段代表無人機飛入飛出路線，紅色數字代表無人機飛入飛出點順序。方案1 是車載無人機從運維站出發(fā)以某一桿塔奇點作為巡檢輸電網出發(fā)點再以之外某一桿塔奇點作為返回點返回運維站中最優(yōu)的規(guī)劃結果，負載巡檢單元段內無人機和巡檢車配合執(zhí)行巡檢作業(yè)任務，例如巡檢飛入飛出點1 至7 間的輸電線路，空載巡檢單元內，巡檢車運載無人機前往下一待巡檢桿塔，例如運維站—停靠點2、?？奎c15—停靠點11。本文算法保證了無人機每次巡檢為最大續(xù)航時間，因此確定了最優(yōu)情況下的無人機飛入飛出輸電網的最少次數，在保證最優(yōu)飛入飛出次數的前提下，方案2 通過領域動作對方案1 的飛入飛出點和巡檢車?？奎c進行調整，由圖7 可知，方案2 在保證每個負載巡檢段內的首尾無人機飛入飛出點不變的前提下，在滿足無人機和車輛相關約束條件的前提下，對飛入飛出點和?？奎c做了不同限度的調整，調整效果總體上是趨于無人機飛入飛出輸電網過程時間更短和巡檢車行駛時間更短，方案2 和方案1各巡檢單元內用時對比如圖10所示。

圖10 方案1和方案2各巡檢單元用時對比Fig.10 Comparison of the time spent on each inspection unit for Scenario 1 and Scenario 2

由圖10可知，各巡檢單元耗時方案2總體上相較于方案1 得到的優(yōu)化，少數巡檢單元例如巡檢單元7（對應飛入飛出點6—7），巡檢單元13，巡檢單元20，三者情況相同，由于為了滿足本巡檢單元段內其他巡檢單元的相關約束，為總體優(yōu)化提供優(yōu)化空間，作出局部犧牲，旨在縮短整體巡檢時間。巡檢單元15（對應飛入飛出點14—15）、16、17、21已無優(yōu)化空間，所以兩方案保持一致。兩方案總體耗時對比如表3所示。

表3 兩方案耗時對比Tab.3 Comparison of the parameters and indicators of the two solutions

由表3 可知。方案2 比方案1 的總耗時縮短了41 min。其中總耗時包括固定巡檢任務耗時和非固定巡檢任務耗時，固定巡檢任務耗時指的是輸電線路中所有桿塔和電力線路巡檢耗時，該耗時不可優(yōu)化，本文的非固定巡檢任務耗時包括巡檢車在空載巡檢單元的行駛時間和無人機飛入飛出輸電網過程中飛行用時，該耗時可優(yōu)化。方案2 的可優(yōu)化巡檢耗時在方案1 的基礎上提升了23.3%，證明了優(yōu)化算法的可行性和有效性。

4 結論

針對已有研究主要考慮單目標電力巡檢以及實際場景下無人機可懸停等待這一情形考慮的缺乏，本文考慮了包含電力桿塔和電力線路的多目標聯(lián)合電力巡檢并以車載無人機協(xié)同電力巡檢任務總用時最小作為優(yōu)化目標，根據 “圖論”相關理論提出了一種面向電力巡檢實際場景的多目標聯(lián)合巡檢的車機協(xié)同電力巡檢協(xié)同路徑規(guī)劃模型，并結合相關算法對其進行求解，通過算例驗證得出如下結論。

1）運用本文提出的改進CPP 和離散桿塔分割弧算法可以快速得到一個較優(yōu)協(xié)同路徑規(guī)劃方案，該方案可快速地為電力公司電力巡檢作業(yè)提供一個實用且有效的車機協(xié)同巡檢路徑規(guī)劃方案。

2）通過對比不同場景下不同策略，可以得出考慮無人機懸停時相較于傳統(tǒng)情況適應場景更廣，解的質量更高更優(yōu)。通過探究自然災害下的優(yōu)化路線，進一步驗證了算法的普適性和有效性。

3）在初始優(yōu)化方案的基礎上結合本文提出的模擬退火算法得到的優(yōu)化方案可以有效地縮短可優(yōu)化耗時，具有較高的現實意義。

4）本文把巡檢車行駛路徑簡化為節(jié)點路由問題研究，具體實際路網問題在此基礎上進一步研究。