基于供區(qū)的輸電網(wǎng)接線圖廠站網(wǎng)格布局算法

蔣正威，闕凌燕，沙樹名，劉風劍，劉向陽

(1. 國網(wǎng)浙江省電力有限公司，浙江 杭州 310007；2. 南京南瑞信息通信科技有限公司，江蘇 南京 210032；3. 河海大學 理學院，江蘇 南京 211100)

0 引言

輸電網(wǎng)單線圖[1-2]也稱輸電網(wǎng)均勻接線圖是電網(wǎng)規(guī)劃設計、運行監(jiān)視、理論線損計算、年度運行方式等業(yè)務的支撐工具。電網(wǎng)潮流圖[3]也稱電網(wǎng)潮流單線圖[4]是輸電網(wǎng)單線圖的應用擴展，通常以輸電網(wǎng)單線圖為底圖，對廠站圖元作動態(tài)疊加電網(wǎng)潮流方向與數(shù)值以及線路兩側(cè)開關(guān)狀態(tài)，用以電網(wǎng)運行監(jiān)控和調(diào)度大屏展示。到目前為止，實際運行的能量管理系統(tǒng)中大部分潮流圖仍依靠人工繪制，而作為這些潮流圖的底圖，難以在管理信息大區(qū)復用。近年來，為滿足面向電網(wǎng)統(tǒng)一決策、分級控制、實時協(xié)同的一體化運行要求，調(diào)控云模型數(shù)據(jù)云平臺按照電網(wǎng)調(diào)度通用數(shù)據(jù)對象結(jié)構(gòu)化設計原則，通過縱向同步工具完成了上下級調(diào)度機構(gòu)之間模型的貫通，形成了全拓撲模型。輸電網(wǎng)單線圖能夠反映電網(wǎng)潮流和主要設備運行狀態(tài)，宏觀展示電網(wǎng)運行態(tài)勢，輔助電網(wǎng)運行決策，可作為檢修可視化、電網(wǎng)運行風險分析等管理信息大區(qū)的系統(tǒng)應用入口。另一方面，電網(wǎng)規(guī)模的逐年遞增，人工維護輸電網(wǎng)單線圖越來越困難。關(guān)于輸電網(wǎng)單線圖的自動生成早有研究[1-14]，主要方向包括廠站位置自動布局和線路自動走線[15-16]。

為了在規(guī)定的圖幅內(nèi)生成廠站圖元比例適中、布局均勻、線路交叉最少的輸電網(wǎng)單線圖，廠站節(jié)點及T 接節(jié)點位置的合理布局是最重要的環(huán)節(jié)，直接決定了自動成圖效果。輸電網(wǎng)接線圖的自動生成是一個復雜的多目標優(yōu)化問題[5-8]，其中廠站的自動布局難度與廠站數(shù)和線路數(shù)相關(guān)。文獻[1]將節(jié)點位置定義成網(wǎng)格，將線路總長度作為目標函數(shù)，采用罰函數(shù)法求得節(jié)點布局。文獻[9]將潮流圖節(jié)點自動布局分解為供區(qū)布局和供區(qū)內(nèi)變電站布局2 個問題求解。供區(qū)布局采用參考地理相對位置、降維簡化、人工干預方式生成，供區(qū)內(nèi)部將線路間的交叉點數(shù)與線路曼哈頓距離綜合起來作為模擬退火的目標函數(shù)獲得局部最優(yōu)解。文獻[10-12,17]采用斥力-張力模型[18]進行節(jié)點自動布局，文獻[4]在此基礎上采用遺傳算法進一步優(yōu)化。文獻[19]對不同電壓等級引入不同權(quán)重，在節(jié)點運動修正方程中引入重力系數(shù)，獲得結(jié)構(gòu)更為清晰的布局。以上的研究工作均在特定目標下取得了較好的結(jié)果[20-23]，本文將處理在任意畫布下的廠站網(wǎng)格均勻布局，為此提出了廠站網(wǎng)格布局的多目標優(yōu)化數(shù)學模型。

