配網線路無人機自主巡檢的路徑規劃方法

成 亮，楊 沛，賈燕翀，張磊源

(國網永濟供電公司，山西 永濟 044500)

0 引言

配電網作為電力系統的重要組成部分，承擔著從輸電網或地區發電廠接受電能，再通過配電設施就地分配或按電壓逐級分配給各類用戶的任務。配電網直接與供電用戶相聯系，因此，配電線路的安全穩定運行對整體電力供應系統的安全性起著至關重要的作用，更是社會穩定和百姓日常生活的基礎[1]。配網線路分布具有點多面廣的特點，很多線路位于地形復雜的野外，導地線、絕緣子塔桿以及其他金具容易受到雷電、風雪以及違章施工等自然和人為因素的破壞，因此，運維人員需要定期對配網線路進行巡檢，以確保線路的正常運行[2-3]。傳統的配網巡檢方式是人工在地面以仰視角度靠肉眼進行觀察，一方面，無法直接觀察到線路設備高處或頂部的情況；另一方面，巡檢安全性差且效率低下[4]。

近年來，隨著無人機技術的飛速發展，無人機由于靈活、輕便、能到達人員無法到達或不便到達的地方等特點，在電力、交通、物流和農業植保等多個領域得到了廣泛應用[5]。尤其在電力巡檢領域，無人機作為新型巡檢平臺已廣泛地應用于電力巡檢業務的活動中。通過無人機可以實現對配網線路的精細化巡檢，線夾斷裂、螺栓松動、防振錘跑位和間隔棒松脫等人工巡檢中不易發現的缺陷在無人機的高清影像中一目了然[6]。

無人機可以更加高效、安全地完成配網巡檢任務，把巡檢人員從高強度、高風險、重復性的體力勞動中解放出來[7-8]。目前，在使用無人機進行配電網巡檢時，主要依靠巡檢人員手動控制無人機拍攝桿塔和線路的圖像[9]。在手動巡檢模式下，巡檢人員需要根據經驗和技術，操控無人機飛到合適的位置，并調整云臺以合適的角度對配網線路和桿塔進行拍照，這對巡檢人員提出了較高的要求[10]。為了更好地發揮無人機的效能，需要研究無人機配網自主巡檢技術。

配網巡檢的主要工作包括對線路本體和桿塔關鍵部件的巡檢，其中以拍攝桿塔上的絕緣子、避雷器和隔離刀閘等關鍵部件為主[11]。配網的桿塔數量較多、種類各異且分布較廣，而無人機由于受到續航能力的約束，單架次飛行只能對部分桿塔進行巡檢。與此同時，所有的桿塔都需要定期巡檢，以保證關鍵部件的正常運行。如何在單次飛行中最大限度地發揮無人機續航能力，巡檢盡可能多的桿塔，同時使得大部分桿塔2次巡檢之間的間隔時間大致相同，是無人機配網自主巡檢需要解決的主要問題。

本文主要研究了無人機對配網桿塔上的關鍵部件進行巡檢的路徑規劃問題。首先，將配網桿塔抽象為點目標，并將每個桿塔距離上一次被巡檢的間隔天數作為該點目標的權重；其次，使用定向問題(Orienteering Problem，OP)對問題進行建模，并通過引入模擬退火(Simulated Annealing,SA)算法的Metropolis策略提升了遺傳算法(Genetic Algorithm,GA)的局部搜索能力；再次，基于OP的標準實例驗證了本文模型和算法的正確性；最后，為了說明本文方法如何應用于真實場景，使用脫敏的配網線路真實數據進行了案例研究，說明本文所提出的算法能在合理的時間內得到無人機配網自主巡檢的最優路徑。

1 問題描述

下面將介紹配網線路無人機自主巡檢路徑規劃問題的建模過程。

1.1 無人機

