趙 越, 李 培, 王 震, 王 平

?

單線圖動(dòng)態(tài)規(guī)劃最優(yōu)布局成圖技術(shù)①

趙 越1, 李 培1, 王 震2, 王 平2

1(國(guó)網(wǎng)江蘇省電力公司揚(yáng)州供電公司, 揚(yáng)州225000)2(廈門億力吉奧信息科技有限公司, 廈門361008)

提出了一種基于動(dòng)態(tài)規(guī)劃算法得到布局最優(yōu)解實(shí)現(xiàn)區(qū)域電網(wǎng)單線圖生成的方法. 根據(jù)電網(wǎng)空間數(shù)據(jù)構(gòu)建拓?fù)淠Ｐ? 執(zhí)行廣度優(yōu)先算法得到多個(gè)能構(gòu)成連通圖的鄰接矩陣以及矩陣遍歷序列, 根據(jù)鄰接矩陣寬度計(jì)算出能容納全部設(shè)備的正方形范圍, 并建立了設(shè)備最小間距為優(yōu)化目標(biāo)的數(shù)學(xué)模型. 提出了動(dòng)態(tài)規(guī)劃最優(yōu)布局求解的算法, 應(yīng)用該算法求解布局最優(yōu)解數(shù)組, 最后按照最少交叉原則進(jìn)行正交化處理. 應(yīng)用實(shí)例表明通過(guò)最優(yōu)解布局的成圖美觀且高效.

區(qū)域電網(wǎng); 拓?fù)淠Ｐ? 動(dòng)態(tài)規(guī)劃算法; 單線圖; 布局最優(yōu)解

單線圖對(duì)于電網(wǎng)的意義和價(jià)值非常大, 不管是配網(wǎng)生產(chǎn)的規(guī)劃設(shè)計(jì)、電網(wǎng)調(diào)度的調(diào)度管理還是配網(wǎng)運(yùn)行的運(yùn)行檢修, 單線圖都是一種必不可少的常用工具. 不過(guò)隨著電網(wǎng)建設(shè)更新日新月異, 單線圖更新也日益頻繁, 同時(shí)電網(wǎng)用戶對(duì)于單線圖的展現(xiàn)效果要求亦不斷提高, 因此單線圖的維護(hù)工作量越來(lái)越多, 如果能有一種可行、高效、美觀的單線圖自動(dòng)生成方法來(lái)解決這個(gè)難題, 就可以進(jìn)一步提高配網(wǎng)生產(chǎn)的工作效率.

當(dāng)前國(guó)內(nèi)許多學(xué)者針對(duì)電網(wǎng)地理信息到單線圖的自動(dòng)生成課題進(jìn)行了大量研究[1-3]. 同時(shí)國(guó)內(nèi)外還有很多學(xué)者對(duì)于退火算法、樹(shù)圖算法、遺傳算法等各種先進(jìn)算法在單線圖布線上的結(jié)合應(yīng)用也進(jìn)行了研究和實(shí)踐[4-13]. 以上文獻(xiàn)提出的單線圖自動(dòng)生成方法都有一定的參考價(jià)值, 但是無(wú)法滿足目前日益復(fù)雜的電網(wǎng)結(jié)構(gòu)以及用戶不斷提高的布局展示要求.

如何設(shè)計(jì)合適算法, 結(jié)合電力GIS系統(tǒng)準(zhǔn)確高效的實(shí)現(xiàn)單線圖的自動(dòng)生成, 值得進(jìn)行深入研究, 本文在深入了解電網(wǎng)單線圖自動(dòng)生成具體要求以及綜合各種先進(jìn)布局理論算法后, 提出了運(yùn)用動(dòng)態(tài)規(guī)劃算法分階段計(jì)算并最終得到符合電網(wǎng)生產(chǎn)實(shí)際使用所需單線圖自動(dòng)生成的方法.

1 基于動(dòng)態(tài)規(guī)劃算法的圖形布局機(jī)制

