聯(lián)絡(luò)型區(qū)域接線圖的自動排布算法

梁 艷 董 昕 鐘小泱 鄭 鵬 陸 璐

（成都工業(yè)學(xué)院，四川 成都 611730）

0 引言

區(qū)域接線圖是配電管理系統(tǒng)實(shí)時監(jiān)控的重要圖形依據(jù)。配電線之間的聯(lián)絡(luò)關(guān)系反應(yīng)了供電情況，是供電運(yùn)行、故障排除的重要依據(jù)。排布清晰、布局科學(xué)的聯(lián)絡(luò)型區(qū)域接線圖為實(shí)現(xiàn)智能配網(wǎng)調(diào)度提供了可能。

區(qū)域接線圖的自動排布研究主要集中于拓?fù)渌阉鲀?yōu)化和布圖優(yōu)化兩方面?；趫D論對配電網(wǎng)的電氣設(shè)備數(shù)據(jù)進(jìn)行建模，使用關(guān)聯(lián)矩陣法和樹搜索法來分析配電網(wǎng)的拓?fù)浣Y(jié)構(gòu)[1-2]，搜索性能良好。基于深度優(yōu)先搜索算法，在構(gòu)造拓?fù)浣Y(jié)構(gòu)時只考慮閉合的刀閘和開關(guān)，降低了算法復(fù)雜性并提高了搜索速度[3]。從外向內(nèi)逐次布局的環(huán)形布局算法，可以支持少量聯(lián)絡(luò)開關(guān)的布局，對存在多個環(huán)的復(fù)雜線路則需進(jìn)行手工調(diào)整[4]。基于模型驅(qū)動及層次結(jié)構(gòu)的一次接線圖生成方法，布局布線效果良好[5]。

已有研究解決了單條或多條獨(dú)立配電線拓?fù)渌阉鞯男阅軉栴}，布圖美觀，可以基本滿足用戶的需求。但是難以支撐具有各種聯(lián)絡(luò)關(guān)系的區(qū)域接線圖的成圖需求。聯(lián)絡(luò)型區(qū)域接線圖，在拓?fù)錂z索和布圖上構(gòu)成環(huán)，大大增加了算法復(fù)雜性；多條配電線的聯(lián)絡(luò)關(guān)系往往顯示不清晰，無法快速找到聯(lián)絡(luò)點(diǎn)；另外，聯(lián)絡(luò)點(diǎn)如果發(fā)生變化，快速重新布圖并快速更新區(qū)域接線圖的效率低，無法滿足實(shí)時監(jiān)控要求。

該文基于圖論建模，以橫平豎直算法為布圖[6]策略，針對已有研究無法支撐聯(lián)絡(luò)型區(qū)域接線圖的自動排布的現(xiàn)狀，提出跨越聯(lián)絡(luò)開關(guān)進(jìn)行拓?fù)渌阉?，對目?biāo)電氣數(shù)據(jù)構(gòu)建有向且有環(huán)的樹，布圖階段先計算設(shè)備坐標(biāo)、再走線，完成具有手拉手聯(lián)絡(luò)關(guān)系的區(qū)域接線圖的排布。實(shí)驗(yàn)表明，該算法搜索性能良好，布圖美觀，多條配電線的聯(lián)絡(luò)關(guān)系一目了然，具有工程應(yīng)用價值。

1 建立數(shù)據(jù)模型

對構(gòu)成區(qū)域接線圖的配電線上的設(shè)備和線路，建立基于CIM（公共信息模型）的數(shù)據(jù)模型[6]。該文重點(diǎn)討論聯(lián)絡(luò)點(diǎn)處拓?fù)鋽?shù)據(jù)的搜索和建模策略。總體策略為依據(jù)搜索范圍內(nèi)的配電線的電氣數(shù)據(jù)，建立線路的樹結(jié)構(gòu)：對于相互沒有聯(lián)系的線路，建立各自獨(dú)立的有向樹；有聯(lián)絡(luò)關(guān)系的多條線路，共同構(gòu)建一棵樹。具體如下。