無人機從起點0出發，選擇部分桿塔進行巡檢，并在完成巡檢任務后返回終點N+1，無人機從起飛到降落的總時長不能超過無人機的最大續航時長Tmax。假設無人機搭載了自動避障和增穩裝置，具有自動避障和一定的抗風能力，因風力影響或避障產生的路徑偏離相對于總飛行路徑長度忽略不計。

1.2 待巡檢的桿塔

用0和N+1分別表示無人機的起點和終點，集合T={1,2,…,i,…,N}為所有待巡檢桿塔的集合，無人機的起點、終點以及所有待巡檢桿塔組成的集合為A={0,1,…,i,…,N,N+1}。待巡檢桿塔i的權重用wi(i∈T)表示，該權重表示桿塔i距離上一次被巡檢的時間間隔，權重越大表示時間間隔越長，則桿塔被巡檢的優先級也越高，需要盡快安排無人機對其進行巡檢。

1.3 無人機的巡檢任務執行時間

用P={0,i,…,j,N+1},i,j∈T表示無人機的巡檢路徑，無人機必須從起點出發執行巡檢任務，并在執行完任務后最終回到終點。無人機在桿塔i與桿塔j之間的飛行時間tij為：

(1)

式中，dij為桿塔i與桿塔j之間的歐氏距離；v為無人機的飛行速度；A為所有頂點集合。

無人機巡檢任務路徑P對應的任務執行時間為：

(2)

1.4 數學模型

針對無人機配網自主巡檢路徑優化問題，以無人機所巡檢桿塔的權重之和最大化作為優化問題的目標函數，建立如下數學模型：

(3)

約束條件為：

(4)

(5)

(6)

tP≤Tmax,

(7)

2≤ui≤N;?i∈T,

(8)

ui-uj+1≤(N-1)(1-xij);?i,j∈T,

(9)

xij∈{0,1};?i,j∈T。

(10)

式(3)的目標函數表示無人機所巡檢桿塔的權重之和最大化；式(4)表示無人機必須從起點出發，并最終返回終點；式(5)表示每個桿塔最多只能被巡檢一次；式(6)是流量守恒約束，即每個節點的入度與出度相等；式(7)是無人機續航能力約束；式(8)和式(9)避免了子路徑，其中ui為桿塔i在路徑P中的排序；式(10)為二元決策變量的取值，當無人機巡檢完桿塔i后飛往桿塔j巡檢，則xij=1，否則，xij=0。

2 改進的遺傳算法

2.1 遺傳算法

GA是美國密歇根大學Holland教授[12]提出的一種啟發式算法，模擬了自然界進化機制和生物進化論，是一類典型的群類算法[13]。由于GA是從一個群體開始搜索最優解，所以具有很強的并行搜索能力，同時，GA是一種與問題無關的算法，對參數的編碼進行選擇、交叉和變異等操作，不需要了解問題的相關知識，僅憑適應度函數對種群中的染色體進行評估。上述優點使得GA被廣泛地應用于無人機路徑規劃等組合優化領域[14-16]。

經典GA包括以下4個步驟：

① 種群初始化。GA從構建一個初始種群開始，初始種群中包含若干條染色體，每條染色體都是一個按特定規則編碼的問題可行解。

② 選擇操作。即從父代種群中挑選出優秀的染色體進行后續遺傳操作，使得種群中的優良基因得到傳承。常見的選擇算子有輪盤賭、隨機抽樣和錦標賽等。

③ 交叉操作。這一步是GA的核心，也是子代種群在父代種群基礎上進行改良的最重要手段，常用的交叉方式有單點交叉和多點交叉等。

④ 變異操作。是為了避免出現早熟現象而對種群進行的擾動，即以一定的概率對種群中的部分染色體進行局部改變，以生成新的染色體，它模擬了生物遺傳中的基因突變現象。

⑤ 適應度評估。GA的收斂速度和尋優能力主要取決于適應度函數的選取，其構建方法主要有2種：以目標函數作為適應度函數；基于目標函數的限界構造法，適應度評估涉及種群中的每一條染色體。

