基于郵遞員問題的變電站巡視路線探究

彭光超

(南方電網(wǎng)深圳供電局有限公司，深圳，518000)

0 引言

目前，我國變電站巡視工作是由變電運行人員完成，主要記錄在變電站巡視記錄本或PDA 等電子設備中，而巡視路線往往依靠工作經(jīng)驗來制定。隨著電網(wǎng)規(guī)模的日益壯大，按照以往的經(jīng)驗制定設備巡視路線往往會造成多走回頭路的現(xiàn)象，造成資源浪費。因此，對變電站設備巡視路線制定進行新的研究顯得十分重要。目前我國變電運行巡視工作存在的問題主要有以下幾點：（1）運行人員缺少必要的知識儲備和衡量標準。我國變電站發(fā)展雖然比較迅速，但是相關的教育程度還不達標，尤其是早期的變電站工作人員，其知識水平參差不齊，同時缺少統(tǒng)一的巡視檢查標準。（2）巡視人員責任心不同。因為變電站的占地面積大，需要巡視的設備種類繁多而且數(shù)量眾多，再加上巡視人員的責任心不同，因此，實際工作中常會出現(xiàn)工作人員沒有到位、錯檢、漏檢等現(xiàn)象。（3）巡視的路徑規(guī)劃方法不科學。由于近年來國民經(jīng)濟的飛速增長，供電企業(yè)人員增長與電力系統(tǒng)的發(fā)展之間的矛盾日益突出；目前變電站巡視人員制定巡視路線都是憑借工作經(jīng)驗，沒有科學有效的判定依據(jù)，導致有些巡視路線不是最佳巡視路線。（4）巡視周期內重復性缺陷數(shù)量大。在某些地區(qū)，電力設備更新?lián)Q代較慢。設備經(jīng)過長期運行后使用壽命大大降低，設備缺陷率較高，且多為重復缺陷。

1 路徑規(guī)劃簡介

路徑規(guī)劃技術被廣泛應用于許多領域。在高科技領域的應用是：移動機器人技術；無人機規(guī)避障礙物飛行；防反彈攻擊等。在日常生活領域的應用主要有：以GIS 為指導的道路設計；車載GPS 系統(tǒng)中的路徑選擇；導游軟件中路線選擇；變電站或其他需要巡視作業(yè)的部門進行路徑規(guī)劃等。在管理決策領域的應用有：最短路、最大流問題，物流管理中的車輛路徑問題(Vehicle Routing Problems)。在通信技術中的應用有信號塔選址、網(wǎng)絡拓撲路線、路由等問題。

從環(huán)境信息性質不同的角度來說，可以將路徑規(guī)劃分成兩種：一種是全局規(guī)劃，它的基礎是先驗完整信息；另一種局部規(guī)劃，它側重傳感器實時感知的信息。動態(tài)路徑規(guī)劃一般按照以下三個步驟進行：1)環(huán)境建模。把已知的環(huán)境信息抽象后建立數(shù)學模型。環(huán)境模型建立好以后，計算機才能進行路徑規(guī)劃計算。通俗地說，就是將實際存在的物理空間抽象成數(shù)字信息，以使計算機可以進行處理。2)路徑搜索。路徑搜索依據(jù)優(yōu)化條件，應用路徑規(guī)劃的算法在所有路徑中尋找并產(chǎn)生一條最優(yōu)路徑。3)路徑平滑。通過環(huán)境建模、路徑搜索后得到的路徑僅是理論上的可行方案，在應用中需要考慮實際情況，再經(jīng)過處理、平滑等“深加工”，最后得出可行的路徑。但是在離散域的路徑規(guī)劃問題中是可以省略路徑平滑這一步驟的，前提是在環(huán)境建模和路徑搜索前已經(jīng)進行了了很好的路徑可行性分析。

路徑規(guī)劃的方法非常的多，不同的方法其優(yōu)缺點也不相同，不同的優(yōu)缺點也決定了各種方法的適用范圍。目前國際上通用的分類方法是從各種算法被發(fā)現(xiàn)的先后順序以及算法的基本原理來分類，按照此原則當前常用于各領域的路徑規(guī)劃算法分四種即傳統(tǒng)算法、圖形學方法、智能仿生學算法和其他算法。

2 郵遞員問題及奇偶點作業(yè)法

變電站巡視路線類似于圖論中的郵遞員問題，某郵遞員出發(fā)送信，要從郵局出發(fā)，而且至少通過一次轄區(qū)內的每一條街道，最后要回到出發(fā)的郵局，以這些條件為前提，郵遞員要怎樣選擇路線，才能保證走得路線最短？巡視人員工作時同樣是在一片區(qū)域內行走，這就需要在眾多路線中尋找最優(yōu)路線，在保證工作質量的同時尋求耗時最短的路線。郵遞員問題的求解方法是Fleury算法，將行走區(qū)域看成一個Euler 圖，求其Euler 環(huán)游；若該圖不是Euler 圖，則通過某些方法使其變換成Euler 圖進行求解；下面就應用管梅谷教授的奇偶點作業(yè)法簡要介紹求解過程。

使用奇偶點作業(yè)法是以下述定理為基礎的。

