最短路徑算法在線(xiàn)路搶修中的應(yīng)用研究

張錦

摘 要：配電網(wǎng)結(jié)構(gòu)越來(lái)越復(fù)雜，電力設(shè)備日益增加，配電網(wǎng)故障定位及最佳路徑選擇的問(wèn)題是電力部門(mén)的研究熱點(diǎn)，也是提高搶修效率和供電質(zhì)量的關(guān)鍵。文章首先分析了配電網(wǎng)使用最短路徑算法進(jìn)行線(xiàn)路搶修的重要意義，其次闡述了最短路徑算法的基本原理、優(yōu)化算法流程，最后對(duì)優(yōu)化算法效率進(jìn)行分析，以便能實(shí)現(xiàn)最短搶修路徑的有效選擇。

關(guān)鍵詞：最短路徑；配電網(wǎng)；線(xiàn)路搶修

中圖分類(lèi)號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1006-8937（2016）09-0063-02

隨著國(guó)民經(jīng)濟(jì)的迅猛發(fā)展，電力系統(tǒng)與工農(nóng)業(yè)生產(chǎn)、居民生活息息相關(guān)，人們對(duì)配電網(wǎng)的穩(wěn)定性和可靠性提出了更高要求。配電網(wǎng)不僅是供電與用電的連接，也承擔(dān)著管理的角色，一旦配電網(wǎng)出現(xiàn)電力故障，配電管理要在盡可能短的時(shí)間內(nèi)恢復(fù)供電，而要最短時(shí)間內(nèi)恢復(fù)供電，對(duì)故障進(jìn)行準(zhǔn)確定位、隔離及搶修是確保配電網(wǎng)高效運(yùn)行的關(guān)鍵，其中對(duì)故障準(zhǔn)確定位是最為關(guān)鍵的，能否準(zhǔn)確對(duì)故障進(jìn)行定位直接影響恢復(fù)供電時(shí)間。雖然配電網(wǎng)自動(dòng)化程度不斷提高，隔離開(kāi)關(guān)可以解決部分電力故障，對(duì)于隔離開(kāi)關(guān)難以解決的故障，就必須派出專(zhuān)門(mén)人員去解決故障。在實(shí)際搶修過(guò)程中，最短路徑選擇成為影響搶修效率的關(guān)鍵要素，能夠有利于確保搶修的及時(shí)性和高效性。基于此，筆者對(duì)基于空間方向的最短路徑優(yōu)化算法在配電網(wǎng)線(xiàn)路搶修進(jìn)行研究。

1 線(xiàn)路搶修使用最短路徑算法的重要意義

配電線(xiàn)路一旦發(fā)生電力故障，要及時(shí)進(jìn)行維護(hù)，而配電網(wǎng)線(xiàn)路復(fù)雜、電力設(shè)備眾多，維修路徑的選擇如果僅依靠實(shí)踐經(jīng)驗(yàn)，就難以提高工作效率，也失去了靈活性，若能尋找一種耗時(shí)較短、路徑也短的線(xiàn)路選擇方式，不僅能夠盡快恢復(fù)供電，確保供電可靠性，還能縮短維修時(shí)間，有效降低電力部門(mén)的運(yùn)營(yíng)成本，提高經(jīng)濟(jì)效益和社會(huì)效益，對(duì)整個(gè)社會(huì)來(lái)說(shuō)意義深遠(yuǎn)。

2 最短路徑優(yōu)化算法的基本原理

根據(jù)幾何原理可知，兩點(diǎn)之間直線(xiàn)距離最短，然而在實(shí)際的配電網(wǎng)線(xiàn)路中，兩點(diǎn)之間直線(xiàn)作為一段道路的概率很小，但沿著兩點(diǎn)之間的直線(xiàn)代表?yè)屝蘧€(xiàn)路的趨勢(shì)，在沿著這個(gè)方向上存在某條道路最短路徑可能性較大。為了計(jì)算最短路徑，可采用夾角最大的貪婪算法，在當(dāng)前節(jié)點(diǎn)處找出所有與其相鄰的鄰接點(diǎn)，取出所有節(jié)點(diǎn)中與當(dāng)前、終點(diǎn)連成直線(xiàn)夾角最大的節(jié)點(diǎn)，然后將此節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，繼續(xù)選取夾角最大的路段，直到當(dāng)前節(jié)點(diǎn)為終點(diǎn)。這種算法即考慮了方向性特征，也考慮全局特性，因此可信度難以得到有效保證，為了提高精確性，對(duì)該算法進(jìn)行優(yōu)化，在經(jīng)過(guò)節(jié)點(diǎn)同時(shí)進(jìn)行起點(diǎn)、終點(diǎn)直線(xiàn)左右兩邊各滿(mǎn)足夾角最大節(jié)點(diǎn)的搜索，即搜索一棵二叉樹(shù)。