目前行業(yè)內(nèi)存在各種專題圖系統(tǒng), 其中圖形布局所采用的算法基本上為以下三種算法.

a) 樹(shù)圖布局算法: 層次數(shù)據(jù)的空間填充性布局算法;

缺點(diǎn): 應(yīng)對(duì)復(fù)雜層次數(shù)據(jù)時(shí), 有序樹(shù)圖正方化性能差, 難以滿足各層數(shù)據(jù)展現(xiàn)需求, 需要人工參與.

b) 正交遺傳算法: 通過(guò)旋轉(zhuǎn)正交法快速提取解空間中的優(yōu)異個(gè)體的布局算法;

缺點(diǎn): 算法對(duì)新空間的探索能力是有限的, 也容易收斂到局部最優(yōu)解. 涉及到大量個(gè)體的計(jì)算, 當(dāng)問(wèn)題復(fù)雜時(shí), 嚴(yán)重影響性能, 同時(shí)對(duì)非線性約束的處理方式是添加懲罰因子, 這是一筆不小的性能開(kāi)支.

c) 有向無(wú)環(huán)算法: 采用消環(huán)、分層、排序、路徑管理的布局算法.

缺點(diǎn): 很多電網(wǎng)數(shù)據(jù)局部成環(huán), 無(wú)法處理.

為了避免布局時(shí)的人工參與, 減少計(jì)算性能消耗, 在通過(guò)綜合蟻群算法、褪火算法、正交遺傳算法、貪心算法、動(dòng)態(tài)規(guī)劃算法等先進(jìn)理論算法后, 最終在動(dòng)態(tài)規(guī)劃算法的基礎(chǔ)上延伸拓展出最適合電力網(wǎng)絡(luò)的布局算法.

動(dòng)態(tài)規(guī)劃算法基本思想與分治法類似, 將問(wèn)題分解為N個(gè)子問(wèn)題, 依次解決各子問(wèn)題, 最后一個(gè)子問(wèn)題就是初始問(wèn)題的解. 在實(shí)際應(yīng)用中動(dòng)態(tài)規(guī)劃算法可按以下幾個(gè)簡(jiǎn)化的步驟進(jìn)行設(shè)計(jì):

(1) 分析最優(yōu)解的性質(zhì), 并刻畫(huà)其結(jié)構(gòu)特征;

(2) 遞歸的定義最優(yōu)解;

(3) 以自底向上或自頂向下的記憶化方式(備忘錄法)計(jì)算出最優(yōu)值;

(4) 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息, 構(gòu)造問(wèn)題的最優(yōu)解.

2 單線圖自動(dòng)生成技術(shù)設(shè)計(jì)思路

基于動(dòng)態(tài)規(guī)劃最優(yōu)布局算法的單線圖自動(dòng)生成設(shè)計(jì)思路如下.

a) 根據(jù)源地理沿布數(shù)據(jù)建立電網(wǎng)拓?fù)浯鎯?chǔ)模型, 實(shí)現(xiàn)設(shè)備、單線圖、拓?fù)潢P(guān)系的存儲(chǔ), 然后完成各段拓?fù)淠Ｐ偷娜ブ?、合并處? 建立網(wǎng)絡(luò)圖拓?fù)淠Ｐ?

b) 根據(jù)網(wǎng)絡(luò)圖拓?fù)淠Ｐ? 建立連通圖得到連通圖的鄰接矩陣, 然后采用廣度優(yōu)先遍歷算法遍歷鄰接矩陣頂點(diǎn)得到矩陣遍歷序列;

c) 開(kāi)啟動(dòng)態(tài)規(guī)劃算法對(duì)序列中的頂點(diǎn)信息求解最優(yōu)值, 得到最優(yōu)值數(shù)組[];

d) 遍歷最優(yōu)值數(shù)組, 按照最優(yōu)值坐標(biāo)放置設(shè)備, 通過(guò)圖形引擎完成每一個(gè)設(shè)備的渲染繪制;

e) 以最少交叉原則完成圖紙正交化處理.

