斯坦納樹模型在含DG配電網規劃中的應用

韓翔宇，劉滌塵，廖清芬，賈　駿，朱　正，胡靜竹

（武漢大學電氣工程學院，武漢 430072）

?

斯坦納樹模型在含DG配電網規劃中的應用

韓翔宇，劉滌塵，廖清芬，賈駿，朱正，胡靜竹

（武漢大學電氣工程學院，武漢 430072）

摘要：不確定性分布式電源的接入，給配電網規劃帶來新的挑戰。首先將含分布式電源的配電網規劃歸納為求解斯坦納樹問題，提出了一種新的配電網規劃建模方法。其次通過DG供電分區的劃定，將分區內的負荷節點處理為一個不接DG的負荷節點，消除DG對配電網規劃的影響。針對斯坦納樹問題傳統解法求解時間會隨著斯坦納點的規模成倍增加的缺陷，采用一種改進的粒子群優化（PSO）算法解決斯坦納樹N-P完全問題。結合54節點算例并與傳統方法計算結果比較，驗證了該方法的有效性。

關鍵詞：分布式電源；配電網規劃；斯坦納樹；供電分區；改進粒子群優化算法

分布式電源DG（distributed generation）是直接接在用戶附近或配網中的小型發電設備，它能使清潔能源和分散能源得到充分利用，緩解能源危機。配電網規劃是帶有約束條件的非線性混合整數優化問題，DG的加入使規劃難度增加。所以含DG的配電網規劃也就成為配電網規劃中的一個難點。

含DG的配電網規劃可劃分為兩部分：DG對配電網及規劃的影響研究［1］和計及DG的配電網協調規劃研究。目前協調規劃的主流求解算法有啟發式算法［2］、數學規劃算法［3］、隨機優化算法［4］等。啟發式算法計算無法保證結果的最優性，數學規劃算法無法逃避隨著求解規模的增大算法難收斂的問題，以遺傳算法［5-6］、蟻群算法與禁忌搜索［7］、粒子群算法［8］等或相應的改進算法為代表的隨機優化算法是目前的研究熱點。文獻［9］采用矩陣全新編碼模式的改進遺傳算法對含有分布式電源的配電網進行規劃，但該算法容易陷入局部最優。

最小斯坦納樹ST（Steiner tree）［10］問題是通過一系列斯坦納點找到一棵連接所有需求節點成本最小的樹。傳統的ST求解方法是基于枚舉實現的，枚舉所有可能的斯坦納點的組合方式，并與非斯坦納點一起構成最小生成樹，可以將其規劃成01背包問題［11］和最小生成樹問題的組合。其算法復雜度為O（2nVE），其中n為圖中斯坦納點的數量，V為圖中所有頂點的數量，E為圖中所有邊的數量。顯然，傳統解法是一個N-P完全問題。Beasley［12］、Ber?man［13］、Zelikovsky［14］等提出過許多斯坦納問題的精確或近似解法，雖然降低了求解復雜度，但斯坦納問題還是沒有被很好地解決。

本文首先對配電網節點進行分類，將配電網規劃問題轉化為求解ST問題，通過劃定供電分區，把其處理為一個負荷節點進行規劃，消除DG對斯坦納樹模型的影響，并采用改進PSO算法對ST配網規劃問題求解。在粒子群進化過程中，通過同時追蹤已找到的最優解、其他隨機粒子找到的同維度最優解以及整個粒子群的最優解進行速度更新，并對整體最優位置進行小擾動，增強了算法跳出局部最優的能力。和傳統算法相比，此算法不易陷入局部最優，能有效避免早熟收斂問題。

1　基于斯坦納樹的配電網節點分類

1.1斯坦納樹問題

最小斯坦納樹問題是一個經典的組合優化問題，在計算機網絡布局、電路設計、生物網絡分析等領域都有重要應用。斯坦納樹問題的傳統解法是一個N-P完全問題，求解時間會隨著斯坦納點的規模成倍增加。所以當斯坦納點規模達到一定數量時，傳統求解方法很難在多項式時間內得到解決。具體描述為給定一個加權圖G=（V，E）以及頂點子集RV，找出圖G中連接R中所有頂點的最小權值的一棵樹，即最小斯坦納樹。其中集合R中的頂點被稱作終端頂點，集合V/R中的頂點被稱作斯坦納頂點。根據加權對象不同，可分成邊加權斯坦納樹問題和點加權斯坦納樹問題。本文采用邊加權形式的斯坦納樹，如圖1所示。

