對(duì)電網(wǎng)巡檢多無(wú)人機(jī)進(jìn)行預(yù)定位和路由的研究*

鄒 林

（南方電網(wǎng)科學(xué)研究院有限責(zé)任公司 廣州 510535）

1 引言

通過高效率的電網(wǎng)巡檢降低電網(wǎng)潛在風(fēng)險(xiǎn)并評(píng)估線路中斷恢復(fù)時(shí)間可以將損失和潛在風(fēng)險(xiǎn)降到最低，是確保電力供應(yīng)可靠性的一個(gè)重要因素［1］。然而，由于電網(wǎng)巡檢和損失評(píng)估環(huán)境是十分危險(xiǎn)的，因此依靠傳統(tǒng)的人工巡檢和風(fēng)險(xiǎn)評(píng)估，很難做到按時(shí)完成電力基礎(chǔ)設(shè)施損失評(píng)估以及不延誤預(yù)期維修進(jìn)度，因此高效率的電網(wǎng)設(shè)計(jì)、防護(hù)和損失評(píng)估研究已成為一種發(fā)展趨勢(shì)。隨著無(wú)人機(jī)技術(shù)的發(fā)展，采用無(wú)人機(jī)等自主系統(tǒng)在保證檢查人員的安全的前提下高效率電網(wǎng)巡檢已經(jīng)成為電力公司的一個(gè)成本效益較高的選擇。實(shí)踐證明，利用無(wú)人機(jī)所搭載的熱紅外攝像機(jī)、CCTV 攝像機(jī)和GPS 對(duì)電網(wǎng)設(shè)施進(jìn)行近距離掃描，可以向地面控制中心發(fā)送準(zhǔn)確的設(shè)備運(yùn)行信息，評(píng)估電網(wǎng)設(shè)備的潛在風(fēng)險(xiǎn)，設(shè)計(jì)高效率的運(yùn)維計(jì)劃［2～3］。影響無(wú)人機(jī)巡檢效果的一個(gè)主要外部因素時(shí)天氣，惡劣天氣不但影響無(wú)人機(jī)的巡檢效果，還有可能導(dǎo)致無(wú)人機(jī)故障造成財(cái)產(chǎn)損失［4］。為此，本文在將多無(wú)人機(jī)應(yīng)用于電網(wǎng)線路和關(guān)鍵目標(biāo)設(shè)施的巡檢的基礎(chǔ)上，提出了一種考慮天氣信息不確定性的多無(wú)人機(jī)覆蓋目標(biāo)節(jié)點(diǎn)和線路的最優(yōu)預(yù)定位位置和路徑的數(shù)學(xué)模型，力圖找到最小成本的多無(wú)人機(jī)的巡檢目標(biāo)節(jié)點(diǎn)和巡檢路徑。

2 問題概述

多無(wú)人機(jī)巡檢問題的目標(biāo)是為提高電網(wǎng)巡檢效率，提供無(wú)人機(jī)最佳巡檢目標(biāo)節(jié)點(diǎn)和最優(yōu)飛行線路。所生成的節(jié)點(diǎn)和路線要保證無(wú)人機(jī)能完成所有指定的目標(biāo)節(jié)點(diǎn)和線路的節(jié)點(diǎn)，同時(shí)最小化巡檢時(shí)間和無(wú)人機(jī)群的總飛行成本［5］。本文所設(shè)計(jì)的多無(wú)人機(jī)巡檢模型分為兩個(gè)階段：第一階段（MUAV-ph1）預(yù)定位和第二階段（MUAV-ph2）無(wú)人機(jī)巡檢路由確定。