上述步驟中, 重點(diǎn)在a步、c步、e 步中, 即如何建立網(wǎng)絡(luò)圖的拓?fù)淠Ｐ秃陀?jì)算網(wǎng)絡(luò)圖設(shè)備最優(yōu)坐標(biāo). 本文的處理方法是采用動(dòng)態(tài)規(guī)劃的方法結(jié)合電力接線圖特點(diǎn)計(jì)算得到設(shè)備布局最優(yōu)值數(shù)組.

3 網(wǎng)絡(luò)圖拓?fù)淠Ｐ蜆?gòu)建

(1) 單線圖對(duì)象存儲(chǔ)

根據(jù)電力系統(tǒng)的空間數(shù)據(jù), 按照線路進(jìn)行分類存儲(chǔ)設(shè)備信息和拓?fù)潢P(guān)系, 即構(gòu)建多線路模型, 以單條線路為標(biāo)記, 分別存儲(chǔ)各自對(duì)應(yīng)的設(shè)備信息和拓?fù)潢P(guān)系.

//單線圖對(duì)象

{

;// 設(shè)備集合

; //版本信息

;// 圖檔類型

;// 變電站名稱

; //饋線

;// 饋線名稱

;// 坐標(biāo)原點(diǎn)

; //連接關(guān)系列表

;// 關(guān)聯(lián)關(guān)系(包含關(guān)系)

}

(2) 網(wǎng)絡(luò)圖對(duì)象存儲(chǔ)

構(gòu)建基于單線圖的環(huán)網(wǎng)拓?fù)潢P(guān)系模型, 用于確定子圖檔與子圖檔之間的關(guān)系, 構(gòu)建連通圖模型, 通過(guò)聯(lián)絡(luò)關(guān)系來(lái)確定線路之間的關(guān)系是否正常, 聯(lián)絡(luò)關(guān)系為環(huán)網(wǎng)點(diǎn)(環(huán)網(wǎng)開(kāi)關(guān)), 拓?fù)潢P(guān)系模型包括饋線F1、饋線F2和聯(lián)絡(luò)開(kāi)關(guān)K三個(gè)基本屬性.

//網(wǎng)絡(luò)圖對(duì)象

{

;// 版本信息

>;// 包含的子圖檔

;// 聯(lián)絡(luò)關(guān)系

}

//聯(lián)絡(luò)關(guān)系模型

{

;// 聯(lián)絡(luò)開(kāi)關(guān)

1;// 饋線1的;

2;// 饋線2的

;// 與聯(lián)絡(luò)開(kāi)關(guān)相連的設(shè)備

}

(3) 合并與去重復(fù)處理

對(duì)構(gòu)建的各段拓?fù)潢P(guān)系模型進(jìn)行合并和去重處理; 其中, 如有需要還可以簡(jiǎn)化設(shè)備, 形成新的拓?fù)潢P(guān)系模型. 如圖 1、圖2 所示, 2 段拓?fù)渲?A1 與A2(B1 與 B2)均代表同一個(gè)設(shè)備, 為消去相同的, 需要對(duì)兩段拓?fù)渲械腁、 B 兩個(gè)設(shè)備進(jìn)行去重與合并處理, 融合成 A12、B12, 結(jié)果如圖 3 所示.

圖1 拓?fù)涠?

圖2 拓?fù)涠?

圖3 拓?fù)涠魏喜⑻幚斫Y(jié)果

最初的線路模型經(jīng)過(guò)去重與合并處理后生成了單條或者多條大的網(wǎng)絡(luò)拓?fù)淠Ｐ?

4 基于動(dòng)態(tài)規(guī)劃的成圖布局處理

4.1 基于動(dòng)態(tài)規(guī)劃的最優(yōu)值求解

(1) 獲取容納全部設(shè)備的正方形范圍

