最小生成樹算法在配電網重構中的應用

， ， ， ，

(1.西南石油大學電氣信息學院，四川 成都 610500；2.國網成都供電公司客服中心，四川 成都 610046；3.國網天府新區供電公司， 四川 成都 610000)

0 引 言

作為電力系統重要組成部分的配電系統，由于直接面向終端用戶，所以對其供電可靠性和電能質量方面的要求也越來越高，而它的完善與否直接關系著廣大用戶的用電可靠性和用電質量[1]。隨著電力用戶逐漸增多，配電線路經常出現超負荷或輕負荷現象，出現電壓降低，并且有功損耗增加。

而通過配電網重構可以很好地解決上述問題，實現負荷的均衡和降低有功損耗。通過配電網絡重構可以實現降低配電網線損，提高系統經濟性；均衡負荷，消除過載，提高供電電壓質量，提高供電可靠性。配電網重構的方法有很多，文獻[2]采用最短路徑算法對配電網進行重構，利用最短路徑算法尋找所有負荷節點的供電最短路徑，在形成的樹狀網絡中利用最小點電壓法進行支路交換操作。該方法對降低系統有功損耗和提高供電質量作用明顯，但由于需要尋找根節點向每個負荷節點供電的最短路徑，計算復雜。文獻[3]采用基于圖論的改進遺傳算法進行重構優化，在初步連接圖的基礎上尋找最優的生成樹，基于破圈法和環路的性質進行編碼操作，得到最優解，該算法在配電網重構中具有理想的效果，能以較大概率保證收斂到全局最優解，但該方法計算量較大，速度較慢。文獻[4]提出了一種利用節點電壓進行配網重構的方法，將電壓均衡指數作為目標函數，通過連續的支路交換操作來尋求配電網的最佳結構，該方法即使在嚴重缺乏量測點時,仍可以進行。文獻[5]提出了通過組合負荷實現尋優的重構方法，利用最短路徑法按照某一順序為每個負荷分別尋找供電路徑, 然后利用遺傳算法選擇最優的負荷排列順序, 從而實現在局部最優解中尋求全局最優解。因算法不依賴于網絡初始結構，可以得到全局最優解，但存在“維數災”問題。此外，還有應用于智能電網的配電網重構[6]，最小供電成本的配電網重構[7]等，及基于各種智能優化算法[8-10]的配電網重構。

基于圖論的最小生成樹算法是網絡最優化算法中最重要的算法之一，在很多工程技術領域中得到應用。例如，在若干城市之間架設通信線纜，鋪設線路、鐵路或各種管道，要求總的路線長度最短或材料最省、成本最低等。而目前常用的最小生成樹算法有Prim算法和Kruskal算法，這里選用改進Kruskal算法進行配電網重構。通過數學建模建立目標函數后利用潮流算法計算環網節點電壓，并對每一條邊賦權值后進行最小生成樹計算，并通過反復迭代更新權值的方式使網絡達到最優。33節點和69節點算例驗證了算法的有效性。

1 配電網重構算法

1.1 數學模型

(1)目標函數

配電網重構一般以降低配電網的線路損耗、提高配電網的電壓質量、提高供電可靠性和均衡負荷等為目標，也可以綜合上述多個指標為目標。采用以最小有功損耗為目標，其表達式為

(1)

(2)

式中，m為網絡中支路總數；Pi和Qi為流過支路的有功功率和無功功率；Ri為支路電阻；Ui為支路的首端電壓；U為最低節點電壓值；ΔP為網絡中所有線路的有功損耗之和。

(2 )約束條件

配電網重構的目標是使f最小，且滿足下面的約束條件。

Ui，min≤Ui≤Ui，max

(3)

Ii≤Ii，max

(4)

Si≤Si，max

(5)

(6)

式中，Ui，min和分別為節點i的電壓下限和上限；Ii，max為支路電流最大值；Si，max為支路i或配電變壓器的最大負載能力；PLi和QLi分別為節點i注入的有功功率和無功功率；Gij、Bij、δij分別為節點i、j的電導、電納和電壓相角差；n為系統總節點數；U1、Uj分別為節點i、j的電壓幅值。網絡輻射狀運行，無環路及孤立節點。

1.2 基于Kruskal算法的最小生成樹計算原理

