輸電網(wǎng)接線圖增量自動(dòng)成圖算法①

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

(南瑞集團(tuán)(國(guó)網(wǎng)電力科學(xué)研究院)有限公司 南京南瑞信息通信科技有限公司,南京 210003)

引言

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

而本文對(duì)廠站布局也是采用力導(dǎo)向算法[2];而在線路規(guī)劃中采用A*算法[3]進(jìn)行線路規(guī)劃;創(chuàng)新性的提出了評(píng)價(jià)算法反饋廠站布局進(jìn)行微調(diào)再布線,不斷調(diào)整之后得到一個(gè)美觀的廠站線路規(guī)劃圖.同時(shí),算法還增加了在不改變歷史廠站線路布局的情況下,對(duì)新添加的廠站線路增量靈活布局的功能,保證了歷史數(shù)據(jù)的穩(wěn)定性.

自動(dòng)成圖算法分為3 個(gè)模塊,第1 部分,對(duì)廠站的位置進(jìn)行布局,為廠站找到合適的位置;第2 部分,對(duì)廠站之間相連的線路采用A*算法進(jìn)行線路規(guī)劃.最后一部分是將成圖之后的結(jié)果進(jìn)行評(píng)價(jià)反饋,對(duì)于一些不合理的廠站和線路的布局不合理的進(jìn)行微調(diào),通過(guò)局部微調(diào)適應(yīng)整體布局.

輸電網(wǎng)接線的成圖算的目標(biāo)是:

1)廠站之間的相對(duì)空間的位置關(guān)系應(yīng)該和實(shí)際的地理相對(duì)位置關(guān)系大致相似.此目的是保證使用人員對(duì)輸電網(wǎng)線路的位置上的使用習(xí)慣.

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

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

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

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

1 廠站網(wǎng)格布局

1.1 廠站網(wǎng)格布局的數(shù)學(xué)模型

廠站位置的布局是線路規(guī)劃的基礎(chǔ)和前提,布局結(jié)果的優(yōu)劣直接關(guān)系到線路規(guī)劃的成圖效果.一個(gè)良好的廠站位置布局,主要表現(xiàn)在廠站在畫(huà)板上分布均勻、相鄰之間的廠站的距離合理等幾個(gè)方面.

廠站位置布局可以抽象成圖當(dāng)中的點(diǎn),輸電線路抽象成圖中的邊,節(jié)點(diǎn)和邊就構(gòu)成一個(gè)圖模型.因此廠站布局和輸電線路規(guī)劃就轉(zhuǎn)換成點(diǎn)的布局和兩點(diǎn)之間邊的路徑規(guī)劃.

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

在FR 算法中,需要計(jì)算以下幾個(gè)值.設(shè)定畫(huà)布的寬為W,高為H,則畫(huà)布大小為[8]:

理想距離:

其中,|V|是節(jié)點(diǎn)的數(shù)量.

節(jié)點(diǎn)之間的歐式距離:

為了保證節(jié)點(diǎn)之間的距離稀疏合理,需要計(jì)算節(jié)點(diǎn)之間引力和斥力.然而斥力存在于所有節(jié)點(diǎn)之間,而引力只存在于兩個(gè)節(jié)點(diǎn)之間存在連線的情況,這正好符號(hào)我們常規(guī)的理解,有關(guān)聯(lián)的節(jié)點(diǎn)之間的距離要近,無(wú)關(guān)聯(lián)的節(jié)點(diǎn)距離遠(yuǎn).所以有節(jié)點(diǎn)u和節(jié)點(diǎn)v之間的引力函數(shù):

節(jié)點(diǎn)u和節(jié)點(diǎn)v之間的斥力函數(shù):

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

廠站布局算法是基于FR 算法為核心進(jìn)行設(shè)計(jì)的,在迭代過(guò)程中,很容易出現(xiàn)局部?jī)?yōu)而整體差的情況.為了避免這種情況,本文選用模擬退火算法替代傳統(tǒng)的迭代方式,避免局部?jī)?yōu)化的情況.模擬退火算法是模擬物理學(xué)上物體逐漸降溫的物理過(guò)程,溫度越低,能量越低;最后達(dá)到相對(duì)穩(wěn)定的狀態(tài).