建模規(guī)則1：一條配電線構(gòu)成的區(qū)域接線圖的搜索范圍是以開閉所的出線開關(guān)或者變電站的配電線出線對應(yīng)的節(jié)點(diǎn)為起點(diǎn)，向負(fù)荷側(cè)沿線路搜索線路和設(shè)備的拓?fù)鋽?shù)據(jù)，直到線路末端，停止線路的搜索。在搜索過程中，如果遇到聯(lián)絡(luò)開關(guān)，則繼續(xù)搜索到另一個變電站的配電線出線點(diǎn)（另一個變電站作為普通節(jié)點(diǎn)處理）?；趫D論理論，一條配電線可建立一棵有一條1 級分支和若干條K 級分支（K ≥1）的有向樹[6]。

建模規(guī)則2：N（N ≥1）條區(qū)域接線圖的搜索，每條配電線的搜索遵照一條配電線的搜索規(guī)則，逐一搜索出N條配電線的線路和設(shè)備數(shù)據(jù)。對N 條區(qū)域接線圖的搜索結(jié)果進(jìn)行數(shù)據(jù)建模，如果N 條配電線中存在聯(lián)絡(luò)關(guān)系，則記手拉手構(gòu)成聯(lián)絡(luò)關(guān)系的聯(lián)絡(luò)線路為M（1 ≦M ≦N）對。N 條配電線構(gòu)成的區(qū)域接線圖將依據(jù)線路彼此的聯(lián)絡(luò)關(guān)系建立N-M（N＞M）棵有向樹；當(dāng)N 條配電線兩兩互為聯(lián)絡(luò)關(guān)系，即N=M 時，N 條配電線建立一棵有向樹。

2 聯(lián)絡(luò)型區(qū)域接線圖的自動排布

自動排布算法包括搜索線路和設(shè)備、建立線路樹結(jié)構(gòu)、建立關(guān)鍵路徑和排布4 個步驟。建立線路樹是該算法的關(guān)鍵。

2.1 搜索線路和設(shè)備

依據(jù)建模規(guī)則搜索用戶所選擇的所有配電線的電氣數(shù)據(jù)，即準(zhǔn)備好排布所需要的線路和設(shè)備的電氣數(shù)據(jù)。在搜索過程中，記錄聯(lián)絡(luò)開關(guān)數(shù)據(jù)信息，以備生成具有多條聯(lián)絡(luò)關(guān)系的區(qū)域接線圖使用。當(dāng)所有需要生成區(qū)域接線圖的線路全部搜索完畢，建立樹結(jié)構(gòu)。

2.2 建立線路樹結(jié)構(gòu)

以圖論為基礎(chǔ)，將搜索的設(shè)備（包括電源點(diǎn)、開關(guān)節(jié)點(diǎn)、T 節(jié)點(diǎn)、線路末梢點(diǎn)、聯(lián)絡(luò)開關(guān)等）作為點(diǎn)，線路作為有向邊，建立有向且有環(huán)的樹結(jié)構(gòu)（該樹的每個子節(jié)點(diǎn)可能有多個父節(jié)點(diǎn)，每個父節(jié)點(diǎn)也可能有多個子節(jié)點(diǎn)）。建立線路樹結(jié)構(gòu)的過程具體如下。

步驟1：從配電線的出線開始，在已經(jīng)搜索出的線路和設(shè)備的電氣數(shù)據(jù)上進(jìn)行搜索。

步驟2：按照深度優(yōu)先遞歸搜索，穿過聯(lián)絡(luò)開關(guān)，一直搜索至線路末端或另一個變電站出線節(jié)點(diǎn)為止。在搜索的過程中建立具有深度信息、父節(jié)點(diǎn)和子節(jié)點(diǎn)數(shù)據(jù)域，可雙向搜索的樹；同時，設(shè)置變電站配電線出線為已經(jīng)建立樹結(jié)構(gòu)的標(biāo)志；建立好的線路樹，存入樹表。

步驟3：重復(fù)步驟1 和2，完成所有線路樹的構(gòu)建。特別地，由于該樹有向且有環(huán)，在搜索過程中構(gòu)成環(huán)時做特殊處理。搜索過的每條路徑上的節(jié)點(diǎn)存儲在一個臨時隊列中，并且設(shè)置已訪問標(biāo)記。當(dāng)再次訪問到該隊列中已經(jīng)訪問過的節(jié)點(diǎn)時，說明構(gòu)成環(huán)，開始進(jìn)行節(jié)點(diǎn)的回退操作，一直回退至可選擇其他不構(gòu)成環(huán)的路徑為止。最終隊列中的全部節(jié)點(diǎn)，加入樹結(jié)構(gòu)的父子節(jié)點(diǎn)關(guān)系隊列中，此條路徑搜索成功。

