配網(wǎng)線路無人機(jī)自主巡檢的路徑規(guī)劃方法

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

(國網(wǎng)永濟(jì)供電公司，山西 永濟(jì) 044500)

0 引言

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

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

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

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

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

1 問題描述

下面將介紹配網(wǎng)線路無人機(jī)自主巡檢路徑規(guī)劃問題的建模過程。

1.1 無人機(jī)

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

1.2 待巡檢的桿塔

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

1.3 無人機(jī)的巡檢任務(wù)執(zhí)行時(shí)間

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

(1)

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

無人機(jī)巡檢任務(wù)路徑P對應(yīng)的任務(wù)執(zhí)行時(shí)間為：

(2)

1.4 數(shù)學(xué)模型

針對無人機(jī)配網(wǎng)自主巡檢路徑優(yōu)化問題，以無人機(jī)所巡檢桿塔的權(quán)重之和最大化作為優(yōu)化問題的目標(biāo)函數(shù)，建立如下數(shù)學(xué)模型：

(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)的目標(biāo)函數(shù)表示無人機(jī)所巡檢桿塔的權(quán)重之和最大化；式(4)表示無人機(jī)必須從起點(diǎn)出發(fā)，并最終返回終點(diǎn)；式(5)表示每個(gè)桿塔最多只能被巡檢一次；式(6)是流量守恒約束，即每個(gè)節(jié)點(diǎn)的入度與出度相等；式(7)是無人機(jī)續(xù)航能力約束；式(8)和式(9)避免了子路徑，其中ui為桿塔i在路徑P中的排序；式(10)為二元決策變量的取值，當(dāng)無人機(jī)巡檢完桿塔i后飛往桿塔j巡檢，則xij=1，否則，xij=0。

2 改進(jìn)的遺傳算法

2.1 遺傳算法

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

經(jīng)典GA包括以下4個(gè)步驟：

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

② 選擇操作。即從父代種群中挑選出優(yōu)秀的染色體進(jìn)行后續(xù)遺傳操作，使得種群中的優(yōu)良基因得到傳承。常見的選擇算子有輪盤賭、隨機(jī)抽樣和錦標(biāo)賽等。

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

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

⑤ 適應(yīng)度評估。GA的收斂速度和尋優(yōu)能力主要取決于適應(yīng)度函數(shù)的選取，其構(gòu)建方法主要有2種：以目標(biāo)函數(shù)作為適應(yīng)度函數(shù)；基于目標(biāo)函數(shù)的限界構(gòu)造法，適應(yīng)度評估涉及種群中的每一條染色體。

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

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

2.2 IGA

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

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

改進(jìn)的遺傳算法(IGA)開始 初始化HGSA的相關(guān)參數(shù)種群初始化(詳見2.2.1節(jié))染色體的約束校驗(yàn)與調(diào)整(詳見2.2.2節(jié))種群的適應(yīng)度評價(jià)(詳見2.2.3節(jié))while終止條件不滿足交叉操作(詳見2.2.4節(jié))染色體的約束校驗(yàn)與調(diào)整引入Metropolis準(zhǔn)則的變異操作(詳見2.2.5節(jié))種群的適應(yīng)度評價(jià)種群更新操作(詳見2.2.6節(jié)) endwhile 輸出最優(yōu)解結(jié)束

2.2.1 種群初始化

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

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

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

按以下3個(gè)步驟完成種群初始化：

① 令T為無人機(jī)待巡檢桿塔的集合，以無人機(jī)的起點(diǎn)為圓心，以無人機(jī)的續(xù)航能力Tmax為直徑，構(gòu)造“Tmax圓”，刪掉集合T中在“Tmax圓”以外的點(diǎn)所對應(yīng)的桿塔編號，得到無人機(jī)續(xù)航能力足以覆蓋的桿塔集合T’；

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

③ 根據(jù)預(yù)設(shè)的種群規(guī)模重復(fù)步驟①～步驟②，得到初始種群。

由于無人機(jī)的續(xù)航能力有限，所以初始種群中的染色體不一定是可行解，需要對種群中的每條染色體進(jìn)行約束檢驗(yàn)，并對不滿足約束條件的染色體進(jìn)行調(diào)整。

