陳巨龍 羅歡 陳實

【摘要】自動繪圖算法針對大規(guī)模電網的潮流圖自動生成是一個復雜的問題，本文采用兩部分來解決。針對廠站的自動布局問題，采用根據(jù)節(jié)點的實際經緯度擬合進通過因式分解后的網格中的算法。針對自動布線問題，首先采用線探索法對線路進行初步布線，再采用lee算法對線探索法無法確定的線路進行布線，最后根據(jù)網格通道布線的特定情況，調整線路位置與所占面積，達到避免線路不必要交叉的問題，同時也解決了線距過近等問題，最終實現(xiàn)了全局美觀。最后針對某省級電網模型的測試驗證了本文研究方法的有效性。

【關鍵詞】潮流圖;自動繪圖;線探索法

1.引言

傳統(tǒng)的潮流圖大都為人工繪制，隨著電網規(guī)模的逐年發(fā)展，原有的人工繪制好的潮流圖都趨于飽和，因此新增或者修改節(jié)點與線路將會耗費大量的時間與精力。現(xiàn)有的系統(tǒng)潮流圖功能很是單一，不能滿足技術人員的實時分析與互動校核的要求[1]。傳統(tǒng)的系統(tǒng)潮流圖是由不同技術人員繪制，因此在繪圖過程中往往缺乏一個統(tǒng)一的規(guī)范，例如節(jié)點的命名等，從而會引起今后的使用過程中的不便利的問題。

雖然國內外對電網的抽象圖智能生成有一定的研究，但是都是針對小規(guī)模的配網而言，對全省的主網潮流圖，包含近200節(jié)點的大規(guī)模電網使用智能算法自動繪圖尚屬首次。電氣圖的智能生成優(yōu)化問題，是一個NP難問題，其計算復雜度隨著節(jié)點和線路規(guī)模的增長呈幾何級數(shù)增長。因此，對于該問題無法在多項式時間內求得最優(yōu)解。而現(xiàn)有的各類進化算法，包括遺傳算法、人工神經網絡、模擬退火算法等均大量的計算時間，而且并不保證求得逼近最優(yōu)解的較優(yōu)解。而各類啟發(fā)式算法盡管計算速度較快，但是很容易使得目標函數(shù)陷入局部極值點而無法跳出，給優(yōu)化過程帶來難以處理的情況[2]。對于節(jié)點布局模塊，本文根據(jù)布局區(qū)域分辨率，對節(jié)點個數(shù)進行因式分解，根據(jù)節(jié)點的實際經緯度，將每個節(jié)點擬合進因式分解后的網格中。節(jié)點布局完成之后采用改進的線探索法[1]對節(jié)點間連線進行初步布線，對無法確定的線路采用lee算法進行布線，在完成整體布線之后，本文根據(jù)節(jié)點與線路的特點調整線路位置與所占面積解決線路重疊、線路之間距離過近、交叉等影響繪圖美觀的問題。

2.節(jié)點自動布局

2.1 根據(jù)節(jié)點個數(shù)的因式分解

由于電網節(jié)點的實際位置是以500kV變電站為中心，220kV變電站與發(fā)電廠為輻射點的格局，因此采用根據(jù)節(jié)點的實際經緯度來對節(jié)點進行布局可以使得整體布局以500kV電壓等級的節(jié)點為中心節(jié)點，220kV電壓等級節(jié)點為輻射點的發(fā)散形式予以表現(xiàn)，一方面可以符合調度員的認知習慣，同時也避免自動布線過程中由于節(jié)點間距離過長，從而使得線路過長的問題。布局所需數(shù)據(jù)為，變電站個數(shù)Ntrans，發(fā)電廠個數(shù)Ngen，每個節(jié)點的電壓等級Tilev與其所處的地理位置（經緯度）Tigeo，可以得出全網節(jié)點的總數(shù)Nsum。其中：

Nsum=Ntrans+Ngen ? ? ? ? ? ? ? ? ? ? ? ? （1-1）