圖1 電氣數(shù)據(jù)搜索結(jié)果

2.3 建立關(guān)鍵路徑

根據(jù)已經(jīng)建立的樹結(jié)構(gòu)，標(biāo)識樹的分支級數(shù)和分支添加到排布圖的順序。首先標(biāo)識1 級分支（每棵樹只有一條0 級分支）第1 個參與排布；然后依據(jù)2 級分支的根節(jié)點(diǎn)在1 級分支中的節(jié)點(diǎn)順序，逐個標(biāo)識2 級分支的添加順序；依次標(biāo)識完所有分支的添加順序。

2.4 排布

遍歷已經(jīng)建立的每棵樹的關(guān)鍵路徑，按照分支添加順序，依次排布每一個分支、計算分支上各個節(jié)點(diǎn)坐標(biāo)，最終形成不交叉、不重疊且橫平豎直排布的區(qū)域接線圖。具體流程如下。

步驟1：遍歷第一棵樹。按照分支的添加順序，遍歷每條分支上的設(shè)備，計算坐標(biāo)。首先，遍歷1 級分支，分支上的節(jié)點(diǎn)按照從父到子的順序，依次計算每個設(shè)備的坐標(biāo)；記錄該分支上設(shè)備的最大T1（xmax，ymax）、最小T1（xmin，ymin）坐標(biāo)值。然后，遍歷第一個2 級分支，分支上的節(jié)點(diǎn)按照由父到子的順序，依次計算每個設(shè)備的坐標(biāo)；記錄該分支上設(shè)備的最大T2（xmax，ymax）、最小T2（xmin，ymin）坐標(biāo)值。此時，將此2 級分支與已經(jīng)添加的1 分支進(jìn)行交叉重疊判斷，如果無交叉，則坐標(biāo)計算成功；否則，從相交點(diǎn)開始，通過左右平移或上下平移的方式，修正所有相交設(shè)備的坐標(biāo)[6]。

步驟2：同理，完成樹的每條分支的坐標(biāo)計算，記錄整棵樹的最大縱坐標(biāo)Ytree1。

步驟3：遍歷第N（N ≥2）棵樹，參考第一棵樹的最大縱坐標(biāo)Ytree1，同上計算第N 棵樹所有設(shè)備坐標(biāo)。

步驟4：最后，依據(jù)畫布大小，整體縮放區(qū)域接線圖內(nèi)的所有設(shè)備，保證圖形全部顯示在窗口內(nèi)。

3 實(shí)例

3.1 搜索線路和設(shè)備

依據(jù)用戶選擇的區(qū)域接線圖的配電線，搜索出每條配電線相關(guān)的線路、設(shè)備和拓?fù)鋽?shù)據(jù)。在此用戶選擇了3 條配電線路Fdr1、Fdr2、Fdr3，則搜索得到三條線路的電氣數(shù)據(jù)，有1 條獨(dú)立線路，2 條有聯(lián)絡(luò)關(guān)系的線路。每條配電線都是從變電站的出線開關(guān)開始向負(fù)荷側(cè)搜索，直到線路末端停止。搜索結(jié)果如圖1 所示，圖中包括變電站SS1、SS2和SS3，站房設(shè)備S1和S2，1 個聯(lián)絡(luò)開關(guān)LSW，3 個黑色矩形表示的開關(guān)及若干個菱形懸掛設(shè)備。聯(lián)絡(luò)開關(guān)為配電線Fdr2 和Fdr3 的聯(lián)絡(luò)點(diǎn)。3 條配電線中的電氣設(shè)備和線路構(gòu)成聯(lián)絡(luò)型區(qū)域接線圖的基礎(chǔ)電氣數(shù)據(jù)。

3.2 建立線路樹

依據(jù)已經(jīng)搜索得到的配電線的電氣數(shù)據(jù)，建立樹結(jié)構(gòu)。由于3 條配電線中，F(xiàn)dr1為獨(dú)立的配電線，其對應(yīng)的樹為Tree1。Fdr2和Fdr3為有聯(lián)絡(luò)關(guān)系的配電線，共同建立一棵樹，對應(yīng)樹Tree2，如圖2 所示。設(shè)備樹Tree2的構(gòu)建過程中，從變電站SS2的出線開關(guān)開始搜索，跨越聯(lián)絡(luò)開關(guān)LSW，一直搜索至線路末端或變電站SS3的出線開關(guān)停止，所以，設(shè)備樹Tree2由配電線Fdr2和Fdr3的電氣設(shè)備共同組成，且共享聯(lián)絡(luò)開關(guān)LSW。

