徐成司, 董樹(shù)鋒, 孫 洲, 李春筱, 孫 明

(1. 浙江大學(xué)電氣工程學(xué)院, 浙江省杭州市 310027; 2. 國(guó)網(wǎng)紹興供電公司, 浙江省紹興市 312000)

基于網(wǎng)絡(luò)簡(jiǎn)化和深度優(yōu)先遍歷的配電網(wǎng)路徑搜索算法

徐成司1, 董樹(shù)鋒1, 孫 洲2, 李春筱2, 孫 明1

(1. 浙江大學(xué)電氣工程學(xué)院, 浙江省杭州市 310027; 2. 國(guó)網(wǎng)紹興供電公司, 浙江省紹興市 312000)

供電路徑分析在配電網(wǎng)分析中有著重要作用,但實(shí)際中配電網(wǎng)往往結(jié)構(gòu)復(fù)雜,在搜索供電路徑前需對(duì)配電網(wǎng)模型進(jìn)行適當(dāng)?shù)暮?jiǎn)化處理。文中提出一種基于公共信息模型(CIM)的配電網(wǎng)網(wǎng)絡(luò)模型簡(jiǎn)化方法,以及在其簡(jiǎn)化結(jié)果上的一種基于深度優(yōu)先遍歷的配電網(wǎng)路徑搜索算法。首先,將配電網(wǎng)模型存儲(chǔ)在圖數(shù)據(jù)結(jié)構(gòu)中,利用圖論算法進(jìn)行網(wǎng)絡(luò)簡(jiǎn)化。隨后,通過(guò)路徑搜索算法搜索得到負(fù)荷節(jié)點(diǎn)的所有供電路徑,并經(jīng)過(guò)分類得到3類路徑集合:按電源分類、按路徑終點(diǎn)負(fù)荷分類和按路徑經(jīng)過(guò)支路分類的路徑集合。該路徑搜索算法可用于配電網(wǎng)拓?fù)浣Y(jié)構(gòu)和支路通斷狀態(tài)等配電網(wǎng)分析描述中。最后,以某省會(huì)城市的一個(gè)實(shí)際配電網(wǎng)架和IEEE 123節(jié)點(diǎn)系統(tǒng)為例,分別驗(yàn)證了網(wǎng)絡(luò)簡(jiǎn)化方法和路徑搜索算法的有效性和實(shí)用性。

公共信息模型; 網(wǎng)絡(luò)簡(jiǎn)化; 深度優(yōu)先遍歷; 配電網(wǎng)拓?fù)? 路徑搜索

0 引言

隨著經(jīng)濟(jì)的發(fā)展,社會(huì)對(duì)電力的需求量增大,配電網(wǎng)的規(guī)劃和運(yùn)行分析日益重要,如規(guī)劃和靜態(tài)安全性分析中的N-1校核計(jì)算、配電網(wǎng)重構(gòu)的優(yōu)化計(jì)算、配電網(wǎng)饋線供電能力的評(píng)估[1]等。