2.2.2 染色體的約束校驗(yàn)與調(diào)整

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

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

② 根據(jù)染色體編碼計(jì)算無人機(jī)的路徑長度，再除以無人機(jī)的飛行速度得到該路徑對應(yīng)的飛行時(shí)長，如果超過了無人機(jī)的續(xù)航時(shí)長，則按照桿塔的權(quán)重從小到大依次刪除其編號，如果2個(gè)桿塔的權(quán)重相同，則優(yōu)先刪除距離更遠(yuǎn)的桿塔，直到該路徑的飛行時(shí)長小于等于無人機(jī)的續(xù)航時(shí)長。

經(jīng)過約束校驗(yàn)與調(diào)整后的染色體是問題的一個(gè)可行解。

2.2.3 種群的適應(yīng)度評價(jià)

染色體的適應(yīng)度代表了路徑規(guī)劃方案的優(yōu)劣，適應(yīng)度越大說明路徑規(guī)劃方案越好。因此，以式(3)作為算法的適應(yīng)度函數(shù)，路徑規(guī)劃方案的收益越高，說明該方案越優(yōu)。后續(xù)的交叉操作基于種群適應(yīng)度評價(jià)的結(jié)果進(jìn)行。

2.2.4 交叉操作

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

① 使用經(jīng)典的輪盤賭方法選擇2條待交叉的染色體，記作父代A和父代B，生成一個(gè)[0,1]區(qū)間的隨機(jī)數(shù)r，若r小于交叉概率PC則轉(zhuǎn)步驟②，否則結(jié)束當(dāng)前操作；

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

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

2.2.5 引入Metropolis準(zhǔn)則的變異操作

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

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

變異算子2：基因調(diào)整。隨機(jī)選擇2個(gè)基因位，將這2個(gè)基因位上的桿塔編號進(jìn)行互換。

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

2.2.6 種群更新操作

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

① 根據(jù)適應(yīng)度值分別對子代種群與父代種群中的染色體進(jìn)行排序；

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

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

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

3 實(shí)驗(yàn)與分析

本節(jié)所有實(shí)驗(yàn)均在i5-6500 CPU 3.2 GHz、內(nèi)存8 GB的臺式計(jì)算機(jī)上、Matlab R2020a的環(huán)境下運(yùn)行。為了展示IGA的性能，本文設(shè)計(jì)了3組實(shí)驗(yàn)。第1組實(shí)驗(yàn)采用正交設(shè)計(jì)法對IGA的相關(guān)參數(shù)進(jìn)行調(diào)優(yōu)，以確定最優(yōu)的參數(shù)組合；第2組實(shí)驗(yàn)基于OP標(biāo)準(zhǔn)實(shí)例數(shù)據(jù)集使用IGA進(jìn)行求解，并與文獻(xiàn)[25]中的最優(yōu)解進(jìn)行對比；第3組實(shí)驗(yàn)使用脫敏的配網(wǎng)線路真實(shí)數(shù)據(jù)，使用IGA進(jìn)行求解，說明本文的模型和方法如何用于配網(wǎng)線路的無人機(jī)自主巡檢。

3.1 確定算法最優(yōu)參數(shù)的正交實(shí)驗(yàn)

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

正交實(shí)驗(yàn)的第一步是確定影響算法的相關(guān)參數(shù)及其取值；然后，構(gòu)建正交表LM(QF)，其中，L表示正交表采用拉丁方法進(jìn)行構(gòu)建，M為實(shí)驗(yàn)的次數(shù)，F(xiàn)為參數(shù)的個(gè)數(shù)，而Q則是每個(gè)參數(shù)的取值個(gè)數(shù)；最后，選取若干個(gè)數(shù)據(jù)集，并在正交表中每個(gè)參數(shù)組合下進(jìn)行多次實(shí)驗(yàn)，并根據(jù)實(shí)驗(yàn)結(jié)果確定最優(yōu)參數(shù)組合。

IGA相關(guān)參數(shù)有：種群規(guī)模NP，交叉概率PC，變異概率PM和迭代次數(shù)Iter，通過實(shí)驗(yàn)測試并參考相關(guān)文獻(xiàn)，確定了上述4個(gè)參數(shù)的取值如表1所示。