⑥ 種群更新。將父代種群中的優秀染色體和新生成的子代種群中的精英合并得到新的種群，體現了生物的遺傳特征。

GA的優點是簡單、快速、有效，尤其在算法的初期，尋優能力很強，但到了后期，由于種群中染色體的差異越來越小，使得進化速度越來越慢，而且容易陷入局部最優解[17]。雖然變異算子可能跳出局部最優，但總體效率偏低，若想改進算法的總體性能就需要提升算法的局部搜索能力。將群類算法與局部搜索算法混合是近年來比較流行的方法[18-20]，本文將SA算法與GA進行結合，設計了一種改進的遺傳算法(Improved Genetic Algorithm，IGA)。

2.2 IGA

SA算法是一種模仿金屬等固體物質退火過程的啟發式算法[21-22]，當初始溫度足夠高、冷卻過程足夠長時，金屬粒子都能達到基準穩態，從而使金屬的強度大大加強。SA算法最重要的特征是概率跳躍特性，也被稱為Metropolis過程，SA算法已被證明通過精確控制降溫過程可以近似1的概率收斂到全局最優[23-24]，但由于條件比較苛刻且收斂速度太慢而無法滿足實際應用的需求。

本文將SA算法的Metropolis準則引入到變異操作中，以提升GA的局部搜索能力。算法的偽代碼如下：

改進的遺傳算法(IGA)開始 初始化HGSA的相關參數種群初始化(詳見2.2.1節)染色體的約束校驗與調整(詳見2.2.2節)種群的適應度評價(詳見2.2.3節)while終止條件不滿足交叉操作(詳見2.2.4節)染色體的約束校驗與調整引入Metropolis準則的變異操作(詳見2.2.5節)種群的適應度評價種群更新操作(詳見2.2.6節) endwhile 輸出最優解結束

2.2.1 種群初始化

本文專門設計了一種整數編碼染色體，由所有待巡檢桿塔的編號組成，如圖1所示。

圖1 IGA染色體編碼示意Fig.1 Schematic diagram of IGA chromosome coding

圖1中的染色體表示無人機從站點出發后，依次巡檢1號、7號、4號、3號和5號桿塔，然后返回站點。

按以下3個步驟完成種群初始化：

① 令T為無人機待巡檢桿塔的集合，以無人機的起點為圓心，以無人機的續航能力Tmax為直徑，構造“Tmax圓”，刪掉集合T中在“Tmax圓”以外的點所對應的桿塔編號，得到無人機續航能力足以覆蓋的桿塔集合T’；

② 將集合T’中的桿塔編號進行隨機排列得到一條染色體，即無人機巡檢桿塔的序列，也就是無人機的巡檢路徑P；

③ 根據預設的種群規模重復步驟①～步驟②，得到初始種群。

由于無人機的續航能力有限，所以初始種群中的染色體不一定是可行解，需要對種群中的每條染色體進行約束檢驗，并對不滿足約束條件的染色體進行調整。

2.2.2 染色體的約束校驗與調整

初始化以及交叉操作后的染色體有可能違反本文模型中的2個約束，即式(5)所代表的目標訪問次數約束以及式(7)所代表的無人機續航能力約束。本文按如下步驟進行約束校驗和調整：

① 判斷染色體中是否存在相同的桿塔編號，如有則刪除多余的編號，保證每個桿塔編號在每條染色體中只出現一次；

② 根據染色體編碼計算無人機的路徑長度，再除以無人機的飛行速度得到該路徑對應的飛行時長，如果超過了無人機的續航時長，則按照桿塔的權重從小到大依次刪除其編號，如果2個桿塔的權重相同，則優先刪除距離更遠的桿塔，直到該路徑的飛行時長小于等于無人機的續航時長。

經過約束校驗與調整后的染色體是問題的一個可行解。

2.2.3 種群的適應度評價

染色體的適應度代表了路徑規劃方案的優劣，適應度越大說明路徑規劃方案越好。因此，以式(3)作為算法的適應度函數，路徑規劃方案的收益越高，說明該方案越優。后續的交叉操作基于種群適應度評價的結果進行。