配電網(wǎng)數(shù)學(xué)模型的建立是網(wǎng)絡(luò)分析應(yīng)用的基礎(chǔ)。目前公共信息模型(common information model,CIM)中的配電網(wǎng)擴(kuò)展模型正不斷成熟,在配電網(wǎng)中應(yīng)用廣泛[2-4]。另外,配電網(wǎng)在運(yùn)行中保持其輻射狀結(jié)構(gòu)是一個(gè)重要約束條件,有很多學(xué)者對(duì)配電網(wǎng)的拓?fù)涿枋龇椒ㄕ归_(kāi)了研究。文獻(xiàn)[5-6]提出用生成樹(shù)的搜索來(lái)得到符合要求的網(wǎng)絡(luò)拓?fù)洹Ｎ墨I(xiàn)[7]采用同時(shí)打開(kāi)和關(guān)閉一個(gè)回路中一對(duì)開(kāi)關(guān)的方法。文獻(xiàn)[8]利用網(wǎng)絡(luò)的回路關(guān)聯(lián)矩陣動(dòng)態(tài)切割及合并回路,以保證配電網(wǎng)輻射狀的拓?fù)浣Y(jié)構(gòu)。文獻(xiàn)[9]提出了配電網(wǎng)滿足輻射狀拓?fù)浼s束的充分必要條件。文獻(xiàn)[10]提出了一種基于供電路徑的配電網(wǎng)拓?fù)涿枋龇椒?該方法的優(yōu)勢(shì)在于可用線性的數(shù)學(xué)公式清晰地描述配電網(wǎng)的輻射狀拓?fù)浣Y(jié)構(gòu)。文獻(xiàn)[10-11]將供電路徑應(yīng)用在配電網(wǎng)重構(gòu)問(wèn)題中;采用基于供電路徑的配電網(wǎng)拓?fù)涿枋?可將重構(gòu)問(wèn)題用混合整數(shù)確定性優(yōu)化方法求解[12-13];文獻(xiàn)[14]提出了一種基于路徑描述的饋線N-1可裝容量的計(jì)算方法,將配電網(wǎng)的供電路徑應(yīng)用在N-1安全校驗(yàn)分析中,說(shuō)明了供電路徑在配電網(wǎng)分析中的有效性。對(duì)于規(guī)模較大的配電網(wǎng),供電路徑數(shù)量很多,有必要采用高效的路徑搜索算法。文獻(xiàn)[10]提出的配電網(wǎng)路徑搜索方法基于廣度優(yōu)先遍歷,需將搜索得到的支路先存儲(chǔ)在樹(shù)結(jié)構(gòu)中以保存路徑信息,再對(duì)樹(shù)進(jìn)行遍歷,將路徑存于鏈表中,搜索過(guò)程占用的空間較大,并且沒(méi)有考慮網(wǎng)絡(luò)中存在多個(gè)變電站的情況。文獻(xiàn)[15]提出一種基于頂點(diǎn)分裂的路徑搜索方法,需頻繁改變網(wǎng)絡(luò)圖的結(jié)構(gòu),且針對(duì)圖中不同的一對(duì)頂點(diǎn),頂點(diǎn)分裂的結(jié)果也不同,效率較低。文獻(xiàn)[16-17]提出的搜索方法不能得到網(wǎng)絡(luò)中所有的供電路徑。配電網(wǎng)往往結(jié)構(gòu)復(fù)雜,如果直接在CIM中獲取供電路徑,涉及的路徑數(shù)量龐大,降低了后續(xù)分析的效率,因此需要對(duì)配電網(wǎng)進(jìn)行適當(dāng)?shù)暮?jiǎn)化處理[18-19]。文獻(xiàn)[18]提出的配電網(wǎng)簡(jiǎn)化模型難以與CIM建立直接聯(lián)系。文獻(xiàn)[19]涉及的化簡(jiǎn)方法僅將區(qū)域網(wǎng)絡(luò)邊界的多端口元件化簡(jiǎn)為二端口元件。

針對(duì)上述問(wèn)題,本文提出一種基于CIM的配電網(wǎng)網(wǎng)絡(luò)模型簡(jiǎn)化方法,以及在該簡(jiǎn)化網(wǎng)絡(luò)上的一種基于深度優(yōu)先遍歷的配電網(wǎng)路徑搜索算法。該網(wǎng)絡(luò)模型簡(jiǎn)化方法可為后續(xù)的路徑搜索等分析提供計(jì)算性能保證。同時(shí),本文提出的基于深度優(yōu)先遍歷的配電網(wǎng)路徑搜索算法,可搜索得到配電網(wǎng)中所有供電路徑,并可通過(guò)分類得到三類不同的路徑集合。該網(wǎng)絡(luò)簡(jiǎn)化和路徑搜索算法能夠應(yīng)用于配電網(wǎng)N-1分析、配電網(wǎng)重構(gòu)問(wèn)題及其他基于供電路徑的配電網(wǎng)分析中。

1 配電網(wǎng)網(wǎng)絡(luò)簡(jiǎn)化

1.1 基于CIM的配電網(wǎng)網(wǎng)絡(luò)模型

采用CIM建模技術(shù)中的節(jié)點(diǎn)—開(kāi)關(guān)模型[20-21]對(duì)配電網(wǎng)建模,得到配電網(wǎng)的原始模型。該模型描述了網(wǎng)絡(luò)中不同導(dǎo)電設(shè)備(conducting equipment)之間的連接關(guān)系,其中連接節(jié)點(diǎn)(connectivity node)、端子(terminal)和導(dǎo)電設(shè)備之間的關(guān)系如圖1所示。

圖1 連接節(jié)點(diǎn)、端子和導(dǎo)電設(shè)備之間的關(guān)系Fig.1 Relationship between connectivity node, terminal and conducting equipment

為在模型簡(jiǎn)化過(guò)程中利用圖論算法,將配電網(wǎng)網(wǎng)絡(luò)存儲(chǔ)在圖數(shù)據(jù)結(jié)構(gòu)中,過(guò)程如下。

1)將原始CIM中的連接節(jié)點(diǎn)存儲(chǔ)在圖的節(jié)點(diǎn)中。

2)將原始模型中包含2個(gè)端子的導(dǎo)電設(shè)備存儲(chǔ)在圖的邊中,邊的兩個(gè)頂點(diǎn)是根據(jù)2個(gè)端子分別找到的2個(gè)連接節(jié)點(diǎn)。

3)對(duì)配電網(wǎng)中的電力變壓器(power transformer),為其建立一個(gè)虛擬連接節(jié)點(diǎn);再對(duì)變壓器的各繞組,根據(jù)端子找到另一個(gè)連接節(jié)點(diǎn),將各繞組存儲(chǔ)在圖的邊中。

4)對(duì)得到的圖進(jìn)行連通性分析,獲得連通子圖,在連通子圖中找出有源電氣島。