第一階段從確定多無(wú)人機(jī)巡檢節(jié)點(diǎn)的位置開始。對(duì)巡檢位置確定要求為能夠覆蓋所有巡檢目標(biāo)設(shè)施，同時(shí)最小化無(wú)人機(jī)的位置數(shù)量和計(jì)算成本。在該過程中，需要充分考慮天氣情況對(duì)無(wú)人機(jī)巡檢位置確定的影響。如果只有在獲得準(zhǔn)確的天氣信息后才能確定無(wú)人機(jī)的巡檢位置，那么就會(huì)沒有充分的時(shí)間確定無(wú)人機(jī)巡檢位置［6］。因此，本文基于隨機(jī)天氣影響值預(yù)定位無(wú)人機(jī)的巡檢位置，然后在第二階段依據(jù)相對(duì)精確的天氣信息對(duì)巡檢位置進(jìn)行調(diào)整，并生成無(wú)人機(jī)的巡檢線路。

第二階段是依據(jù)無(wú)人機(jī)的數(shù)量、類型和預(yù)定位數(shù)據(jù)，生成最優(yōu)無(wú)人機(jī)路徑，力求在最短飛行時(shí)間內(nèi)完成電網(wǎng)巡檢。同時(shí)依據(jù)更新的天氣信息對(duì)預(yù)定位數(shù)據(jù)進(jìn)行調(diào)整。為了充分保證巡檢質(zhì)量，線路制定時(shí)可以在每個(gè)預(yù)定位位置上部署多架無(wú)人機(jī)進(jìn)行巡檢。此外，所提出的路由模型考慮了無(wú)人機(jī)飛行成本和巡檢時(shí)間。

飛行路徑規(guī)劃遵循以下四個(gè)要求：1）無(wú)人機(jī)可直接從選定節(jié)點(diǎn)飛越到任何可訪問的目標(biāo)節(jié)點(diǎn)；2）每個(gè)目標(biāo)節(jié)點(diǎn)和線路可以僅被巡檢一次，但是可以多次飛越；3）無(wú)人機(jī)必須返回到原始位置或另一個(gè)選定節(jié)點(diǎn)；4）每個(gè)無(wú)人機(jī)每次只執(zhí)行單個(gè)目標(biāo)的巡檢任務(wù)［7～8］。

圖1 描述了提出的MUAV 問題的兩階段優(yōu)化的流程圖。第一階段的目標(biāo)是確定無(wú)人機(jī)預(yù)定位位置。輸入數(shù)據(jù)包括無(wú)人機(jī)最大飛行時(shí)間和隨機(jī)的天氣影響尺度。第二階段問題生成用于巡檢結(jié)果的無(wú)人機(jī)路徑。一旦無(wú)人機(jī)位置信息被提供給MUAV-ph2，基于數(shù)量檢測(cè)的預(yù)處理方法消除考慮無(wú)人機(jī)飛行能力的不可行線路，并計(jì)算目標(biāo)覆蓋約束的上限值。最后應(yīng)用拉格朗日啟發(fā)式［9］和次梯度法［10］求得MUAV-ph2最優(yōu)路線方案。

圖1 MUAV模型優(yōu)化流程圖

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

被建模在目標(biāo)電力網(wǎng)絡(luò)G（V，E）上的多UAV巡檢方案數(shù)據(jù)集是由兩個(gè)類型的節(jié)點(diǎn)和三個(gè)類型的路徑集合組成：目標(biāo)節(jié)點(diǎn)數(shù)據(jù)集發(fā)V1、UAV 預(yù)定位節(jié)點(diǎn)數(shù)據(jù)集V2、初始路徑集E1、中間路徑集E2和返回路徑集E3。無(wú)人機(jī)位置集V2分為兩個(gè)子集：與受極端天氣影響區(qū)域中的電力線路連接的一組節(jié)點(diǎn)V21和所有其他節(jié)點(diǎn)V22。如圖2 所示，電力網(wǎng)絡(luò)有兩個(gè)目標(biāo)節(jié)點(diǎn)n1、n2∈V1，四個(gè)無(wú)人機(jī)預(yù)先定位候選點(diǎn)n3、n4、n5和n6，其中n3，n4∈V21，n5，n6∈V22。