定理 設C 是一條經(jīng)過賦權連通圖G 的每條邊至少一次的回路，則C 是G 的最優(yōu)回路。當且僅當C 對應的Euler 圖滿足：

奇偶點作業(yè)法基本步驟：

1)按照一個方案找到圖中所有奇頂點（必為偶數(shù)個），然后進行兩兩配對直至得到的新圖中，沒有了奇頂點。

2)按照1 中的方法重復計算，直到得到的圖中重復邊總長度變短。

3)根據(jù)定理中的條件（2）反復執(zhí)行步驟2。

3 實例驗證

3.1 變電站實例

圖1 某變電站站內設備平面圖

某變電站有500kV、220kV、35kV 三個電壓等級，。500kV 變壓器有3 臺，500kV 輸電線路有4 回， 220kV 輸電線路有10 回，占地面積35000 平方米；其站內設備平面圖如圖1 所示。

3.2 變電站平面圖形

根據(jù)圖論理論，設每個區(qū)域內RFID 標簽為圖G 中的頂點，記為 V (G ) ，其中 v1=主控室定位點，v2=500kV 設備區(qū)域定位點，v3=#5 主變區(qū)域定位點，v4=35kV5M 區(qū)域定位點，v5=220kV 設備區(qū)域定位點，v6=#4 主變區(qū)域定位點，v7=#3 主變區(qū)域定位點，v8=35kV3M 區(qū)域定位點，v9=35kV4M 區(qū)域定位點，v10=站用電區(qū)域定位點。各設備區(qū)域間的道路記為圖G 中的邊，記為 E ( G )，即根據(jù)查閱圖紙資料，確定圖G 的每一條邊的權數(shù)(單位：米)如下：w12= 9，w23= 11，w34= 8，w45= 26，w59= 17，w69=10,w26=8,w25=19,w35=28,w13=14,w27=18,w7,10=22,w78=10,w89=9,w1,10=7。這樣就將變電站的平面圖抽象為無向圖G ，如圖2。

圖2

圖3

根據(jù)奇偶點作業(yè)法，首先判斷圖G 是否為Euler 圖。圖G中，頂點 v1, v2, v7,v9是奇度點。所以圖G 非歐拉圖。此時求解歐拉回路需要添加重復邊。給 v1,v2的一條鏈增加一條重復邊；給 v7,v9的一條鏈 v7, v8,v9，每條邊增加一條重復邊，且使得增加的重復邊權數(shù)和最小。由此得到圖3，此時圖3 中無奇點，圖3已是歐拉圖。

3.3 檢驗過程

對圖3 進行檢驗，計算已添加重復邊的每個圈的權數(shù)和與每個圈所含重復邊的權數(shù)和。如表1 所示。

表1 圖3 的檢驗表

從表1 可以看出，所有含有重復邊的圈所含重復邊的權數(shù)和都沒有超過本圈的權數(shù)和的一半。所以該方案是最優(yōu)方案。

3.4 求解過程

3.5 對比分析

通過上面的分析可以得出新的巡視路線，為了評價新制定的巡視路線的優(yōu)劣性，我們進行了兩次巡視。一次按照以往制定好的巡視路線Line1 進行巡視，一次按照新制定的巡視路線Line2進行巡視，將兩次巡視中人員走動的距離，消耗時間進行對比，對比結果如表2 所示。

表2 結果對比表

從表2 中可以看出，按照新的巡視路線Line2 進行巡視，可縮短走動距離87 米，節(jié)約時間33 分鐘。按照兩人巡視，一天一次巡視來計算，共可節(jié)約時間60 分鐘；在某些特殊情況下，譬如事故狀態(tài)，特殊保供電等情況下，變電站的巡視次數(shù)會大為增加，由此帶來的時間節(jié)約效果更加明顯。按照此方法制定的巡視路線會進一步提高人員的工作效率，也有利于緩解生產(chǎn)一線人員的工作壓力。

4 結語

本文通過分析我國變電站的巡視工作現(xiàn)狀，總結其存在的問題；簡要介紹了郵遞員問題及奇偶點作業(yè)法。最后以某變電站為實例，對其巡視路線進行研究，驗證了郵遞員問題在變電站巡視路線規(guī)劃問題中的應用，且節(jié)約效果明顯。本文通過應用管理科學、圖形學等學科知識，尋求變電站巡視最佳路線，希望對電力企業(yè)實現(xiàn)巡視工作的高質量和高效率有所幫助。

[1] 周俊，變電設備狀態(tài)檢修策略及應用研究[D]，保定，華北電力大學，2006.

[2] Edmonds J，Johonson E L.Matching，Euler tour and the Chinese postman[J].Mathematical Programming，1973,5:88-124.

[3] 管梅谷，奇偶點圖上作業(yè)法[J]，數(shù)學學報，1960，10（3）：263-266.

[4] 李儀光，何斌斌，羅杰等，深圳供電局輸變電設備狀態(tài)巡視策略的研究[J]，機電工程技術，2011,40(6)，71-73.

[5] 賀鵬，殷亞君，最短路徑算法淺析[J]，甘肅科技，2010(1)：42—43.

[6] 王興亮，變電站設備狀態(tài)巡視模式探討[J]，中國高新技術企業(yè)，2011,24：92-98