輸電網接線圖增量自動成圖算法①

沈自虎,吳淑瑋,葛藝曉,張守田

(南瑞集團(國網電力科學研究院)有限公司 南京南瑞信息通信科技有限公司,南京 210003)

引言

電網可視化一直是電網中比較重要的研究課題.在傳統方式中,不管是輸電網接線圖可視化還是廠站接線圖可視化在實踐中都耗費了大量的人力物力.它們的實現方式往往是人工手動繪制或者初級的計算機自動繪制,后期再加上較多的后期人工干預.本文主要的研究對象是輸電網接線圖的自動生成.電網接線圖能夠反映出廠站和線路之間的拓撲情況,是電網的調度、檢修、計劃等部門常用的參考;它在實際的實時調度和生產管理中有較多的應用.近幾年隨著國家電網的快速發展,廠站線路的數量規模越來越大,計算機相關技術也在飛速發展,利用計算機自動生成相關輸電網接線圖是現階段研究的熱點問題.文獻[1]是在能量管理系統(EMS)中實現了潮流圖單線圖的自動布局,但并沒有實現基于歷史線路的問題的規劃問題,且線路規劃算法也不相一致.成圖效果也存在不同.

而本文對廠站布局也是采用力導向算法[2];而在線路規劃中采用A*算法[3]進行線路規劃;創新性的提出了評價算法反饋廠站布局進行微調再布線,不斷調整之后得到一個美觀的廠站線路規劃圖.同時,算法還增加了在不改變歷史廠站線路布局的情況下,對新添加的廠站線路增量靈活布局的功能,保證了歷史數據的穩定性.

自動成圖算法分為3 個模塊,第1 部分,對廠站的位置進行布局,為廠站找到合適的位置;第2 部分,對廠站之間相連的線路采用A*算法進行線路規劃.最后一部分是將成圖之后的結果進行評價反饋,對于一些不合理的廠站和線路的布局不合理的進行微調,通過局部微調適應整體布局.

輸電網接線的成圖算的目標是:

1)廠站之間的相對空間的位置關系應該和實際的地理相對位置關系大致相似.此目的是保證使用人員對輸電網線路的位置上的使用習慣.

2)整體布局均勻,包括廠站和線路.

3)廠站之間的連接線使用直線連接,盡量采用橫豎直線,且拐點少.

4)廠站線路的交叉盡可能少,避免線路重合和拐點在線路上.

5)主干線路(500 kV)以上的線路盡量布局在中心位置.

1 廠站網格布局

1.1 廠站網格布局的數學模型

廠站位置的布局是線路規劃的基礎和前提,布局結果的優劣直接關系到線路規劃的成圖效果.一個良好的廠站位置布局,主要表現在廠站在畫板上分布均勻、相鄰之間的廠站的距離合理等幾個方面.

廠站位置布局可以抽象成圖當中的點,輸電線路抽象成圖中的邊,節點和邊就構成一個圖模型.因此廠站布局和輸電線路規劃就轉換成點的布局和兩點之間邊的路徑規劃.

在大規模點的布局上,力導向算法有著非常廣泛的應用,它的優點是可以清晰的展現圖中各點之間的關系,由Peter Eades 在1984年首次提出[4].該算法的核心是將圖中的點和線模擬力學系統,且圖中的各點同時受到吸引力和排斥力的影響.圖中每個節點與其它節點都存在斥力,有線連接的節點之間存在引力.如果引力大于斥力,則兩個節點相互靠近;如果斥力大于引力,則兩個節點相互拉遠.經過多次迭代,最后形成一個穩定的系統.具有代表性的力導向算法有Fruchterman TMJ 等提出的基于原子引力模型的FR 算法、Kamada T 等提出的基于能量模型的KK 算法和Hu YF 提出的Hu 氏算法[5–7].本文采用FR 算法,它是在經典彈簧模型上的一些改進,模擬物理粒子理論中原子之間的力場來調節位置關系.

