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

邢耀杰 李艷

摘 要：基于研究郵遞員問題的無向圖法，結合奇偶點作業(yè)法，本文解決了變電站巡視路線規(guī)劃問題。通過分析比較證實，本文的路徑規(guī)劃方法制定變電站巡視路線，在時間管理和人員安排方面優(yōu)勢明細。

關鍵詞：變電站巡視；路徑規(guī)劃；無向圖；奇偶點作業(yè)

在當前，變電站值班人員是巡視變電站站內設備的的主力軍，并將巡視結果錄入工作薄中，作業(yè)人員根據(jù)自己相關的技術經驗規(guī)劃巡視的路徑。但隨著我國綜合國力的不斷增強，電網(wǎng)規(guī)模及等級也在逐步擴大，人工經驗巡檢設備容易造成工作重復的現(xiàn)象，帶來人力和時間的浪費。因此研究并開發(fā)相對規(guī)范化的變電站設備巡視路線勢在必行。

1 路徑規(guī)劃

許多領域都應用了路徑規(guī)劃技術。按照環(huán)境特點，路徑規(guī)劃主要包括兩方面：一方面全局規(guī)劃路徑，主要是將環(huán)境特性作為先驗證的方法；另一方面是局部規(guī)劃，環(huán)境特性作為實時感知的因素。

完成動態(tài)路徑規(guī)劃主要步驟如下：（1）環(huán)境建模。用數(shù)字信息表征實際存在的物理空間，方便計算機處理，完成路徑規(guī)劃計算。（2）路徑搜索。依據(jù)本項目的優(yōu)化條件及要求列出所有可能的路徑方案，再應用路徑規(guī)劃的算法，找出一條最優(yōu)路徑。（3）路徑平滑。通過上述步驟（1）和步驟（2）后，取得的路徑規(guī)劃是在理論上可實現(xiàn)的，應用時還需要綜合考慮實際情況，再經過平滑等處理，獲得最終的可行方案。但是，若該路線是離散型的，且在步驟（1）和步驟（2）前已對路徑可實現(xiàn)性進行了全面解析，路徑平滑這一步驟是可以省略的。

2 郵遞員問題和奇偶點作業(yè)法（graphical method based on an odd-even-point approach，GMOEPA）

圖論中的郵遞員問題可以作為變電站巡視路線規(guī)劃問題的參考對象。郵遞員問題是：某郵遞員從郵局出發(fā)送信，且要求轄區(qū)內的每一條街道都至少通過一次，最后還需要回到出發(fā)的郵局，基于這些基本條件，郵遞員應該如何選擇送信路線，最后保證最短的送信路程？變電站巡視人員也是在一片區(qū)域內完成巡視工作，在滿足遍歷每個檢測設備的條件下，存在著眾多路線方案，這就需要從中尋找最優(yōu)路線，即在在保證工作質量的基礎上，獲得最短耗時路線方案。

郵遞員問題是用奇偶點作業(yè)法的求解的，將行走區(qū)域視為一個無向圖后，再求其無向環(huán)游；若該圖不能視為無向圖，則需要通過某些方法使其變換成無向圖再進行求解；下面就依據(jù)奇偶點作業(yè)法介紹求解過程。

使用GMOEPA是以下述定理為基礎的。

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

（1）在最優(yōu)回路C中G的每條邊出現(xiàn)率不得高于兩次。

（2）在最優(yōu)回路C中G的每條邊出現(xiàn)兩次的權之和應小于二分之一圈的總權。

GMOEPA的執(zhí)行過程如下：

過程一：在某一規(guī)劃路徑中，將線路中的奇頂點全部標識出來，其數(shù)量必定為2的倍數(shù)，進而通過兩兩對應，確保新的規(guī)劃路徑中不會出現(xiàn)奇頂點；

過程二：循環(huán)執(zhí)行過程一，當滿足最優(yōu)值時，繼續(xù)下一過程；

過程三：依據(jù)條件（1）循環(huán)過程二。

3 實際案例分析

利用GMOEPA即可得到變電站最優(yōu)巡視路徑，同時本文通過對比分析基于GMOEPA的巡視路徑和人工巡視路徑，驗證前者的可行性及優(yōu)越性。

為了對新制定的巡視路線優(yōu)劣性做出適當?shù)脑u價，在實際驗證環(huán)節(jié)，我們進行了兩次巡視，表1給出將兩次巡視的優(yōu)劣對比結果，對比因素包括：人員走動的距離以及巡檢消耗的時間。

根據(jù)上述上表可得出Line2效果非常明顯，人工經驗巡視路徑相比于GMOEPA得到的巡視路徑其路程多出157m，作業(yè)時間也高出將近一個小時。

從上表可以明顯比較出，按照新的巡視路徑Line2進行巡視，巡視人員的走動距離 減少157米，節(jié)約時間49分鐘。若以兩名變電人員完成該變電站檢查工作，且巡視次數(shù)以每天巡視1次計算，時間可以節(jié)省將近100min。當遇到重大保電活動、特殊運行方式安排，變電站將加強監(jiān)視，其每日工作量將急劇增加，使用新的巡視路徑將大大改善作業(yè)時間，減小變電工作人員的工作壓力，同時也可減低作業(yè)人員的容錯率。

4 總結

本文分析了我國變電站的巡視路線制定方式，首先指出這種依照經驗設定的巡視路線存在的問題，接著簡單地描述有關郵遞員問題，介紹了GMOEPA法，最后以內蒙古某變電站為例，設計出新的方案，有效的證明了郵遞員問題的解決方法的可靠性，且結果表明新的路徑規(guī)劃方案可以顯著減少時間、人力消耗。

參考文獻：

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

[2]彭光超.基于郵遞員問題的變電站巡視路線探究[J].電子測試，2014（s2）：181-183.

[3]費蓉，崔杜武.中國郵遞員問題的動態(tài)規(guī)劃算法研究[J].計算機研究與發(fā)展，2005，42（2）：294-299.