圖1斯坦納樹Fig.1　Steiner tree

其中圖（b）中網絡邊值的權重如表1所示。

1.2含DG的配電網節點分類

含DG的配電網節點分類與傳統配電網節點分類有很強的相關性，主要異別在于DG所連節點如何分類問題。含DG配電網中的節點仍可分為3類［15］：供應節點、負荷節點和互聯節點。對DG所連節點分類問題處理如下：若DG接在負荷節點，則該節點仍歸類為負荷節點；若DG接在負荷點附近的互聯節點上，則視該節點功率為負值的負荷節點，把連接有DG的互聯節點歸類為負荷節點。

供應節點是配電網和輸電網的公共連接（PCC）點，是配電網的電源點。在配電網中供應點一般只有1個，是配電網分配電能的源點。

負荷節點是接有負荷的節點，它為負荷提供能量。實際配電網中，負荷客戶或者二級網絡的母線節點均歸類為負荷節點。對于基于斯坦納樹的配網規劃問題，負荷節點是必須連接的節點，是潮流的終點，也即為斯坦納問題中的目標點。

流入節點功率和流出節點功率相同的節點均為互聯節點。在待規劃的配網中，待建設的節點或規劃中可利用的非負荷節點均歸類為互聯節點。對于基于斯坦納樹的配網規劃問題，互聯節點即為斯坦納點，是可連可不連的待選點。

表1　網絡邊值權重Tab.1　Network boundary value

2　基于斯坦納樹的含DG配電網模型及分析

含DG的配電網規劃是在滿足可靠性的基礎上達到經濟性最優的目標，考慮的成本包括饋電線路的安裝、運行費用、網絡損耗和用戶停電損失費用。本文將其總和轉化為以年為單位的等值費用，并把該等年值費用作為斯坦納樹的權值進行規劃。

2.1目標函數

數學模型為式中：Z為總成本；Z1為線路建設費用和年運行費用；Z2為網損和用戶停電損失費用；Cr為分布式電源的減污費用；a0為投資的折現率；T為投資的回收年限；c1為單位長度線路造價和運行費用的總和；c2為電價；L為規劃線路的集合；Δpli,j為線路li,j的有功損耗；τmax為最大負荷利用小時數；J為節點的集合；ω1,ω2,ω3為權值；Clij為線路li,j故障用戶的停電費用。

相關成本函數計算公式如下。

（1）單位長度線路建設和運行費用［16］為

式中：c0為單位長度線路年建設費用；r為單位長度線路電阻；τ為年運行時間；i為線路中的電流。

（2）線路有功損耗為

式中：ρj,k為i、j節點線路的電導率；lj,k為i、j節點之間線路的長度；Pj,k為線路傳輸的有功功率；Sj,k為視在功率；Uj,k和δj,k分別為電壓和線路兩端相角差。

（3）停電損失費用為

式中：λ為配電線路單位長度故障率；c3,j為 j節點的停電損失費用。

（4）DG減污費用。

含有DG的配電網規劃，增加分布式電源的減污因子作為罰單元，體現分布式電源的環境效應和配電網對分布式電源的接納能力。

式中：α為減污系數，為生產單位電能傳統能源產生污染治理成本減去分布式電源產生污染治理成本的差值；PDG,q為第q個DG有功功率。

2.2約束條件

基于斯坦納樹的含DG配電網規劃主要考慮約束條件如下。

（1）節點電壓約束為

（2）線路熱約束為

（3）分布式電源有功出力約束為

（4）網絡潮流約束為

式中：PDG,j和QDG,j分別為節點 j處DG的有功功率和無功功率；PL,j和QL,j為節點 j處負荷的有功功率和無功功率；Gj,k和Bj,k為電導和電納。

（5）配網的連通性。

在求取斯坦納樹的過程中，連通性約束條件自動滿足。

（6）配網的輻射性。

n=m+1（10）

式中：n為配電網節點總數；m為原有支路和新建支路之和。

計算時，將由饋電線路的建設費用、運行費用、網絡損耗以及停電損失費用轉化成的等年值費用作為斯坦納樹的權值，以網絡總成本最小為目標搜索最小生成樹。搜索最小生成樹時考慮網絡的連通性和輻射性約束條件，最后計算網絡潮流，驗證節點電壓、線路電流和分布式電源容量約束條件。

2.3模型中DG的處理