1.2 基于圖論算法的網(wǎng)絡(luò)簡(jiǎn)化方法

文獻(xiàn)[22]提出了一種基于CIM的配電網(wǎng)拓?fù)涫湛s方法,對(duì)關(guān)聯(lián)3個(gè)及以上端子數(shù)的連接節(jié)點(diǎn)進(jìn)行分支線收縮和負(fù)荷點(diǎn)歸并處理。為提高網(wǎng)絡(luò)簡(jiǎn)化效果,本文進(jìn)一步考慮配電網(wǎng)中開(kāi)關(guān)與交流線段等設(shè)備的簡(jiǎn)化。簡(jiǎn)化步驟如下。

步驟1:將原圖中的連接節(jié)點(diǎn)作為母線節(jié)點(diǎn)(topological node)的成員,再將圖中的節(jié)點(diǎn)改為對(duì)應(yīng)的母線節(jié)點(diǎn),邊中的頂點(diǎn)信息也進(jìn)行相應(yīng)替換,得到初始簡(jiǎn)化圖。

步驟2:合并交流線段(AC line segment)兩端的節(jié)點(diǎn)。首先,找到交流線段的2個(gè)頂點(diǎn)v1和v2。對(duì)其中一個(gè)頂點(diǎn)如v2,找出除該交流線段外的與其相連的所有邊。對(duì)其中每一條邊,將這條邊上的設(shè)備加到v1與該邊的非v2頂點(diǎn)之間的邊上,并刪除這條邊。若v1與該邊的非v2頂點(diǎn)之間原來(lái)不存在邊,則需新建一條邊。最后,將頂點(diǎn)v2包含的連接節(jié)點(diǎn)加入頂點(diǎn)v1中,并刪除節(jié)點(diǎn)v2和該交流線段。

步驟3:在圖中找出所有含有開(kāi)關(guān)的邊,分別進(jìn)行如下處理。首先從圖中刪去這條邊,獲得連通子圖,如果網(wǎng)絡(luò)沒(méi)有分裂,則該開(kāi)關(guān)的狀態(tài)對(duì)配電網(wǎng)的運(yùn)行有影響,重新將這條邊加入圖中。如果網(wǎng)絡(luò)分裂成2個(gè),則要對(duì)下面兩種情況進(jìn)行處理:①一是無(wú)源的且包含負(fù)荷的子網(wǎng),說(shuō)明刪去的邊對(duì)應(yīng)的開(kāi)關(guān)狀態(tài)必然為閉合,則將該邊兩端的節(jié)點(diǎn)合并,合并的方法與步驟2中相同;②二是無(wú)源的不包含負(fù)荷的子網(wǎng),說(shuō)明該子網(wǎng)對(duì)配電網(wǎng)的運(yùn)行無(wú)影響,則從圖中刪除該子網(wǎng)。若不出現(xiàn)上述兩種情況,則重新將刪去的邊加入圖中。

步驟4:刪除只與兩條邊連接的聯(lián)絡(luò)節(jié)點(diǎn)。將與聯(lián)絡(luò)節(jié)點(diǎn)相連的兩條邊合并為一條,并將該節(jié)點(diǎn)刪除。

圖2以某配電網(wǎng)網(wǎng)絡(luò)為例表述網(wǎng)絡(luò)簡(jiǎn)化的過(guò)程。經(jīng)步驟3簡(jiǎn)化后的網(wǎng)絡(luò)如圖2(c)所示,圖中已無(wú)聯(lián)絡(luò)節(jié)點(diǎn),則圖2(c)即為所得的簡(jiǎn)化配電網(wǎng)網(wǎng)絡(luò)。

圖2 配電網(wǎng)網(wǎng)絡(luò)簡(jiǎn)化示例Fig.2 Illustration of distribution network simplification

圖2(c)中S1和S2為電源節(jié)點(diǎn),L1,L2,L3為負(fù)荷節(jié)點(diǎn)。其中L1,L2,L3分別對(duì)應(yīng)原網(wǎng)絡(luò)中的負(fù)荷Load1和Load2,Load3和Load4,Load5和Load6。簡(jiǎn)化后網(wǎng)絡(luò)圖的邊上均有開(kāi)關(guān)設(shè)備。該簡(jiǎn)化可提高路徑搜索、配電網(wǎng)重構(gòu)和供電能力分析等的效率。

2 基于深度優(yōu)先遍歷的配電網(wǎng)路徑搜索算法