表1 IGA相關(guān)參數(shù)及其取值Tab.1 Related parameters and their values of IGA

在表1的基礎(chǔ)上構(gòu)建正交表L16(44)，并基于文獻(xiàn)[25]中的3個(gè)OP基準(zhǔn)實(shí)例數(shù)據(jù)集，采用正交實(shí)驗(yàn)法對IGA參數(shù)進(jìn)行調(diào)優(yōu)。所選取的數(shù)據(jù)集為文獻(xiàn)[25]中Tmax=30的3個(gè)實(shí)例，每個(gè)實(shí)例進(jìn)行10次重復(fù)實(shí)驗(yàn)并取平均值，輸入Minitab軟件得到的參數(shù)分析結(jié)果如圖3所示。

(a) 種群規(guī)模均值

(b) 交叉概率均值

(c) 變異概率均值

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

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

3.2 基于OP標(biāo)準(zhǔn)實(shí)例數(shù)據(jù)集的數(shù)值實(shí)驗(yàn)

為了展示IGA的算法性能，基于小規(guī)模和大規(guī)模的OP標(biāo)準(zhǔn)實(shí)例數(shù)據(jù)集設(shè)計(jì)了2組數(shù)值實(shí)驗(yàn)。所有實(shí)驗(yàn)均在3.1節(jié)中正交實(shí)驗(yàn)確定的最優(yōu)參數(shù)組合下進(jìn)行。

① 小規(guī)模數(shù)值實(shí)驗(yàn)

使用IGA對文獻(xiàn)[25]中的第3組經(jīng)典OP標(biāo)準(zhǔn)實(shí)例數(shù)據(jù)集進(jìn)行數(shù)值實(shí)驗(yàn)，該組數(shù)據(jù)集的頂點(diǎn)數(shù)量n為33。在同組的所有標(biāo)準(zhǔn)實(shí)例中，頂點(diǎn)的位置和權(quán)重完全相同，只是最大持續(xù)時(shí)間Tmax不同。使用IGA對每個(gè)實(shí)例運(yùn)行10次，并將所求得的最大收益及對應(yīng)的路徑長度記錄在表2中。其中，Gap表示IGA求得的解與文獻(xiàn)[25]最優(yōu)解的差距，計(jì)算公式為：

(11)

表2 OP標(biāo)準(zhǔn)實(shí)例數(shù)據(jù)集3(33個(gè)點(diǎn))的對比實(shí)驗(yàn)結(jié)果Tab.2 Comparative experimental results of OP benchmark instance dataset 3 (33 points)

從實(shí)驗(yàn)結(jié)果可以看出，IGA求得的第3組經(jīng)典OP基準(zhǔn)實(shí)例數(shù)據(jù)集的最優(yōu)解均優(yōu)于文獻(xiàn)[25]的解，收益的平均Gap為-14.01%，說明IGA求得的收益比文獻(xiàn)[25]求得的收益平均提升了14.01%；路徑長度的Gap為0.55%，這是因?yàn)镮GA求得的路徑方案訪問了更多的節(jié)點(diǎn)，可以理解為：IGA用平均0.55%的路徑增加換來了14.01%的收益增長。

② 大規(guī)模數(shù)值實(shí)驗(yàn)

使用IGA對文獻(xiàn)[29]中的P6經(jīng)典OP基準(zhǔn)實(shí)例數(shù)據(jù)集進(jìn)行求解，該組數(shù)據(jù)集的頂點(diǎn)數(shù)量n為66。在同組所有標(biāo)準(zhǔn)實(shí)例中的頂點(diǎn)位置和權(quán)重完全相同，只是最大持續(xù)時(shí)間Tmax不同。使用IGA對每個(gè)實(shí)例運(yùn)行10次，并將所求得的最大收益及算法運(yùn)行時(shí)長記錄在表3中。其中，Gap表示IGA求得的解與文獻(xiàn)[29]最優(yōu)解的差距，計(jì)算公式為：

(12)