為消除DG對斯坦納樹規劃模型的影響，需劃定DG的供電分區。依次搜索DG相臨近的負荷節點，直到臨近負荷節點的負荷總和與該發電機發電量相當，把這些負荷節點劃定為DG的供電分區并處理成一個不接分布式電源的負荷節點。供電分區內的線路不列入斯坦納樹的搜尋范圍，但其線路綜合成本需加到最優線路的總成本里。

3　基于改進粒子群算法的斯坦納樹配網求解

本文算法基于“搜索+調整”的思想，計算線路平均綜合成本，把該成本作為斯坦納樹的邊權值。再以電源點（DG和PCC點）、負荷點為起點和終點求解斯坦納樹，再驗算其潮流是否滿足，對于不滿足約束的線路進行修正，最終得到滿足約束條件的斯坦納樹。

在構造最小斯坦納過程中，傳統算法枚舉所有可能組合再通過最小生成樹算法求得最小權值網絡。但由于斯坦納樹是一個NP完全問題，此方法求解效率過低。

Kennedy和Eberhart［17］提出的基本粒子群迭代公式，即

式中：pbkid為粒子在飛行過程所經歷過的最好位置；gbkid為每一個粒子都能記住自己搜索到的最好解；i=1,2,…,N，N為粒子個數；d=1,2,…,D，D為目標搜索空間維度；e1和e2為加速因子；f1和f2為隨機數，介于［0，1］之間；vkid和xxid為第k次迭代中粒子i第d維的速度和位置。

為了克服粒子群易發散，早熟等缺點，本文采用多向學習自適應的粒子群算法CLSPSO（compre?hensive learning&self-adaptive particle swarm opti?mization）［18］，粒子的速度更新公式改進為

式中：ω為慣性權重；||fn1、||fn2、||fn3均為參數服從N（0,1）正態分布的絕對值，在傳統算法中，加速因子往往為定值，為使加速收斂且不陷入局部最優，本算法中e1、e2、e3采用自適應的方法，其自適應動態系數為

可以看出，加速因子會隨著搜索迭代數的增加而遞減。

具體實現流程如圖2所示。

圖2計算流程Fig.2　Flow chart of calculation

具體優化步驟如下。

（1）采集配電網地理信息，將節點進行分類并構建無向圖。

（2）劃定DG供電分區：從每一個分布電源為起點，通過狄克斯特拉（Dijkstra）算法依次搜索與它相臨近的點，直到臨近負荷節點的負荷總和與該發電機發電量相當，即劃分每個分布式電源的供電范圍，未劃分至分布式電源供電分區的負荷由電網供應節點供電。

（3）計算網絡權值，修正節點網絡，得到無向有權的鄰接矩陣。

（4）用弗洛伊德（Floyd）算法求出兩兩之間最短路徑，得到配網的強連通圖。

（5）改進的粒子群算法計算最小生成樹，并存儲最小值，當最小生成樹總權值小于存儲的最小值時，計算該生成樹的潮流，判斷電壓、電流、DG出力是否滿足約束，若均滿足，用此結果替換已有的最小值。若不滿足，進行粒子的更新。

4　實際含DG配電網規劃求解

用Matlab編程計算，采用修改的某地區54節點算例。該地區有97條可規劃線路，結構如圖3所示，線路參數見文獻［19］。

圖3中，黑色圓圈代表負荷點，白色圓圈代表斯坦納點，節點5、43、46接有DG，如圖中黑色實心三角所示，容量分別為160 kVA、200 kVA、100 kVA。其他參數：r0=0.08，c2=0.5元/（kW·h），λ=0.05，τmax=3 000 h，T=20。

圖3 可規劃線路Fig.3　Structure of planning lines

用多向學習自適應的粒子群算法、遺傳算法GA（genetic algorithm）、模擬退火算法SA（simulated annealing algorithm）、基本粒子群算法PSO對該算例進行優化，各進行20次計算，結果如圖4所示。最優線路總造價為580.806萬元。統計每種算法得到最優值的次數和方差，結果如表2所示。

從圖4和表2可以看出，4種算法20次優化結果呈現一定程度的波動性，CLSPSO優化算法標準差最小，說明波動性最小，穩定性較強。4種算法都能搜索到最優解，CLSPSO優化算法搜索到最優解次數遠高于另外3種算法，搜索效率較高，全局搜索能力較強。綜上信息，多向學習自適應的粒子群算法是一種較為理想的規劃算法。