在經(jīng)過(guò)簡(jiǎn)化的配電網(wǎng)網(wǎng)絡(luò)圖中搜索供電路徑。目前的配電網(wǎng)路徑搜索算法仍基于圖論算法[23],文獻(xiàn)[24]采用深度優(yōu)先和廣度優(yōu)先兩種方法尋找故障恢復(fù)路徑,文獻(xiàn)[25]采用深度優(yōu)先方法搜索負(fù)荷轉(zhuǎn)移路徑。這些方法無(wú)法搜索得到圖中所有的供電路徑,不能滿足描述配電網(wǎng)拓?fù)涞男枰?。在此基礎(chǔ)上,本文提出一種基于深度優(yōu)先的配電網(wǎng)路徑搜索算法,對(duì)深度優(yōu)先遍歷的規(guī)則進(jìn)行一定調(diào)整,以得到所有的供電路徑。同時(shí)通過(guò)分類得到3類供電路徑:按電源分類的路徑;按路徑終點(diǎn)負(fù)荷分類的路徑;按路徑中經(jīng)過(guò)支路分類的路徑,以便于配電網(wǎng)拓?fù)涞拿枋觥?/p>

2.1 搜索按電源分類的所有供電路徑算法

(1)

為得到按電源分類的所有供電路徑,需要對(duì)每一個(gè)電源節(jié)點(diǎn)分別搜索出以該電源為起點(diǎn)的所有路徑。與深度優(yōu)先遍歷類似,搜索從一個(gè)電源出發(fā)的所有路徑也是一個(gè)遞歸的過(guò)程。為了在搜索到某個(gè)節(jié)點(diǎn)時(shí),能夠向前推出該節(jié)點(diǎn)到電源節(jié)點(diǎn)的供電路徑信息,本文采用一個(gè)堆棧結(jié)構(gòu)來(lái)實(shí)現(xiàn)遞歸。將搜索得到的路徑集合存入數(shù)組R中。

棧中存儲(chǔ)的元素是圖中的節(jié)點(diǎn)?；谏疃葍?yōu)先的思路,每次成功訪問(wèn)一個(gè)節(jié)點(diǎn)后,需要令該節(jié)點(diǎn)入棧,再對(duì)新棧頂元素T的鄰接點(diǎn)進(jìn)行搜索。若T的所有鄰接點(diǎn)都不滿足被訪問(wèn)的條件,則T出棧。將棧中保存的節(jié)點(diǎn)依次相連,就能得到從棧底節(jié)點(diǎn),即電源節(jié)點(diǎn)到棧頂節(jié)點(diǎn)之間的一條路徑。再將棧頂節(jié)點(diǎn)與新搜索到的節(jié)點(diǎn)相連,得到一條新的路徑r。新搜索到的節(jié)點(diǎn)需要滿足下列3個(gè)條件才能入棧:①該節(jié)點(diǎn)不存在于棧中;②當(dāng)前生成的該節(jié)點(diǎn)的供電路徑r與已經(jīng)搜索得到的路徑都不同;③該節(jié)點(diǎn)不是電源節(jié)點(diǎn)。

若新搜索到的節(jié)點(diǎn)不滿足上述任意一個(gè)條件,則繼續(xù)對(duì)T的下一個(gè)鄰接點(diǎn)進(jìn)行搜索,否則節(jié)點(diǎn)入棧,同時(shí)增加一條新的路徑記錄r。若在搜索T的鄰接點(diǎn)過(guò)程中沒(méi)有新節(jié)點(diǎn)入棧,則T出棧,據(jù)此設(shè)置一個(gè)標(biāo)記變量f記錄T是否需要出棧。

所述算法的流程如圖3所示。

圖3 搜索按電源分類的所有路徑的算法流程Fig.3 Flow chart of algorithm for searching all paths sorted by power sources

2.2 搜索按電源分類的路徑算法復(fù)雜度分析

設(shè)網(wǎng)絡(luò)圖中電源節(jié)點(diǎn)數(shù)為n,負(fù)荷節(jié)點(diǎn)數(shù)為m。因配電網(wǎng)中一般電源數(shù)較少,n可表示為O(1)[26]。由于配電網(wǎng)通常為弱環(huán)網(wǎng),一個(gè)負(fù)荷節(jié)點(diǎn)的供電路徑數(shù)的數(shù)量級(jí)為常數(shù)級(jí),因此配電網(wǎng)中總供電路徑數(shù)可表示為O(m)。

堆棧中存放一個(gè)電源節(jié)點(diǎn)和多個(gè)負(fù)荷節(jié)點(diǎn),其大小不超過(guò)m+1。路徑在最長(zhǎng)的情況下包括了所有的負(fù)荷節(jié)點(diǎn),平均長(zhǎng)度可表示為O(m)。由此,數(shù)組R的大小可表示為O(m2),這也是該算法所用存儲(chǔ)空間的主要部分,即算法的空間復(fù)雜度。

進(jìn)棧操作次數(shù)的量級(jí)與路徑數(shù)量相同,為O(m)。每得到一條新的路徑,均需要與已獲得的路徑相比較。因路徑比較需對(duì)其包含元素分別依次比較,則比較次數(shù)的量級(jí)為O(m2),故該算法的時(shí)間復(fù)雜度為O(m3)。

2.3 按終點(diǎn)負(fù)荷節(jié)點(diǎn)分類和按經(jīng)過(guò)支路分類的路徑