3.3 建立關(guān)鍵路徑

依據(jù)已經(jīng)建立的樹結(jié)構(gòu)，針對每一棵樹，建立關(guān)鍵路徑。依據(jù)樹深度，搜索每條路徑包括的結(jié)點(diǎn)，標(biāo)識1 級分支、分級分支，直至標(biāo)記完所有分支，并標(biāo)記分支添加的順序，以此作為分支計算坐標(biāo)的順序。Tree1包括一條1 級分支和3 條2 級分支，按照2 級分支的根節(jié)點(diǎn)在1 級分支中出現(xiàn)的順序，識別3 條2 級分支。Tree2包括一條1 級分支和4 條2 級分支，按照2 級分支的根節(jié)點(diǎn)在1 級分支中出現(xiàn)的順序，識別4 條2 級分支。

根據(jù)上一步建立的樹結(jié)構(gòu)，Tree1是由Fdr1建立的樹，Tree2是由Fdr2和Fdr3共同建立的一棵樹。在此對Tree1和Tree2建立關(guān)鍵路徑，并標(biāo)識分支等級及分支的添加順序。自動布圖效果的示意圖，如圖3 所示。

特別地，在做設(shè)備橫平豎直化排布處理時，為了避免交叉，二級分支在排布時進(jìn)行上下交錯排布處理，在圖例中，Tree1的第一條2 級分支2.1 自下向上排布，第二條2 級分支則自上而下排布。這樣極大的減少了交叉的可能，節(jié)省了相交平移設(shè)備的坐標(biāo)修正成本。

Tree2由2 條配電線構(gòu)成，在設(shè)備樹構(gòu)建環(huán)節(jié)已經(jīng)將兩條線路融合。排布過程中，會將聯(lián)絡(luò)開關(guān)LSW 作為普通線路中的節(jié)點(diǎn)進(jìn)行處理而不是作為線路末端。在實(shí)例情形中，聯(lián)絡(luò)開關(guān)作為1 級分支節(jié)點(diǎn)參與排布，為了能快速識別聯(lián)絡(luò)點(diǎn)，可在著色時高亮顯示。變電站SS3，也作為普通站房節(jié)點(diǎn)參與排布，成為2 級分支的一部分。

3.4 應(yīng)用分析

圖3 構(gòu)成了3 條配電線組成的聯(lián)絡(luò)型區(qū)域接線圖，在實(shí)際工程應(yīng)用中，聯(lián)絡(luò)開關(guān)的屬性和開合狀態(tài)有可能發(fā)生變化，增量更新顯示范圍，快速重新成圖供工程監(jiān)控人員使用，尤其重要。在該實(shí)例中，更改聯(lián)絡(luò)開關(guān)LSW 的狀態(tài)為合且修改屬性為普通開關(guān)，則配電線2 的搜索范圍會增大。搜索算法快速搜索新范圍的電氣設(shè)備數(shù)據(jù)，然后在已有排布數(shù)據(jù)基礎(chǔ)上，繼續(xù)增量排布，在保留已有排布效果的同時大大提高了布圖速度。

圖2 設(shè)備樹結(jié)構(gòu)示意圖

圖3 自動布圖效果

4 結(jié)語

通過實(shí)驗(yàn)驗(yàn)證，該文提出的算法兼容各種聯(lián)絡(luò)關(guān)系的區(qū)域接線圖的自動布圖，具有良好的適應(yīng)性；對聯(lián)絡(luò)型線路的排布，聯(lián)絡(luò)點(diǎn)顯示清晰，方便工程人員監(jiān)控調(diào)度；聯(lián)絡(luò)關(guān)系發(fā)生變化時，基于已有拓?fù)鋽?shù)據(jù)基礎(chǔ)，可以快速重新構(gòu)建排布樹，效率高。算法遵守橫平豎直的排布原則，部分多聯(lián)絡(luò)架空線路的排布，有走線重疊的現(xiàn)象，需要手動調(diào)圖，對于這種情況，有待進(jìn)一步優(yōu)化。另外，排布過程中對于分支的上下交錯排布處理，雖然避免了相交的可能，但可能造成排布空間的浪費(fèi)。