2.2.4 交叉操作

本文使用經典的輪盤賭方法從父代種群中選擇染色體進行交叉操作，染色體的適應度越高，其優良的基因被遺傳到下一代的可能性也越高。本文采用兩點交叉方式，具體操作步驟如下：

① 使用經典的輪盤賭方法選擇2條待交叉的染色體，記作父代A和父代B，生成一個[0,1]區間的隨機數r，若r小于交叉概率PC則轉步驟②，否則結束當前操作；

② 由于父代A和父代B的染色體長度可能不同，所以需要分別產生2個交叉位，然后將2個交叉位之間的基因片段進行互換，得到2條新的染色體子代C和子代D，雙點交叉操作的過程如圖2所示。

圖2 雙點交叉操作示意Fig.2 Schematic diagram of two-point crossover operation

2.2.5 引入Metropolis準則的變異操作

由于桿塔的權重不同，所以通過替換染色體中的桿塔編號有可能提升適應度。同時，對染色體進行路徑長度校驗，即改變對桿塔的巡檢順序有可能縮短無人機的路徑長度，從而使得無人機可以訪問更多的桿塔，提升染色體的適應度，所以本文設計了2種變異算子。

變異算子1：基因替換。隨機選擇1個基因位，使用無人機續航能力足以覆蓋的桿塔集合T’中未出現在染色體中的桿塔編號替換該基因位上的桿塔編號。

變異算子2：基因調整。隨機選擇2個基因位，將這2個基因位上的桿塔編號進行互換。

在每次變異操作中，首先，隨機選取1種變異算子生成1個新染色體；然后，使用2.2.2中的方法對新染色體進行約束校驗和調整，并得到滿足所有約束條件的新染色體；最后，運用Metropolis準則以一定的概率接收新染色體。

2.2.6 種群更新操作

種群更新操作是將新生的子代種群與父代種群進行合并的操作，具體步驟如下：

① 根據適應度值分別對子代種群與父代種群中的染色體進行排序；

② 根據公式N1=NP×Gap計算得到從子代種群中取出染色體的數量，其中NP是種群規模，Gap是代溝；

③ 根據公式N2=NP×(1-Gap)計算得到從父代種群中取出染色體的數量；

④ 從子代種群中取出適應度排名后N1位的染色體，與父代種群中適應度排名前N2位的染色體合并，得到一個新的種群，作為下一輪迭代的新種群。

3 實驗與分析

本節所有實驗均在i5-6500 CPU 3.2 GHz、內存8 GB的臺式計算機上、Matlab R2020a的環境下運行。為了展示IGA的性能，本文設計了3組實驗。第1組實驗采用正交設計法對IGA的相關參數進行調優，以確定最優的參數組合；第2組實驗基于OP標準實例數據集使用IGA進行求解，并與文獻[25]中的最優解進行對比；第3組實驗使用脫敏的配網線路真實數據，使用IGA進行求解，說明本文的模型和方法如何用于配網線路的無人機自主巡檢。

3.1 確定算法最優參數的正交實驗

正交實驗是一種確定多個因素和多個水平最佳組合的常用實驗方法[26-28]，依據正交性選擇部分參數組合進行實驗，能夠使用較少的實驗次數找出最佳的實驗條件。

正交實驗的第一步是確定影響算法的相關參數及其取值；然后，構建正交表LM(QF)，其中，L表示正交表采用拉丁方法進行構建，M為實驗的次數，F為參數的個數，而Q則是每個參數的取值個數；最后，選取若干個數據集，并在正交表中每個參數組合下進行多次實驗，并根據實驗結果確定最優參數組合。

IGA相關參數有：種群規模NP，交叉概率PC，變異概率PM和迭代次數Iter，通過實驗測試并參考相關文獻，確定了上述4個參數的取值如表1所示。

表1 IGA相關參數及其取值Tab.1 Related parameters and their values of IGA

