胡 榮,未召弟,符 楊
(上海電力學(xué)院電力與自動化工程學(xué)院,上海 200090)
配電系統(tǒng)自動分析是配電管理系統(tǒng)(DMS)的重要功能,其主要內(nèi)容包括配電網(wǎng)的拓?fù)浞治觥⒊绷饔?jì)算、可靠性計(jì)算、結(jié)構(gòu)優(yōu)化或網(wǎng)絡(luò)重構(gòu)、故障定位隔離與恢復(fù)等.網(wǎng)絡(luò)拓?fù)浞治龉δ芙鉀Q配電網(wǎng)電氣拓?fù)涞慕栴},是其他高級功能的基礎(chǔ)[1,2].在進(jìn)行結(jié)構(gòu)優(yōu)化、網(wǎng)絡(luò)重構(gòu)、故障恢復(fù)操作時,各種開關(guān)狀態(tài)組合會產(chǎn)生多種拓?fù)浣Y(jié)構(gòu),不僅會出現(xiàn)孤島,而且可能出現(xiàn)環(huán)路.因此,需對兩種情形進(jìn)行判斷,確保生成配電網(wǎng)輻射狀網(wǎng)架,以尋找滿足目標(biāo)函數(shù)最優(yōu)的網(wǎng)架結(jié)構(gòu).根據(jù)圖論概念,將配電網(wǎng)拓?fù)浣Y(jié)構(gòu)視為無向圖.目前多數(shù)文獻(xiàn)[3-5]采用鄰接表來存儲無向圖,物理模型不夠直觀,文獻(xiàn)[6]采用矩陣染色法對拓?fù)浣Y(jié)構(gòu)僅作連通性分析.本文采用鄰接矩陣存儲方法和深度優(yōu)先遍歷算法,動態(tài)檢測網(wǎng)絡(luò)拓?fù)淠P?
建立實(shí)用模型,實(shí)現(xiàn)圖模一體化,是網(wǎng)絡(luò)拓?fù)浞治龉δ艿年P(guān)鍵.配電網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)類似于一種數(shù)據(jù)結(jié)構(gòu)——圖.根據(jù)有關(guān)圖論知識,配電系統(tǒng)拓?fù)浣Y(jié)構(gòu)圖可表示為:
式中:V—— 包括電源、負(fù)荷側(cè)配變在內(nèi)的 n個節(jié)點(diǎn)的非空集;
D—— 邊的集合(配電網(wǎng)饋線集合).
如圖 1所示,當(dāng)兩節(jié)點(diǎn)的連接不涉及方向關(guān)系時,圖為無向圖,配電網(wǎng)絡(luò)拓?fù)鋱D為無向圖.當(dāng)兩節(jié)點(diǎn)之間存在邊(有連接關(guān)系)時,兩節(jié)點(diǎn)互為鄰接點(diǎn),對應(yīng)邊用(V1,V2)表示.對于無向圖,若每對節(jié)點(diǎn)之間都有路徑直接或間接相通,則該圖為連通圖.因此,無向圖 1為連通圖.
圖1 圖狀結(jié)構(gòu)G
從邏輯結(jié)構(gòu)看,圖是一種非線性結(jié)構(gòu),任意兩個節(jié)點(diǎn)都可能存在關(guān)系,因而圖的存儲方法也有很多.本文采用更直觀形象的鄰接矩陣存儲方法,利用網(wǎng)基結(jié)構(gòu)矩陣 Dn×n作為鄰接矩陣來描述配電網(wǎng)拓?fù)浣Y(jié)構(gòu),以及取決于配電線路的架設(shè)、線路開關(guān)的狀態(tài)和網(wǎng)絡(luò)運(yùn)行方式的配電網(wǎng)的潛在連接方式[7].若圖 1代表某一小型配電系統(tǒng),則其網(wǎng)基結(jié)構(gòu)矩陣為:
在配電分析系統(tǒng)中,配電網(wǎng)拓?fù)浣Y(jié)構(gòu)信息經(jīng)DSCADA系統(tǒng)實(shí)時采集并傳遞給 GIS動態(tài)生成,其網(wǎng)基結(jié)構(gòu)矩陣 Dn×n隨拓?fù)浣Y(jié)構(gòu)的變化而動態(tài)變化,因此需要快速有效的算法進(jìn)行動態(tài)檢測,實(shí)現(xiàn)結(jié)構(gòu)優(yōu)化、故障定位和隔離,以及供電快速恢復(fù)等高級功能.
配電系統(tǒng)多為環(huán)網(wǎng)設(shè)計(jì),開環(huán)運(yùn)行.每個用戶終端原則上必須備有雙側(cè)電源,一側(cè)電源在正常運(yùn)行方式下對負(fù)荷供電,另一側(cè)作為緊急備用電源.配電網(wǎng)的這種設(shè)計(jì)及運(yùn)行方式?jīng)Q定了配電網(wǎng)拓?fù)浣Y(jié)構(gòu)圖中除源節(jié)點(diǎn)之外的每個節(jié)點(diǎn)都有且只有一個父鄰接點(diǎn).若配電網(wǎng)絡(luò)不連通,即某節(jié)點(diǎn)沒有父鄰接點(diǎn),意味著此負(fù)荷點(diǎn)沒有電源供電,稱之為孤島;若某節(jié)點(diǎn)有兩個或兩個以上父鄰接點(diǎn),說明此負(fù)荷節(jié)點(diǎn)有多個電源,稱之為環(huán)路.
配電網(wǎng)環(huán)路有 2類[8]:一是 2個電源節(jié)點(diǎn)之間形成的環(huán)路,即從配電網(wǎng)的一個電源節(jié)點(diǎn)出發(fā),每個節(jié)點(diǎn)只經(jīng)過一次,到達(dá)本電源點(diǎn)或另一個電源節(jié)點(diǎn)的環(huán);二是負(fù)荷節(jié)點(diǎn)之間形成的環(huán)路,即從配電網(wǎng)的某一個節(jié)點(diǎn)出發(fā),每個節(jié)點(diǎn)只經(jīng)過一次,又回到這個節(jié)點(diǎn)的環(huán).配電網(wǎng)正常運(yùn)行拓?fù)浣Y(jié)構(gòu)中一般不允許出現(xiàn)孤島及環(huán)路.
文獻(xiàn)[6]對配網(wǎng)拓?fù)浣Y(jié)構(gòu)作出連通性判斷,但未對環(huán)路作出分析.本文將基于圖狀配電網(wǎng)拓?fù)浣Y(jié)構(gòu),采用高效算法實(shí)現(xiàn)配電網(wǎng)拓?fù)浣Y(jié)構(gòu)的孤島和環(huán)路的動態(tài)檢測功能.
為盡快找到最優(yōu)目標(biāo)函數(shù)(網(wǎng)損最小、可靠性最高等)的網(wǎng)絡(luò)結(jié)構(gòu),需淘汰拓?fù)浣Y(jié)構(gòu)不正常的網(wǎng)架結(jié)構(gòu).深度優(yōu)先遍歷算法(DFS)是一種人工智能算法,能夠自動尋優(yōu).其優(yōu)點(diǎn)是占內(nèi)存較少,通常情況下可不必完全遍歷即能找到最優(yōu)方案或接近方案,以節(jié)省計(jì)算時間,提高計(jì)算效率.
DFS算法進(jìn)行遍歷的過程是從某個頂點(diǎn)出發(fā),沿著某條搜索路徑對圖中每個節(jié)點(diǎn)各做一次且僅做一次訪問[9].原理如下:設(shè) x是當(dāng)前被訪問節(jié)點(diǎn),對 x做過訪問標(biāo)記后,選擇一條從 x出發(fā)的未檢測過的邊(x,y).若發(fā)現(xiàn)節(jié)點(diǎn) y已訪問過,則重新選擇另一條從 x出發(fā)的未檢測過的邊,否則沿邊(x,y)到達(dá)未曾訪問過的 y,對 y訪問并將其標(biāo)記;從 y開始搜索,直到搜索完從 y出發(fā)的所有路徑,即訪問完 y所有子節(jié)點(diǎn)之后,才回溯到節(jié)點(diǎn)x,再選擇一條從 x出發(fā)的未檢測過的邊.上述過程直至從 x出發(fā)的所有邊都已檢測過為止.此時,若 x不是源點(diǎn),則回溯到 x的父節(jié)點(diǎn),直至圖中所有和源點(diǎn)有路徑相通的節(jié)點(diǎn)(即源點(diǎn)的所有子節(jié)點(diǎn))都已被訪問過.若圖 1是連通圖,則遍歷過程結(jié)束,否則繼續(xù)選擇一個尚未被訪問的節(jié)點(diǎn)作為新源點(diǎn),進(jìn)行新的搜索過程.
電源點(diǎn)是配電網(wǎng)潮流首端,因此從電源點(diǎn)開始逐個遍歷,進(jìn)行標(biāo)記,依次遍歷其鄰接點(diǎn).若遍歷中搜索到其他電源點(diǎn),或某負(fù)荷節(jié)點(diǎn)被訪問 2次,即可判斷拓?fù)浣Y(jié)構(gòu)中存在環(huán)路;若遍歷過程結(jié)束,仍有某負(fù)荷節(jié)點(diǎn)不曾被訪問,則此負(fù)荷點(diǎn)為電源孤立節(jié)點(diǎn);若遍歷結(jié)束后未發(fā)現(xiàn)孤點(diǎn)或環(huán)路,說明配電網(wǎng)拓?fù)浣Y(jié)構(gòu)為正常運(yùn)行的輻射、開式網(wǎng)狀.
為使 DFS算法能夠快速高效檢測動態(tài)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),設(shè)置數(shù)組 visited[0,1,…,n-1]及環(huán)路判斷向量 path如下.
(1)數(shù)組 visited[0,1,…,n-1]的設(shè)置 由于圖中任一節(jié)點(diǎn)都可能與其他節(jié)點(diǎn)鄰接,在訪問了某節(jié)點(diǎn)之后,可能順著某條回路再次回到該節(jié)點(diǎn).為了避免重復(fù)訪問同一個節(jié)點(diǎn),必須標(biāo)記每個已訪問的節(jié)點(diǎn).為此,可設(shè)一數(shù)組 visited[0,1,…,n-1],visited[i]的初值為 0,一旦訪問了節(jié)點(diǎn) i之后,將其置為 1.
(2)環(huán)路判斷向量 path的設(shè)置 向量path記錄已訪問過且有可能產(chǎn)生環(huán)路的點(diǎn),path[i]的值隨程序的進(jìn)行會不斷變化,其原則是:訪問到某點(diǎn)后即將其放入 path中,若判斷完該點(diǎn)所有鄰接節(jié)點(diǎn)且沒有回路時,將該點(diǎn)從 path中刪除.
(3)動態(tài)檢測配電網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖的主要步驟 具體步驟如下.
第 1步 首先選取某個電源節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn) i(1≤i≤n),把 visited[i]置為 1,表示該點(diǎn)已被訪問,并將 i放入堆棧 path中.
第 2步 從 0~N中依次取當(dāng)前點(diǎn) i的各級鄰接點(diǎn) j,如果 j為另一電源點(diǎn)則說明存在一類環(huán)路;如果 j已被訪問過且 j不是當(dāng)前節(jié)點(diǎn) i的父節(jié)點(diǎn),則說明存在二類環(huán)路;如果出現(xiàn)以上兩種情況中的一種,則程序記下環(huán)路,然后逐層退出遞歸,反之則把 j作為當(dāng)前節(jié)點(diǎn)重新進(jìn)行深度優(yōu)先遍歷.如果 j≥N則說明當(dāng)前節(jié)點(diǎn)的所有連通節(jié)點(diǎn)已被處理完,此時把當(dāng)前節(jié)點(diǎn) i點(diǎn)從 path中移除,返回遞歸上一層.
第 3步 若上述判斷未發(fā)現(xiàn)環(huán)路,取出下一個電源點(diǎn)重復(fù)第 2步.
第 4步 判斷完所有電源點(diǎn)后,由所有的visited[i]統(tǒng)計(jì)從來沒有被訪問過的節(jié)點(diǎn),若有,標(biāo)記所有孤點(diǎn),否則該拓?fù)浣Y(jié)構(gòu)一切正常.配電網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的動態(tài)檢測流程見圖 2.
圖2 配電網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的動態(tài)檢測流程
根據(jù)流程圖編寫程序?qū)ε潆娋W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)進(jìn)行動態(tài)監(jiān)測,可以剔除存在孤島和環(huán)路的結(jié)構(gòu),以進(jìn)一步提高配電網(wǎng)網(wǎng)絡(luò)重構(gòu)、故障恢復(fù),以及尋找網(wǎng)損最小、可靠性最高的網(wǎng)架結(jié)構(gòu)的效率,并將檢驗(yàn)結(jié)果以可視化界面給出,將核心算法封裝為模塊供高級功能調(diào)用,從而進(jìn)一步提高計(jì)算效率.
在配電網(wǎng) GIS能夠直接讀取 DSCADA中的實(shí)時數(shù)據(jù)的前提下,只有配電網(wǎng)自動分析系統(tǒng)能夠辨識正常與非正常動態(tài)網(wǎng)絡(luò)結(jié)構(gòu),進(jìn)行潮流計(jì)算、網(wǎng)架結(jié)構(gòu)優(yōu)化、可靠性計(jì)算,才有現(xiàn)實(shí)意義,才能構(gòu)建強(qiáng)大的配電網(wǎng)系統(tǒng).
本文采用鄰接矩陣的形式表示配電網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖,深度優(yōu)先搜索(DFS)算法進(jìn)行圖的遍歷和搜索,編寫了“配電網(wǎng)拓?fù)浣Y(jié)構(gòu)動態(tài)檢測”程序.為增強(qiáng)直觀可視性,利用 VC++6.0編程工具,實(shí)現(xiàn)了友好的人機(jī)交互界面,并將核心算法封裝為獨(dú)立模塊,以便潮流計(jì)算、網(wǎng)絡(luò)優(yōu)化或重構(gòu)等高級功能軟件的調(diào)用.圖 3為典型的復(fù)雜配電網(wǎng)[10],此網(wǎng)架結(jié)構(gòu)中有 4個電源節(jié)點(diǎn) S1,S2,S3,S4,50個負(fù)荷節(jié)點(diǎn)(1~50),實(shí)線表示原始線路,虛線表示可運(yùn)行的線路.
圖3 典型的復(fù)雜配電網(wǎng)
分別對其各種非正常拓?fù)浣Y(jié)構(gòu)進(jìn)行動態(tài)檢測,如圖 4所示.界面中給出了各種配電網(wǎng)拓?fù)浣Y(jié)構(gòu)的檢測信息,對部分故障的負(fù)荷節(jié)點(diǎn)進(jìn)行標(biāo)記(方框顯示).
由圖 4a中的“檢測信息”可知,此復(fù)雜配電網(wǎng)中負(fù)荷節(jié)點(diǎn) 38為孤點(diǎn),即無電源對其進(jìn)行供電.由圖 4b中的“檢測信息”可知,此配電網(wǎng)結(jié)構(gòu)中負(fù)荷節(jié)點(diǎn) 11,12,45,44,38,32,39,33,34,35,36為雙向電源供電,構(gòu)成了一類環(huán)路.圖 4c給出了二類環(huán)路的非正常拓?fù)浣Y(jié)構(gòu),由“檢測信息”可知,11,12,45,44,38,15,14顯示均由電源 S2供電.
圖4 非正常拓?fù)浣Y(jié)構(gòu)
為了驗(yàn)證程序的運(yùn)行效率,采用文獻(xiàn)[10]至文獻(xiàn)[12]的算例給出的網(wǎng)架結(jié)構(gòu)進(jìn)行計(jì)算速度測算和正確率檢驗(yàn).對 3個算例可能出現(xiàn)的各種孤島和環(huán)路情況進(jìn)行的 600次試驗(yàn)表明,程序平均計(jì)算時間小于 1 ms,正確率達(dá) 100%,見表 1.
表1 程序運(yùn)算效率驗(yàn)證結(jié)果
由表 1可知,程序計(jì)算速度及穩(wěn)定可靠性均達(dá)到較高水平,完全可以高效地為配網(wǎng)重構(gòu)、故障恢復(fù)提供可信賴的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),檢驗(yàn)結(jié)果驗(yàn)證了涉及的思想、采用的方法的合理性與優(yōu)越性.
本文利用圖狀結(jié)構(gòu)進(jìn)行配電網(wǎng)絡(luò)拓?fù)浣?采用深度優(yōu)先遍歷算法進(jìn)行快速動態(tài)檢測,編程采用 VC++6.0軟件,建立了圖形用戶界面;將程序封裝為模塊,便于網(wǎng)絡(luò)重構(gòu)或故障恢復(fù)等高級功能軟件的調(diào)用.通過算例演示及軟件測試,驗(yàn)證了軟件的正確性與優(yōu)越性.
[1]顧秀芳,關(guān)長余.配電網(wǎng)潮流計(jì)算的拓?fù)浞治鲅芯浚跩].華北電力大學(xué)學(xué)報,2008,35(2):47-50.
[2]張宏,郭宗仁.基于節(jié)點(diǎn)—— 支路關(guān)聯(lián)矩陣的配電網(wǎng)饋線故障區(qū)域定位算法[J].電力自動化設(shè)備,2004,24(1):27-29.
[3]馬志剛,基于遺傳模擬退火算法的配電網(wǎng)重構(gòu)研究[D].南昌大學(xué),2006.
[4]邱生,張焰.用鄰接表保存中壓配電網(wǎng)拓?fù)浣Y(jié)構(gòu)[J].電力自動化設(shè)備,2005,3(3):57-59.
[5]王林川,潘文明,梁棟,等.一種基于鄰接矩陣的算法在配電網(wǎng)重構(gòu)中應(yīng)用[C]∥電力系統(tǒng)與自動化專業(yè)第 24屆學(xué)術(shù)年會論文集,2008:367-369.
[6]崔巖.鄰接矩陣染色法及其在電力系統(tǒng)網(wǎng)絡(luò)拓?fù)浞治鲋械膽?yīng)用[J].電力系統(tǒng)保護(hù)與控制,2008,36(16):52-56.
[7]劉健,畢鵬翔,楊文宇,等.配電網(wǎng)理論及應(yīng)用[M].北京:中國水利水電出版社,2007:7-12.
[8]楊建軍,戰(zhàn)紅,劉揚(yáng).基于環(huán)路和改進(jìn)遺傳算法的配電網(wǎng)絡(luò)重構(gòu)優(yōu)化[J].高電壓技術(shù),2007,33(5):109-113.
[9]SAHNISartaj.Data structures,algorithms,and applications in C++[M].Beijing:China Machine Press,2004:98-105.
[10]VLADIMIRO,MIRANDA,RANITO JV,etal.Genetic algorithms in optimalmultistage distribution network planning[J].IEEE Trans on Power Systems,1994,9(4):1 927-1 933.
[11]MORADI Adel,FOTUHI-FIRUZABAD M.Optimal switch placement in distribution systems using trinary partic le swarm optim ization algorithm[J].Trans.on Power Delivery,2008,23(1):271-279.
[12]W ATANABE Isamu,NODU Makoto.A genetic algorithm for optim izing switching sequence of service restoration in distribution systems[C]∥Proceedings of the 2004 Congress on Evolutionary Computation,2004:1683-1690.