張永濤，李 博，張 甲，劉 濤，豆貝貝

（國(guó)網(wǎng)河南省電力公司周口供電公司，河南 周口 466000）

0 引言

經(jīng)過多年的技術(shù)革新和換代，現(xiàn)有變電站巡檢機(jī)器人搭載可見光相機(jī)、紅外熱像儀等傳感檢測(cè)設(shè)備，可實(shí)現(xiàn)站內(nèi)設(shè)備外觀檢測(cè)、開關(guān)位置觀測(cè)、表計(jì)讀數(shù)、紅外測(cè)溫以及異常狀態(tài)告警、聲音視頻采集等功能，已經(jīng)發(fā)展成為融合視覺模式識(shí)別、導(dǎo)航及路徑規(guī)劃、無線傳輸控制及自主充電等眾多技術(shù)于一體的智能型系統(tǒng)［1］。

巡檢機(jī)器人除了用于變電站日常巡視外，還可以在高溫、冰雪、雷暴、臺(tái)風(fēng)等天氣條件下進(jìn)行巡檢；在設(shè)備檢修投運(yùn)后、新設(shè)備24 h 試運(yùn)行期、系統(tǒng)過負(fù)荷以及特殊保供電時(shí)期，對(duì)某區(qū)域的設(shè)備進(jìn)行反復(fù)巡檢；還可以實(shí)現(xiàn)遠(yuǎn)方狀態(tài)識(shí)別、遠(yuǎn)方異常確認(rèn)、缺陷定點(diǎn)跟蹤等一系列功能［2］。220 kV 及以上變電站占地面積大，設(shè)備分布廣、數(shù)量多，使用巡檢機(jī)器人的優(yōu)勢(shì)更加明顯。與人工巡檢相比，機(jī)器人巡檢可以有效提高巡檢效率和覆蓋面，降低惡劣天氣下巡視的安全風(fēng)險(xiǎn)，巡檢數(shù)據(jù)記錄全面、連續(xù)，有助于后續(xù)分析［3］。機(jī)器人巡檢是智能和無人值守巡檢技術(shù)的發(fā)展方向，具有廣闊的發(fā)展空間和應(yīng)用前景［4］。

實(shí)際應(yīng)用過程中，部分巡檢機(jī)器人的行駛路線并非為最優(yōu)路線，導(dǎo)致巡檢過程不夠高效［5］?？紤]到電池續(xù)航能力和行駛速度的限制，為了提高巡檢機(jī)器人工作效率，應(yīng)該對(duì)其巡檢路線進(jìn)行優(yōu)化。目前文獻(xiàn)中報(bào)道的優(yōu)化方法有3 類：

1）采用智能算法對(duì)巡視路線進(jìn)行優(yōu)化。文獻(xiàn)［6］采用Hopfield 神經(jīng)網(wǎng)絡(luò)算法對(duì)巡檢機(jī)器人巡視路線進(jìn)行優(yōu)化，將巡視點(diǎn)與網(wǎng)絡(luò)神經(jīng)元相對(duì)應(yīng)，最優(yōu)路徑與網(wǎng)絡(luò)的能量函數(shù)對(duì)應(yīng)，得到正常巡視、特殊巡視下巡檢路線優(yōu)化圖。文獻(xiàn)［7］將變電站巡視問題轉(zhuǎn)化為對(duì)關(guān)鍵巡視點(diǎn)的遍歷問題，采用蟻群算法對(duì)巡視路徑進(jìn)行優(yōu)化，得到較好的可行解。文獻(xiàn)［8］基于遺傳算法的改進(jìn)蟻群算法對(duì)巡視路線圖進(jìn)行優(yōu)化，對(duì)于異常路線，采用深度優(yōu)先搜索算法，進(jìn)行巡檢機(jī)器人局部路徑規(guī)劃。