隨著中國電網(wǎng)結(jié)構(gòu)日趨復雜，省地級調(diào)度機構(gòu)調(diào)管廠站數(shù)量監(jiān)控系統(tǒng)功能日益豐富，對于輸電網(wǎng)單線圖應用除了拓撲關(guān)系的正確展示外，也對圖形的簡潔美觀、邏輯清晰提出了要求。在實際應用中，每個廠站均可根據(jù)拓撲關(guān)系歸集到供區(qū)。利用供區(qū)的這一特性，本文根據(jù)拓撲關(guān)系及典型方式下線路兩側(cè)斷路器運行狀態(tài)使用二分法將廠站布局到不同的矩形塊內(nèi)。同時，為確保布局區(qū)域內(nèi)的廠站網(wǎng)格均勻布局，本文提出了基于廠站權(quán)重系數(shù)的力導向網(wǎng)格布局改進算法，其中重新定義了力導向算法中排斥力和吸引力計算公式。通過力導向改進算法實現(xiàn)電網(wǎng)接線圖的廠站自動布局。此外，采用網(wǎng)格化布局，即將廠站布局在網(wǎng)格點上，以增加輸電網(wǎng)接線圖的辨識度。

1 基于供區(qū)的廠站網(wǎng)格布局數(shù)學模型

針對在任意畫布下的廠站網(wǎng)格均勻布局，本文將其建模為帶約束條件的多目標優(yōu)化函數(shù)。廠站表示為Vi(i=1,2,···,N)， 廠站Vi的平面坐標表示為(x(Vi),y(Vi))， 廠站間線路表示為Line(Vi,Vj)(i≠j)，布局區(qū)域的寬度和高度為W和L。布局優(yōu)化的目標為：供區(qū)布局合理、無廠站間重疊、布局區(qū)域內(nèi)廠站網(wǎng)格均勻分布、線路的交叉盡量少、線路長度合理。具體描述如下。

（1）布局區(qū)域劃分合理度E1。布局區(qū)域劃分合理度是廠站供區(qū)劃分合理性的衡量指標。在供區(qū)面積和供區(qū)形狀2 個因素的影響下，計算布局區(qū)域劃分合理度E1為

式中：λ11，λ12為權(quán)重系數(shù)；n為供區(qū)的個數(shù)；Ni為第i個供區(qū)的廠站個數(shù)；Si為第i個供區(qū)的實際面積；ρ為理想密度；N為廠站總數(shù)；Ri為第i個供區(qū)的邊長比例，大小為供區(qū)寬度和高度中最大值與最小值之比。當供區(qū)內(nèi)廠站實際密度與理想密度的距離較大、供區(qū)邊長比例過大時，布局區(qū)域的劃分不合理，反之，布局區(qū)域劃分合理。

（2）廠站分布均勻度E2。廠站分布均勻度是衡量廠站分布均勻性的指標。先從水平方向均勻地劃分布局區(qū)域，再從豎直方向均勻地劃分布局區(qū)域，統(tǒng)計每個區(qū)域塊內(nèi)廠站個數(shù)。其計算公式為

式中：m為均勻劃分布局區(qū)域得到的區(qū)域塊數(shù)；Mj為第j個區(qū)域塊內(nèi)的廠站數(shù)目。廠站分布標準差越大，不同區(qū)域塊的廠站數(shù)目越不均衡；反之，廠站分布整體上越均勻。

（3）線路交叉值E3。先判斷任意兩條線路是否存在交叉點，再統(tǒng)計所有的交叉數(shù)目，即獲得線路交叉值。線路交叉值越小，線路走向越清晰，因此應當盡量減少線路交叉。

（4）線路長度合理度E4。線路長度合理度是衡量線路長度合理性的指標，過長或過短的線路均會影響布局效果。其計算公式為

式中：Lm為所有線路長度的平均值；k為廠站理想距離，其值大小由式（9）計算可得。E4越大，表明線路長度越不合理，反之則表明線路長度相對合理。

以上是本文優(yōu)化的主要目標，無廠站間重疊、廠站網(wǎng)格分布則是優(yōu)化上述目標時必須達到的條件。具體包括：（1）無廠站間重疊：廠站間重疊指兩個廠站的坐標相同。廠站重疊會導致布局結(jié)果無法使用，因此不允許出現(xiàn)廠站間重疊的情況。（2）廠站網(wǎng)格分布：廠站網(wǎng)格分布指所有廠站分布在布局區(qū)域的整數(shù)網(wǎng)格點上。廠站網(wǎng)格分布可以呈現(xiàn)出規(guī)整的廠站分布效果，因此本文希望實現(xiàn)廠站網(wǎng)格分布。