圖2 電力網(wǎng)絡(luò)的說(shuō)明性示例

3.1 無(wú)人機(jī)預(yù)定位

無(wú)人機(jī)預(yù)定位模型確定要建立哪個(gè)UAV 預(yù)先定位位置，以便評(píng)估所有目標(biāo)節(jié)點(diǎn)和不確定性線路。 本文將模型定義為兩階段隨機(jī)程序MUAV-ph1 和MUAV-ph1。其 中MUAV-ph1 為預(yù)定位，MUAV-ph2為巡檢路線生成。由于天氣影響尺度具有相對(duì)的隨機(jī)性，因此本文通過等價(jià)公式來(lái)確定近似的確定性天氣影響值，并通過近似天氣場(chǎng)景ω1…ωN來(lái)求解預(yù)定位位置模型。預(yù)定位模型的數(shù)學(xué)公式為

式（1）是預(yù)定位位置設(shè)置成本最小化的目標(biāo)函數(shù)。式（1）中的第一項(xiàng)是無(wú)人機(jī)位置設(shè)置成本的總和，式（1）中的第二項(xiàng)是考慮用于預(yù)定位的所有天氣場(chǎng)景的近似影響平均值。約束條件式（2）表示確保目標(biāo)線路必須被至少一個(gè)無(wú)人機(jī)預(yù)定位位置覆蓋。式（2）中ai，j，ω值是基于以下兩個(gè)原則確定：首先，每個(gè)電力線路必須由指定的無(wú)人機(jī)預(yù)定位置覆蓋；其次，預(yù)定位置必須能夠承受隨機(jī)極端天氣的影響［11～12］。如算法1 所述，無(wú)人機(jī)預(yù)定位位置必須滿足以下兩個(gè)條件：1）UAV 至少覆蓋至少一條電力線路；2）預(yù)定位位置之間距離不能超過無(wú)人機(jī)最大飛行距離。如果滿足兩個(gè)條件，則ai，j，ω取值1，否則取值0。

算法1：確定ai，j，ω的值

式（3）表明任何選定的巡檢節(jié)點(diǎn)必須在兩階段隨機(jī)程序中完成設(shè)置。式（4）給出了預(yù)定位巡檢目標(biāo)節(jié)點(diǎn)的最大閾值。

在通過MUAV-ph1完成無(wú)人機(jī)預(yù)定位后，剩余未選擇的節(jié)點(diǎn)被重新標(biāo)記為虛擬節(jié)點(diǎn)，然后在MUAV-ph2 中再次輸入用于無(wú)人機(jī)路徑生成。如圖2 所示，e4是需要進(jìn)行巡檢和損壞評(píng)估的目標(biāo)線路。假設(shè)在MUAV-ph1 中沒有選擇節(jié)點(diǎn)n4作為預(yù)定位位置。然后，在MUAV-ph2 中，n4將被從網(wǎng)絡(luò)中排除。但是，在網(wǎng)絡(luò)中沒有節(jié)點(diǎn)n4就不能表示巡檢線路e4。為了解決這個(gè)問題，在MUAV-ph1 中將沒有選擇的元素i ∈(V21-V′ )標(biāo)記為MUAV-ph2中的虛擬節(jié)點(diǎn)。修改的目標(biāo)節(jié)點(diǎn)集的定義是J=V1∪(V21-V′)。

3.2 無(wú)人機(jī)巡檢路徑生成

基于階段1 所完成的預(yù)定位，階段2 生成的目標(biāo)電力網(wǎng)絡(luò)的最佳巡檢路徑，以便最小化UAV 飛行成本。

無(wú)人機(jī)k∈K 開始和結(jié)束從/到位置的飛行i∈V'通過橫向線路的直接損壞評(píng)估E。