再通過因式分解將Nsum分解為m×n，其中m與n都為整數(shù)，由于最終結果是在1280×720的區(qū)域中，因此m與n應滿足：

的關系。本文所設計的系統(tǒng)可以滿足200個節(jié)點的自動布局。因此：

m×n≤200 ? ? ? ? ? ? ? ? ? ?（1-3）

因式分解的過程為：

（1）確定布局系數(shù)k，其中k為：

k=1280/720（1-4）

其中：

m=k×n（1-5）

（2）確定布局區(qū)域網格的行數(shù)n與列數(shù)m，根據(jù)（1-5）與（1-3）可知：

k×n2=200 ? ? ? ? ? ? ?（1-6）

從而得出ms，ns，其中ms與ns為目標的因式分解。

2.2 根據(jù)節(jié)點實際經緯度的擬合網格算法

完成因式分解之后，再將布局區(qū)域分為ms×ns的網格，然后再根據(jù)每一個節(jié)點的經緯度，通過擬合算法將每個節(jié)點布置在ms×ns的網格中。下面介紹擬合網格算法。

（1）確定某地電網經緯度范圍（longitudemin，longitudemax），維度范圍（latitudemin，latitudemax）。

（2）確定電網所有節(jié)點的經緯度Tigeo，其中Tigeo的數(shù)據(jù)結構為（longitudei，longitudei）。

（3）搜索在經度范圍為（longitudemin，longitude1）的節(jié)點，其中：

（1-7）

得出第一列的廠站集合NUM1，再以此搜索（longitude1，longitude2），….，（longitudei-1，longitudei），….，（longitudemax-1，longitudemax），其中：

（1-8）

范圍之間的廠站，將各個區(qū)間經度的廠站以此分別列入集合NUM2，NUM3，…，NUMi，…，NUMmax中。

（4）將所有經度滿足（longitudemin，longi-tude1）之間的NUM1個節(jié)點布置在網格的第一列中，布置規(guī)則為根據(jù)NUM1集合中節(jié)點的緯度大小，緯度由高到低排入第一列的ns行中。若NUM1≥ns，求出NUM1east，其中：

NUM1east= NUM1-ns ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（1-9）

然后搜索出NUM1集合中NUM1east個經度最大，即最靠東的節(jié)點，將這類節(jié)點歸入NUM2集合中。若NUMi≥ns，則按照上述跪著求出NUMieast，其中：

NUMieast= NUMi-ns ? ? ? ? ? ? ? ? ? ? ? ? ? ? （1-10）

然后在NUMi集合中搜索出NUMieast個經度最大的，即最靠東的節(jié)點，將這類節(jié)點歸入NUMi+1集合中。

（5）本系統(tǒng)的自動布局的原則是盡可能使得全局均勻排布，即若NUM1<0.75ns，則會對第一列網格中留出很多空白網格，從而使得全局不美觀，因此按照上述原則，對這類集合進行修改。即若NUM1<0.75ns，則從NUM2集合中搜索NUM2west個廠站，其中：

（1-11）

這NUM2west個廠站是NUM2集合中經度最?。ㄗ羁课鳎┑膹S站，將NUM2west個廠站歸入第一列中，即放入NUM1集合中。NUMi集合也遵循上述原則，其中i=2、3、…、max。

3.線路的自動布線

自動布線的目標是將所有有聯(lián)絡關系的線路通過橫平豎直的折線段表示在繪圖區(qū)域中。

3.1 廠站出線位置規(guī)定

廠站的出線位置合理就可以很好避免布線過程中出現(xiàn)的不必要的交叉，考慮到廠站在圖形中的寬度與長度，本文規(guī)定廠站的橫向最多出7回線路，廠站的豎向最多出4回，下面為事先制定要的廠站出線位置規(guī)定。

圖1 廠站的出線位置規(guī)則

圖2 線探索的應用

對Vi節(jié)點的出線位置規(guī)定步驟為：

（1）確定與Vi節(jié)點，其坐標位置為（xVi，yVi）相關聯(lián)的節(jié)點Vj坐標位置（xVj，yVj）。