假設(shè)O，D點(diǎn)分別表示起點(diǎn)和終點(diǎn)，OD之間最短路徑優(yōu)化算法：假設(shè)存在一搶修路徑隊(duì)列，先將O作為當(dāng)前節(jié)點(diǎn)，K1是與O點(diǎn)連接且OK1與OD夾角為負(fù)的節(jié)點(diǎn)，K2是與與O點(diǎn)連接且OK2與OD夾角為正的節(jié)點(diǎn)，表達(dá)式如下（1），（2）所示：

3 優(yōu)化算法流程

在使用上述優(yōu)化算法進(jìn)行計(jì)算時(shí)，首先要定義一個(gè)存放節(jié)點(diǎn)編號(hào)的路徑隊(duì)列，Node[]、i，num分別表示數(shù)組、序號(hào)及節(jié)點(diǎn)總數(shù)。具體優(yōu)化算法流程，如下圖1所示。

4 算法效率分析

為了驗(yàn)證上述優(yōu)化算法是否有效，筆者通過(guò)實(shí)例實(shí)驗(yàn)進(jìn)行驗(yàn)證，實(shí)驗(yàn)選用某供電局轄區(qū)街道圖，如圖2所示，路口節(jié)點(diǎn)數(shù)n和路段數(shù)量m分別為245和410，在配電線(xiàn)路中任意取四點(diǎn)A、B、C、D，用優(yōu)化前和優(yōu)化后的算法分別計(jì)算AB，CD之間的最短路徑，優(yōu)化前，優(yōu)化后的計(jì)算結(jié)果分別為：（AbB，Cc1d2D）、（AaB，Cc2d2D）。為了對(duì)優(yōu)化前后兩種計(jì)算結(jié)果對(duì)比更明確，兩種計(jì)算結(jié)果進(jìn)行比較，見(jiàn)表1。表中N1、N2、T、L分別表示最短路徑的路段個(gè)數(shù)、求解過(guò)程搜索的節(jié)點(diǎn)數(shù)、求解時(shí)間及最短路徑長(zhǎng)度。

根據(jù)上述分析結(jié)果可以看出：第一，優(yōu)化后的算法效果比優(yōu)化前算法結(jié)果要好，當(dāng)搜索時(shí)間相同時(shí)，計(jì)算精確度相對(duì)較高；第二，求解時(shí)間與節(jié)點(diǎn)數(shù)量N2幾乎成正比關(guān)系。經(jīng)過(guò)試驗(yàn)表明：在配電網(wǎng)最短路徑實(shí)際運(yùn)用，優(yōu)化后的算法更具有優(yōu)越性，

也更具有實(shí)用性和操作性。

5 結(jié) 語(yǔ)

綜上所述，配電線(xiàn)路結(jié)構(gòu)復(fù)雜、電力設(shè)備眾多，一旦發(fā)生故障，為了確保盡快恢復(fù)供電，尋找最短路徑是提高維修效率的重要方法之一，對(duì)基于空間方向的最短路徑優(yōu)化算法進(jìn)行研究，結(jié)果表明：優(yōu)化后的算法比優(yōu)化前的算法效果更好，適合在線(xiàn)求解供電線(xiàn)路的最短路徑。

參考文獻(xiàn)：

[1] 王曉麗，楊兆升，呂旭濤.平行四邊形限制最短路徑算法及其在交通網(wǎng) 絡(luò)中的應(yīng)用[J].吉林大學(xué)學(xué)報(bào)（工學(xué)版），2013，（1）.

[2] 葉品勇，都洪基.Dijkstra算法在配電網(wǎng)最佳搶修路徑計(jì)算中的應(yīng)用[J].繼電器，2013，（11）.

[3] 張娟.基于的配電網(wǎng)故障定位及其供電恢復(fù)[D].昆明：昆明理工大學(xué)，2011.