在MUAV-ph2 中，目標(biāo)函數(shù)（5）是多UAV 的最小化飛行成本（），其與參與巡檢的UAV 的數(shù)量和巡檢完成時(shí)間（FT）成比例。式（6）表示用于巡檢的無(wú)人機(jī)數(shù)量閾值。式（7）確保每個(gè)UAV 巡檢路線至少覆蓋電力網(wǎng)絡(luò)中的一個(gè)目標(biāo)節(jié)點(diǎn)。式（8）表示離開任何目標(biāo)節(jié)點(diǎn)的UAV 的總數(shù)量與返回的UAV 的數(shù)量相同，式（9）表示接入任何巡檢位置的UAV 的總數(shù)量與離開的UAV 的數(shù)量相同。式（10）表示任何通過從i 到j(luò) 或相反的目標(biāo)線路E2至少被巡檢一次。式（11）確保每個(gè)無(wú)人機(jī)飛行路徑（包括飛行時(shí)間和特定節(jié)點(diǎn)上的檢查）必須受其最大飛行時(shí)間的約束。式（12）是通過UAV 計(jì)算最小任務(wù)完成時(shí)間。式（13）用于確保無(wú)人機(jī)從起點(diǎn)到目的地的完整飛行路徑。

3.3 模型求解優(yōu)化

因?yàn)樗岢龅哪Ｐ途哂卸嗦窂降目蚣埽虼吮疚牟捎靡韵滤姆N方法來(lái)提高M(jìn)UAV-ph2 的計(jì)算性能。第一種方法是通過分析電網(wǎng)中的約束條件和無(wú)人機(jī)的數(shù)量來(lái)簡(jiǎn)化飛行時(shí)間約束。第二種方法是生成目標(biāo)覆蓋約束的上限。第三種方法是提出一種預(yù)處理算法，在給定的技術(shù)規(guī)范下確定考慮飛行可行性的二元變量的值，并為兩個(gè)修正約束生成系數(shù)。最后一種方法是提出了一種拉格朗日松弛方法，得到了一個(gè)高質(zhì)量的MUAV-ph2目標(biāo)函數(shù)的下限值［13～14］。

1）重新制定飛行時(shí)間約束

如果任何無(wú)人機(jī)未被分配用于電網(wǎng)巡檢，則無(wú)需檢查無(wú)人機(jī)是否能夠通過式（11）的約束條件在最大飛行時(shí)間內(nèi)完成飛行。在這種情況下，式（11）的左側(cè)是0，但右側(cè)保持恒定值。因此，在式（14）中將Bk替換為Bkhk。變量hk表示UAV k是否被指定用于電網(wǎng)巡檢和損傷評(píng)估。

2）目標(biāo)覆蓋約束上限

此優(yōu)化方法旨在為約束條件式（7）提供上限閾值。根據(jù)式（7），目標(biāo)節(jié)點(diǎn)必須由至少一架無(wú)人機(jī)評(píng)估，但是沒有對(duì)飛越該節(jié)點(diǎn)的無(wú)人機(jī)的數(shù)量設(shè)置上限。如果強(qiáng)加一個(gè)更嚴(yán)格的上限，它可以幫助減少解決方案空間，因此可以提高收斂性。

如圖3 所示，節(jié)點(diǎn)6 在四個(gè)獨(dú)立的線路上與C1、C2、C3 和C4 連 接。UAV 想 要 在 節(jié) 點(diǎn)6 上 飛行。如果每個(gè)線路被多個(gè)獨(dú)立的UAV 朝向節(jié)點(diǎn)6掃描并且流入任何UAV，則總共四個(gè)UAV 將在節(jié)點(diǎn)6 上飛行。因此，式（7）可以通過限制節(jié)點(diǎn)j 上允許的最大無(wú)人機(jī)的數(shù)量。作為式（15）中所示的上限約束。上限由算法2所計(jì)算。

圖3 通過節(jié)點(diǎn)的最大UAV數(shù)量的說(shuō)明性示例

3）飛行可行性檢測(cè)的預(yù)處理