2）通過相關(guān)算法獲取任意2 個(gè)巡視點(diǎn)之間的最短距離，并將所求距離存入解集合供下一步使用；通過相關(guān)算法（煙花算法、蟻群算法、遺傳算法、模擬退火算法等）對(duì)前期解集合中的解進(jìn)行組合，得到最短巡檢路線的巡視點(diǎn)順序［9-10］。文獻(xiàn)［11］將全局最優(yōu)路徑規(guī)劃分為兩部分，分別為求解任意2 個(gè)巡視點(diǎn)之間的最短路徑以及求解使得總路徑最短的巡視點(diǎn)最優(yōu)化排列組合。將改進(jìn)Dijkstra算法與模擬退火算法相結(jié)合，應(yīng)用于變電站巡檢機(jī)器人路徑規(guī)劃。文獻(xiàn)［12］使用Floyd 算法對(duì)每對(duì)節(jié)點(diǎn)的最短距離進(jìn)行求解并存儲(chǔ)，利用遺傳算法求解得到最優(yōu)巡檢路線。

3）采用圖論中的Kruskal 算法、Prim 算法求得最小生成樹，對(duì)結(jié)果進(jìn)行調(diào)整以遍歷所有節(jié)點(diǎn)回到原點(diǎn)。圖的遍歷是按照某種規(guī)則訪問圖中各頂點(diǎn)且僅一次的操作，即將網(wǎng)絡(luò)結(jié)構(gòu)按某種規(guī)則線性化的過程。文獻(xiàn)［13］以貪心算法和局部搜索算法思想為主，結(jié)合啟發(fā)式思想算法對(duì)最小生成樹的Kruskal 算法進(jìn)行改進(jìn)，找到最短巡檢路線；文獻(xiàn)［14］利用改進(jìn)Prim 算法生成最小生成樹，設(shè)計(jì)遍歷算法遍歷最小生成樹，得到最短巡視路線。

上述研究主要是變電站巡檢機(jī)器人磁導(dǎo)航方式下的定點(diǎn)巡視路線優(yōu)化，隨著傳感器技術(shù)的發(fā)展和變電站機(jī)器人無軌化巡視的趨勢(shì)，目前變電站機(jī)器人多數(shù)采用激光定位導(dǎo)航系統(tǒng)，激光導(dǎo)航效率更高、更加智能靈活，可以做到智能避讓，維護(hù)成本低，改變路線只需要軟件重新設(shè)置，提高了被巡檢目標(biāo)的覆蓋率。針對(duì)巡檢機(jī)器人全站全巡的路線優(yōu)化問題未見相關(guān)研究。

考慮到巡檢機(jī)器人巡視路線優(yōu)化問題與圖論中“中國(guó)郵遞員問題”相似，對(duì)某變電站巡檢機(jī)器人巡視路線的拓?fù)浣Y(jié)構(gòu)進(jìn)行分析，構(gòu)造歐拉圖，得到最佳巡視路線圖，研究成果可為變電運(yùn)維人員及生產(chǎn)廠家提供參考。

1 任務(wù)規(guī)劃流程

根據(jù)變電站內(nèi)需要巡視設(shè)備的類型和項(xiàng)目，設(shè)定巡檢任務(wù)點(diǎn)，并根據(jù)不同的巡檢任務(wù)，規(guī)劃巡檢路線，任務(wù)規(guī)劃包括點(diǎn)位選擇、任務(wù)設(shè)置和巡檢路徑規(guī)劃3 個(gè)部分。

1.1 點(diǎn)位選擇

機(jī)器人巡檢點(diǎn)位的設(shè)定要求多角度、全方位覆蓋變電站范圍內(nèi)所有設(shè)備，做到不漏設(shè)備、不漏點(diǎn)。除了通過預(yù)先設(shè)定的分類選擇巡檢點(diǎn)位外，還可以通過不同字段和接線圖畫面進(jìn)行選擇。

1.2 任務(wù)設(shè)置

巡檢機(jī)器人任務(wù)設(shè)置要結(jié)合巡檢任務(wù)耗時(shí)和巡檢時(shí)間段合理安排。

巡檢任務(wù)耗時(shí)。單次巡檢時(shí)間不應(yīng)超過機(jī)器人的續(xù)航時(shí)間，2 個(gè)任務(wù)之間需要間隔充裕的時(shí)間進(jìn)行充電。

