基于雙向廣度優先搜索的配電網可靠性評估

盧純，劉少云

(1．國網新源建設有限公司，北京100000;2．國網新疆電力公司，新疆烏魯木齊830001)

基于雙向廣度優先搜索的配電網可靠性評估

盧純1，劉少云2

(1．國網新源建設有限公司，北京100000;2．國網新疆電力公司，新疆烏魯木齊830001)

配電網是電力系統與用電客戶的連接環節，對配電網進行可靠性評估，可以發現配電網的薄弱環節，為電網的維護提供重要信息。針對配電網負荷點密集、計算量大的特點，文章應用雙向廣度優先搜索方法進行最小路的搜索。該方法具有搜索快、用時短、準確性高的優點，通過C++實現程序設計，使得整個配電網可靠性評估過程迅速且準確進行。對某配電網實例進行可靠性評估，得到了與傳統方法相同的結果，并且速度較快。算例結果表明基于雙向廣度優先搜索的配電網可靠性評估方法是有效的。

配電網;可靠性評估;雙向廣度優先搜索;最小路

0 引言

配電系統是電力系統中供電點與用戶之間的整個配電部分，配電網的可靠性對社會經濟等各方面有著直接影響。因此對配電網的可靠性展開快速準確的評估，并提高其可靠性具有重要的現實意義［1－3］。

目前，我國關于配電網的可靠性評估已有一部分研究，但是很多局限于理論方面的探討，未能應用到實踐，沒有滿足對電網的建設發展等提供有效的指導。從當前關于可靠性的研究成果可知，對于可靠性評估的方法主要分為兩類:第一類被稱為解析法(Analytical Method)，如故障后果分析法、網絡等值法［4］、最小割集法［5］、最小路法［6－8］等;第二類叫做模擬法(Simulation Technique)，通常指的就是蒙特卡洛模擬法［9－10］。

隨著電網結構復雜程度的增加，如何快速準確實現可靠性指標的計算成為眾多可靠性評估方法研究的關鍵。文獻［11］構建了采用GO法的可靠性評估模型，該模型對復雜系統不用定性分析，所以不會隨電網結構的擴大而變得復雜，可以較快計算出評估電網可靠性所需要的指標數據。文獻［12］研究了廣度優先算法和最小路法結合的可靠性評估模型，采用廣度優先搜索算法不重復搜索的特點進行最短路徑的搜索。文獻［13］采用Dijkstra算法來求取最短路徑，然后基于最小路徑實現可靠評估。這種求解最短路徑的方法是逐步求出距離原點距離最短的點，而且更新該點與其相鄰各點的距離，最終求出最短路徑。上述所提方法中，都涉及到如何在保證評估準確性的同時提高搜索速度的問題。

本文研究了一種基于雙向廣度優先搜索(Double Breadth First Search，DBFS)［14］算法的配電網可靠性評估方法。該方法具有搜索快、用時短、準確性高的優點，將DBFS方法用于求取最小路徑，然后用最小路法進行評估，可以顯著提高運算速度。利用C++實現程序設計，通過對某配電網開展可靠性評估，驗證了算法的準確性與快速性。

1 配電網可靠性指標

配電系統可靠性側重點是配電系統電源對廣大用電客戶保持持續供電的能力。配電系統的可靠性最終要借助各種可靠性指標來評估。無論是配電系統的性能，還是負荷以及元件的性能，往往都是具有概率的特征。因此，現在國內外關于配電系統的可靠性評估相關研究，選用的分析指標均是基于概率的指標［15－16］。

1.1 負荷點的可靠性指標

(1)平均故障率

平均故障率(λ，次/a)表示的是系統內某一負荷點在一個具體的時間段內，由于系統的元件故障引起的停電次數。可以采用下式計算:

(2)平均停運持續時間

平均停運持續時間(r，h/次)表示的是從停電開始到恢復供電這個時間段的平均值。

(3)平均停運時間

平均停運時間U(h/a)表示的是用電客戶在某一給定的時間段內停電時長的平均值。通常，平均停運時間越大，那么該負荷點的故障排除需要的時間也就越長，供電可靠性水平越低。

式中:λ'i為元件i故障率;λ″i為元件i檢修停運率;γ'i為元件i的平均故障修復時間;γ″i為元件i的平均檢修持續時間;n為負荷點與電源之間的電氣元件總數。

1.2 系統的可靠性指標

系統的可靠性評估指標為:系統平均停電持續時間SAIDI、系統平均停電頻率SAIFI、用戶平均停電持續時間CAIDI、用戶平均停電頻率CAIFI、不可靠率ASUI，根據分析獲得的負荷點的可靠性指標作為基礎，可求出系統的可靠性指標，具體公式如下:

式中:λi為負荷點i的平均故障率;Ni為負荷點i的用戶數;Ui為負荷點i的年平均停運時間。

1.3 典型網絡結構可靠性計算