在表1的基礎上構建正交表L16(44)，并基于文獻[25]中的3個OP基準實例數據集，采用正交實驗法對IGA參數進行調優。所選取的數據集為文獻[25]中Tmax=30的3個實例，每個實例進行10次重復實驗并取平均值，輸入Minitab軟件得到的參數分析結果如圖3所示。

(a) 種群規模均值

(b) 交叉概率均值

(c) 變異概率均值

(d) 迭代次數均值圖3 正交實驗參數分析Fig.3 Analysis diagram of orthogonal experimental parameters

由正交實驗的原理以及圖3所示的參數分析結果，可以確定IGA的最佳參數組合為：種群規模NP=700，交叉概率PC=0.8，變異概率PM=0.4，迭代次數Iter=400。

3.2 基于OP標準實例數據集的數值實驗

為了展示IGA的算法性能，基于小規模和大規模的OP標準實例數據集設計了2組數值實驗。所有實驗均在3.1節中正交實驗確定的最優參數組合下進行。

① 小規模數值實驗

使用IGA對文獻[25]中的第3組經典OP標準實例數據集進行數值實驗，該組數據集的頂點數量n為33。在同組的所有標準實例中，頂點的位置和權重完全相同，只是最大持續時間Tmax不同。使用IGA對每個實例運行10次，并將所求得的最大收益及對應的路徑長度記錄在表2中。其中，Gap表示IGA求得的解與文獻[25]最優解的差距，計算公式為：

(11)

表2 OP標準實例數據集3(33個點)的對比實驗結果Tab.2 Comparative experimental results of OP benchmark instance dataset 3 (33 points)

從實驗結果可以看出，IGA求得的第3組經典OP基準實例數據集的最優解均優于文獻[25]的解，收益的平均Gap為-14.01%，說明IGA求得的收益比文獻[25]求得的收益平均提升了14.01%；路徑長度的Gap為0.55%，這是因為IGA求得的路徑方案訪問了更多的節點，可以理解為：IGA用平均0.55%的路徑增加換來了14.01%的收益增長。

② 大規模數值實驗

使用IGA對文獻[29]中的P6經典OP基準實例數據集進行求解，該組數據集的頂點數量n為66。在同組所有標準實例中的頂點位置和權重完全相同，只是最大持續時間Tmax不同。使用IGA對每個實例運行10次，并將所求得的最大收益及算法運行時長記錄在表3中。其中，Gap表示IGA求得的解與文獻[29]最優解的差距，計算公式為：

(12)

表3 OP標準實例數據集P6(64個點)的對比實驗結果Tab.3 Comparative experimental results of OP benchmark instance dataset P6 (66 points)

從實驗結果可以看出，除了最后3個實例IGA求得的解比文獻[29]中P6經典OP基準實例數據集的最優解稍差，其余11個實例均求得與文獻[29]相同的解，收益的平均Gap為0.39%；算法運行時長的平均Gap為77.75%，說明IGA的運行時長遠小于文獻[29]的算法，可以理解為：IGA以0.39%的收益損失提升了77.75%的算法效率。

3.3 基于脫敏配網線路真實數據的仿真實驗

為了說明上述研究工作在現實場景中的應用，基于脫敏的配網線路真實數據進行了仿真實驗，仿真場景如圖4所示。

圖4 無人機自主巡檢配網線路場景Fig.4 Scenario of distribution network line inspected by autonomous UAV

無人機從站點0出發，對配網線路進行自主巡檢，共有4條線路、67個桿塔，圖中每個點代表一個桿塔。桿塔上方有2個數字，其中，第1個數字是桿塔的編號，第2個數字是桿塔的權重，即該桿塔距離上一次被巡檢的時間間隔，時間間隔越長則權重越大，在圖4中的顏色也越深。

