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

徐成司, 董樹鋒, 孫 洲, 李春筱, 孫 明

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

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

徐成司1, 董樹鋒1, 孫 洲2, 李春筱2, 孫 明1

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

在經(jīng)過簡化的配電網(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ǎng)拓?fù)涞男枰?。在此基礎(chǔ)上,本文提出一種基于深度優(yōu)先的配電網(wǎng)路徑搜索算法,對深度優(yōu)先遍歷的規(guī)則進(jìn)行一定調(diào)整,以得到所有的供電路徑。同時通過分類得到3類供電路徑:按電源分類的路徑;按路徑終點負(fù)荷分類的路徑;按路徑中經(jīng)過支路分類的路徑,以便于配電網(wǎng)拓?fù)涞拿枋觥?/p>

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

(1)

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

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

若新搜索到的節(jié)點不滿足上述任意一個條件,則繼續(xù)對T的下一個鄰接點進(jìn)行搜索,否則節(jié)點入棧,同時增加一條新的路徑記錄r。若在搜索T的鄰接點過程中沒有新節(jié)點入棧,則T出棧,據(jù)此設(shè)置一個標(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é)點數(shù)為n,負(fù)荷節(jié)點數(shù)為m。因配電網(wǎng)中一般電源數(shù)較少,n可表示為O(1)[26]。由于配電網(wǎng)通常為弱環(huán)網(wǎng),一個負(fù)荷節(jié)點的供電路徑數(shù)的數(shù)量級為常數(shù)級,因此配電網(wǎng)中總供電路徑數(shù)可表示為O(m)。

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

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

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

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

(2)

(3)

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

(4)

按電源分類和按終點負(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é)點供電路徑狀態(tài)的集合加以描述。文獻(xiàn)[10]證明了若以下2個約束條件成立,則網(wǎng)絡(luò)為輻射狀。

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

(5)

(6)

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

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

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

(7)

(8)

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

4 算例分析

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

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

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

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

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

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

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

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

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

(9)

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

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

(10)

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

5 結(jié)語

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

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

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

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

[1] 肖峻,谷文卓,貢曉旭,等.基于饋線互聯(lián)關(guān)系的配電網(wǎng)最大供電能力模型[J].電力系統(tǒ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)自動化,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)自動化,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] 孫明,董樹鋒,夏圣峰,等.基于路徑描述的饋線分區(qū)N-1可裝容量計算方法[J].電力系統(tǒ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] 張旭,程雪婷,趙冬梅,等.一種基于頂點分裂的電網(wǎng)在線故障恢復(fù)路徑搜索方法[J].電力系統(tǒ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)自動化,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)的簡化模型[J].中國電機(jī)工程學(xué)報,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ò)化簡的含分布式電源的配電網(wǎng)可靠性分析[J].電力系統(tǒ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ù)[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].中國電機(jī)工程學(xué)報,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)險的電網(wǎng)調(diào)度操作最佳供電路徑生成策略[J].電力系統(tǒ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—),男,主要研究方向:電氣與自動化。E-mail： 3140103128@zju.edu.cn

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

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

(編輯章黎)