一個完整的電力網絡是通過各種各樣的元件連接而成，在對配電網開展可靠性方面的評估時，可以通過對并聯或者串聯的若干元件進行等效處理，簡化為一個元件，這樣可以使整個評估過程的計算量得到很大程度的降低。

1.3.1 串聯網絡的計算

對于由n個可修復元件組成的串聯網絡如圖1所示，串聯系統的多種參數可以采用如下公式進行計算。

等效故障率:

等效每次故障平均停電持續時間:

等效年平均停電時間:

圖1 串聯等值網絡

1.3.2 并聯網絡的計算

對于并聯的網絡結構，如圖2所示。

圖2 并聯等值網絡

等效每次故障平均停電持續時間:

等效年平均停電時間:

在實際處理過程中，通常會遇到含有三個甚至更多的元件所組成的網絡，先把其中的兩個元件等效處理為一個元件，然后將合并后的元件再和第三個元件進行組合處理，以此類推進行處理。

等效故障率:

2 雙向廣度優先搜索算法

2.1 最小路評估方法

在實際配電網當中，不同的網絡其線路結構以及電氣設備都有所區別，所選擇的計算方式也不可能完全相同，根據實際情況改變計算方式，無形之中增加了計算的復雜程度，加大了可靠性評估的難度。為了有效應對與解決這些潛在的問題，以降低配電系統可靠性方面評估的難度，相關學者提出了基于最小路的配電網評估方法。

基于最小路的評估方法的核心是首先尋找配電系統中的所有負荷點與電源點之間的最小路，然后根據最小路的選擇情況，將整個配電系統的所有元件分成兩類:一類元件是處在最小路上的;另一類元件是處在非最小路上。對于最小路上的元件以及非最小路上的元件進行計算以及處理的原則詳見文獻［8］。

2.2 廣度優先搜索求取最小路

廣度優先搜索(BreadthFirstSearch，BFS)［17－18］是圖論中的一個較為簡單的搜索方法。在實際搜索過程中，BFS搜索方法是一種“廣撒網”的理論，在開始搜索之前，并沒有預期或者估計可能的位置節點，不具有針對性，而是直接對整張圖進行全面、系統的展開搜索，一直到尋求到想要的結果才結束。BFS搜索法的流程圖如圖3所示。

圖3 BFS流程圖

2.3 雙向廣度優先算法

盡管廣度搜索的方法可以獲得最優解，但由于其自身的搜索特點，造成空間消耗過快，影響計算效率。假如從起點和終點同時開始展開搜索，理論上可以減少一半的搜索時間，進而提高了效率。雙向廣度優先搜索方法是以常規的廣度優先搜索為基礎，分別從初始點與目標點同時按BFS方式進行擴展，使之在中間某節點相遇。圖4描述了雙向廣度優先搜索的思路和執行過程:分別從初始節點沿著正方向開始搜索、從目標節點沿著反方向朝著出始節點開始搜索，一直到兩個搜索過程同時到達在中間某個節點時結束，從而得到網絡中的一條路徑。和常規的廣度優先搜索算法不同的是，雙向廣度優先算法在搜索過程中減少了擴展出的狀態數，雙向進行，因此提高了效率，加快了整個網絡結構的搜索過程;同時可以和BFS一樣，具有“求出的解是最優解”的優點。

為了詳細說明DBFS算法搜索的實現過程，以圖4所示的7節點無向圖為例進行詳細介紹。

圖47 節點系統圖

DBFS算法的詳細過程可以描述為:搜索開始后，起始節點V1和目標節點V4、V7、V6同時向前開始搜索，然后在中間節點V2、V5、V3中某個位置會和，完成路徑搜索。采用DBFS對圖進行搜索時，整個過程是逐層搜索，出現重復的次數比較少，效率相對較高。

2.4 雙向廣度優先算法的C++程序實現

對于復雜的網絡結構，節點及支路數目較多，將配網系統的的等效有向圖作為原始數據，可以用C++編寫計算機程序，使搜索過程更加便捷，提高效率。計算機程序實現的流程圖如圖5所示。

3 算例分析

本文以南方某配電系統為例，進行可靠性分析，采用BFS和DBFS兩種搜索方法同時計算，以驗證基于雙向廣度優先搜索的評估方法的準確性與快速性。該配電網絡具有3 000 kW的備用容量，不考慮變電站10 kV母線停運及斷路器相鄰兩側隔離開關的故障。該配電網的接線圖如圖6所示，線路和負荷參數詳見表1和表2。

圖5 計算機程序流程圖

圖6 配電網接線圖

對于算例中較簡單的網絡結構，采用BFS和DBFS分別搜索最小路徑，兩種方法的所用時間如表3所示。

然后采用最小路法進行評估，得到配電網的可靠性指標結果是相同的，如表4和表5所示。

表1 供電干線參數

表2 系統元件可靠性參數

表3 兩種方法時間對比

表4 各負荷點的可靠性指標

表5 系統可靠性指標