為了驗證不同型號的無人機在不同巡檢速度下的巡檢效果，設定無人機的續航能力分別為20，25和30 min，并設定無人機的平均巡檢速度分別為5，10和15 m/s，組合后得到9組仿真實驗，例如，案例(25，15)表示續航時長為25 min，巡檢速度為15 m/s。利用TOP模型對上述無人機自主巡檢配網線路的任務進行建模，并使用IGA對每個案例求得10次，并將所求得最優解的巡檢桿塔數量、路徑收益、路徑時長和算法運行時長記錄在表4中。

表4 仿真實驗結果Tab.4 Simulation experiment results

案例(20，5)的最優巡檢路徑如圖5所示。由圖5可以看出，無人機對所有30 d未巡檢的桿塔進行了巡檢，同時由于續航能力允許，還對15 d未巡檢的37#桿塔進行了巡檢，但算法求得的最優巡檢路徑與現實中的巡檢方案略有出入。現實中的配網巡檢一般以單條線路為單位，無人機從小號桿到大號桿依次進行巡檢，這樣便于巡檢后的內業操作與處理。雖略有出入，但算法可以為實際操作提供參考，大大降低了手動規劃巡檢路徑的工作量。IGA求得的案例(30，15)最優巡檢路徑如圖6(a)所示，從表4中看到該路徑的時長為24.460 7 min。而按實際業務需求操作的巡檢路徑如圖6(b)所示，經過計算可知，圖6(b)路徑的時長為25.342 6 min。實驗結果表明，IGA求得的巡檢路徑方案更優，說明IGA能夠有效縮短巡檢路徑時長，提升巡檢效率。

圖5 案例(20，5)的最優巡檢路徑示意Fig.5 Schematic diagram of optimal inspection path in case (20,5)

(a) 算法最優路徑

(b) 實際操作路徑圖6 案例(30，15)的算法最優路徑與實際操作路徑示意Fig.6 Schematic diagram of optimal path and piratical operation path in case (30,15)

通過對上述9組仿真實驗結果進行分析，有以下4個發現：

① 無人機會優先巡檢權重較高的桿塔，這符合配網線路巡檢的業務需求，即應該對較長時間沒有被巡檢的桿塔優先巡檢。

② 本文提出的IGA穩定性較好，而且可以在合理的時間內求得較優的無人機自主巡檢方案，每個案例的路徑時長都達到了續航能力的上限，這說明算法求得的巡檢方案最大限度地發揮了無人機的效用。

③ 同一型號的無人機執行巡檢任務時，飛行速度越快可以巡檢的桿塔數量越多；不同型號的無人機執行巡檢任務時，續航能力較強的無人機可以巡檢更多數量的桿塔。但速度可以彌補續航能力的不足，比如案例(20，10)中雖然無人機的續航能力只有20 min，但如果它以10 m/s的平均速度進行巡檢，可以巡檢36個桿塔，多于案例(25，5)的25個桿塔和案例(30，5)的30個桿塔。

④ 在案例(20，5)中，無人機僅能巡檢1條線路，而在案例(25，15)和案例(30，15)中，無人機能巡檢全部的67個桿塔。這符合不同業務場景下的需求，比如日常巡檢任務可以由續航能力較短的無人機進行精細化巡檢，而在應急場景下，一般使用續航能力較長的無人機快速地對所有線路進行巡檢，以便發現線路問題。

4 結束語

本文基于無人機對配網線路進行自主巡檢的場景，在考慮無人機續航能力的前提下，構建了以巡檢收益最大化為目標的OP模型，并首次將桿塔的巡檢間隔時間作為權重，來優化無人機自主巡檢的路徑。在傳統GA的基礎上，引入了SA算法的Metropolis準則，以提升遺傳算法的局部搜索能力，仿真實驗表明，IGA可以求得大部分經典OP基準實例數據集的最優解。IGA還可以應用于無人機自主巡檢的實際場景中，并可以在合理的運行時間內求得較優的無人機自主巡檢方案。在未來的研究中，將關注多無人機協同進行自主巡檢的場景，同時，除了桿塔的巡檢任務，還會關注桿塔之間線路通道的巡檢任務。