在FR 算法中,需要計算以下幾個值.設定畫布的寬為W,高為H,則畫布大小為[8]:

理想距離:

其中,|V|是節點的數量.

節點之間的歐式距離:

為了保證節點之間的距離稀疏合理,需要計算節點之間引力和斥力.然而斥力存在于所有節點之間,而引力只存在于兩個節點之間存在連線的情況,這正好符號我們常規的理解,有關聯的節點之間的距離要近,無關聯的節點距離遠.所以有節點u和節點v之間的引力函數:

節點u和節點v之間的斥力函數:

其中,F1和F2分別為引力因子和斥力因子.

廠站布局算法是基于FR 算法為核心進行設計的,在迭代過程中,很容易出現局部優而整體差的情況.為了避免這種情況,本文選用模擬退火算法替代傳統的迭代方式,避免局部優化的情況.模擬退火算法是模擬物理學上物體逐漸降溫的物理過程,溫度越低,能量越低;最后達到相對穩定的狀態.

線性溫度下降表達式:

Tt為當前時刻溫度,Tt+1下 一時刻溫度,γ為冷卻系數,且一般為略小于1 的正數.

本文設置初始溫度為T0=1000,停止溫度為Tend=1.

為了選擇最優的布點結果,本文采用以下幾個評價函數進行評價:

點的布局評價函數[8]:

1.2 廠站網格布局的算法實現

FR 算法的核心步驟主要分為3 個部分,首先計算圖中各點之間的斥力,其次計算有邊相連的節點之間的引力,最后計算斥力和引力的合力來計算節點的移動位置.然而,每一次計算只能得到圖的部分能量最小,要得到全局的能量最小,需要經過多次迭代才能夠滿足需求.

在點的一定次數的位置偏移中,隨著迭代次數的增多,位置的調整也越來越微小,圖形之間的布局會越來越好.在模擬退火算法中,給出初始溫度和冷卻速率來限制節點的最大位移.隨著溫度的降低,位置的偏移會越來越細微,使得圖最終能夠得到一個相對穩定的狀態.在算法實現過程中,為了得到較好的布點效果,算法添加了并發的參數循環計算,利用計算機多核CPU 的計算性能,計算出最優的參數值.

1.2.1 節點布局的偽代碼

節點布局的偽代碼如圖1所示.

圖1 節點布局算法偽代碼

1.2.2 布點實驗

不同的彈力系數F1和 斥力系數F2對點的布局影響會非常的大,故該算法通過多線程并行的計算不同F1、F2參數條件布點之后的相交代價,通過比較,選擇最小代價的參數F1、F2和布局結果.在實驗中,不同數據輸入的情況中,動態計算參數F1和F2的值比固定的F1和F2的值的效果要好很多.

實驗中,本文選取了57 個廠站節點和98 條邊線路作為實驗數據.在CPU 為Intel(R)Core(TM)i3-8130U CPU @ 2.20 GHz(2208 MHz),內存為8 GB 的單機筆記本電腦中對不同的冷卻系數做了實驗對比,通過計算出的引力、斥力系數,交叉偏差因子和運行時間評價布局結果的好壞.

通過表1數據結果可以看到,當冷卻系數為0.93時,交叉偏差乘積最小,運行時間最短.而且通過實驗發現,布局效果不是隨著冷卻系數的增加而改變,而是先增加后減小.同時,冷卻系數對引力、斥力系數也有影響,不同的冷卻系數得到不同的引力、斥力.

表1 冷卻系數γ 取值在0.90～0.95 的布點結果表

對應圖中的結果,生成如圖2所示的節點布局圖.

圖2中的6 幅圖分別展示了49 個節點和連線的分布情況.從圖中看出,從 γ=0.92開始,點的布局就變的扁長,點的布局也較為稀疏.單具體才差別并不大.但從表1的測試結果數據中可以知道,當 γ=0.93時,效果最好.