線性溫度下降表達(dá)式:

Tt為當(dāng)前時(shí)刻溫度,Tt+1下 一時(shí)刻溫度,γ為冷卻系數(shù),且一般為略小于1 的正數(shù).

本文設(shè)置初始溫度為T(mén)0=1000,停止溫度為T(mén)end=1.

為了選擇最優(yōu)的布點(diǎn)結(jié)果,本文采用以下幾個(gè)評(píng)價(jià)函數(shù)進(jìn)行評(píng)價(jià):

點(diǎn)的布局評(píng)價(jià)函數(shù)[8]:

1.2 廠站網(wǎng)格布局的算法實(shí)現(xiàn)

FR 算法的核心步驟主要分為3 個(gè)部分,首先計(jì)算圖中各點(diǎn)之間的斥力,其次計(jì)算有邊相連的節(jié)點(diǎn)之間的引力,最后計(jì)算斥力和引力的合力來(lái)計(jì)算節(jié)點(diǎn)的移動(dòng)位置.然而,每一次計(jì)算只能得到圖的部分能量最小,要得到全局的能量最小,需要經(jīng)過(guò)多次迭代才能夠滿足需求.

在點(diǎn)的一定次數(shù)的位置偏移中,隨著迭代次數(shù)的增多,位置的調(diào)整也越來(lái)越微小,圖形之間的布局會(huì)越來(lái)越好.在模擬退火算法中,給出初始溫度和冷卻速率來(lái)限制節(jié)點(diǎn)的最大位移.隨著溫度的降低,位置的偏移會(huì)越來(lái)越細(xì)微,使得圖最終能夠得到一個(gè)相對(duì)穩(wěn)定的狀態(tài).在算法實(shí)現(xiàn)過(guò)程中,為了得到較好的布點(diǎn)效果,算法添加了并發(fā)的參數(shù)循環(huán)計(jì)算,利用計(jì)算機(jī)多核CPU 的計(jì)算性能,計(jì)算出最優(yōu)的參數(shù)值.

1.2.1 節(jié)點(diǎn)布局的偽代碼

節(jié)點(diǎn)布局的偽代碼如圖1所示.

圖1 節(jié)點(diǎn)布局算法偽代碼

1.2.2 布點(diǎn)實(shí)驗(yàn)

不同的彈力系數(shù)F1和 斥力系數(shù)F2對(duì)點(diǎn)的布局影響會(huì)非常的大,故該算法通過(guò)多線程并行的計(jì)算不同F(xiàn)1、F2參數(shù)條件布點(diǎn)之后的相交代價(jià),通過(guò)比較,選擇最小代價(jià)的參數(shù)F1、F2和布局結(jié)果.在實(shí)驗(yàn)中,不同數(shù)據(jù)輸入的情況中,動(dòng)態(tài)計(jì)算參數(shù)F1和F2的值比固定的F1和F2的值的效果要好很多.

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

通過(guò)表1數(shù)據(jù)結(jié)果可以看到,當(dāng)冷卻系數(shù)為0.93時(shí),交叉偏差乘積最小,運(yùn)行時(shí)間最短.而且通過(guò)實(shí)驗(yàn)發(fā)現(xiàn),布局效果不是隨著冷卻系數(shù)的增加而改變,而是先增加后減小.同時(shí),冷卻系數(shù)對(duì)引力、斥力系數(shù)也有影響,不同的冷卻系數(shù)得到不同的引力、斥力.

表1 冷卻系數(shù)γ 取值在0.90～0.95 的布點(diǎn)結(jié)果表

對(duì)應(yīng)圖中的結(jié)果,生成如圖2所示的節(jié)點(diǎn)布局圖.