本節(jié)所述的兩類路徑均可通過(guò)搜索2.1節(jié)的路徑得到。搜索以某個(gè)負(fù)荷為終點(diǎn)的所有路徑,過(guò)程如下:遍歷按電源分類的所有路徑,對(duì)每一條路徑,判斷其終點(diǎn)處的節(jié)點(diǎn)是否為指定的負(fù)荷節(jié)點(diǎn),若是,則記錄該路徑。進(jìn)而,對(duì)圖中的每一個(gè)負(fù)荷節(jié)點(diǎn),進(jìn)行上述搜索,可得到按路徑終點(diǎn)負(fù)荷分類的所有路徑。

(2)

(3)

搜索經(jīng)過(guò)某一條支路的所有路徑,過(guò)程如下:遍歷從電源出發(fā)的所有路徑,對(duì)每一條路徑中所包含的支路進(jìn)行搜索,若含有指定支路,則記錄該路徑。進(jìn)而,對(duì)圖中的每一條支路進(jìn)行相應(yīng)搜索,可得到按路徑中經(jīng)過(guò)支路分類的所有路徑。

(4)

按電源分類和按終點(diǎn)負(fù)荷分類的路徑,二者所包含的路徑數(shù)量均等于配電網(wǎng)中所有的供電路徑數(shù)。

3 供電路徑在配電網(wǎng)拓?fù)涿枋鲋械膽?yīng)用

3.1 配電網(wǎng)輻射狀結(jié)構(gòu)的描述

配電網(wǎng)輻射狀結(jié)構(gòu)可以用該網(wǎng)絡(luò)中所有負(fù)荷節(jié)點(diǎn)供電路徑狀態(tài)的集合加以描述。文獻(xiàn)[10]證明了若以下2個(gè)約束條件成立,則網(wǎng)絡(luò)為輻射狀。

1)對(duì)于任意一個(gè)負(fù)荷節(jié)點(diǎn)i,以該節(jié)點(diǎn)為終點(diǎn)的所有供電路徑中,有且僅有一條連通,即

(5)

(6)

約束條件1)中涉及路徑即為按終點(diǎn)負(fù)荷分類的路徑。

3.2 支路開(kāi)關(guān)狀態(tài)描述

3.3 電源和支路上負(fù)荷量的描述

(7)

(8)

上述供電路徑對(duì)配電網(wǎng)輻射狀約束等拓?fù)潢P(guān)系的描述,在配電網(wǎng)重構(gòu)和配電網(wǎng)供電能力分析等問(wèn)題中均會(huì)涉及,可以加以應(yīng)用。

4 算例分析

4.1 配電網(wǎng)網(wǎng)絡(luò)簡(jiǎn)化算例分析

附錄A圖A1給出了某省會(huì)城市的一個(gè)實(shí)際配電網(wǎng)網(wǎng)架圖,其中包含3個(gè)變電站,分別為S1,S2和S3。該模型的連接節(jié)點(diǎn)有668個(gè),導(dǎo)電設(shè)備有784個(gè)。采用1.1節(jié)所述方法,將該網(wǎng)架模型存儲(chǔ)在圖數(shù)據(jù)結(jié)構(gòu)中,得到1個(gè)有源電氣島,其中節(jié)點(diǎn)的數(shù)量為633,邊的數(shù)量為632。

根據(jù)1.2節(jié)的網(wǎng)絡(luò)簡(jiǎn)化方法對(duì)有源電氣島進(jìn)行簡(jiǎn)化處理,得到的配電網(wǎng)網(wǎng)絡(luò)圖如附錄A圖A2所示。對(duì)簡(jiǎn)化網(wǎng)絡(luò)中的節(jié)點(diǎn)重新編號(hào),S1,S2和S3對(duì)應(yīng)電源節(jié)點(diǎn),L1～L16對(duì)應(yīng)負(fù)荷節(jié)點(diǎn)。其中S1,S2和S3分別與附錄A圖A1中的變電站S1,S2和S3相對(duì)應(yīng)。

經(jīng)簡(jiǎn)化,網(wǎng)絡(luò)圖中有19個(gè)節(jié)點(diǎn)和18條邊。有源電氣島的節(jié)點(diǎn)和邊的數(shù)量分別減少為原來(lái)的3%和2.8%。若采用文獻(xiàn)[22]的拓?fù)涫湛s簡(jiǎn)化方法,所得簡(jiǎn)化圖中節(jié)點(diǎn)的數(shù)量為89,邊的數(shù)量為88,有源電氣島節(jié)點(diǎn)和邊的數(shù)量分別減少為原來(lái)的14.1%和13.9%。與文獻(xiàn)[22]相比,所提算法簡(jiǎn)化后的配電網(wǎng)網(wǎng)絡(luò)圖的節(jié)點(diǎn)數(shù)量及邊的數(shù)量明顯減少,簡(jiǎn)化效果更為顯著。

4.2 配電網(wǎng)路徑搜索算法算例分析