圖2 冷卻系數γ 取值在0.90～0.95 的布點結果圖

2 輸電線路規劃

廠站規劃的位置布局完成后的線路規劃直接決定著圖形的美觀程度.如果線路像圖1那樣采用直連,則會產生非常多的交叉且不美觀.線路增多時,交叉更是會指數性增多.故需要一種高效率的全局的線路規劃算法,實現線路的美觀布局.常見的線路規劃算法有Dijkstra 算法[9]、Bellman - ford 算法[10]、Floyd-Warshall算法[11]、SPFA 算法[12]、李氏迷宮算法[13]和A*搜索算法[14]這幾種算法.本文采用的A*算法是一種啟發式式搜索算法,是求解最短路徑中最有效的算法.它具有算法靈活,效率高等優點.

2.1 目標

經過第一步節點布局的基礎上,得到密度合理的節點分布,線路規劃的目標有以下幾個方面:

1)線路交叉和拐點盡量少,且拐點盡量不在線上;

2)線路盡量橫平豎直,出線和入線為0°、30°、45°、60°和90°;

3)線路之間重合線盡量少,出線和入線重合除外;

4)所有節點必須在網格點上.

通過上面的要求和目標,本文設計了下面的代價模型.

2.2 代價函數模型

在A*算法中,代價函數g(x)和h(x)決定線路的走向.而h(x)作為啟發函數,其作用是控制A*算法的行為,引導A*算法快速接近目標節點.g(x)在A*算法中對路徑規劃起主要作用,它決定兩點之間中間的路徑該如何規劃.

下面為起點到節點i的最小代價函數ti:

ti?1表 示起點到當前節點的最小代價,則tend表示到從起點到終點的代價值,其中min(ω1f1+ω2f2+ω3f3+ω4f4)為 當前節點到下一節點的g(x)最小代價.ω1、ω2、ω3、ω4為權重系數,f1為 線路交叉函數;f2為線路拐角函數;f3為 區域影響函數;f4為路徑長度函數.

那么在線路規劃中,所有線路(重復線路值算一條)的總代價值就為:

1)線路交叉函數

輸電線路分為不同的電壓等級,若當前線路與其它線路的相交且電壓等級相同,用n表示不同電壓等級的條數,m表示相同電壓等級的條數,a1和b1表示不同電壓等級的權重.通過b1>a1的條件限制使得在線路規劃中,盡量避免相同電壓等級的線路的交叉,而選擇不通電壓等級線路交叉的情況.c1是常數影響因子,它的主要作用是調整f1函數的權重大小.

2)線路拐角函數

針對不同的線路出線情況,設定不同的權重值.

若該線為出線,則f2=0;若為后面的幾種情況,則是不同的權重值,在不同的情況下,選擇不同的走向.并且在線路規劃中,為了美觀,更傾向于橫平豎直,且拐彎少的情況.故在以下6 種情況下,a2這種情況最好且a2的值最小;其它幾個權重值則需要根據不同的線路規劃需要設定不同的值.

3)區域影響函數

設起點為P,終點為Q,中間某一節點的E,區域影響函數為:

其中,F(P,Q)為P,Q連接函數.要求F(P,Q)的值,首先要得到除當前連接的廠站外,其它與P有連接的變電站;第二步,假設其中的一個變電站的坐標為p(x,y),P(xp,yp),Q(xq,yq).

圖3是經過E點時,F(P,E)=1,F(Q,E)=1;同樣在經過E21時,F(P,E21)=1,F(Q,E21)=1; 而F(P,E12)=0,F(Q,E12)=1;故此時會選擇P→E12→Q這條路徑.此外,a3>b3的作用是規范路徑出線的方向,當一個點的出線較多時,對其它的線路影響相對較小一些.

4)路徑長度函數

路徑函數的作用是記錄線路的路徑長度,可以減少線路之間不必要的步數.當兩條線路起點終點一致的情況下,優先選擇路徑長度f4最 小的情況.其中a4為路徑函數的權重系數.