由上面數據可以知道，BFS和DBFS兩種方法均可實現最短路徑的搜索，而且DBFS搜索效率更高。可靠性指標的數據相同，表明DBFS的搜索結果是正確的，可以在提高速度的同時實現對配電網的準確評估。

4 結論

對配電網進行有效及時的狀態評估至關重要。最小路法評估模型適用于各種電網結構，如何準確快速地完成最小路徑搜索，實現指標計算是評估過程中非常關鍵的環節。本文研究了基于雙向廣度優先算法的配電網評估方法，利用廣度優先搜索算法搜索電網結構的最短路徑，具有快速、準確的優點，提高了配電網評估的效率。通過編寫C++計算機程序，結合算例，證明了這種方法是有效可行的。

［1］程德才，趙書強，馬燕峰．配電網可靠性指標的灰色組合預測方法及應用［J］．電力科學與工程，2009，25(3):18－21．

［2］任建文，李越佳．基于饋線分區的分布式電源接入配電網可靠性評估［J］．華北電力大學學報(自然科學版)，2015，42(6):29－34．

［3］徐其迎，王少卿，李日隆．基于區間算法的配電系統可靠性評估方法［J］．電力科學與工程，2003，19(4):26－28．

［4］張杰，王曉剛，鄧智杰，等．基于改進網絡等值和故障影響矩陣的復雜配電網可靠性評估［J］．中國電力，2016，49(7):20－26．．

［5］相曉鵬，邵玉槐．基于最小割集法的配電網可靠性評估算法［J］．電力學報，2006，21(2): 149－153．

［6］XIE K，ZHOU J，BILLINTON R．Reliability evaluation algorithm for complex medium voltage electrical distribution networksbasedontheshortestpath［J］．IEEE Proceedings-Generation，Transmission andDistribution，2003，150(6):686－690．

［7］周念成，謝開貴，周家啟，等．基于最短路的復雜配電網可靠性評估分塊算法［J］．電力系統自動化，2005，29(22):39－44．

［8］戴雯霞，吳捷．基于最小路的配電網可靠性快速評估法［J］．電力自動化設備，2002，22(7): 29－31．

［9］侯雨伸，王秀麗，劉杰，等．基于擬蒙特卡羅方法的電力系統可靠性評估［J］．電網技術，2015，39(3):744－750．

［10］侯雨伸，王秀麗，張玥，等．考慮維度重要性的電力系統可靠性評估擬蒙特卡洛方法［J］．電力系統自動化，2016，40(16):31－37．

［11］徐荊州，李揚，陳霄．基于GO法的配電網可靠性評估［J］．電力系統及其自動化學報，2006，18(5):66－69．

［12］郭慧敏．應用最小路－廣度優先搜索的配電系統可靠性評估［J］．電力系統保護與控制，2007，35(22):14－17．

［13］張小娟，李澤榮，張重遠，等．基于最小路法的配電網可靠性評估［J］．電網與清潔能源，2010，26(8):24－28．

［14］王桂平，張帥．基于雙向廣度優先搜索的魔力方塊問題求解［J］．計算機工程，2011，37(20): 219－222．

［15］葛少云，季時宇，劉洪，等．基于多層次協同分析的高中壓配電網可靠性評估［J］．電工技術學報，2016，31(19):172－181．

［16］胡美玉，胡志堅，鄧奧攀，等．基于元件層級和電源可達性的配電網可靠性評估混合算法［J］．電力系統保護與控制，2016，44(8):22－29．

［17］張海波，張曉云，張莉，等．基于廣度優先搜索的配電網故障恢復算法［J］．電網技術，2010，34(7):103－108．

［18］劉愛國，張弘．一種基于廣度優先搜索配電網潮流計算的改進編號方法［J］．中國電力，2016，49(10): 74－78．

Reliability Evaluation of Distribution Network Based on Double Breadth First Search

LU Chun1，LIU Shaoyun2
(1．State Grid Xin Yuan Construction Co．，Ltd．，Beijing 100000，China; 2．State Grid Xinjiang Electric Power Company，Urumchi 830001，China)

As alink between power system and customers，the distribution network is of great importance．And the reliability evaluation of the distribution network can find the weakness and provide important information for the maintenance of the power grid．According to the characteristics of heavy load and large amount of calculation in distribution network，the double first search method is used to search the minimal path in this paper．This method has the advantages of fast searching，short consumption time and high accuracy．Through the implementation of C++programming，the reliability evaluation process is carried out with speed and accuracy．The reliability of a distribution network is evaluated，and the accuracy and rapidity of the algorithm are verified．

distribution network;reliability evaluation;double breadth first search; the minimal path

TM73

A

1672－0792(2017)07－0009－06

盧純(1986－)，男，碩士研究生，工程師，研究方向為配電網規劃、電網狀態評估;劉少云(1985－)，男，工程師，研究方向配電網規劃、電網狀態評估。

10.3969/j.ISSN.1672－0792.2017.07.002

2017－05－22。