基于分層布局思想的配電網拓撲圖自動生成算法

楊貴云，吳倩，曹彥昆，侯曉宇，孫華，王踐

（天地電研(北京)科技有限公司，北京市 昌平區 102206）

0 引言

面對電網的“差異化”用電、可靠性要求，以及國家電網公司日益強化的“精益化管理”的要求，亟待對配電網實施以問題診斷為基礎、以遠景目標網架為導向、以項目落地為目標的規劃工作。

配電網規劃工作注重宏觀網架結構[1-6]，直接在地理信息系統(geographic information system，GIS)接線圖上做規劃非常不方便，原因如下：GIS圖中主干接線不清晰，且圖中涉及的細節太多；在雜亂無章的接線圖上無法辨識電網問題，進而無法制定方案及貫徹以問題導向、以目標引領的規劃思路，規劃結果在GIS圖上也無法很好地得到展現和解釋。

為了便于審查規劃項目，需要從多個維度分時間、分空間、依指標、按地理接線、按拓撲接線等方式出圖出表，使之化繁為簡、分而審之。網格化規劃圖表多，任務重，遇到上級電源、市政規劃、導向目標、政策環境發生變化時，所有年份圖紙都要修改，所有相關表格都要重做，工作量極大。如果開發出能夠自動成圖的規劃工具，將大大節省人力[7]。

綜上，開發出自動生成拓撲接線圖的網格化規劃軟件是十分必要的。而拓撲生成算法正是自動生成配電網拓撲接線圖的核心[8]。

拓撲圖的生成涉及圖形的自動布局問題[9]，至今都沒有很好的算法，拓撲圖自動生成算法的實現難度包括以下方面[10]：

1）對象的擺放。對象包括變電站、開關站(開閉所)、變壓器等，這些對象對整個圖形的布局起到了決定性的作用，其位置將會影響拓撲圖的可讀性。

2）線路的自動正交化。在拓撲圖上，所有的線路都是橫平豎直排列，平行線路之間的距離要相等。

3）線路的交叉最小化。在拓撲圖上必須盡量保證盡可能減少正交跨越。

已有的拓撲算法大多是基于優化函數的，目標是使圖中的交叉最小化[11]。其中：有些算法需要經過很多次迭代(耗時很長)才能獲得最優或次優解，如改進遺傳算法[12]；有些算法雖然對于少量饋線的布局具有良好的效果，但隨著饋線和變電站數量的增加，算法很難收斂，如模擬退火算法[13]。因此，目前對于網格化規劃仍沒有成熟和適用的算法。

本文通過橫向對比各大主流拓撲生成算法、深度挖掘現狀拓撲圖生成的痛點問題，基于分層求解的思想，借鑒圖論的知識，利用深度優先遍歷(depth first search，DFS)算法，提出拓撲圖自動生成算法。該算法避免了因直接一次性求取所有設備在接線圖中合理坐標而可能導致的求解過程高度復雜甚至無解的問題，降低了空間復雜度。另外，每層布局都使用深度優先遍歷算法，降低了軟件開發的難度。最后，通過工程實際應用，驗證了該算法的有效性和適用性。

1 配電網拓撲圖自動生成算法的基本思路

拓撲圖自動生成算法的目的是求出配電網中每個設備在圖紙中的具體位置，即X軸和Y軸坐標。為了實現橫平豎直排布設備的要求，本文借助二維數組找出每個設備在圖紙中的行、列序號，實現等間距布置。

1.1 分層布局的思想

拓撲圖自動生成的實現分為3層：第1層是確定單條饋線的拓撲布局；第2層是確定兩兩變電站之間所有饋線的拓撲布局；第3層是確定所有變電站之間的拓撲布局。其中，第1層是基礎，目的是確定某一條饋線的拓撲接線，包括主干線和分支線。第2層是將每2個互有聯絡的變電站之間所有饋線的連接關系確定下來。第3層是確定各變電站在圖紙上的坐標位置及連接情況，即在所有變電站之間的布局數組中插入兩兩變電站之間的布局數組，就得到了整個配電網的拓撲布局數組。

實現這種拓撲圖自動生成算法，需要分以下5個步驟：

1）生成單條饋線的布局數組。通過DFS算法，將單條饋線上主干線和各分支線上的各設備及其相互之間的連接關系用二維數組的形式保存起來，生成單條饋線的布局數組。