根據(jù)鄰接矩陣的寬度, 計(jì)算出一個(gè)能容納全部子圖檔并留有最少空位的正方形范圍, 考慮到范圍越大, 計(jì)算函數(shù)需要花費(fèi)的時(shí)間越大, 所以使用一個(gè)能容納全部子圖檔并留有最少空位的正方形范圍;

滿足:>=(-1)*(-1);

(2) 建立設(shè)備最小間距的目標(biāo)函數(shù)模型

遍歷第一個(gè)設(shè)備到最后一個(gè)設(shè)備, 如果兩個(gè)設(shè)備間有連接關(guān)系(,), 就計(jì)算兩個(gè)點(diǎn)之間的距離, 不重復(fù)計(jì)算距離, 為了減少設(shè)備間連接的交叉, 構(gòu)建的函數(shù)模型應(yīng)滿足有關(guān)系設(shè)備盡量緊湊, 同時(shí)不能重疊.

對(duì)應(yīng)的函數(shù)模型為:

為計(jì)算設(shè)備間距離的公式:

其中,和屬于1到L之間的正整數(shù), 代表每個(gè)備中心點(diǎn)的坐標(biāo)值;

(3) 動(dòng)態(tài)規(guī)劃算法求解最優(yōu)值

開(kāi)啟動(dòng)態(tài)規(guī)劃算法, 迭代尋找函數(shù)新的最優(yōu)解, 直到確定每個(gè)設(shè)備中心點(diǎn)的x和y的值.

a) 根據(jù)Link的長(zhǎng)度(序列長(zhǎng)度=設(shè)備數(shù)量)計(jì)算出頂點(diǎn)范圍, 構(gòu)建*個(gè)格子, 每個(gè)格子用于存儲(chǔ)當(dāng)前格子存儲(chǔ)的設(shè)備下標(biāo)編號(hào)和對(duì)應(yīng)的,值;

b) 根據(jù)動(dòng)態(tài)規(guī)劃算法, 按下標(biāo)計(jì)算出第一個(gè)設(shè)備順序放入空閑格子的函數(shù)值;

c) 根據(jù)連接關(guān)系尋找最優(yōu)解并迭代執(zhí)行該過(guò)程, 直至設(shè)備全部遍歷完成, 在迭代過(guò)程中需要判斷設(shè)備是否有連接, 如果無(wú)連接, 則將下標(biāo)記錄到無(wú)連接數(shù)組中, 繼續(xù)迭代該過(guò)程; 否則進(jìn)行動(dòng)態(tài)規(guī)劃算法, 按下標(biāo)繼續(xù)放置設(shè)備;

d) 遍歷完序列Link后, 整理數(shù)據(jù), 遍歷每個(gè)子圖檔存儲(chǔ)的唯一格子對(duì)象, 根據(jù)格子對(duì)象中的設(shè)備對(duì)象的下標(biāo)進(jìn)行排序, 并返回每個(gè)設(shè)備的和值.

本算法中, 以計(jì)算解出的值是否為最小值為最優(yōu)解, 即如果為最小值則記錄為最佳位置, 直至計(jì)算完畢后無(wú)法找到更小值為止. 計(jì)算完畢后, 如圖4所示, 按下標(biāo)存儲(chǔ)每個(gè)設(shè)備的最優(yōu)解, 最優(yōu)解數(shù)組的格式為[](二維整形數(shù)組), 比如[1,1], [2,2], [3,3]..., [1,1]對(duì)應(yīng)設(shè)備1的最佳位置.

得到最優(yōu)解數(shù)組的動(dòng)態(tài)規(guī)劃最優(yōu)布局算法如圖4所示.

圖4 最優(yōu)解數(shù)組生成流程圖

4.2 基于動(dòng)態(tài)規(guī)劃的圖紙正交化處理

經(jīng)過(guò)之前的處理, 每個(gè)設(shè)備都已經(jīng)按層等間距互不重疊地排列, 后續(xù)的調(diào)整都不應(yīng)該再調(diào)整設(shè)備的坐標(biāo), 所以我們參考設(shè)備的位置來(lái)完成圖紙正交化處理