設(shè)定巡檢時(shí)間。例行巡檢應(yīng)安排在白天進(jìn)行，為提高機(jī)器人的運(yùn)行可靠性，建議減少正午高溫時(shí)開展巡檢任務(wù)；應(yīng)盡量在陰天、夜間負(fù)荷高峰時(shí)開展紅外測(cè)溫，以提高數(shù)據(jù)的準(zhǔn)確性［15］。

1.3 路徑規(guī)劃

巡檢機(jī)器人接收到用戶的巡檢任務(wù)后，生成1條以充電房位置為路線起點(diǎn)和終點(diǎn)，包含各個(gè)巡視點(diǎn)的最優(yōu)巡檢路線。

優(yōu)化的路線可以降低機(jī)器人巡檢時(shí)間，節(jié)省機(jī)器人電力消耗，提高機(jī)器人巡檢效率。根據(jù)巡視點(diǎn)的數(shù)量，路徑優(yōu)化方法可分為3 類：

1）單一巡視點(diǎn)。主要用于缺陷定點(diǎn)跟蹤、應(yīng)急事故特巡和應(yīng)急輔助操作。這類問題的目標(biāo)是求變電站內(nèi)兩點(diǎn)間的最短距離，常見優(yōu)化方法有Dijkstra算法、Floyd 算法等。

2）多個(gè)巡視位置。此類問題即求從充電房出發(fā)經(jīng)過各個(gè)巡視點(diǎn)且僅一次回到原點(diǎn)的最短距離，比較成熟的方法有兩種，一是根據(jù)巡視點(diǎn)的位置采用貪婪算法求得最小生成樹，設(shè)計(jì)遍歷算法求得最佳路線；二是求解任意兩個(gè)巡視點(diǎn)之間的最短距離并存儲(chǔ)，求解使得總路徑最短的巡視點(diǎn)最優(yōu)化排列組合。

3）全站全巡。該問題將點(diǎn)的優(yōu)化問題轉(zhuǎn)化為線的優(yōu)化問題，下文將重點(diǎn)介紹。

2 路徑規(guī)劃實(shí)現(xiàn)

巡檢機(jī)器人在變電站內(nèi)有專用的行駛路線，假設(shè)在巡視路線上的任何位置機(jī)器人都可以轉(zhuǎn)向或倒行。

變電站巡檢機(jī)器人路徑規(guī)劃建模遵循原則為：選擇充電室作為出發(fā)點(diǎn)和終點(diǎn)；每條巡視路線至少巡視1 次；巡視路線的總路程最小。

通常，1 個(gè)220 kV 變電站大概有3 000～4 000 個(gè)巡檢點(diǎn)位，1 個(gè)110 kV 變電站大概有800 個(gè)巡檢點(diǎn)位［2］。某220 kV 變電站巡視路線如圖1 所示［4］，每條線路上分布著數(shù)量不等的巡視點(diǎn)。

2.1 模型建立

圖1 某變電站巡檢機(jī)器人巡視路線

變電站巡視道路構(gòu)成一個(gè)非連通圖，其拓?fù)浣Y(jié)構(gòu)由5 個(gè)環(huán)形結(jié)構(gòu)和6 個(gè)樹枝形結(jié)構(gòu)組成，如圖2所示，線上的數(shù)字代表巡檢道路的長(zhǎng)度。圖中直線代表巡視路線，節(jié)點(diǎn)代表路線交叉、轉(zhuǎn)折處，或者是“斷頭路”的終點(diǎn)。

圖2 巡視路線拓?fù)浣Y(jié)構(gòu)

巡檢機(jī)器人遇到樹枝形結(jié)構(gòu)巡視路線時(shí)，最優(yōu)的方法總是先進(jìn)去再退出，為了簡(jiǎn)化計(jì)算，可以將這類分支就近收縮到相鄰節(jié)點(diǎn)上，此時(shí)，線路u—b 成為橋，連接上、下不同的2 個(gè)環(huán)形結(jié)構(gòu)，如圖3 所示。

2.2 模型求解

巡檢路線的優(yōu)化問題也轉(zhuǎn)化為“中國(guó)郵遞員問題”，即從一點(diǎn)出發(fā)，經(jīng)過所有路線，返回原點(diǎn)，求總路程最小的方案［16］。中國(guó)郵遞員問題的求解方法包括構(gòu)造歐拉圖和畫出歐拉環(huán)游。