基于以上優(yōu)化效果分析，本文優(yōu)化目標函數(shù)為

式中：λ1、λ2、λ3、λ4為權(quán)重系數(shù)；E1、E2、E3、E4分別為布局區(qū)域劃分合理度、廠站分布均勻度、線路交叉值、線路長度合理度；Vi、Vj分別為第i、j個廠站的位置； Z為整數(shù)集。在平面直角坐標系中，帶約束的多目標函數(shù)很難使用傳統(tǒng)方法直接求解。因此，本文使用力導向網(wǎng)格布局改進算法進行近似優(yōu)化求解。

2 力導向算法及其改進

2.1 F&R 算法簡介

F&R 算法[18]主要包括3 個部分：吸引力的計算、排斥力的計算、計算節(jié)點在合力下的移動距離并用模擬退火算法控制節(jié)點的最大位移。F&R 算法并沒有考慮更復雜的情況，因此當節(jié)點超過一定數(shù)目時，其求解的布局效果并不好[24-25]。下節(jié)將改進F&R 算法，以適應針對供區(qū)的網(wǎng)格均勻布局、任意區(qū)域布局等其他條件。

2.2 力導向網(wǎng)格布局改進算法

2.2.1 預處理

在自動布局的過程中，廠站布局效果很大程度上取決于廠站的初始坐標。F&R 算法中節(jié)點的初始坐標由算法隨機分布，布局的結(jié)果很不穩(wěn)定，因此本文將廠站的地理坐標應用到廠站坐標的初始布局中，另外可大致確保廠站的地理相對位置。廠站的地理坐標分布不均勻，并不能直接用作廠站的初始坐標。本文將廠站的地理坐標映射到布局區(qū)域的一定范圍內(nèi)。

2.2.2 吸引力的計算

F&R 算法中引力公式計算一般情況下兩個廠站間的吸引力，即兩個廠站之間有線路相連時，引力的大小和兩廠站間距離的平方成正比，否則，兩個廠站之間沒有吸引力。計算引力Fa為

k的計算和布局區(qū)域的面積以及廠站的個數(shù)有關(guān)。本文在計算k時引入了縮小尺度，目的是為了讓所有廠站分布在布局區(qū)域的合理范圍內(nèi)，即

式中：S為計算理想距離時的縮小尺度。

2.2.3 排斥力的計算

在F&R 算法中，排斥力的計算在所有的節(jié)點間進行，并且排斥力的大小僅僅和節(jié)點的距離有關(guān)。當節(jié)點數(shù)目較多、連接密切時，排斥力產(chǎn)生的布局效果并不好。本文考慮了兩個廠站距離過近和廠站出線度對網(wǎng)格均勻布局的影響，在排斥力計算過程中引入了新的力。此外，為了防止廠站被排斥到區(qū)域邊緣，本文只計算廠站固定范圍內(nèi)的排斥力Fr，即

式中：D為試驗參數(shù)；F1，F(xiàn)2為排斥力計算過程中引入的新力。

隨著算法循環(huán)進行，整個系統(tǒng)逐漸趨于穩(wěn)定，廠站的位置也逐漸固定，因此布局不合理的兩個廠站越不容易被排開。本文使用指數(shù)型函數(shù)加大距離過近的廠站間的排斥力，計算F1的公式為

式中：dm為出線度較大廠站的閾值，為試驗參數(shù)；dg(Vi)和dg(Vj)分別為廠站Vi和Vj的實際出線度。

2.2.4 廠站的偏移

本文將廠站受到的所有力合成，得到每個廠站所受合力F，將F分解成x軸方向上的力Fx以及y軸方向上的力Fy，然后利用式（14）計算廠站在x軸方向上移動距離Δdx和y軸方向上移動距離Δdy。

式中：Ti為第i次迭代時模擬退火函數(shù)的取值。