（2）判斷（xVi，yVi）與（xVj，yVj）的大小關系。如Vi與Vj兩節(jié)點的位置坐標滿足xVi>xVj，yVi>yVj時，Vj則在圖1中B方向，則Vi所對應的出線位置則如圖1中對應連接B節(jié)點的出現(xiàn)位置。

根據(jù)上述方法對全局節(jié)點先行規(guī)定出現(xiàn)位置，為下一步布線算法做好準備。

3.2 基于線探索法與lee算法的線路走線設計

由于傳統(tǒng)的lee算法是采用廣度搜算算法的思想，但是針對大規(guī)模的電網，布局區(qū)域大，可行的走向方案很多，使用lee算法搜索出一條最優(yōu)線路將會耗費大量的計算時間，因此本系統(tǒng)需要一種有較高效率的算法，來減少計算時間，本次研究采用改進型的lee算法，即線探索法來對線路進行布線，下面介紹具體步驟：

（1）由兩個有聯(lián)絡關系的節(jié)點A與B分別引出一條水平輔助線和一條垂直輔助線，檢測兩節(jié)點之間的輔助線有無交點。

（2）若無交點，檢測輔助線所遇障礙，并在所遇障礙出距離為d的點標記E。

（3）對E點若在的輔助線引出一條與之處置的輔助線，并檢兩節(jié)點的輔助點間是否存在交點，若無交點，則繼續(xù)根據(jù)上述規(guī)則引出輔助。

（4）若檢測到兩節(jié)點的輔助線存在一個交點D，則以交點所在的輔助線向節(jié)點所在位置回溯，所得結果既為走線方案。

圖2所示為線探索法的例示。

由于線探索法有很高的搜索效率，但是在布線過程的后期由于可用的繪圖的空白區(qū)域已經趨于飽和，因此線探索法在這種情況的應用往往不能搜索到一個可行的方案，從而需要lee算法予以配合才能完成，首先搜索出布線失敗的線路，對這類線路使用lee算法進行布線，下面介紹lee算法的具體步驟。假設起始變電站網格為A，我們賦予網格值為“0”，這樣，其相鄰的不是障礙的網格值被標記為“1”，并向外擴展;從“1”擴展而來的網格點的網格值被標記為“2”，如此下去，直到擴展到目標變電站B或者無法擴展為止。只要在A，B間存在路徑，用lee氏算法一定可以找到一條路徑，并可以保證該路徑是最短的。擴展過程如3圖所示。

圖3 lee算法示例

圖4 豎向通道中線路重合的情況

圖5 豎向通道中重合線路調整規(guī)則

使用Lee算法搜索到可行通路后，可能會出現(xiàn)大量的可行通路，而許多通路拐點過多，不是最優(yōu)的，則需要對Lee算法加入判斷最優(yōu)路徑的過程，因此為避免出現(xiàn)過多拐點，在回溯過程中，采用貪婪行為，即回溯時盡量不拐彎的準則。

3.3 走線的調整與優(yōu)化

通過上述兩種算法對線路進行初步布線，但是很出線線路重合，或者線距過近的問題，因此需要對線路的走線方案進行優(yōu)化。

由于每一個廠站被布置在網格中，網格之間的每一列與每一行都為走向通道，因此計算每一豎向通道中線段的數(shù)量ni與每一橫向通道中的線段數(shù)量mi，計算橫向通道德高度h與豎向通道的寬度d，下面以對全局豎向通道內線段進行修改為例。

將豎向通道分為ni份，即每一條線段占據(jù)一份，得到：

N=d/ni ? ? ? ? ? ? ? ? （2-1）

其中N為豎向通道中每一線段所占據(jù)的寬度。

通道內線段按照從高到低，從左至右分別安排至每一分中，若遇到多條線段重合的情況，則按照圖4、5所示準則進行調整。