圖3 巡視路線簡(jiǎn)化結(jié)果

2.2.1 構(gòu)造歐拉圖

根據(jù)歐拉定理，如果一個(gè)連通圖要一筆畫成（即從一點(diǎn)出發(fā)，經(jīng)過所有的邊且僅一次，又回到原點(diǎn)），則圖中每一個(gè)節(jié)點(diǎn)出發(fā)的邊數(shù)均為偶數(shù)。能夠滿足上述要求的圖稱為歐拉圖。

尋找邊數(shù)為奇數(shù)的節(jié)點(diǎn)，并進(jìn)行兩兩配對(duì)，增加重復(fù)邊，文獻(xiàn)中介紹的常見配對(duì)方案包括3 種［17-18］。方案Ⅰ是尋找距離最近的兩點(diǎn)進(jìn)行連接，如果重復(fù)邊小于所在回路權(quán)值和的一半，將重復(fù)邊保留下來，剩下的節(jié)點(diǎn)繼續(xù)配對(duì)；方案Ⅱ是尋找距離最短的兩點(diǎn)進(jìn)行配對(duì)，并去掉上述節(jié)點(diǎn)的關(guān)聯(lián)邊，剩余節(jié)點(diǎn)按照上述方法進(jìn)行配對(duì)；方案Ⅲ是求解所有奇度節(jié)點(diǎn)的最小生成樹，然后根據(jù)規(guī)則進(jìn)行調(diào)整。

配對(duì)成功與否驗(yàn)證方法為：將連通圖中的重復(fù)邊權(quán)值求和，如果小于總權(quán)值的一半則為可行解；如果連通圖中每個(gè)閉合圈重復(fù)邊的權(quán)值都小于該閉合圈總權(quán)值的一半，則為最優(yōu)解。本文采用方案Ⅰ進(jìn)行求解，方案Ⅱ、Ⅲ主要適用于奇度節(jié)點(diǎn)數(shù)量較多的情形，且存在一定的局限性。

對(duì)圖3（a）進(jìn)行分析，w、t 點(diǎn)的邊數(shù)為3，兩者需要配對(duì)，由于w—x—t 路線和大于w—s—t 路線，w、t兩點(diǎn)通過w—s—t進(jìn)行連接，如圖4（a）所示，配對(duì)后圖中各點(diǎn)的邊數(shù)均為偶數(shù)，重復(fù)路線和約占整個(gè)回路的22%，滿足要求。

對(duì)圖3（b）進(jìn)行分析，b、f、g、l 的邊數(shù)均為奇數(shù)，遵循重復(fù)邊最小原則，把奇數(shù)點(diǎn)的邊數(shù)改為偶數(shù)。其中，g、l 兩點(diǎn)配對(duì)，經(jīng)過g—h—l 路線權(quán)值最小，成功配對(duì)；同理，f、b 兩點(diǎn)通過f—a—b 進(jìn)行配對(duì)，如圖4（b）所示，重復(fù)路線權(quán)值和約占整個(gè)回路的28%，經(jīng)驗(yàn)證上述重復(fù)邊為最優(yōu)解。

2.2.2 畫出歐拉環(huán)游

給定一個(gè)歐拉圖，如果某條路線可以經(jīng)過所有的邊僅一次，則稱該回路為歐拉環(huán)游。通常采用Fleury 算法進(jìn)行求解，設(shè)G 為一無向歐拉圖，按照“除非別無選擇，否則不走回頭路，不過獨(dú)木橋”的原則，求其歐拉回路的步驟為：

1）v 代表點(diǎn)，e 代表線，任取G 中一頂點(diǎn)v0，令P0=v0；

2）假設(shè)沿Pi=v0e1v1e2v2…eivi走到頂點(diǎn)vi，按下述方法從E（G）-｛e1，e2，…，ei｝中選ei+1：

a）ei+1與vi相關(guān)聯(lián)；

b）除非無別的邊可供選擇，否則ei+1不應(yīng)該是Gi=G-｛e1，e2，…，ei｝中的橋。