圖2中的6 幅圖分別展示了49 個(gè)節(jié)點(diǎn)和連線的分布情況.從圖中看出,從 γ=0.92開(kāi)始,點(diǎn)的布局就變的扁長(zhǎng),點(diǎn)的布局也較為稀疏.單具體才差別并不大.但從表1的測(cè)試結(jié)果數(shù)據(jù)中可以知道,當(dāng) γ=0.93時(shí),效果最好.

圖2 冷卻系數(shù)γ 取值在0.90～0.95 的布點(diǎn)結(jié)果圖

2 輸電線路規(guī)劃

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

2.1 目標(biāo)

經(jīng)過(guò)第一步節(jié)點(diǎn)布局的基礎(chǔ)上,得到密度合理的節(jié)點(diǎn)分布,線路規(guī)劃的目標(biāo)有以下幾個(gè)方面:

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

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

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

4)所有節(jié)點(diǎn)必須在網(wǎng)格點(diǎn)上.

通過(guò)上面的要求和目標(biāo),本文設(shè)計(jì)了下面的代價(jià)模型.

2.2 代價(jià)函數(shù)模型

在A*算法中,代價(jià)函數(shù)g(x)和h(x)決定線路的走向.而h(x)作為啟發(fā)函數(shù),其作用是控制A*算法的行為,引導(dǎo)A*算法快速接近目標(biāo)節(jié)點(diǎn).g(x)在A*算法中對(duì)路徑規(guī)劃起主要作用,它決定兩點(diǎn)之間中間的路徑該如何規(guī)劃.

下面為起點(diǎn)到節(jié)點(diǎn)i的最小代價(jià)函數(shù)ti:

ti?1表 示起點(diǎn)到當(dāng)前節(jié)點(diǎn)的最小代價(jià),則tend表示到從起點(diǎn)到終點(diǎn)的代價(jià)值,其中min(ω1f1+ω2f2+ω3f3+ω4f4)為 當(dāng)前節(jié)點(diǎn)到下一節(jié)點(diǎn)的g(x)最小代價(jià).ω1、ω2、ω3、ω4為權(quán)重系數(shù),f1為 線路交叉函數(shù);f2為線路拐角函數(shù);f3為 區(qū)域影響函數(shù);f4為路徑長(zhǎng)度函數(shù).

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

1)線路交叉函數(shù)

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

2)線路拐角函數(shù)

針對(duì)不同的線路出線情況,設(shè)定不同的權(quán)重值.

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

3)區(qū)域影響函數(shù)

設(shè)起點(diǎn)為P,終點(diǎn)為Q,中間某一節(jié)點(diǎn)的E,區(qū)域影響函數(shù)為:

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

圖3是經(jīng)過(guò)E點(diǎn)時(shí),F(P,E)=1,F(Q,E)=1;同樣在經(jīng)過(guò)E21時(shí),F(P,E21)=1,F(Q,E21)=1; 而F(P,E12)=0,F(Q,E12)=1;故此時(shí)會(huì)選擇P→E12→Q這條路徑.此外,a3>b3的作用是規(guī)范路徑出線的方向,當(dāng)一個(gè)點(diǎn)的出線較多時(shí),對(duì)其它的線路影響相對(duì)較小一些.

4)路徑長(zhǎng)度函數(shù)

路徑函數(shù)的作用是記錄線路的路徑長(zhǎng)度,可以減少線路之間不必要的步數(shù).當(dāng)兩條線路起點(diǎn)終點(diǎn)一致的情況下,優(yōu)先選擇路徑長(zhǎng)度f(wàn)4最 小的情況.其中a4為路徑函數(shù)的權(quán)重系數(shù).

圖3 區(qū)域影響函數(shù)示意圖

2.3 路徑規(guī)劃算法

路徑規(guī)劃A*算法的核心是如何計(jì)算代價(jià)函數(shù),它決定了從起點(diǎn)到終點(diǎn)每一個(gè)中間節(jié)點(diǎn)的位置.它的代價(jià)函數(shù)為:

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

2.3.1 數(shù)據(jù)預(yù)處理