2）生成兩兩變電站之間所有饋線的布局數組。在單條饋線拓撲圖的基礎上，將兩兩變電站之間所有饋線的連接關系用二維數組的形式保存起來，生成兩兩變電站間的布局數組。

3）生成所有變電站之間的布局數組。所有變電站之間的布局數組用于確定變電站間的布局。將所有電源和變電站抽象為圖的頂點，將兩兩變電站之間的連線抽象為邊。將所有變電站之間的連接關系用二維數組的形式保存起來，生成所有變電站間的布局數組。

4）生成配電網全網的布局數組。將兩兩變電站之間所有饋線的布局數組插入所有變電站之間的布局數組中，便可生成配電網全網的布局數組。

5）生成配電網全網的拓撲接線圖。根據配電網全網的布局數組，計算出各節點的行、列序號，即可生成配電網全網的拓撲接線圖。

1.2 有向圖中兩點間最大距離的求解算法

有向圖中兩點間最大距離的求解算法用于確定各設備在拓撲圖中的X軸坐標。配電網中單條饋線的布局數組、兩兩變電站間布局數組、所有變電站間布局數組的確定都是基于求解有向圖中兩點間最大距離的問題來實現的。

對于單條饋線的拓撲，確定兩點間最大距離即是確定最長單條饋線及其起、止點的X軸坐標，這條最長的路徑被定義為主干線。對于兩兩變電站間的拓撲，確定兩點間最大距離即是確定所有饋線中最長饋線的起、止點的X軸坐標，在此基礎上可確定各線中所有設備的X軸坐標。對于所有變電站間的拓撲布局，確定兩點間最大距離即是確定相隔最遠的兩變電站的X軸坐標，進而確定中間各變電站在最終圖紙中的X軸坐標。

定義無任何前驅的點為初始點，初始點的入度為0，無任何后繼的點為終止點，終止點的出度為0[14]。DFS從每個初始點開始按照設定方向遍歷到圖中所有可達到的終止點，不斷進行深度優先搜索的遞歸調用，直到找到某個給定初始點到給定終止點的最大距離[15]。

1.3 避免交叉的布局優化算法

避免交叉的布局優化算法用于確定配電網所有設備在最終拓撲圖中的Y軸坐標。結合前述設備的X軸坐標，即可確定所有設備在圖紙中的位置。

確定設備的Y軸坐標，可以通過將兩兩變電站間的布局數組插入所有變電站間的布局數組中，以形成全網布局數組的方式來實現。步驟如下：

1）確定全網拓撲接線圖的大小(行數和列數)。以共有9個變電站(V0,V1,…,V8)的配電網為例，所有變電站間的拓撲布局數組如圖1所示。將兩兩變電站間的布局數組的行、列信息填充到所有變電站間的布局數組中，便得到如圖2所示的配電網全網的布局數組。

圖1 9個變電站間的拓撲布局數組 Fig. 1 Topology layout array of 9 substations

圖2 9個變電站的全網布局數組 Fig. 2 Distribution network layout array of 9 substations

按照以下方法統計出配電網全網拓撲接線圖所占用的總行數和總列數：①統計圖2數組的第1行中有連接關系的所有相鄰2列的布局數組(即兩兩變電站間的布局數組)的行數(每條主干線和分支線分別占一行)，可得到第1行中所有列之間 的行數R1,R2,…,Rn-1，那么第1行的總行數為max(R1,R2,…,Rn-1)=RL1，以此類推，統計出所有其他各行的總行數RL2,RL3,…,RLm，即可得到全網拓撲接線圖需要占用的總行數R=RL1+RL2+…+RLm；②統計圖2數組的第1、2列對應的各行中有連接關系的所有相鄰2行的布局數組的列數(開關、變壓器和變電站各占一列)，可得到各行的第1、2列之間的列數分別為L1,L2,…,Lp-1，那么第1、2列的總列數為max(L1,L2,…,Lp-1)=LR1，以此類推，統計骨架布局中所有其余相鄰2列的兩變電站之間的總列數LR2,LR3,…,LRn-1，即可得到整個拓撲接線圖需要占用的列數L=LR1+LR2+…+LRn-1。

2）計算出每個設備的位置坐標。根據統計出的全網拓撲數組的行數R和列數L，可在A3或A4大小的圖紙上計算出等間隔布置時每個設備的X軸和Y軸坐標，這樣就實現了各變電站及各設備在圖紙上不交叉的等距分布。

2 拓撲圖自動生成算法的實現

2.1 數據預處理及單條饋線布局數組的生成