本文使用模擬退火函數(shù)控制廠站的最大位移，目的是防止廠站被排斥到布局區(qū)域邊緣，影響到廠站網(wǎng)格均勻布局。模擬退火函數(shù)的選取會直接影響到布局效果，因此本文使用指數(shù)型模擬退火函數(shù)控制廠站的最大位移，即

式中：p3和p4為實驗參數(shù)。指數(shù)型模擬退火函數(shù)式（15）使廠站在循環(huán)初期快速地排開，在循環(huán)后期快速地趨于穩(wěn)定狀態(tài)?？紤]到布局區(qū)域的寬度和高度可能不同，本文使用兩向模擬退火算法，即式（15）控制廠站在x軸和y軸方向上的不同最大位移，參數(shù)p3的取值受布局區(qū)域?qū)挾群透叨鹊挠绊憽?/p>

上述循環(huán)迭代結(jié)束后，按照四舍五入的方式對廠站的橫縱坐標取整，控制廠站網(wǎng)格布局。由于力F1的作用，廠站坐標取整后確保不會重疊。

3 基于供區(qū)劃分的廠站網(wǎng)格均勻布局

3.1 供區(qū)的布局區(qū)域劃分

在劃分布局區(qū)域的過程中，本文先使用力導向網(wǎng)格布局改進算法計算供區(qū)中心點坐標和供區(qū)的相對位置，再使用二分法對布局區(qū)域進行劃分，同時保證供區(qū)位置的合理性。

3.1.1 供區(qū)坐標和供區(qū)相對位置的計算

本文使用力導向網(wǎng)格布局改進算法計算布局在合理位置的供區(qū)中心點，并將供區(qū)中心點的相對位置作為供區(qū)的相對位置，其中供區(qū)中心點設置為Vci(i=1,2,···,n)，供區(qū)中心點的設置是為了更好的劃分區(qū)域，但并不參與到廠站的布局過程中?？紤]到劃分布局區(qū)域的特殊性，這里需要對力導向網(wǎng)格布局改進算法做如下調(diào)整。

在預處理過程中，將相同供區(qū)的廠站地理坐標的平均值映射到布局區(qū)域，作為供區(qū)中心點的初始坐標。供區(qū)中心點的初始坐標并沒有考慮供區(qū)間的復雜關(guān)系，因此不能直接用于布局區(qū)域的劃分。經(jīng)過力導向網(wǎng)格布局改進算法的多次迭代，供區(qū)中心點布局在合理的位置，同時供區(qū)的相對位置也更加合理。計算兩個供區(qū)中心點間吸引力時，若兩個供區(qū)中心點對應的供區(qū)間存在兩個廠站有線路相連，則認為是兩個供區(qū)中心點間有線路相連；否則，無線路相連。

理想距離k的計算不僅要考慮供區(qū)中心點的數(shù)目，還要考慮供區(qū)大小的影響。本文在計算供區(qū)中心點的理想距離時引入了權(quán)重，因此計算式為

式中：n為供區(qū)中心點的個數(shù)；w為供區(qū)內(nèi)廠站個數(shù)與所有供區(qū)廠站個數(shù)的均值的比值。

3.1.2 劃分布局區(qū)域的二分法

獲取供區(qū)的相對位置后，本文采用二分法的思想對布局區(qū)域進行劃分，即根據(jù)供區(qū)的相對位置，對布局區(qū)域一分為二，直到所有供區(qū)劃分完畢。

根據(jù)供區(qū)的相對位置劃分布局區(qū)域的時候，首先將供區(qū)中心點合理分成2 部分，再根據(jù)兩部分供區(qū)中心點對應供區(qū)內(nèi)廠站的個數(shù)比，從布局區(qū)域的長邊進行劃分。其中，將供區(qū)中心點合理地分成2 個部分：首先將供區(qū)中心點映射到長邊對應的坐標軸，并對映射后的供區(qū)中心點從小到大排列，再分2 種情況考慮：供區(qū)中心點個數(shù)為2n時，將前n個供區(qū)中心點分到一個部分，后n個供區(qū)中心點分到另一個部分。供區(qū)中心點個數(shù)為2n+1 時，將前n個供區(qū)中心點分到一個部分，后n個供區(qū)中心點分到另一個部分。分別計算兩個部分供區(qū)中心點對應的供區(qū)內(nèi)廠站個數(shù)，將第n+1 個點分到廠站個數(shù)較少的部分。