3）當(dāng)2）不能再進(jìn)行時(shí)算法停止。

求得的歐拉回路如圖4 所示，圖中各節(jié)點(diǎn)排列順 序 為u—z—y—w—s—t—x—w—s—u 與a—f—e—i—j—k—l—h—g—h—l—m—c—b—g—f—a—b—a，各個(gè)連通圖的歐拉回路不止一條。

圖4 路徑優(yōu)化結(jié)果

2.2.3 優(yōu)化結(jié)果分析

變電站在規(guī)劃階段應(yīng)把巡檢機(jī)器人巡檢工作考慮在內(nèi)，設(shè)備的選擇與安裝應(yīng)減少巡視盲區(qū)，安措圍欄樁的設(shè)置應(yīng)不影響非檢修間隔的巡檢工作，巡檢路線盡量采用迂回方式，減少斷頭路，以提高機(jī)器人的巡檢效率。對(duì)原巡檢道路進(jìn)行改造，采用奇偶點(diǎn)圖上作業(yè)法對(duì)度為奇數(shù)的節(jié)點(diǎn)進(jìn)行配對(duì)，新的拓?fù)浣Y(jié)構(gòu)如圖5 所示，線上的數(shù)字代表新鋪設(shè)道路的長(zhǎng)度。

圖5 巡檢道路改造后的拓?fù)浣Y(jié)構(gòu)

巡檢道路改造前，巡檢機(jī)器人巡視路線為a—f—e—d—e—i—n—i—j—o—j—k—p—k—l—m—c—b—g—h—l—h—g—f—g—b—r—q—r—u—v—u—z—y—w—s—t—x—w—x—t—u—r—b—a，路線總長(zhǎng)度430 m。對(duì)斷頭路進(jìn)行改造后，巡視路線為a—d—e—f—e—i—j—i—n—o—j—k—p—k—l—h—g—h—l—m—c—b—g—f—a—q—r—q—s—w—s—t—x—w—y—z—u—t—u—v—u—r—b—a，路線總長(zhǎng)度384 m，與優(yōu)化前減少10.7%，證明了算法的有效性。

2.3 多巡檢機(jī)器人協(xié)同作業(yè)

多個(gè)巡檢機(jī)器人配合作業(yè)，要結(jié)合設(shè)備區(qū)的位置、巡檢道路的設(shè)置，合理選擇充電房的位置，以提高巡視效率。按照工作范圍進(jìn)行分區(qū)，分區(qū)方法為［19］：

1）按照線路分割。把一個(gè)作業(yè)區(qū)分成若干段邊不重復(fù)的子線路，每一段線路由一個(gè)巡檢機(jī)器人進(jìn)行巡視，線路分割如圖6 所示。首先，從充電房到子線路的起點(diǎn)，將該路線上的設(shè)備巡視完成后到達(dá)終點(diǎn)，最后從終點(diǎn)返回充電房。從充電房到達(dá)巡視路線的過程中，巡檢機(jī)器人不進(jìn)行巡視任務(wù)。

2）按照回路分割。把回路切割成若干段邊不重復(fù)的子回路，將子回路距離充電房最近的點(diǎn)與充電房進(jìn)行連接，如圖7 所示，該方案適合回路較多且界限清晰的情形。模型中線路u—b 連接兩個(gè)連通圖，適用于回路分割。

圖6 線路分割

圖7 回路分割

4 結(jié)語

通過對(duì)某220 kV 變電站巡檢機(jī)器人巡視路線的拓?fù)浣Y(jié)構(gòu)進(jìn)行改造，運(yùn)用奇偶點(diǎn)圖上作業(yè)法，得到最佳巡檢路線。研究成果可用于變電站內(nèi)設(shè)備檢修時(shí)巡檢路線的規(guī)劃、新建變電站巡檢道路的設(shè)計(jì)、變電站舊巡檢道路的改造等。當(dāng)變電站內(nèi)“田形”路線較多時(shí)，奇數(shù)節(jié)點(diǎn)的配對(duì)以及配對(duì)后的驗(yàn)證問題需要進(jìn)一步研究。