圖4計算結果Fig.4　Calculation results

表2優化結果Tab.2　Optimization results

采用多向學習自適應的粒子群算法對斯坦納樹配網規劃模型進行求解，求得最優網絡如圖5所示。該模型對含有DG的配電網規劃人員具有一定的工程指導作用。

圖5最優網架Fig.5　Optimal network frame

優化前和優化后的網架在結構上的改變如表3所示。原始線路和增加的線路用（a，b）形式表示，其中a和b分別為支路的起始和終端節點編號。

最后考慮分布式電源的發電隨機性，分析未接入分布式電源與分布式電源全接入這兩種極端情況。未接入DG與接入DG后最優網架的節點電壓如圖6所示。定義節點電壓裕度指標KU為

表3線路結構Tab.3　Line structure

式中：Ulimit為節點電壓上限值，本文中取為1.05；U0為節點電壓當前值。根據式（15）計算各節點的電壓裕度，結果如圖7所示。

圖6　最優網架節點電壓Fig.6　Voltages of optimal network

圖7　節點電壓裕度Fig.7　Tolerances of bus voltage

從圖6和圖7可以看出，接入DG后，節點電壓有所上升，但都未達到上限值；節點電壓裕度有所下降，裕度值較大的節點下降幅度較大，這說明遠離電源的節點電壓上升幅度大，分布式電源的接入對末端負荷節點的電壓抬升效果更顯著。

僅從電壓約束考慮，系統還可進一步接納分布式電源，接納容量與電壓裕度的關系有待研究。電網調度人員可對節點的電壓裕度進行排序，劃定電壓裕度警戒線，對于裕度值處在警戒線以下的節點，需格外警惕，必要時需減少該些節點附近的DG出力，極端情況下需切除DG機組。

5　結論

（1）多向學習自適應的PSO算法很好地解決了斯坦納樹N-P完全問題，擴展了ST的使用范圍。

（2）模型中充分考慮了分布式電源的減污效應，并以減污因子作為對更為環保的分布式電源發電的激勵，節約了資源，促進可持續發展的實施。

（3）對于傳統粒子群算法易發散、早熟的問題，增加了整體最優位置擾動環節，提高算法全局搜索能力和搜索效率，通過54節點實際算例驗證了改進粒子群算法的有效性。

參考文獻：

［1］于建成，遲福建，徐科，等（Yu Jiancheng，Chi Fujian，Xu Ke，et al）.分布式電源接入對電網的影響分析（Analy?sis of the impact of distributed generation on power grid）［J］.電力系統及其自動化學報（Proceedings of the CSUEPSA），2012，24（1）：138-141.

［2］Tao Xiaohu，Haubrich H.A two-stage heuristic method for the planning of medium voltage distribution networks with large-scale distributed generation［C］//International Confer?ence on Probabilistic Methods Applied to Power Systems，Stockholm.Sweden，2006：793-798.

［3］ Partanen J.A modified dynamic programming algorithm for sizing，locating and timing of feeder reinforcements［J］. IEEE Trans on Power Delivery，1990，5（1）：277-283.

［4］孔濤，程浩忠，李鋼，等（Kong Tao，Cheng Haozhong，Li Gang，et al）.配電網規劃研究綜述（Review of power dis?tribution network planning）［J］.電網技術（Power System Technology），2009，33（19）：92-99.

［5］王雷，顧潔（Wang Lei，Gu Jie）.中壓配電網優化規劃的改進單親遺傳算法（Improved partheno-genetic algo?rithm for medium voltage distribution network optimal planning）［J］.電力系統及其自動化學報（Proceedings of the CSU-EPSA），2006，18（3）：72-76.

［6］李德泉，徐建政，羅永（Li Dequan，Xu Jianzheng，Luo Yong）.含分布式電源的配電網擴展規劃（Distribution network expansion planning including distributed genera?tion）［J］.電力系統及其自動化學報（Proceedings of the CSU-EPSA），2012，24（5）：88-92.

［7］陳根軍，唐國慶（Chen Genjun，Tang Guoqing）.基于禁忌搜索與蟻群最優結合算法的配電網規劃（Tabu searchant colony optimization hybrid algorithm based distribu?tion network planning）［J］.電網技術（Power System Tech?nology），2005，29（2）：23-27.

［8］李振坤，陳星鶯，余昆，等（Li Zhenkun，Chen Xingying，Yu Kun，et al）.配電網重構的混合粒子群算法（Hybrid particle swarm optimization for distribution network recon?figuration）［J］.中國電機工程學報（Proceedings of the CSEE），2008，28（31）：35-41.