1)線路去重

因?yàn)檩旊娋€路中有大量的起點(diǎn)終點(diǎn)變電站一致的情況.如“代東I 線”和“代東II 線”,這兩條輸電線路的起點(diǎn)變電站和終點(diǎn)變電站都為代王變和東郊變.在后面的路徑規(guī)劃中,因?yàn)橐婕暗骄€路交叉和重復(fù)計(jì)算的情況,所以,要在路徑規(guī)劃前,先去除重復(fù)的線路.之后在顯示線路時(shí),在通過(guò)節(jié)點(diǎn)偏移算法將重復(fù)的線路按照相對(duì)位置進(jìn)行偏移.

2)線路排序

按照線路的電壓等級(jí)和線路長(zhǎng)度兩個(gè)參數(shù)進(jìn)行排序.優(yōu)先按照電壓等級(jí)由高到低,其次是按照線路的長(zhǎng)度由短到長(zhǎng)進(jìn)行排序.按照習(xí)慣,電壓等級(jí)高的線路作為核心線路,要求為橫平豎直,交叉和拐角少,所以優(yōu)先對(duì)其進(jìn)行排序.第二按照線路由短到長(zhǎng)進(jìn)行排序,目的是優(yōu)先安排短的線路,短的線路相比長(zhǎng)的線路更容易布置且不會(huì)有太多的拐角.實(shí)驗(yàn)過(guò)程中發(fā)現(xiàn),不同排序順序的成圖效果會(huì)非常大.

3)剔除T 接線

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

2.3.2 路徑規(guī)劃算法描述

第1 步.單線路路徑規(guī)劃.

(1)依次處理預(yù)先已排序的線路,優(yōu)先對(duì)高電壓等級(jí)的線路進(jìn)行布線.設(shè)定電壓門(mén)檻值,若高于此值,則出線方向?yàn)樯舷伦笥壹案鱾€(gè)方向的45 度角等8 個(gè)方向;否則出線方向增加30 度和60 度等16 個(gè)方向.此為第一步出線.

(2)使用A*算法實(shí)現(xiàn)從起點(diǎn)到終點(diǎn)的線路規(guī)劃,得到路徑的中間拐點(diǎn).

第2 步.T 節(jié)線處理.

因?yàn)門(mén) 接線是一種特殊的線路,它的一端是主線路的一個(gè)T 接點(diǎn),另一端是廠站.所以在線路規(guī)劃中,首先需要在主線路上找一個(gè)合適的點(diǎn)作為T(mén) 接點(diǎn),本文算法是在主線路中最長(zhǎng)線段的等分點(diǎn),如有一個(gè)T 接點(diǎn),則為二等分點(diǎn)處.之后在按照第一步的算法進(jìn)行線路規(guī)劃.

第3 步.重復(fù)路徑偏移.

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

(2)將每條線路的中間節(jié)點(diǎn)進(jìn)行優(yōu)化,若連續(xù)的3 個(gè)點(diǎn)在一條直線上,則去除中間點(diǎn).此過(guò)程是減少線路中的多余節(jié)點(diǎn).若中間節(jié)點(diǎn)太多,則加入反饋列表,對(duì)廠站布局進(jìn)行反饋.

(3)對(duì)重復(fù)的線路按照某種特定的規(guī)則進(jìn)行偏移.本文實(shí)驗(yàn)中采用每?jī)蓷l線相隔4 個(gè)單位.

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

2.4 路徑規(guī)劃算法樣例

圖4為使用A*路徑規(guī)劃算法,結(jié)合代價(jià)函數(shù)模型的路徑節(jié)點(diǎn)的代價(jià)圖.圖中的數(shù)字為起點(diǎn)A為到終點(diǎn)B中間所計(jì)算的各個(gè)節(jié)點(diǎn)的最小代價(jià).其中從點(diǎn)A到點(diǎn)B的最小代價(jià)為10,在圖中為灰色有背景部分.直觀上看,符合成圖的最終需求.

3 線路規(guī)劃反饋廠站布局