單條饋線的拓撲是配電網全網拓撲圖實現的基礎。首先根據DFS確定兩點間最大距離所經過的路徑為主干線，進而確定主干線的各個頂點，并使主干線頂點均勻分布；再繼續遍歷，確定各分支線及其頂點，使各分支線頂點等距分布，每條分支線與主干線各占一行；直到本條饋線上所有頂點的連接關系均體現出來為止。

2.1.1 生成拓撲圖前的預處理

1）設備和連接的表示

單條饋線是以電源或變電站為起始點，以設備為終止點的線段。電源或變電站、開關、環網柜、柱上變等均用“頂點”表示，設備之間的連接關系用“邊”表示。

2）數據預處理

數據預處理的主要功能有重復線段的刪除、相交線段的判斷及處理、頂點匹配、懸線處理等[16]。

重復線段是指2條線段之間的最大距離小于設定容差的線段。重復線段的刪除應用于刪除重復的架空或電纜線路。

相交線段的判斷需要全面考慮各種相交情況。約定：①當點與線段的距離小于容差時，將其視為由實測或繪制時造成的誤差，判定為相交，當大于容差時，判定為不相交；②當2條線段不相交時，計算它們的虛交點Q，若Q點在其中一條線段上，且Q點距離另一條線段近端點的距離小于容差，則將另一條線段延長至虛交點Q。相交線段的判斷和處理應用于合并串、并聯連接的導線設備。

頂點匹配是把一定容差范圍內線段的端點作為一個頂點。約定：求解擬匹配點的平均坐標(包括X軸和Y軸坐標)，以此點為圓心，以一定的容差為半徑畫圓，將落在圓內的線段刪除，以圓心為頂點，形成新的線段。頂點匹配應用于刪除多余開關、環網柜等設備，僅保留其中一個。

懸線是指沒有與周圍的線段建立起關聯關系的線段。懸線處理應用于刪除不完整線路。

2.1.2 單條饋線布局數組的生成

運用DFS算法確定單條饋線的主干線及各分支線。運用DFS找到以節點V0為起點、V11為終點的最長有向路徑P (V0,V1,V2,…,V11)，長度為11，如圖3中藍色線所示。各分支線的選取及節點順序的確定與主干線類似，約定所有分支線均向右擴展。

圖3 從V0節點開始的最長路徑排序 Fig. 3 Longest path sort from V0 node

按照上述規則和步驟讀取并解析每條饋線的設備及其拓撲連接關系，將設備及其連接關系轉化成單條饋線的布局數組，如圖4所示。

圖4 單條饋線的布局數組 Fig. 4 Layout array of single line

各節點在布局數組中的行、列序號分別代表這個節點在拓撲圖中的位置。根據饋線布局數組，可以很方便地得到饋線的拓撲圖。

2.2 兩兩變電站間布局數組的生成

生成兩兩變電站間布局數組的步驟如下：

1）線段方向的修改。假定2條饋線的方向如圖5(a)所示。經檢查，不符合從左到右的方向假定，因此將線段方向進行如圖5(b)所示的修改。

圖5 各饋線方向的修改 Fig. 5 Direction modification of each line

2）找出兩兩變電站之間的所有饋線，合并起、止點，相關節點重新編號。2個變電站之間的饋線往往不止一條，需要找出兩者之間的所有饋線，做到不重不漏。可保持節點較多的饋線中各節點的編號不變，將其他饋線的編號重新排列，形成新拓撲圖，如圖6所示。

圖6 兩變電站之間2條饋線調整后的拓撲圖 Fig. 6 Topological diagram of two lines between two substations after adjustment

3）確定兩變電站間拓撲的布局數組。按照重新修改的線段方向和調整之后的頂點編號，根據DFS算法，得到兩變電站間2條饋線的布局數組，

如圖7所示。

圖7 兩變電站間2條饋線的布局數組 Fig. 7 Layout array between two lines of two substations

如果兩變電站之間的2條饋線有公共連接點，需要分情況進行處理，其中較難處理的情況有如下2種：

①交點在其中一條饋線的末端且有環路，如圖8所示。圖8(a)中的2條饋線在其中一條饋線分支線的末端V20處相交，且有環路。在這種情況下，可保持路徑最長、設備最多的一條饋線不 動，本著使交叉點最少的原則，將環路信息放在布局數組的底部；調整之后的布局數組如圖8(b)所示。 況下，考慮將環路信息放在布局數組的頂部，如圖9(b)所示。