本文以IEEE 123節(jié)點(diǎn)系統(tǒng)為例,驗(yàn)證基于深度優(yōu)先的配電網(wǎng)路徑搜索算法。網(wǎng)絡(luò)接線圖如圖4所示,圖中包含2個(gè)電源、129條支路和127個(gè)負(fù)荷節(jié)點(diǎn),其中電源節(jié)點(diǎn)為點(diǎn)150和451。

圖4 算例網(wǎng)絡(luò)Fig.4 Example network

所提路徑搜索算法基于Java語(yǔ)言編程實(shí)現(xiàn),采用的計(jì)算機(jī)CPU型號(hào)為Intel Core i5-3337U、內(nèi)存為4 GB。經(jīng)路徑搜索,得到該算例中所有的供電路徑,總數(shù)為782條,其中以電源點(diǎn)150為起點(diǎn)的路徑有377條,以電源點(diǎn)451為起點(diǎn)的路徑有405條。搜索過(guò)程共耗時(shí)32 ms,說(shuō)明該算法的時(shí)間復(fù)雜度較優(yōu)越,可用于實(shí)際配電網(wǎng)的高效分析中。

從電源150和451出發(fā)的部分路徑搜索結(jié)果列于附錄B表B1中。

(9)

分類上述經(jīng)搜索得到的路徑,可得到按路徑終點(diǎn)負(fù)荷分類的路徑和按路徑經(jīng)過(guò)支路分類的路徑。以帶有開(kāi)關(guān)的支路300-350為例分析供電路徑的應(yīng)用,附錄B表B2展示了經(jīng)過(guò)支路300-350的所有路徑。設(shè)表B2中路徑1～6的狀態(tài)為W1～W6,節(jié)點(diǎn)350的負(fù)荷量為Q350,則通過(guò)支路300-350的功率如下:

S300-350=(W1+W2+W3+W4+W5+W6)Q350

(10)

同時(shí),附錄B表B2中列出的路徑也是經(jīng)過(guò)支路300-350,同時(shí)為負(fù)荷節(jié)點(diǎn)300和350供電的所有路徑,故支路300-350上的開(kāi)關(guān)狀態(tài)可表示為:W1+W2+W3+W4+W5+W6。

5 結(jié)語(yǔ)

本文提出的配電網(wǎng)模型簡(jiǎn)化方法可使網(wǎng)絡(luò)中的節(jié)點(diǎn)和支路數(shù)量顯著減少,從而避免在后續(xù)分析中計(jì)算量過(guò)大的問(wèn)題。對(duì)不同的配電網(wǎng)問(wèn)題,可適當(dāng)選取4個(gè)簡(jiǎn)化步驟中的一部分操作,并在簡(jiǎn)化過(guò)程中采用圖論算法改變網(wǎng)絡(luò)結(jié)構(gòu),使該方法具有較好的普適性。例如在供電能力分析中,可執(zhí)行所有步驟的簡(jiǎn)化;在需考慮電壓降落和網(wǎng)損的問(wèn)題中,不進(jìn)行步驟2(合并交流線段兩端節(jié)點(diǎn))的操作。

本文提出的基于深度優(yōu)先遍歷的配電網(wǎng)路徑搜索算法,能夠高效地搜索得到配電網(wǎng)中所有的供電路徑?；谠撍惴ǖ玫降穆窂侥軌蜻m應(yīng)配電網(wǎng)拓?fù)涞拿枋?可應(yīng)用于基于路徑描述的配電網(wǎng)N-1校驗(yàn)、N-1可裝容量分析、配電網(wǎng)重構(gòu)等問(wèn)題中?；诒疚暮臀墨I(xiàn)[14]成果的供電能力分析軟件已經(jīng)應(yīng)用于某實(shí)際配電網(wǎng),取得了較好的效果。

為保留快速查找的優(yōu)勢(shì),本文方法將供電路徑存儲(chǔ)在數(shù)組中,但由于搜索前路徑的數(shù)量未知,數(shù)組初始長(zhǎng)度不易確定,因此估算網(wǎng)絡(luò)中供電路徑的數(shù)量,提高算法效率,是進(jìn)一步的研究方向。