通過上述規(guī)則對重合線路進行調整位置，可以很好的避免不必要的交叉，按照上述規(guī)則對每一個通道中的線路進行調整，但是由于部分通道內線路過多，而個別通道線路少，就會導致線路多的通道內線路擁擠，線路之間的線距過近，線路少的通道中線距大，局部稀疏，導致面積使用不合理的問題，因此為了避免上述問題，需對全局的豎向通道的寬度d與橫向通道的高度h進行調整，具體步驟為：

統(tǒng)計所有豎向通道個數(shù)a，橫向通道個數(shù)b，統(tǒng)計全局豎向通道中線段數(shù)量n，橫向通道中線段數(shù)量m。根據(jù)豎向通道個數(shù)a與寬度d，計算出豎向走線的線路所占面積。

Sd=a×d ? ? ? ? ? ? ? ? ? ? ?（2-2）

根據(jù)橫向通道個數(shù)b與高度h，計算出橫向走線的線路所占面積。

Sh=b×h ? ? ? ? ? ? ? ? ? ? ? ?（2-3）

圖6 實際電網潮流圖最終效果

由于線路所占面積不平均是導致上述問題的根本原因，調整每條線路所占面積，使得全局橫向走線的線路所占面積一致，全局豎向走線線路所占面積一致。

Sn=Sd/n? ? ? ? ? ? ? ? ? ? ? ? （2-4）

Sm=Sh/n ? ? ? ? ? ? ? ? ? ?（2-5）

其中Sn為調整后的豎向走線的線段所占面積，Sm為調整后的橫向走線的線段所占面積。

4.系統(tǒng)算例

本文對包括152個廠站與394條線路的貴州電網進行潮流圖的自動生成，總共耗時13s。本系統(tǒng)也滿足廠站的位置拖動修改，線路跟進改進的功能。下圖為系統(tǒng)最終成圖效果。

從圖6可以看出節(jié)點均勻的分別在布局區(qū)域中，220kV電壓等級的節(jié)點輻射狀的分布在500kV電壓等級的節(jié)點的周圍。在布線方面，線路很好的避免了不必要的交叉，且線路之間的線距也是在可以接受的范圍之內。

5.總結

本文分為自動布局與自動布線兩部分，自動布局可以節(jié)點在滿足相對地理位置的情況下以發(fā)散的形式分布在中心節(jié)點的周圍，自動布線部分通過采用特定的方法對線路位置進行修改很好的避免了不必要的重復，從而使得全局繪圖美觀。

參考文獻

[1]沈偉，吳文傳等.能量管理系統(tǒng)中潮流單線圖自動生成算法[J].電力系統(tǒng)及其自動化，2010，34（6）：48-56.

[2]何勝，梅娟，石貴陽等.代謝網絡自動繪制的快速網格布局算法[J].食品與生物技術學報，2008，27（5）：86-90.

[3]宋適宇，何廣宇，徐彭亮等.輸電網單線圖的自動生成算法[J].電力系統(tǒng)及其自動化，2007，31（34）：12-15.

[4]程遠，嚴偉，李曉明.基于斥力-張力模型的網絡拓撲圖布局算法[J].計算機工程，2004，30（3）：104-105.

[5]陳傳波，胡誼東，何力等.目標驅動的迷宮布線算法及優(yōu)化[J].華中科技大學學報：2004，32（1）：49-51.

[6]KAWAHARA K，YOSHIZU K，ZOKA Y，et al.Construction of auto matic drawing system of power system diagram by using GA//Proceedings of 2000 International Conference on Power System Technology：Vol 1，December 4-7，Perth，Australia：497-502.

[7]BATTISTA G D，EADES P，TAMASSIA R，et a.Algorit hms for drawing graphs：an Annotated Bibliography.Computational Geomet ry：Theory and Applications，1994，4（5）：235-282.

作者簡介：

陳巨龍（1983—），男，碩士，工程師，現(xiàn)供職于貴州電網公司電力調度控制中心，研究方向：調度自動化及計算機信息處理。

羅歡（1990—），男，四川大學碩士研究生在讀，研究方向：調度自動化及計算機信息處理。

陳實，男，博士，現(xiàn)供職于四川大學，研究方向：調度自動化及計算機信息處理。