根據(jù)單線圖基本布局規(guī)則, 所有設(shè)備之間的連線都應(yīng)該是橫平豎直的, 所以需要對(duì)設(shè)備連接線按照某些規(guī)則添加一些拐點(diǎn)形成正交化的形態(tài). 我們目前采用的是動(dòng)態(tài)規(guī)劃的方法為邊線添加拐點(diǎn)達(dá)到正交化, 圖5是一幅最優(yōu)布局后的圖, 我們從上到下逐層調(diào)整上下子設(shè)備之間的邊線.

以上圖為例調(diào)整上游設(shè)備與各下游設(shè)備之間連線的正交化. 首先求得上游設(shè)備連線的數(shù)目,然后求出一個(gè)中位數(shù)/2

對(duì)于每一條連線做如下處理:

(=-1;>=0;--)

{

處理左邊正交化;

+=3.0;;

}

(=;j<;++)

{

(==)

{處理中間正交化;MiddleSpace+=2.0;}

Else

{處理右邊正交化;RightSpace-=3.0;}

}

a) 處理左連線正交化

圖5 設(shè)備連線正交化處理前

圖6 處理左連線正交化

b) 處理中間連線正交化

圖7 中間連線正交化

c) 處理右連線正交化

圖8 右連線正交化

以上三種處理方法都要考慮到一種情況, 如圖9, 設(shè)備X2 本身有多條線穿出, 當(dāng)前調(diào)整的這條線從哪邊穿出能減少與其他邊的交叉是很值得考慮的.

圖9 連線正交化參考下游設(shè)備調(diào)整

5 算法示例

本文引用某地區(qū)電網(wǎng)架構(gòu)模型, 該模型具備線路之間環(huán)網(wǎng)多的特點(diǎn), 可用于驗(yàn)證上述原理. 某地區(qū)局部電網(wǎng)聯(lián)絡(luò)線路數(shù)據(jù)如表1所示.

表1 某地區(qū)局部電網(wǎng)聯(lián)絡(luò)線路數(shù)據(jù)

表中, 第1列表示聯(lián)絡(luò)開(kāi)關(guān), 第2、3、4、5列都是有聯(lián)絡(luò)關(guān)系的線路. 某地區(qū)電網(wǎng)采用最優(yōu)布局算法前、后布局如圖9, 圖10所示. 可以看出采用動(dòng)態(tài)規(guī)劃最優(yōu)布局算法布局后圖形繪制區(qū)域整體布局更加均勻、美觀、清晰, 滿足單線圖自動(dòng)布局的要求. 驗(yàn)證了基于動(dòng)態(tài)規(guī)劃方法的最優(yōu)布局算法的正確性及有效性.

圖9 普通算法布局

圖10 動(dòng)態(tài)規(guī)劃算法布局

6 結(jié)語(yǔ)

本文提出了一種基于動(dòng)態(tài)規(guī)劃最優(yōu)布局算法的單線圖自動(dòng)生成方法. 通過(guò)分析現(xiàn)有布局算法的不足, 并深入研究布局過(guò)程, 采用動(dòng)態(tài)規(guī)劃思想重新設(shè)計(jì)布局算法, 為單線圖生成的自動(dòng)布局處理提供了更多的選擇. 通過(guò)對(duì)布局算法的優(yōu)化, 拓廣了動(dòng)態(tài)規(guī)劃方法的應(yīng)用范圍, 同時(shí)提高了單線圖自動(dòng)布局的效率和美觀程度.

與現(xiàn)有技術(shù)相比, 存在下面兩點(diǎn)優(yōu)點(diǎn):

第一、提出了由多條線路構(gòu)成的網(wǎng)絡(luò)連通圖構(gòu)想方案, 通過(guò)函數(shù)模型計(jì)算出連通圖頂點(diǎn)的位置來(lái)確定設(shè)備的位置, 并且該位置是最合適的, 能夠快速、完美成圖.