由于配電網是閉環設計，開環呈輻射狀運行，配電網絡重構問題所求的最優解可看作是在賦權圖中尋找以根節點為起點，滿足目標函數的最小生成樹問題[11]。將Kruskal算法應用于配電網絡重構的一個顯著優勢就是可以建立所有負荷節點與根節點的連接，并自動形成輻射狀網絡。

為便于描述,可用G=(V,E)來描述一個配電網絡(其中V為節點集合、E為邊集合)[12]，配電網重構問題所求的最優解可以認為是滿足目標函數中的一棵最小生成樹T。用l(e)表示邊的權值，則所有負荷節點和根節點的最小生成樹可以表示為[8]

(7)

Kruskal算法是目前公認的求最小生成樹問題的最好方法。對于一個連通賦權圖G=(V,E)，圖G的最小生成樹T按下述方法構造：在E中選擇權值最小的邊，作為T的第一條邊，相繼選擇E剩下的邊中權值最小的邊加入T，且該邊滿足不與前面所選的邊構成圈，持續這種做法，直至產生一個生成樹[9]。

1.3 配電網重構的搜索算法

由于Kruskal算法不依賴網絡的初始結構,使得形成樹狀網絡變得較容易，并且易于解決復雜結構網絡的尋優問題。具體步驟如下。

由文獻[4]可知，在僅能夠獲得配電線路沿線柱上開關處的量測信息的情況下，仍然能夠求解出網絡重構后沿線各處的電壓降落，因此對于量測不足的配電系統，也可以認為其電壓降落是已知的。所以對于配電網來說其各節點電壓值是很容易得到的。由此，文獻[4]提出基于電壓的平衡指數來調整聯絡開關和分段開關的位置，最終得到一個滿足約束的最優網絡。定義網絡中各聯絡開關和分段開關的電壓平衡指數為VBLi-j。

VBLi-j=max(UNi，UNj)/min(UNi，UNj)

(8)

式中，min(UNi，UNj)表示取小值；max(UNi，UNj)表示取大值。

所提算法主要步驟如下。

(1)求電壓平衡指數：閉合配電網中的所有聯絡開關，通過計算環網潮流得到節點電壓，以此來求得各開關的電壓平衡指數。

(2)初始最小生成樹的生成：以各開關的電壓平衡指數為求最小生成樹的邊的權值，利用最小生成樹算法Kruskal算法求得最小樹T(K)，這是對配電網的初次優化，得到一個輻射狀運行的網絡，通過潮流計算得到最小生成樹T(K)的有功損耗和最低節點電壓。

(3)聯絡開關排序：將得到的除最小生成樹T(K)外斷開的開關按權值從小到大的順序放入隊列Q中，在下面所用的標準算例中，得到斷開的開關有5條，作為聯絡開關處理。

(4)聯絡開關排序：取出隊列Q之首的開關k放到T(K)中，由此產生一個環路，計算當前網絡的權值，選擇除新加邊外環路上所有開關，按權值從小到大排列放入隊列Q1中。

(5)迭代更新：斷開隊列Q1之首的開關n，即可構成一棵新的樹T(N)。進行潮流計算，比較T(N)和T(K)的有功損耗。

比較結果分為以下兩種情況。

1)若T(N)的有功損耗小于T(K)的有功損耗，且滿足約束，則此聯絡開關閉合為最優結果，將Q1中斷開的開關n放入隊列Q的末端，并且清空隊列Q1，返回步驟(4)。

2)若T(N)的有功損耗大于T(K)的有功損耗，將Q1中首元素n置于Q1隊列末端,返回步驟(5)，反復迭代。

在此過程中可能會出現依次斷開Q1隊列的所有開關后依然無法得到使T(N)的有功損耗小于T(K)的有功損耗的開關n。在這種情況下，開關k為最優開關，將開關k放入隊列Q的末端，并且清空隊列Q1，返回步驟(4)。

當初始隊列Q中的聯絡開關全部動作完時算法結束。

2 算例分析

為驗證所提方法的正確性和可行性,選擇文獻[4]所用的2個標準算例33節點系統和69節點系統進行驗證,并將計算結果和不同算法重構的運算結果進行比較。

2.1 33節點系統