圖8 兩饋線末端有交點且有環路的情況 Fig. 8 Case that there is an intersection and a loop at the end of two lines

圖9 兩饋線中間有交點且有環路的情況 Fig. 9 Case that there is an intersection and a loop between two lines

2.3 所有變電站之間布局數組的生成

生成所有變電站之間布局數組的具體步驟 如下：

1）所有變電站間連接關系的確定。將所有發電廠、變電站及其連接關系全部體現在有向圖中，如圖10所示，規定線段的方向為從左至右。

圖10 所有變電站間布局圖的方向定義 Fig. 10 Direction definition of layout of all substations

2）采用DFS算法求取變電站間的最大距離。以V0節點路徑排序(如圖11所示)為例，使用深度優先遍歷，直到確定節點V0—V5的最長路徑，從而可以確定節點V0—V5在二維數組中的位置。通過分析可知，二維數組中的行數和列數由各個節點的入度、出度和相互間的連接關系共同決定。

圖11 V0—V5節點路徑排序 Fig. 11 Path sorting from V0 node to V5 node

依照相同的方法，還可以確定圖11中節點V0—V8的最長路徑，從而得出節點V0—V8在二維數組中的位置。在所有初始節點到所有終端節點的最長路徑確定后，綜合起來便可確定所有節點在二維數組中的最終位置——所有變電站間的布局數組。圖12即為圖11中所有變電站間的布局數組。

圖12 各節點在二維數組中的位置 Fig. 12 Positions in a two-dimensional array of each node

2.4 配電網全網布局數組的生成

根據避免交叉的布局優化算法，可確定全網拓撲接線圖的行數和列數。在A3大小的圖紙上計算出拓撲圖等間隔布置時每個設備的X軸和Y軸坐標，使各變電站及各設備在圖紙上等距分布。

為簡化起見，在圖12所示的9節點(V0—V8)變電站間布局數組的基礎上僅填充V0和V1兩變電站間布局數組，從而生成配電網全網的布局數組，如圖13所示。

圖13 僅填充V0和V1兩變電站信息的9個變電站的 配電網全網布局數組 Fig. 13 Distribution network layout array of 9 substations filled with only V0 and V1 substation information

2.5 配電網全網拓撲接線圖的生成

根據上述求得的各變電站及各設備在圖紙上的X、Y軸坐標值，即可在圖紙上確定出各點(設備)的位置。

如果全網布局數組中某兩點間存在相互連接，就在這兩點之間生成一條邊。將所有的互聯關系均用邊替代[17]，即可生成配電網全網的拓撲接線圖。以圖13所示的全網布局數組為例，對應生成的拓撲接線圖如圖14所示。

圖14 僅填充V0和V1兩變電站信息的9個變電站的 配電網全網的拓撲接線圖 Fig. 14 Topology wiring diagram of distribution network of 9 substations filled with only V0 and V1 substation information

3 拓撲布線圖自動生成算例

3.1 高壓配電網拓撲布線圖的實現

應用拓撲圖自動生成算法對山東德州晶華網格2019年10 kV現狀電網進行自動拓撲布線，其拓撲圖如圖15所示。本次繪圖涉及變電站頂點20個，用時0.23 s。

圖15 德州晶華網格2019年10 kV現狀電網拓撲圖 Fig. 15 Topology of 10 kV power grid in Dezhou Jinghua in 2019

3.2 中壓配電網拓撲布線圖的實現

應用拓撲圖自動生成算法對山東德州晶華網格遠景年10 kV電網進行自動拓撲布線，其拓撲圖如圖16所示。本次繪圖涉及變電站頂點44個，用時0.42 s。

圖16 德州晶華網格遠景年10 kV電網拓撲圖 Fig. 16 Topology of 10 kV power grid in Dezhou Jinghua in future

4 結論

利用深度優先遍歷算法，提出了基于分層布局思想的配電網拓撲圖自動生成算法，該算法修正了遺傳算法等需經多次迭代才能獲得最優或次優解的問題，改進了退火算法等隨著饋線和變電站數量增加而難以收斂的問題。通過對國網德州供電公司城市電網規劃河東區晶華網格2019年10 kV現狀電網、遠景年10 kV電網進行自動拓撲布線，驗證了該算法的正確性、快速性和普適性。該算法生成的拓撲圖雖然能清晰、準確地反映線路之間的連接關系，但目前尚不能反映各條線路的相對地理位置。下一步，將考慮從兼顧電氣拓撲連接和相對地理位置的角度改進自動拓撲布局的算法。