附錄見(jiàn)本刊網(wǎng)絡(luò)版(http://www.aeps-info.com/aeps/ch/index.aspx)。

[1] 肖峻,谷文卓,貢曉旭,等.基于饋線互聯(lián)關(guān)系的配電網(wǎng)最大供電能力模型[J].電力系統(tǒng)自動(dòng)化,2013,37(17):72-77.

XIAO Jun, GU Wenzhuo, GONG Xiaoxu, et al. A total supply capability model for power distribution network based on feeders interconnection[J]. Automation of Electric Power Systems, 2013, 37(17): 72-77.

[2] NEUMANN S. CIM extensions for electrical distribution[C]// Proceedings of 2001 IEEE Power Engineering Society Winter Meeting, January 28-February 1, 2001, Columbus, OH, USA: 904-907.

[3] WANG X F, SCHULZ N N, NEUMANN S. CIM extensions to electrical distribution and CIM XML for the IEEE radial test feeders[J]. IEEE Trans on Power Systems, 2003, 18(3): 1021-1028.

[4] 李荔芳,劉東,陳清鶴.公共信息模型在配電網(wǎng)建模工具中的應(yīng)用[J].電力系統(tǒng)自動(dòng)化,2005,29(24):55-59.

LI Lifang, LIU Dong, CHEN Qinghe. Application of CIM in distribution grid modeling tool[J]. Automation of Electric Power Systems, 2005, 29(24): 55-59.

[5] ENACHEANU B. Radial network reconfiguration using genetic algorithm based on the matroid theory[J]. IEEE Trans on Power Systems, 2008, 23(1): 186-195.

[6] LI J. Distribution system restoration with microgrids using spanning tree search[J]. IEEE Trans on Power Systems, 2014, 29(6): 3021-3029.

[7] SYAHPUTRA R, ROBANDI I, ASHARI M. Distribution network efficiency improvement based on fuzzy multiobjective method[J]. IPTEK Journal of Proceedings Series, 2014, 1(1): 224-229.

[8] 黃弦超,楊雨,范聞博.配電網(wǎng)多故障搶修與供電恢復(fù)聯(lián)合優(yōu)化模型[J].電力系統(tǒng)自動(dòng)化,2014,38(11):68-73.DOI:10.7500/AEPS20130506015.

HUANG Xianchao, YANG Yu, FAN Wenbo. Combined optimization model for maintenance scheduling and service restoration of distribution system[J]. Automation of Electric Power Systems, 2014, 38(11): 68-73. DOI: 10.7500/AEPS20130506015.

[9] LAVORATO M, FRANCO J F, RIDER M J, et al. Imposing radiality constraints in distribution system optimization problems[J]. IEEE Trans on Power Systems, 2012, 27(1): 172-180.

[10] ROMERO R E, EXPSITO A G, SANTOS J R, et al. Path-based distribution network modeling: application to reconfiguration for loss reduction[J]. IEEE Trans on Power Systems, 2005, 20(2): 556-564.

[11] DUAN Dongli, LING Xiaodong, WU X Y, et al. Reconfiguration of distribution network for loss reduction and reliability improvement based on an enhanced genetic algorithm[J]. International Journal of Electrical Power & Energy Systems, 2015, 64(64): 88-95.

[12] JABR R A, SINGH R, PAL B C. Minimum loss network reconfiguration using mixed-integer convex programming[J]. IEEE Trans on Power Systems, 2012, 27(2): 1106-1115.

[13] BORGHETTI A. A mixed-integer liner programming approach for the computation of the minimum-losses radial configuration of electrical distribution networks[J]. IEEE Trans on Power Systems, 2012, 27(3): 1264-1273.

[14] 孫明,董樹(shù)鋒,夏圣峰,等.基于路徑描述的饋線分區(qū)N-1可裝容量計(jì)算方法[J].電力系統(tǒng)自動(dòng)化,2017,41(16):123-129.DOI:10.7500/AEPS20161101003.

SUN Ming, DONG Shufeng, XIA Shengfeng, et al. Path-based calculation method for feeder partition available capability satisfied withN-1 security criterion[J]. Automation of Electric Power Systems, 2017, 41(16): 123-129. DOI: 10.7500/AEPS20161101003.

[15] 張旭,程雪婷,趙冬梅,等.一種基于頂點(diǎn)分裂的電網(wǎng)在線故障恢復(fù)路徑搜索方法[J].電力系統(tǒng)自動(dòng)化,2014,38(10):71-77.DOI:10.7500/AEPS20131104018.

ZHANG Xu, CHENG Xueting, ZHAO Dongmei, et al. A path searching method based on vertex splitting for online power grid fault restoration[J]. Automation of Electric Power Systems, 2014, 38(10): 71-77. DOI: 10.7500/AEPS20131104018.

[16] 張海波,張曉云,陶文偉.基于廣度優(yōu)先搜索的配電網(wǎng)故障恢復(fù)算法[J].電網(wǎng)技術(shù),2010,34(7):103-108.

ZHANG Haibo, ZHANG Xiaoyun, TAO Wenwei. A breadth-first search based service restoration algorithm for distribution network[J]. Power System Technology, 2010, 34(7): 103-108.

[17] 王超杰,任建文,徐偉男,等.基于距離向量的失電孤島供電路徑搜索方法[J].電力系統(tǒng)自動(dòng)化,2016,40(6):65-70.DOI:10.7500/AEPS20150720003.

WANG Chaojie, REN Jianwen, XU Weinan, et al. Power supply path searching algorithm for an electricity losing island based on distance vector[J]. Automation of Electric Power Systems, 2016, 40(6): 65-70. DOI: 10.7500/AEPS20150720003.

[18] 劉健,程紅麗,畢鵬翔.配電網(wǎng)的簡(jiǎn)化模型[J].中國(guó)電機(jī)工程學(xué)報(bào),2001,21(12):77-82.

LIU Jian, CHENG Hongli, BI Pengxiang. A simplified model for distribution system[J]. Proceedings of the CSEE, 2001, 21(12): 77-82.

[19] 王旭東,林濟(jì)鏗.基于網(wǎng)絡(luò)化簡(jiǎn)的含分布式電源的配電網(wǎng)可靠性分析[J].電力系統(tǒng)自動(dòng)化,2010,34(4):38-43.

WANG Xudong, LIN Jikeng. Reliability evaluation based on network simplification for the distribution system with distributed generation[J]. Automation of Electric Power Systems, 2010, 34(4): 38-43.

[20] 郭創(chuàng)新,董樹(shù)鋒,張金江.電力信息技術(shù)[M].北京:科學(xué)出版社,2015.

[21] 汪華.基于公共信息模型的電網(wǎng)建模[J].電網(wǎng)技術(shù),2008,32(增刊2):186-188.

WANG Hua. Power network model based on CIM[J]. Power System Technology, 2008, 32(Supplement 2): 186-188.

[22] 廖懷慶,劉東,黃玉輝,等.基于公共信息模型拓?fù)涫湛s的配電網(wǎng)轉(zhuǎn)供能力分析[J].電網(wǎng)技術(shù),2012,51(6):51-55.

