最短路徑演算法線上路搶修中的應用論文

　　從某頂點出發，沿圖的邊到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑叫做最短路徑。下面是小編為大家整理的最短路徑演算法線上路搶修中的應用論文，歡迎閱讀。

　　摘要：配電網結構越來越複雜，電力裝置日益增加，配電網故障定位及最佳路徑選擇的問題是電力部門的研究熱點，也是提高搶修效率和供電質量的關鍵。文章首先分析了配電網使用最短路徑演算法進行線路搶修的重要意義，其次闡述了最短路徑演算法的基本原理、最佳化演算法流程，最後對最佳化演算法效率進行分析，以便能實現最短搶修路徑的有效選擇。

　　關鍵詞：最短路徑；配電網；線路搶修

　　隨著國民經濟的迅猛發展，電力系統與工農業生產、居民生活息息相關，人們對配電網的穩定性和可靠性提出了更高要求。配電網不僅是供電與用電的連線，也承擔著管理的角色，一旦配電網出現電力故障，配電管理要在儘可能短的時間內恢復供電，而要最短時間內恢復供電，對故障進行準確定位、隔離及搶修是確保配電網高效執行的關鍵，其中對故障準確定位是最為關鍵的，能否準確對故障進行定位直接影響恢復供電時間。雖然配電網自動化程度不斷提高，隔離開關可以解決部分電力故障，對於隔離開關難以解決的'故障，就必須派出專門人員去解決故障。在實際搶修過程中，最短路徑選擇成為影響搶修效率的關鍵要素，能夠有利於確保搶修的及時性和高效性。基於此，筆者對基於空間方向的最短路徑最佳化演算法在配電網線路搶修進行研究。

　　1.線路搶修使用最短路徑演算法的重要意義

　　配電線路一旦發生電力故障，要及時進行維護，而配電網線路複雜、電力裝置眾多，維修路徑的選擇如果僅依靠實踐經驗，就難以提高工作效率，也失去了靈活性，若能尋找一種耗時較短、路徑也短的線路選擇方式，不僅能夠儘快恢復供電，確保供電可靠性，還能縮短維修時間，有效降低電力部門的運營成本，提高經濟效益和社會效益，對整個社會來說意義深遠。

　　2.最短路徑最佳化演算法的基本原理

　　根據幾何原理可知，兩點之間直線距離最短，然而在實際的配電網線路中，兩點之間直線作為一段道路的機率很小，但沿著兩點之間的直線代表搶修線路的趨勢，在沿著這個方向上存在某條道路最短路徑可能性較大。為了計算最短路徑，可採用夾角最大的貪婪演算法，在當前節點處找出所有與其相鄰的鄰接點，取出所有節點中與當前、終點連成直線夾角最大的節點，然後將此節點作為當前節點，繼續選取夾角最大的路段，直到當前節點為終點。這種演算法即考慮了方向性特徵，也考慮全域性特性，因此可信度難以得到有效保證，為了提高精確性，對該演算法進行最佳化，在經過節點同時進行起點、終點直線左右兩邊各滿足夾角最大節點的搜尋，即搜尋一棵二叉樹。

　　假設O，D點分別表示起點和終點，OD之間最短路徑最佳化演算法：假設存在一搶修路徑佇列，先將O作為當前節點，K1是與O點連線且OK1與OD夾角為負的節點，K2是與與O點連線且OK2與OD夾角為正的節點，表示式如下（1），（2）所示：

　　3.最佳化演算法流程

　　在使用上述最佳化演算法進行計算時，首先要定義一個存放節點編號的路徑佇列，Node[]、i，num分別表示陣列、序號及節點總數。具體最佳化演算法流程，如下圖1所示。

　　4.演算法效率分析

　　為了驗證上述最佳化演算法是否有效，筆者透過例項實驗進行驗證，實驗選用某供電局轄區街道圖，如圖2所示，路口節點數n和路段數量m分別為245和410，在配電線路中任意取四點A、B、C、D，用最佳化前和最佳化後的演算法分別計算AB，CD之間的最短路徑，最佳化前，最佳化後的計算結果分別為：（AbB，Cc1d2D）、（AaB，Cc2d2D）。為了對最佳化前後兩種計算結果對比更明確，兩種計算結果進行比較，見表1。表中N1、N2、T、L分別表示最短路徑的路段個數、求解過程搜尋的節點數、求解時間及最短路徑長度。

　　根據上述分析結果可以看出：第一，最佳化後的演算法效果比最佳化前演算法結果要好，當搜尋時間相同時，計算精確度相對較高；第二，求解時間與節點數量N2幾乎成正比關係。經過試驗表明：在配電網最短路徑實際運用，最佳化後的演算法更具有優越性，也更具有實用性和操作性。

　　5 結語

　　綜上所述，配電線路結構複雜、電力裝置眾多，一旦發生故障，為了確保儘快恢復供電，尋找最短路徑是提高維修效率的重要方法之一，對基於空間方向的最短路徑最佳化演算法進行研究，結果表明：最佳化後的演算法比最佳化前的演算法效果更好，適合線上求解供電線路的最短路徑。

　　參考文獻：

　　[1] 王曉麗，楊兆升，呂旭濤.平行四邊形限制最短路徑演算法及其在交通網絡中的應用[J].吉林大學學報（工學版），2013，（1）.

　　[2] 葉品勇，都洪基.Dijkstra演算法在配電網最佳搶修路徑計算中的應用[J].繼電器，2013，（11）.