基于圖論的配電網規劃問題

曹磊

摘 要：以城鎮配電變電站選址和設計最佳配電線路為研究背景，討論了將配電網絡抽象為賦權圖后圖元及權值的確定方法，構造算例，采用最短路徑Dijkstra算法和Kruskal最小生成樹算法進行了求解。

關鍵詞：配電網；賦權值圖；Kruskal算法；Dijkstra算法

1 配電網拓撲圖圖元的確定

圖是反映對象之間關系的一種分析工具，節點、線段、方向是圖的三要素。如果在圖的每條線段e上都賦予一個非實數ω（e），則稱G為一個賦權圖，ω（e）稱為線段e的權值，權值可以描述線段具有的特性。

1.1 節點

從單純的數學對應關系上來說，一個負荷點或是一個線路交點都可以對應圖中的一個節點，但實際情況是，配電網絡中包含有不勝枚舉的負荷、設備或線路交叉點，如果都將其獨立視為節點將帶來海量的計算與理論分析，勢必使研究工作難以正常進行。根據相關要求，城市配電網應根據電壓等級、負荷密度和運行管理的需要劃分成若干個相對獨立的分區配電網。各個分區以現狀和規劃的主要路網、水系等為界，區域范圍內的負荷數量較為集中，負荷類型較為一致，理論上可以將眾多的負荷看作是一個整體進而抽象為一個節點。因此拓撲圖中的一個節點可以等效一個實際的配電分區。

1.2 線段

圖論中的線段代表節點之間的聯系，其長短曲直對拓撲結構分析不會造成影響。在配電網絡拓撲結構中，線段并不是直接代表實際的輸電線路，而代表的是可能架設主干線路的輸電走廊。

1.3 權值

配電變電站選址和設計配電線路的問題，兩者的分析方法不同，故在同一個拓撲圖上，同一條線段會出現兩個不同的權值ω1和ω2。

在進行負荷預測的前提下，配電變電站的合理選址需要綜合考慮3個原則：等負荷原則A，初始投資最小化原則B，運行費用最小化原則C。原則A主要適用于年負荷變化量較小的場合。原則B主要考慮的是配電線路的架設問題，適用于銅芯導體消耗量大的場合。原則C適用于負荷的年最大計算負荷運行小時數相差很大的場合，運行費用制約著變電站運行的經濟性。3種原則有各自的適用范圍，彼此有普遍適用性，共同作用影響著變電站的選址：

λ1、λ2、λ3為權重系數，取值越大，說明優先考慮程度越高。ω1i就是配電網絡拓撲圖中第i條線段的權值。

在進行配電線路的規劃中，ω2i是指第i條輸電走廊架設輸電線路的建設費用wc（主要包括線路材料費用和施工費用）和運行費用wo（主要是線路損耗）之和：

wc一般按照供電部門提供的單位工程造價計算而得，wo根據線損公式計算可得。

2 圖論算法及算例

將變電站選址、設計配電線路問題轉化為拓撲問題后求解，其實質是基于線段權值和點線連接關系構造矩陣，再利用一定的圖論算法進行求解。當變電站節點與配電分區的節點合并時，合并節點與其他節點就構成了一種最短路關系，所以求解最短路徑問題即可選擇出最佳的變電站建設位置。賦權圖中必然會包含賦權的樹T，T中所有樹枝的權值最小時，稱樹T為該圖的最小生成樹。設計最佳配電線路問題就屬于最小生成樹問題，配電線路相當于拓撲圖中的最小樹，既要連接所有配電分區（節點），又要最大程度保證運行經濟性（權值之和最小）。本文根據如下算例，利用Dijkstra算法和Kruskal算法分別求解最短路徑和最小生成樹。

城鎮某區域內有12個配電分區抽象等效為12個節點。各供電分區之間存在可能架設配電線路的輸電走廊，等效為節點之間的14條線段。變電站選址和設計配電線路問題的賦權值圖分別為圖1和圖2。

利用Matlab編程求解可得變電站選址問題計算結果為：

第i行的元素之和為：213，153，111，99，121，133，99，103，119，137，145，177。代表節點i到其他各節點最短路徑之和。可以看出99為最小值，V4和V7到其他節點的最短路徑和最小，故應選擇v4或v7建設配電變電站。

設計配電線路問題的計算結果所構成的最小生成樹見圖3。

該最小生成樹（圖中較粗的線段）即為最佳配電線路的走向，輸電走廊v2v3，v3v9，v8v11未得到利用。

綜合以上兩個問題結論，既變電站選址為v4或v7節點，設計的配電線路為：

v1v2—v2v6—v5v6—v3v4—v4v5—v4v7—v7v8—v10v11—v10v12—v9v10—v8v9。

參考文獻

[1]樂樂.基于配電網自動化的網絡拓撲分析[D].浙江大學，2008.

[2]蘇建國，葉劍芳.城市配電網變電站選址優化[J].河南電力，2002，（3）：11-14.