為了加快MUAV-ph2模型的求解速度，本文提出了一種有效的預(yù)處理算法。首先，如果飛行兩個(gè)節(jié)點(diǎn)之間的距離大于無(wú)人機(jī)的最大飛行時(shí)間Bk，那么變量xi，j，k將固定為0。其次，式（15）給出了經(jīng)過節(jié)點(diǎn)j 無(wú)人機(jī)的最大數(shù)量。算法2給出了上述預(yù)處理過程。

算法2：基于數(shù)量檢測(cè)的預(yù)處理

4）下限生成的拉格朗日對(duì)偶算法

利用拉格朗日對(duì)偶方法可以推導(dǎo)出MUAV-ph2 目標(biāo)函數(shù)的下限值。在MUAV-ph2 模型中，約束條件式（13）是指數(shù)型的，計(jì)算資源會(huì)隨著無(wú)人機(jī)數(shù)量和目標(biāo)節(jié)點(diǎn)數(shù)量的增多而快速增大［15］。因此，需要放寬式（13）的約束，并將其添加到目標(biāo)函數(shù)（5）中：

通過求解拉格朗日對(duì)偶函數(shù)L( λ )能夠得出MUAV-ph2模型的目標(biāo)函數(shù)下限值。在式（16）中，迭代修改拉格朗日乘數(shù)，通過使用算法3 所示次梯度方法找到式（16）的最小值。

算法3：次梯度方法

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

MUAV 模型由兩個(gè)階段組成：MUAV-ph1（預(yù)定位）和MUAV-ph2（路由決策）。在第一階段中，本文利用模擬的隨機(jī)數(shù)據(jù)來(lái)驗(yàn)證MUAV-ph1 與確定性模型的解在極端天氣條件下能夠正常運(yùn)行。為模擬MUAV-ph1中的不穩(wěn)定天氣條件，極端天氣的影響尺度值wxi，j，ω由wxi，j，ω～U( )0.4，0.9 隨機(jī)生成。MUAV-ph2 在如圖4 所示的真實(shí)電網(wǎng)拓?fù)渲羞M(jìn)行有效性測(cè)試。

圖4 實(shí)驗(yàn)電網(wǎng)拓?fù)鋱D

所有實(shí)驗(yàn)均在配備Intel Xeon 3.00GHz 處理器和364GB RAM 的Linux 服務(wù)器上運(yùn)行。CPLEX 12.6用作混合整數(shù)規(guī)劃（MIP）求解器［16］。本實(shí)驗(yàn)利用CPLEX 的解池特性，快速生成一組可行的解候選（即第一階段中的無(wú)人機(jī)預(yù)先定位位置和第二階段中的無(wú)人機(jī)路徑），以找到接近最優(yōu)的解。兩個(gè)算法終止標(biāo)準(zhǔn)是兩個(gè)半小時(shí)CPU 運(yùn)行時(shí)間限制。實(shí)驗(yàn)所使用的無(wú)人機(jī)有兩種型號(hào)，每種型號(hào)無(wú)人機(jī)的飛行能力和飛行成本如表1所示。

表1 無(wú)人機(jī)參數(shù)

本實(shí)驗(yàn)使用隨機(jī)數(shù)評(píng)估隨機(jī)MUAV-ph1 模型。在隨機(jī)數(shù)的計(jì)算中，對(duì)MUAV-ph1模型的目標(biāo)值與50 種情形下的目標(biāo)值及其確定性對(duì)等體的期望值集在10 個(gè)不同問題規(guī)模的問題實(shí)例中進(jìn)行了比較。比較結(jié)果如表2 所示，其中隨機(jī)數(shù)是通過從EVdet中減去EVsto獲得的?？紤]到MUAV-ph1 是最小化問題，正隨機(jī)數(shù)值支持隨機(jī)假設(shè)下的MUAV-ph1 在本實(shí)驗(yàn)中呈現(xiàn)的所有結(jié)果下都優(yōu)于確定性模型。此外，實(shí)驗(yàn)中所有測(cè)試用例都在1min內(nèi)完成計(jì)算的。