表3 OP標(biāo)準(zhǔn)實(shí)例數(shù)據(jù)集P6(64個(gè)點(diǎn))的對比實(shí)驗(yàn)結(jié)果Tab.3 Comparative experimental results of OP benchmark instance dataset P6 (66 points)

從實(shí)驗(yàn)結(jié)果可以看出，除了最后3個(gè)實(shí)例IGA求得的解比文獻(xiàn)[29]中P6經(jīng)典OP基準(zhǔn)實(shí)例數(shù)據(jù)集的最優(yōu)解稍差，其余11個(gè)實(shí)例均求得與文獻(xiàn)[29]相同的解，收益的平均Gap為0.39%；算法運(yùn)行時(shí)長的平均Gap為77.75%，說明IGA的運(yùn)行時(shí)長遠(yuǎn)小于文獻(xiàn)[29]的算法，可以理解為：IGA以0.39%的收益損失提升了77.75%的算法效率。

3.3 基于脫敏配網(wǎng)線路真實(shí)數(shù)據(jù)的仿真實(shí)驗(yàn)

為了說明上述研究工作在現(xiàn)實(shí)場景中的應(yīng)用，基于脫敏的配網(wǎng)線路真實(shí)數(shù)據(jù)進(jìn)行了仿真實(shí)驗(yàn)，仿真場景如圖4所示。

圖4 無人機(jī)自主巡檢配網(wǎng)線路場景Fig.4 Scenario of distribution network line inspected by autonomous UAV

無人機(jī)從站點(diǎn)0出發(fā)，對配網(wǎng)線路進(jìn)行自主巡檢，共有4條線路、67個(gè)桿塔，圖中每個(gè)點(diǎn)代表一個(gè)桿塔。桿塔上方有2個(gè)數(shù)字，其中，第1個(gè)數(shù)字是桿塔的編號，第2個(gè)數(shù)字是桿塔的權(quán)重，即該桿塔距離上一次被巡檢的時(shí)間間隔，時(shí)間間隔越長則權(quán)重越大，在圖4中的顏色也越深。

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

表4 仿真實(shí)驗(yàn)結(jié)果Tab.4 Simulation experiment results

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

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

(a) 算法最優(yōu)路徑

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

通過對上述9組仿真實(shí)驗(yàn)結(jié)果進(jìn)行分析，有以下4個(gè)發(fā)現(xiàn)：

① 無人機(jī)會優(yōu)先巡檢權(quán)重較高的桿塔，這符合配網(wǎng)線路巡檢的業(yè)務(wù)需求，即應(yīng)該對較長時(shí)間沒有被巡檢的桿塔優(yōu)先巡檢。

② 本文提出的IGA穩(wěn)定性較好，而且可以在合理的時(shí)間內(nèi)求得較優(yōu)的無人機(jī)自主巡檢方案，每個(gè)案例的路徑時(shí)長都達(dá)到了續(xù)航能力的上限，這說明算法求得的巡檢方案最大限度地發(fā)揮了無人機(jī)的效用。

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

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

4 結(jié)束語

本文基于無人機(jī)對配網(wǎng)線路進(jìn)行自主巡檢的場景，在考慮無人機(jī)續(xù)航能力的前提下，構(gòu)建了以巡檢收益最大化為目標(biāo)的OP模型，并首次將桿塔的巡檢間隔時(shí)間作為權(quán)重，來優(yōu)化無人機(jī)自主巡檢的路徑。在傳統(tǒng)GA的基礎(chǔ)上，引入了SA算法的Metropolis準(zhǔn)則，以提升遺傳算法的局部搜索能力，仿真實(shí)驗(yàn)表明，IGA可以求得大部分經(jīng)典OP基準(zhǔn)實(shí)例數(shù)據(jù)集的最優(yōu)解。IGA還可以應(yīng)用于無人機(jī)自主巡檢的實(shí)際場景中，并可以在合理的運(yùn)行時(shí)間內(nèi)求得較優(yōu)的無人機(jī)自主巡檢方案。在未來的研究中，將關(guān)注多無人機(jī)協(xié)同進(jìn)行自主巡檢的場景，同時(shí)，除了桿塔的巡檢任務(wù)，還會關(guān)注桿塔之間線路通道的巡檢任務(wù)。