3.2 廠站布置的全局優(yōu)化

在廠站布置的全局優(yōu)化過程中，本文使用力導向網(wǎng)格布局改進算法處理布局區(qū)域內(nèi)的所有廠站。由于要將廠站布局在供區(qū)內(nèi)的網(wǎng)格點上，布局區(qū)域內(nèi)的廠站間吸引力的計算依舊使用式（7），但不同的是，供區(qū)間廠站的距離一般會大于供區(qū)內(nèi)廠站的距離。因此，這里對理想距離k的計算做了如下改變：當Vi和Vj同屬一個供區(qū)時，使用式（9）和式（10）計算供區(qū)內(nèi)廠站的理想距離k。當Vi和Vj分屬兩個供區(qū)時，理想距離k的大小與供區(qū)對應的供區(qū)中心點間的距離dVCiVCj有關(guān)。其計算公式為

式中：λ為權(quán)重系數(shù)。

3.3 基于供區(qū)劃分的廠站布局算法

本文將力導向網(wǎng)格布局改進算法應用到基于供區(qū)劃分的廠站網(wǎng)格均勻圖的自動布局中，最終使所有廠站均勻地分布在供區(qū)內(nèi)的網(wǎng)格點上。根據(jù)以上分析和基于供區(qū)劃分的廠站網(wǎng)格均勻布局算法的描述，該算法的流程如圖1 所示。

圖1 基于供區(qū)劃分的廠站網(wǎng)格均勻布局算法流程Fig. 1 Flow chart of power station grid layout algorithm based on supply area division

4 實驗分析與結(jié)果

本文使用某省部分實驗數(shù)據(jù)進行了基于供區(qū)劃分的廠站網(wǎng)格均勻圖布局。硬件配置環(huán)境為CPU（i7-8700）+ 內(nèi)存（8 G）。算法的迭代次數(shù)I設置為800；縮小尺度S設置為1.5；在排斥力計算過程中，D設置為3k；dm設置為5；在兩向模擬退火算法中，p3的大小設置為布局區(qū)域邊長的1/10，p4設置為0.2。

4.1 供區(qū)布局結(jié)果及分析

本實驗測試了供區(qū)的布局效果，其中實驗數(shù)據(jù)包含了4 個供區(qū)的58 座廠站和139 條輸電線路，區(qū)域的寬度和高度分別設置為11、9。在沒有使用力導向網(wǎng)格布局改進算法的情況下，基于二分法的供區(qū)布局效果并不好，供區(qū)間線路產(chǎn)生了無法避免的交叉；而使用力導向網(wǎng)格布局改進算法處理供區(qū)布局后，布局區(qū)域劃分合理度E1的值由1.173 0 降為1.132 5，供區(qū)的相對位置合理，有效減少了供區(qū)間的線路交叉。

4.2 線路交叉值測試結(jié)果及分析

為了分析力導向網(wǎng)格布局改進算法在減少交叉方面的作用，本實驗測試了迭代過程中線路交叉數(shù)的變化。圖2 顯示了線路交叉數(shù)的迭代變化過程，其值一開始迅速減小，隨著迭代次數(shù)的增加，線路交叉數(shù)穩(wěn)定在合理范圍內(nèi)。

圖2 迭代過程中線路交叉值的變化Fig. 2 Variation of line crossing value in iteration process

4.3 廠站分布均勻度測試結(jié)果及分析

本實驗使用式（3）測試了力導向網(wǎng)格布局改進算法在控制廠站均勻分布方面的性能，得到了如圖3 所示的結(jié)果。

圖3 迭代過程中廠站分布均勻度的變化Fig. 3 Variation of station distribution uniformity in iterative process

廠站網(wǎng)格布局數(shù)學模型為多目標函數(shù)，且主要目標為減少交叉，因此廠站分布均勻度并沒有呈現(xiàn)出穩(wěn)定的下降狀態(tài)，但交叉數(shù)目快速減少。