圖3 區域影響函數示意圖

2.3 路徑規劃算法

路徑規劃A*算法的核心是如何計算代價函數,它決定了從起點到終點每一個中間節點的位置.它的代價函數為:

其中,g(x)是起點到中間某一節點的最短距離;h(x)為啟發函數,一般取曼哈頓距離[15],切比雪夫距離[16]、歐幾里得距離或平方后的歐幾里得距離為主要函數.如果h(x)=0,則A*算法退化為Dijkstra 算法.根據2.2 可知,g(x)=ti.同時設定啟發函數切比雪夫距離,即為h(x)=D·max(|x1?x|,|y1?y|).基于A*算法,結合上面的數學模型,最終得到廠站的線路規劃算法.

2.3.1 數據預處理

1)線路去重

因為輸電線路中有大量的起點終點變電站一致的情況.如“代東I 線”和“代東II 線”,這兩條輸電線路的起點變電站和終點變電站都為代王變和東郊變.在后面的路徑規劃中,因為要涉及到線路交叉和重復計算的情況,所以,要在路徑規劃前,先去除重復的線路.之后在顯示線路時,在通過節點偏移算法將重復的線路按照相對位置進行偏移.

2)線路排序

按照線路的電壓等級和線路長度兩個參數進行排序.優先按照電壓等級由高到低,其次是按照線路的長度由短到長進行排序.按照習慣,電壓等級高的線路作為核心線路,要求為橫平豎直,交叉和拐角少,所以優先對其進行排序.第二按照線路由短到長進行排序,目的是優先安排短的線路,短的線路相比長的線路更容易布置且不會有太多的拐角.實驗過程中發現,不同排序順序的成圖效果會非常大.

3)剔除T 接線

T 接線是輸電線路中比較特殊的情況,它的一端直接連接到一條主干線路上.而普通的線路時連接著兩端廠站,這種情況直接進行線路規劃;而對T 接線則需要重新計算T 接點的位置后在進行線路規劃.故需要對其剔除特殊處理.

2.3.2 路徑規劃算法描述

第1 步.單線路路徑規劃.

(1)依次處理預先已排序的線路,優先對高電壓等級的線路進行布線.設定電壓門檻值,若高于此值,則出線方向為上下左右及各個方向的45 度角等8 個方向;否則出線方向增加30 度和60 度等16 個方向.此為第一步出線.

(2)使用A*算法實現從起點到終點的線路規劃,得到路徑的中間拐點.

第2 步.T 節線處理.

因為T 接線是一種特殊的線路,它的一端是主線路的一個T 接點,另一端是廠站.所以在線路規劃中,首先需要在主線路上找一個合適的點作為T 接點,本文算法是在主線路中最長線段的等分點,如有一個T 接點,則為二等分點處.之后在按照第一步的算法進行線路規劃.

第3 步.重復路徑偏移.

(1)將重復的線路分組.

(2)將每條線路的中間節點進行優化,若連續的3 個點在一條直線上,則去除中間點.此過程是減少線路中的多余節點.若中間節點太多,則加入反饋列表,對廠站布局進行反饋.

(3)對重復的線路按照某種特定的規則進行偏移.本文實驗中采用每兩條線相隔4 個單位.

(4)最后輸出線路及中間拐點.

2.4 路徑規劃算法樣例

圖4為使用A*路徑規劃算法,結合代價函數模型的路徑節點的代價圖.圖中的數字為起點A為到終點B中間所計算的各個節點的最小代價.其中從點A到點B的最小代價為10,在圖中為灰色有背景部分.直觀上看,符合成圖的最終需求.

3 線路規劃反饋廠站布局

在線路規劃過程中點是固定的,所以一定會產生點布局不合理而導致線路規劃不美觀的情況,因此需要對已經規劃好的線路,進行點的位置的調整.本文所采取的策略為增加反饋環節,多次對點進行反饋微調來達到目標的美觀效果.圖5為線路規劃反饋算法的流程圖.