［9］麻秀范，崔換君（Ma Xiufan，Cui Huanjun）.改進遺傳算法在含分布式電源的配電網規劃中的應用（An im?proved genetic algorithm for distribution network planning with distributed generation）［J］.電工技術學報（Transac?tions of China Electrotechnical Society），2011，26（3）：175-181.

［10］鄭瑩，王建新，陳建二（Zheng Ying，Wang Jianxin，Chen Jian′er）.Steiner Tree問題的研究進展（Survey of Steiner Tree problem）［J］.計算及科學（Computer Science），2011，38（10）：16-22.

［11］林濟鏗，王旭東，李勝文，等（Lin Jikeng，Wang Xudong，Li Shengwen，et al）.基于含連通圖約束的背包問題的圖分割方法（Graph partitioning method based on con?nected graph constrained knapsack problem）［J］.中國電機工程學報（Proceedings of the CSEE），2012，32（10）：134-141.

［12］Beasley J E.An SST-based algorithm for the Steiner prob?lem in graphs［J］.Networks，1989，19（1）：1-16.

［13］Kou L，Markowsky G，Berman L.A fast algorithm for Stein?er trees［J］.Acta Informatica，1981，15（2）：141-145.

［14］Zelikovsky A Z.An 11/6-approximation algorithm for the network Steiner problem［J］.Algorithmica，1993，9（5）：463-470.

［15］Avella P，Villacci D，Sforza A.A Steiner arborescence model for the feeder reconfiguration in electric distribu?tion networks［J］.European Journal of Operational Re?search，2005，164（2）：505-509.

［16］Duan Gang，Yu Yixin.Power distribution system optimiza?tion by an algorithm for capacitated Steiner tree problems with complex-flows and arbitrary cost functions［J］.Interna?tional Journal of Electrical Power&Energy Systems，2003，25（7）：515-523.

［17］Kennedy J，Eberhart R.Particle swarm optimization［C］// IEEE International Conference on Neural Networks.Perth，Australia，1995：1942-1948.

［18］闞超豪（Kan Chaohao）.多向學習自適應的粒子群算法（Particle swarm optimization with comprehensive learn?ing&self-adaptive）［J］.計算機工程與應用（Computer Engineering and Applications），2013，49（6）：23-28.

［19］Samui A，Singh S，Ghose T，et al.A direct approach to op?timal feeder routing for radial distribution system［J］.IEEE Trans on Power Delivery，2012，27（1）：253-260.

韓翔宇（1990—），男，碩士研究生，研究方向為配電網規劃和電力系統暫態過電壓。Email：zhuzhuaizhuren@163.com

劉滌塵（1953—），男，博士，教授，研究方向為電力系統運行與控制。Email：dcliu@whu.edu.cn

廖清芬（1975—），女，博士，副教授，研究方向為電力系統運行與控制。Email：qfliao@whu.edu.cn

中圖分類號：TM715

文獻標志碼：A

文章編號：1003-8930（2016）06-0062-06

DOI：10.3969/j.issn.1003-8930.2016.06.011

作者簡介：

收稿日期：2014-09-11；修回日期：2015-11-25

基金項目：國家電網公司科技項目（5211011400BT）。

Steiner Tree Model for Distribution Network Planning With DG

HAN Xiangyu，LIU Dichen，LIAO Qingfen，JIA Jun，ZHU Zheng，HU Jingzhu
（College of Electrical Engineering，Wuhan University，Wuhan 430072，China）

Abstract：The traditional distribution network planning methods are challenged by the access of the uncertain distribut?ed generation.Firstly，the distribution network planning with distributed generation is converted into solving the Steiner tree problem and a new distributed network planning model is proposed.Secondly，through the delineation of DG power supply region，the load buses in the region are processed into one load bus without DG，eliminating the effect of DG on the distribution network planning.In order to solve the problem that the computing time multiplied as the Steiner nodes increased，an improved particle swarm optimization（PSO）algorithm is proposed to solve the Steiner tree N-P complete problem.Typical results of the traditional algorithm and the proposed algorithm are further illustrated and compared through a real 54 nodes system to testify the effectiveness of the methods in this paper.

Key words：distributed generation；distribution network planning；Steiner tree（ST）；power supply region；improved particle swarm optimization（PSO）algorithm