第二、放棄樹(shù)圖布局算法、遺傳算法等算法, 通過(guò)算法優(yōu)化, 使用動(dòng)態(tài)規(guī)劃算法計(jì)算出最優(yōu)解, 而不是近似的最優(yōu)解.

1 徐彭亮,何光宇,梅生偉,張王俊,王偉.基于地理信息的輸電網(wǎng)單線圖自動(dòng)生成新算法.電網(wǎng)技術(shù),2008,32(21):9–12.

2 劉健,吳媛,劉鞏權(quán).配電饋線地理圖到電氣接線圖的轉(zhuǎn)換.電力系統(tǒng)自動(dòng)化,2005,29(14):73–77.

3 章堅(jiān)民,葉琳,孫維真.基于地理相對(duì)位置的省級(jí)輸電網(wǎng)均勻接線圖自動(dòng)生成.電力系統(tǒng)自動(dòng)化,2010,(24):55–59.

4 陳學(xué)松,蔡述庭.基于模擬退火算法的矩形優(yōu)化排樣問(wèn)題的研究.數(shù)學(xué)的實(shí)踐與認(rèn)識(shí),2008,38(9):68–71.

5 沈偉,吳文傳,張伯明,鎬俊杰.能量管理系統(tǒng)中電網(wǎng)潮流單線圖自動(dòng)生成算法.電力系統(tǒng)目動(dòng)化,2010,34(6):48–53.

6 邢佳磊,楊洪耕,何亞平.地區(qū)電網(wǎng)運(yùn)行單線圖的智能自動(dòng)布局.電力系統(tǒng)自動(dòng)化,2010,34(4):59–64.

7 王治華,董樹(shù)鋒,張王俊.輸電網(wǎng)單線圖自生成的新方法.電力系統(tǒng)保護(hù)與控制,2010,38(18):155–159.

8 張旭,馮恩民.具有性能約束布局問(wèn)題的優(yōu)化算法及收斂性.大連理工大學(xué)學(xué)報(bào),2005,45(5):766–771.

9 陳勇,鄧其軍,周洪.無(wú)重疊交叉的配電網(wǎng)單線圖自動(dòng)生成算法.電力自動(dòng)化設(shè)備,2010,30(11):90–93.

10 Rossouw FJ, Beukes HJ, Enslin JHR. Modelling network problems with power flow equations and diagrams. AJ. Africon, 1999 IEEE, 1999, (2): 643–648.

11 Deng QJ, Zhou H, Chen Y. Design and implement of drawing of GOO one-line diagram of smart distribution network. 2010 International Conference Electrical and Control Engineering (ICECE). 2010. 3533–3536.

12 Li X, Feng XL, Zeng ZY, et al. Distribution feeder one-line diagrams automatic generation from geographic diagrams based on GIS. Third International Conference Electric Utility Deregulation and Restructuring and Power Technologies (DRPT 2008). 2008. 2228–2232.

13 Zhang LH, Pei XD, Kleine U. Analog macro-cell placement with very fast simulated re-annealing algorithm. Journal of Software, 2002, 13(6): 1059– 1062.

Optimal Layout Mapping Technology for Single Line Dynamic Programming

ZHAO Yue1, LI Pei1, WANG Zhen2, WANG Ping2

1(State Grid Yangzhou Power Supply Company, Yangzhou 225000, China)2(Xiamen Great Power GEO Information Technology Co. Ltd., Xiamen 361008, China)

A new method for generating the single line diagram of the regional power network is proposed based on the dynamic programming algorithm. According to the topological model of spatial data in power grid, the implementation of the breadth first algorithm can obtain the adjacency matrix and matrix traversal sequence of the connected graph, and the square range of the total equipment can be accommodated by the adjacency matrix. A dynamic programming optimal layout algorithm is proposed, which is used to solve the layout optimization problem. The application example shows that the optimal solution layout is beautiful and efficient.

regional power network; topological model; dynamic programming algorithm; single line graph; layout optimal solution

2015-11-13;

2015-12-21

[10.15888/j.cnki.csa.005256]