圖4 線路規劃代價圖

圖5 線路規劃反饋算法流程圖

通過遍歷已經成好的圖的每條邊,設定反饋閾值.若某條線的代價超過設定的閾值,就將線和兩端端點以及端點所關聯的線,加入到需要重新布線和布點數組中.而不被改變的線路和點則設置為歷史的線路和點,重新布線的線和點則設置為新的線路和點.在經過廠站布局和線路規劃后,計算其總代價,與上一次布局代價相比較,選擇較小的布局結果.當布局結果的代價不在減小時,此時,停止反饋,輸出布局結果.

而本文設定的反饋閾值L為所有線路規劃前10%的代價值,換句話說,就是每次對至少10%的線路進行微調.

選取42 個點和68 條線進行實驗.經過初始布局和三次迭代之后,輸出結果.在反饋過程中,布局總代價逐漸減少,點布局和線規劃都存在位置的改變和優化,成圖效果不斷改善.圖6為不同迭代時期的代價及成圖效果.

圖6 反饋成圖效果

4 增量廠站線路規劃

隨著輸電線路的不斷建設,廠站線路投運和退役是比較常見的事.所以在廠站線路布局完初始布局完以后,有新的廠站線路投運再次布局時,就需要不改變原來的線路和廠站位置,只調整和布局相關的廠站和線路即可.為了滿足這個需求,只需在廠站布局和線路規劃算法做一些預處理和微調即可.

1)數據預處理

傳入的廠站和線路分為歷史廠站、歷史線路和新建廠站和新建線路.若新建線路的兩端廠站在歷史線路中能找到相同起始和終點廠站,則將與其相同的線路的中間節點復制到這條線路中,同時將其節點移除新建線路,加入到歷史節點中.

同時設置所有線路和所有廠站兩個變量,供廠站布局使用.

2)廠站布局

在所有處理邏輯不變的情況下,只改變循環變量.新建廠站在計算排斥力時,只計算新建廠站與其它所有廠站之間的斥力;計算引力時,只計算該場站與其它相關聯的廠站的引力.這樣對歷史廠站的位置不會產生影響,只需布置新的廠站的位置.

3)線路規劃

線路規劃也只需將循環變量改為新建線路;只規劃新建線路的中間節點的路徑.

圖7為增量布局的結果.圖7(a)為原始的廠站布局,圖7(b)在原始廠站都沒有改變的情況下新增了2 個廠站和3 條線路.其中1 條為普通線路,另外2 條為T 接線路.而且通過增量成圖算法找到的位置從實際效果上也比較合理,基本符合增量成圖目標效果.

圖7 增量成圖效果

5 評價及實驗結果

該算法的有兩個核心模塊組成,點布局力導向算法的一次迭代的時間復雜度為O(|V2||E|),經過模擬退火迭代的時間復雜度為O(n?|V2||E|).表2為計算不同冷卻系數下的代價和運行時間,很明顯,當冷卻系數為0.92 時,總代價最小,且運行時間最短.圖8是不同的冷卻系數生成的實驗結果,可以看到成圖結果基本滿足美觀的要求.且在γ=0.92時,效果最好.

表2 冷卻系數γ 取值在0.90～0.95 的布線結果

圖8 冷卻系數γ 取值在0.90～0.95 的布線結果

6 結語

本文通過實現改進力導向算法和A*算法,構建了一個線路規劃的模型函數及評價函數,并通過布點,布線,反饋三個步驟,實現了輸電線路增量自動成圖的功能.同時還對影響成圖的參數進行了實驗比對,得到了當 γ=0.92 或者γ=0.93時成圖效果較好.由于成圖的時間復雜度高,存在當數據量較大時,成圖時間較長的問題.下一步需要深入研究,解決這方面問題.