LIAO Huaiqing, LIU Dong, HUANG Yuhui, et al. Analysis on transfer capability of distribution network based on CIM topological contraction[J]. Power System Technology, 2012, 51(6): 51-55.

[23] 周云,嚴(yán)正,李乃湖,等.系統(tǒng)恢復(fù)路徑搜索新算法及其適用性研究[J].中國(guó)電機(jī)工程學(xué)報(bào),2016,36(15):4152-4161.

ZHOU Yun, YAN Zheng, LI Naihu, et al. A new system restoration path search algorithm and its applicability research[J]. Proceedings of the CSEE, 2016, 36(15): 4152-4161.

[24] BABU P R, KRISHNA K V, SHIRISHA W, et al. Heuristic search strategy for service restoration using DFS and BFS techniques[C]// India International Conference on Power Electronics, January 28-30, 2011, New Delhi, India: 8p.

[25] 姜惠蘭,史建昇,曾凱,等.基于風(fēng)險(xiǎn)的電網(wǎng)調(diào)度操作最佳供電路徑生成策略[J].電力系統(tǒng)自動(dòng)化,2015,39(10):157-162.DOI:10.7500/AEPS20140708010.

JIANG Huilan, SHI Jiansheng, ZENG Kai, et al. Optimal power supply path in dispatching operation based on risk[J]. Automation of Electric Power Systems, 2015, 39(10): 157-162. DOI: 10.7500/AEPS20140708010.

[26] WEISS M A. Data structures and algorithm analysis in C[M].2版.北京:機(jī)械工業(yè)出版社,2010.

APathSearchingAlgorithmforDistributionNetworkBasedonNetworkSimplificationandDepthFirstTraversal

XUChengsi1,DONGShufeng1,SUNZhou2,LIChunxiao2,SUNMing1

(1. College of Electrical Engineering, Zhejiang University, Hangzhou310027, China;2. State Grid Shaoxing Electric Power Company, Shaoxing312000, China)

The power supply paths play an important role in the distribution network analysis. However, the distribution network is often complex in practice and it is necessary to simplify the distribution network model before searching the power supply paths. A simplified method of distribution network model based on common information model (CIM) and a path searching algorithm for distribution network based on the depth first traversal in the network simplification results are proposed. Firstly, the distribution network model is stored in a graph data structure and the network is simplified by using the graph theory algorithms. Subsequently, all the power supply paths of load nodes are searched in the distribution network by the path searching algorithm and classified into three categories of path sets respectively in terms of electric source, the load at the end of paths and the branch which the paths pass through. The path searching algorithm can be applied to the distribution network analysis such as describing the topological structure of the distribution network and the state of the branch switches. Finally, a typical distribution network framework in a provincial capital and IEEE network with123nodes are taken as examples to validate the effectiveness and practicability of the proposed network simplification method and path searching algorithm.

common information model (CIM); network simplification; depth first traversal; distribution network topology; path searching

2017-06-05;

2017-09-16。

上網(wǎng)日期: 2017-11-13。

徐成司(1995—),男,主要研究方向:電氣與自動(dòng)化。E-mail： 3140103128@zju.edu.cn

董樹(shù)鋒(1982—),男,通信作者,博士,副教授,主要研究方向:智能電網(wǎng)優(yōu)化與控制技術(shù)。E-mail: dongshufeng@zju.edu.cn

孫 洲(1987—),男,工程師,主要研究方向:電網(wǎng)規(guī)劃。E-mail: 419535239@qq.com

(編輯章黎)