表2 MUAV-ph1的實(shí)驗(yàn)結(jié)果

通過求解MUAV-ph1，得到了無(wú)人機(jī)的預(yù)先定位位置，同時(shí)也確定了目標(biāo)區(qū)域包括哪些總線和電力線，如圖5 所示。該圖中由9 個(gè)無(wú)人機(jī)預(yù)定位位置、30 條總線和33 條在目標(biāo)區(qū)域內(nèi)以灰色陰影顯示的電力線組成。圖中還包括9 個(gè)虛擬節(jié)點(diǎn)用于UAV路徑生成。

表3 給出了MUAV-ph2 解決方案集，其中C2、C3 和C4 是覆蓋目標(biāo)區(qū)域的預(yù)定位位置的最小數(shù)量。由于某些目標(biāo)節(jié)點(diǎn)（例如C1→1，C5→02，C6→23 和C7→24）與選定的目標(biāo)節(jié)點(diǎn)沒有連接，因此未選擇的無(wú)人機(jī)預(yù)定位候選節(jié)點(diǎn)被包括用于路徑生成目的的虛擬節(jié)點(diǎn)。掃描目標(biāo)區(qū)域需要六個(gè)型號(hào)Ⅰ無(wú)人機(jī)和三個(gè)型號(hào)Ⅱ無(wú)人機(jī)：C2 處有兩個(gè)無(wú)人機(jī)，C3處有一個(gè)無(wú)人機(jī)，中心4處有六個(gè)無(wú)人機(jī)。

表3 無(wú)人機(jī)巡檢路徑和任務(wù)分配

通過改變無(wú)人機(jī)單次最長(zhǎng)飛行時(shí)間對(duì)MUAV-ph1和MUAV-ph2計(jì)算結(jié)果的影響，進(jìn)行了靈敏度分析。從表4 觀察到，隨著最長(zhǎng)飛行時(shí)間的增加，巡檢的目標(biāo)節(jié)點(diǎn)的數(shù)量逐漸減少。例如在＃4中，UAV 單次飛行時(shí)間達(dá)到10min，則在巡檢過程中可以僅從單個(gè)目標(biāo)節(jié)點(diǎn)覆蓋所有目標(biāo)區(qū)域。這樣導(dǎo)致無(wú)人機(jī)預(yù)定位的計(jì)算成本被最小化，但是增加了無(wú)人機(jī)巡檢的飛行成本。表4 中，為預(yù)定位的計(jì)算成本。

表4 不同單次最長(zhǎng)飛行時(shí)間的預(yù)定位和路由方案

對(duì)表4 中預(yù)定位和路由方案進(jìn)行分析可知，方案#2 具有最少的無(wú)人機(jī)飛行成本；方案#4 具有最經(jīng)濟(jì)的預(yù)定位成本，但是具有最長(zhǎng)的巡檢時(shí)間。

5 結(jié)語(yǔ)

本文提出了一種利用多無(wú)人機(jī)進(jìn)行電網(wǎng)損失評(píng)估的兩階段優(yōu)化數(shù)學(xué)模型。第一階段的數(shù)學(xué)模型在充分考慮到不確定天氣對(duì)無(wú)人機(jī)巡檢目標(biāo)確定的影響，以最小化的計(jì)算成本預(yù)定位盡量能夠覆蓋巡檢區(qū)域的巡檢目標(biāo)節(jié)點(diǎn)。基于第一階段預(yù)定位結(jié)果，第二階段模型按照預(yù)設(shè)的無(wú)人機(jī)數(shù)量進(jìn)一步生成無(wú)人機(jī)巡檢路徑來(lái)完成電網(wǎng)巡檢。實(shí)驗(yàn)表明，給數(shù)學(xué)模型具有較好的計(jì)算效率，能夠生成符合要求的多無(wú)人機(jī)巡檢方案。