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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

1.1 分層布局的思想

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

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

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

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

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

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

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

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

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

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

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

1.3 避免交叉的布局優(yōu)化算法

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

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

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

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

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

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

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

2 拓撲圖自動生成算法的實現(xiàn)

2.1 數(shù)據(jù)預處理及單條饋線布局數(shù)組的生成

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

2.1.1 生成拓撲圖前的預處理

1）設備和連接的表示

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

2）數(shù)據(jù)預處理

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

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

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

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

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

2.1.2 單條饋線布局數(shù)組的生成

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

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

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

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

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

2.2 兩兩變電站間布局數(shù)組的生成

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

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

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

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

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

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

如圖7所示。

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

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

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

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

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

2.3 所有變電站之間布局數(shù)組的生成

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

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

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

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

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

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

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

2.4 配電網全網布局數(shù)組的生成

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

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

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

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

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

如果全網布局數(shù)組中某兩點間存在相互連接，就在這兩點之間生成一條邊。將所有的互聯(lián)關系均用邊替代[17]，即可生成配電網全網的拓撲接線圖。以圖13所示的全網布局數(shù)組為例，對應生成的拓撲接線圖如圖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 高壓配電網拓撲布線圖的實現(xiàn)

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

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

3.2 中壓配電網拓撲布線圖的實現(xiàn)

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

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

4 結論

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