該配電網為12.66 kV的配電系統，有33個節點、37條支路,其中的5條為聯絡開關，系統總有功負荷為3 715 kW，初始有功損耗為202.68 kW。采用所提方法得到的優化結果如表1所示。

表1 33節點系統配電網絡重構結果

由表1結果可以看出所提算法與文獻[4]的結果一致。重構前系統最低電壓為0.913 1 p.u.,重構后系統最低電壓為0.937 8 p.u.，提高了2.7%，從一定程度上改善了電壓質量，系統重構前后電壓變化如圖1所示。重構前系統有功損耗為202.68 kW，重構后系統有功損耗為139.55 kW，降低了31.1%。

圖1 33節點系統重構前后節點電壓比較

2.2 69節點系統

該配電網為12.66 kV的配電系統，有69個節點、73條支路,其中的5條為聯絡開關，系統總有功負荷為3 802.19 kW，初始有功損耗為226.05 W。采用所提方法得到的優化結果如表2所示。由于所采用的節點編號與文獻[4]不同，所以得到的開關編號不同，但最終結果是一致的。

在系統規模增大后，所得計算結果仍與文獻[4]的結果保持一致，這說明了針對不同規模的配電系統所提算法仍然適用。由表2可知，重構前系統最低電壓為0.901 8 p.u.，重構后系統最低電壓為0.942 8 p.u.，提高了4.5%，改善了整個配電系統的電壓質量；重構前系統有功損耗為226.05 kW，重構后系統有功損耗為99.67 kW，降低了56.03%。

表2 69節點系統配電網絡重構結果

圖2 69節點系統重構前后節點電壓比較

3 結 論

(1)提出了以有功損耗最小為目標函數的配電網絡重構方法,該方法利用Kruskal算法在配電網所有開關閉合的情況下,將線路電壓平衡指數為權值,通過尋找圖的最小生成樹初步優化網絡,為后續的細致優化提供一個可行的初始解。通過Kruskal算法的初步優化使得所提算法不依賴網絡的初始結構，具有更好的適用性。

(2)通過動態調整各條邊的權值并反復迭代進行支路交換操作，細致優化網絡,進一步尋找滿足目標函數的網絡拓撲,兩個常用算例表明該算法取得了滿意的效果。

通過對以上算例的分析可知,利用算法對網絡進行重構后,網絡的供電電壓質量明顯提高,有功損耗也大為降低,重構效果明顯，與此同時適用不同規模的配電網絡。

[1] 王守相,王成山.現代配電系統分析[M].北京：高等教育出版社，2007.

[2] 王磊,柯麗芳,姚李孝,等.基于最短路算法和最小節點電壓法的配電網絡重構[J].電網與清潔能源,2011,27(6):4-7.

[3] 楊建軍,戰紅.基于圖論的改進遺傳算法在配網重構中的應用[J].電力系統保護與控制,2010,38(21):122-125.

[4] 畢鵬翔,劉健,張文元.以提高供電電壓質量為目標的配網重構[J].電網技術,2002,26(2):41-43.

[5] 余貽鑫,段剛.基于最短路算法和遺傳算法的配電網絡重構[M].中國電機工程學報,2000,20(9):44-49.

[6] Daniel P Bernardon,Luciano L Pfitscher,Luciane N Canha.Smart Grid Concepts Applied to Distribution Network Reconfiguration[C].Universities Power Engineering Conference(UPEC), 47th International 2012：1-6.

[7] Miguel Arias-Albornoz.Distribution Network Configuration for Minimum Energy Supply Cost[J].IEEE Transactions on Power Systems, 2004(1)：538-542.

[8] 許立雄，呂林，劉俊勇.基于改進粒子群優化算法的配電網絡重構[J].電力系統自動化，2006,30(7):27-30.

[9] 李振坤，陳星鶯，余昆,等.配電網重構的混合粒子群算法[J].中國電機工程學報，2008,31(28):35-41.

[10] 陳春，汪沨，劉蓓，等.基于基本環矩陣與改進和聲搜索算法的配電網重構[J]. 電力系統自動化，2014，38(6):55-60.

[11] 王磊,呂娟,張強. 基于最小生成樹算法的配電網絡重構[J].陜西電力，2009(1)：13-17.

[12] 龔勛.圖論與網絡最優化算法[M].重慶：重慶大學出版社,2009.