4.4 線路長度合理度測試結(jié)果及分析

本實驗計算了每次迭代中所有線路長度合理度的大小。圖4 顯示了所有線路長度值的迭代變化過程，該值在一開始迅速減小，之后隨著迭代次數(shù)的增加逐漸減小，最終趨于穩(wěn)定狀態(tài)。

圖4 迭代過程中線路長度合理度的變化Fig. 4 Variation of line length in iteration process

4.5 廠站網(wǎng)格化布局處理結(jié)果及分析

本實驗使用電網(wǎng)數(shù)據(jù)進行了基于F1的廠站網(wǎng)格布局測試，局部結(jié)果對比如圖5 所示。在未使用力F1控制廠站網(wǎng)格布局時，37 號與44 號廠站、42 號與43 號廠站取整后出現(xiàn)了坐標重疊問題。相反，使用力F1控制廠站網(wǎng)格布局后，廠站坐標取整后如圖5 d）所示，圖5 中不存在廠站重疊問題，因此，力F1有效地控制廠站分布在布局區(qū)域的網(wǎng)格點上。

圖5 網(wǎng)格處理局部結(jié)果對比Fig. 5 Comparison of local results of grid processing

4.6 實驗結(jié)果及分析

為了測試本文算法的處理效果，對包含58 座廠站和139 條輸電線路的數(shù)據(jù)進行了基于供區(qū)劃分的廠站網(wǎng)格均勻圖的自動布局測試。整個算法耗時20.06 s，實驗結(jié)果如圖6 所示。

圖6 58 座廠站網(wǎng)格布局結(jié)果Fig. 6 Grid layout of 58 stations

由圖6 可以看到：布局區(qū)域劃分的大小合理并且正確反映了供區(qū)之間的位置關(guān)系，廠站比較均勻地分布在供區(qū)內(nèi)的網(wǎng)格點上，沒有廠站坐標的重疊和線路的交叉點。此外，廠站網(wǎng)格均勻圖的結(jié)構(gòu)合理，能夠清晰地辨別出廠站之間的連接關(guān)系。但是，圖6 中左上角的廠站分布不夠均勻，存在較大的空白區(qū)域，若能對部分廠站進行局部優(yōu)化，則整體布局效果會更好。

4.7 基于真實數(shù)據(jù)的廠站網(wǎng)格布局

為了更好地測試算法的處理效果，這里使用了復雜的電網(wǎng)數(shù)據(jù)，包括7 個供區(qū)的106 座廠站和247 條線路。整個算法耗時96.31 s，布局區(qū)域的寬度和高度分別設置為17、13，其他參數(shù)取值均與圖6 相同。實驗結(jié)果如圖7 所示，供區(qū)的相對位置比較合理，供區(qū)內(nèi)的廠站網(wǎng)格分布也比較均勻，能夠清晰地分辨出線路走向，線路交叉比較少。某省調(diào)結(jié)合調(diào)控云數(shù)據(jù)云平臺，其應用界面如圖8 所示。

圖7 106 座廠站網(wǎng)格布局結(jié)果Fig. 7 Grid layout of 106 stations

圖8 電網(wǎng)接線圖應用于潮流可視化的界面Fig. 8 UI of power flow visualization with power grid diagram

5 結(jié)語

針對供區(qū)劃分的廠站網(wǎng)格均勻圖的自動布局，本文提出了力導向網(wǎng)格布局改進算法。力導向網(wǎng)格布局改進算法引入了廠站權(quán)重系數(shù)，重新定義了排斥力和吸引力的計算方法，采用兩向模擬退火算法控制廠站布局均勻?；诠﹨^(qū)劃分的廠站網(wǎng)格均勻圖的自動布局分為2 個階段：供區(qū)的布局區(qū)域劃分和廠站的全局優(yōu)化。將本文算法應用到某省廠站網(wǎng)格均勻圖的自動生成，表明本文算法得到的網(wǎng)格均勻圖中廠站能夠比較均勻地分布在供區(qū)內(nèi)的網(wǎng)格點上，可以滿足用戶的實際需求。下一步將在本文算法基礎上廠站優(yōu)化布局的同時對線路進行橫平豎直優(yōu)化布局。