基于供區的輸電網接線圖廠站網格布局算法

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

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

0 引言

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

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

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

1 基于供區的廠站網格布局數學模型

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

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

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

（2）廠站分布均勻度E2。廠站分布均勻度是衡量廠站分布均勻性的指標。先從水平方向均勻地劃分布局區域，再從豎直方向均勻地劃分布局區域，統計每個區域塊內廠站個數。其計算公式為

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

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

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

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

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

基于以上優化效果分析，本文優化目標函數為

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

2 力導向算法及其改進

2.1 F&R 算法簡介

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

2.2 力導向網格布局改進算法

2.2.1 預處理

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

2.2.2 吸引力的計算

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

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

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

2.2.3 排斥力的計算

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

式中：D為試驗參數；F1，F2為排斥力計算過程中引入的新力。

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

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

2.2.4 廠站的偏移

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

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

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

式中：p3和p4為實驗參數。指數型模擬退火函數式（15）使廠站在循環初期快速地排開，在循環后期快速地趨于穩定狀態?？紤]到布局區域的寬度和高度可能不同，本文使用兩向模擬退火算法，即式（15）控制廠站在x軸和y軸方向上的不同最大位移，參數p3的取值受布局區域寬度和高度的影響。

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

3 基于供區劃分的廠站網格均勻布局

3.1 供區的布局區域劃分

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

3.1.1 供區坐標和供區相對位置的計算

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

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

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

式中：n為供區中心點的個數；w為供區內廠站個數與所有供區廠站個數的均值的比值。

3.1.2 劃分布局區域的二分法

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

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

3.2 廠站布置的全局優化

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

式中：λ為權重系數。

3.3 基于供區劃分的廠站布局算法

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

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

4 實驗分析與結果

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

4.1 供區布局結果及分析

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

4.2 線路交叉值測試結果及分析

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

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

4.3 廠站分布均勻度測試結果及分析

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

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

廠站網格布局數學模型為多目標函數，且主要目標為減少交叉，因此廠站分布均勻度并沒有呈現出穩定的下降狀態，但交叉數目快速減少。

4.4 線路長度合理度測試結果及分析

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

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

4.5 廠站網格化布局處理結果及分析

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

圖5 網格處理局部結果對比Fig. 5 Comparison of local results of grid processing

4.6 實驗結果及分析

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

圖6 58 座廠站網格布局結果Fig. 6 Grid layout of 58 stations

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

4.7 基于真實數據的廠站網格布局

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

圖7 106 座廠站網格布局結果Fig. 7 Grid layout of 106 stations

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

5 結語

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