在線路規(guī)劃過(guò)程中點(diǎn)是固定的,所以一定會(huì)產(chǎn)生點(diǎn)布局不合理而導(dǎo)致線路規(guī)劃不美觀的情況,因此需要對(duì)已經(jīng)規(guī)劃好的線路,進(jìn)行點(diǎn)的位置的調(diào)整.本文所采取的策略為增加反饋環(huán)節(jié),多次對(duì)點(diǎn)進(jìn)行反饋微調(diào)來(lái)達(dá)到目標(biāo)的美觀效果.圖5為線路規(guī)劃反饋算法的流程圖.

圖4 線路規(guī)劃代價(jià)圖

圖5 線路規(guī)劃反饋算法流程圖

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

而本文設(shè)定的反饋閾值L為所有線路規(guī)劃前10%的代價(jià)值,換句話說(shuō),就是每次對(duì)至少10%的線路進(jìn)行微調(diào).

選取42 個(gè)點(diǎn)和68 條線進(jìn)行實(shí)驗(yàn).經(jīng)過(guò)初始布局和三次迭代之后,輸出結(jié)果.在反饋過(guò)程中,布局總代價(jià)逐漸減少,點(diǎn)布局和線規(guī)劃都存在位置的改變和優(yōu)化,成圖效果不斷改善.圖6為不同迭代時(shí)期的代價(jià)及成圖效果.

圖6 反饋成圖效果

4 增量廠站線路規(guī)劃

隨著輸電線路的不斷建設(shè),廠站線路投運(yùn)和退役是比較常見(jiàn)的事.所以在廠站線路布局完初始布局完以后,有新的廠站線路投運(yùn)再次布局時(shí),就需要不改變?cè)瓉?lái)的線路和廠站位置,只調(diào)整和布局相關(guān)的廠站和線路即可.為了滿足這個(gè)需求,只需在廠站布局和線路規(guī)劃算法做一些預(yù)處理和微調(diào)即可.

1)數(shù)據(jù)預(yù)處理

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

同時(shí)設(shè)置所有線路和所有廠站兩個(gè)變量,供廠站布局使用.

2)廠站布局

在所有處理邏輯不變的情況下,只改變循環(huán)變量.新建廠站在計(jì)算排斥力時(shí),只計(jì)算新建廠站與其它所有廠站之間的斥力;計(jì)算引力時(shí),只計(jì)算該場(chǎng)站與其它相關(guān)聯(lián)的廠站的引力.這樣對(duì)歷史廠站的位置不會(huì)產(chǎn)生影響,只需布置新的廠站的位置.

3)線路規(guī)劃

線路規(guī)劃也只需將循環(huán)變量改為新建線路;只規(guī)劃新建線路的中間節(jié)點(diǎn)的路徑.

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

圖7 增量成圖效果

5 評(píng)價(jià)及實(shí)驗(yàn)結(jié)果

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

表2 冷卻系數(shù)γ 取值在0.90～0.95 的布線結(jié)果

圖8 冷卻系數(shù)γ 取值在0.90～0.95 的布線結(jié)果

6 結(jié)語(yǔ)

本文通過(guò)實(shí)現(xiàn)改進(jìn)力導(dǎo)向算法和A*算法,構(gòu)建了一個(gè)線路規(guī)劃的模型函數(shù)及評(píng)價(jià)函數(shù),并通過(guò)布點(diǎn),布線,反饋三個(gè)步驟,實(shí)現(xiàn)了輸電線路增量自動(dòng)成圖的功能.同時(shí)還對(duì)影響成圖的參數(shù)進(jìn)行了實(shí)驗(yàn)比對(duì),得到了當(dāng) γ=0.92 或者γ=0.93時(shí)成圖效果較好.由于成圖的時(shí)間復(fù)雜度高,存在當(dāng)數(shù)據(jù)量較大時(shí),成圖時(shí)間較長(zhǎng)的問(wèn)題.下一步需要深入研究,解決這方面問(wèn)題.