基于故障概率的配電設備排查路徑規(guī)劃

馬天佚，朱建明，楊 霖，張 馳

(1.國網北京城區(qū)供電公司，北京 西城 100035 ；2.中國科學院大學工程科學學院，北京 石景山 100049)

配電系統(tǒng)結構復雜，設備分散，對停電發(fā)生時故障設備的準確定位造成了一定的困難，極大影響了應急搶修、應急電源接入等配電網應急管理手段與效率[1-2]。現(xiàn)階段配電自動化技術的應用尚未成熟，多數(shù)情況下僅能劃定故障設備所處區(qū)域，難以準確定位，仍需搶修人員對故障區(qū)域內的設備進行排查以確定故障點。因此，排查路徑的優(yōu)劣直接影響配電系統(tǒng)應急搶修工作效率。目前關于電力系統(tǒng)及相關領域應急路徑規(guī)劃的研究主要集中在目標位置明確時的最短路徑規(guī)上，國內外學者通過很多優(yōu)化模型和算法對此類問題進行了深入研究。但是，對于故障點不確定情況下的故障排查路徑規(guī)劃鮮有報道，而這是現(xiàn)階段配電系統(tǒng)乃至整個電力系統(tǒng)需要解決的主要問題之一。

本文針對停電事件發(fā)生時故障點僅被劃定在某一區(qū)域內的排查路徑規(guī)劃進行系統(tǒng)研究，同時考慮到配電設備故障概率的差異性，對基于設備故障概率的排查路徑進行深入探討，類比旅行商問題(TSP)建立排查路徑規(guī)劃模型并應用遺傳算法對其進行求解，確保在停電事件發(fā)生時，合理規(guī)劃排查路徑，及時定位故障設備，提高配電系統(tǒng)應急能力。

1 排查路徑規(guī)劃模型的建立

傳統(tǒng)的應急搶修路徑規(guī)劃研究主要致力于以“總時間最短”或“總路徑最短”為單一目標的路徑最短化問題。文獻[3]以停電用戶滿意度衡量的總時間最短為目標，考慮到路徑行駛時間的區(qū)間性，運用二分法構建應急電源路徑優(yōu)化模型；文獻[4-10]以“總路徑最短”為目標，分別依托迪杰斯特拉算法(Dijkstra)、小波變換法、弗洛伊德算法(Floyd)、粒子群算法、Critic、拉格朗日數(shù)乘法等不同形式的最短路徑算法，對應急搶修路徑進行規(guī)劃選擇。

然而，實際運行中，配電系統(tǒng)設備種類繁多，設備類型、運行年限、制造工藝、所處環(huán)境等因素各不相同，因此配電設備的故障概率存在較大差異[11-16]。僅以“總時間最短”或“總路徑最短”為目標無法將不同設備的故障概率差異納入總體規(guī)劃，以確保大故障概率設備的排查優(yōu)先性。當考慮設備故障概率的差異性時，故障點被劃定在限定區(qū)域內的排查路徑規(guī)劃問題可以看作一個多目標組合優(yōu)化問題，其規(guī)劃目標有兩個：一是排查工作的及時性，即搶修人員從接到故障信息，獲知故障限定區(qū)域開始， 以最快的速度找到限定區(qū)域內故障設備的準確位置。該目標可以轉化為搶修人員從初始位置開始，遍歷故障限定區(qū)域內的所有配電設備的所需時間的最小化，即傳統(tǒng)研究中以“總時間最短”或“總路徑最短”為目標的路徑規(guī)劃問題；二是排查工作的準確性，即搶修人員在考慮時間或路徑最短化的同時，以最大的概率優(yōu)先排查出限定區(qū)域內故障設備的準確位置。該目標可以轉化為搶修人員在保證時間最短化的同時，優(yōu)先對限定區(qū)域內故障概率較大的設備進行排查。

綜上所述，該問題可以描述為：在已知搶修人員初始位置、故障限定區(qū)域、限定區(qū)域內設備數(shù)量、各設備實際位置、故障概率以及通過各行駛路徑所需的時間的前提下，搶修人員從初始位置出發(fā)，逐一排查限定區(qū)域內的所有配電設備，如何規(guī)劃排查路徑，以兼顧路徑時間的最小化和大故障概率設備的優(yōu)先性。該路徑規(guī)劃模型的建立分兩步進行，第一步是在不考慮設備故障概率的情況下，以排查“總時間最短”為目標，規(guī)劃排查路徑；第二步是在此基礎上，綜合考慮設備故障概率，建立“總時間最短”和“大故障概率設備優(yōu)先級最高”為雙目標，優(yōu)化排查路徑規(guī)劃。

1.1 不考慮設備故障概率時的排查路徑

首先僅以排查工作的及時性作為目標，認為限定區(qū)域內配電設備的故障概率相同。此時的排查路徑規(guī)劃問題可以看作典型的旅行商問題(TSP)，可將故障限定區(qū)域抽象為無向賦權圖，搶修人員的初始位置和配電設備的位置即為圖的頂點，各頂點間的行駛時間即為圖的邊權，選擇一條從搶修人員初始位置開始遍歷限定范圍內所有配電設備的路徑，使得經過該路徑所需的時間最短。即針對限定區(qū)域內的配電設備集合J={1，2，…，j}，求解最佳排查路徑π(J)={V1，V2，…，Vj}，使得：

(1)

其中，Yj為目標函數(shù)；j為故障限定區(qū)域內配電設備數(shù)；S為搶修人員初始位置；t(S，V1)為搶修人員初始位置S到第一個排查的設備V1所需的時間；t(Vi，Vi+1)為搶修人員從第i個排查的設備Vi到第i+1個排查的設備Vi+1的所需的時間。

1.2 考慮設備故障概率時的排查路徑

在式(1)所建立的路徑規(guī)劃模型的基礎上，計入配電設備的故障概率，即針對限定區(qū)域內的配電設備集合N={1，2，…，n}，求解最佳排查路徑π(N)={V1，V2，…，Vn}，以兼顧排查時間的最小化以及大故障概率設備的優(yōu)先性，使得：

(2)

其中，Z為目標函數(shù)；n為故障限定區(qū)域內配電設備數(shù)；PVj為設備Vj的故障概率。該模型的目標時搶修人員從初始位置出發(fā)，遍歷限定區(qū)域內的所有設備，且到達某設備前所經歷的時間與該設備故障概率的乘積之和最小化。

2 模型求解

上節(jié)所建立的兩個排查路徑規(guī)劃模型均與旅行商問題問題(TSP)類似，是NP完全問題(NP-complete)，其可行解為無向賦權圖中所有頂點的全排列，復雜度隨著圖中頂點數(shù)目的增加呈指數(shù)倍增長。因此，當故障限定區(qū)域內設備數(shù)量較大時，無法使用精確算法進行求解其最優(yōu)解，只能采用近似算法求解求解較優(yōu)解。本文擬采用啟發(fā)式算法中的遺傳算法對該問題進行求解。

遺傳算法(genetic algorithm)是一種通過模擬生物進化過程和遺傳機理搜索近似最優(yōu)解的算法，可用于解決復雜的非線性優(yōu)化問題，常被用于規(guī)劃計算類研究[17-19]。遺傳算法首先隨機生成初始種群作為所求問題的初始解，并設定最大遺傳代數(shù)。種群由通過基因編碼的個體染色體組成。然后，根據(jù)所求問題的目標函數(shù)規(guī)定適應度函數(shù)，并通過選擇、交叉、變異、進化逆轉等操作，按照優(yōu)勝劣汰、適者生存的原理，逐代演化產生適應度更高的種群。當達到設定的最大遺傳代數(shù)后，選取其中適應度最大的個體染色體，并將其解碼，作為問題的最優(yōu)近似解。具體流程如圖1所示。

(1)問題參數(shù)：包括搶修人員初始位置、限定區(qū)域內設備數(shù)量、位置和故障概率、通過各行駛路徑所需的時間等實際參數(shù)以及初始種群中個體染色體數(shù)目m、選擇概率Ps、交叉概率Pc、變異概率Pm、最大遺傳代數(shù)maxgen等設定值；

(2)編碼：當限定區(qū)域內配電設備數(shù)量為n時，首先對設備分別編號，形成設備集N={1，2，…，n}，然后將遺傳算法中個體染色體分為n段基因，每一段基因即為一個設備編號，如個體染色體|1|2|…|i|…|n|就表示排查路徑順序為1→2→…→i→…→n；

(3)生成初始種群：根據(jù)第1步中設定的初始種群的個體染色體數(shù)目m以及限定區(qū)域內配電設備數(shù)量n，隨機生成一個大小為m×n的初始種群，作為該問題的初始解集；

(4)適應度函數(shù)：根據(jù)實際問題的目標函數(shù)建立適應度函數(shù)，對種群中的個體染色體計算適應度。由于遺傳算法默認為求取問題的最大值，而本文的排查路徑規(guī)劃問題需要求解目標函數(shù)的最小值，因此考慮將目標函數(shù)的倒數(shù)作為遺傳算法的適應度函數(shù)，即對于種群中的個體染色體|k1|k2|…|ki|…|kn|，根據(jù)是否考慮設備故障概率，分別建立如式(3)和式(4)的適應度函數(shù)：

不考慮設備故障概率時：

(3)

考慮設備故障概率時：

(4)

其中，t(S，k1)為搶修人員從初始位置S到第一個排查的設備k1所需的時間，t(ki，ki+1)為搶修人員從第i個排查的設備ki到第i+1個排查的設備ki+1所需的時間。

(5)選擇：根據(jù)設定的選擇概率Ps，從舊種群中選擇適應度函數(shù)較大的個體染色體進入新種群；

(6)交叉：在選擇操作后，對種群中的個體兩兩分組，根據(jù)設定的交叉概率Pc，隨機在每組兩個個體的染色體中分別選擇兩個相對應的位置，并將這兩個位置中間的基因進行互換(產生基因重復時需進行修正)；

(7)變異：在選擇、交叉操作后，根據(jù)設定的變異概率Pm，在種群的個體染色體上選擇兩個位置，將兩個位置的基因進行互換；

(8)進化逆轉：在選擇、交叉、變異操作后，任意在種群中個體染色體上選擇兩個位置，將兩個位置中間的基因逆向排列，然后對逆轉后個體的適應度函數(shù)進行計算，當逆轉后個體適應度函數(shù)增大時，以新個體取代舊個體，否則舍棄新個體保留舊個體。

(9)循環(huán)條件：判斷循環(huán)次數(shù)是否達到設定的最大遺傳代數(shù)maxgen，當達到時，循環(huán)結束，否則，繼續(xù)進行循環(huán)操作；

(10)解碼：針對遺傳算法最終得到的適應度最大的個體染色體，將其解碼為基因段，以得到實際問題的近似最優(yōu)解。

3 算例分析

以某配電系統(tǒng)為實例，驗證提出的排查路徑規(guī)劃模型和遺傳算法的可行性和有效性。該限定區(qū)域交通網絡圖如圖2所示。假定搶修人員的初始位置為S，限定區(qū)域內的配電設備共12臺，分別編號為{1，2，…，12}，則網絡圖中共13個頂點，頂點坐標和設備故障概率見表1。搶修人員從初始位置開始可以選擇多條路徑進行排查，根據(jù)實時路況信息可以得到所需的路徑時間，單位為min，標注在網絡圖中。

表1 限定區(qū)域內設備坐標及故障概率Tab.1 Coordinate positions and failure probability of the equipment in defined areas

在不考慮設備故障概率和考慮設備故障概率兩種情況下，分別根據(jù)式(3)和式(4)建立路徑規(guī)劃模型，并應用遺傳算法進行求解。

首先確定問題參數(shù)，故障區(qū)域已限定于圖2所示范圍內，其中搶修人員初始位置及12臺配電設備的位置坐標、故障概率以及搶修人員初始位置數(shù)據(jù)可由表1得出，通過各行駛路徑所需的時間已由圖2標注。經過筆者多次試驗分析及計算結果比對，在不影響計算精度及收斂速度的情況下，設定初始種群中個體染色體數(shù)目m為1 000，選擇概率Ps、交叉概率Pc均為0.9，變異概率Pm為0.05，最大遺傳代數(shù)maxgen為100。

其次對圖2限定區(qū)域內的配電設備進行編號，形成設備集N={1，2，…，12}，即每個個體染色體由12段基因組成，每一段基因表示的數(shù)字即為一個設備編號，編號次序即為設備排查順序。由此可形成一個含1000個個體染色體的初始種群。

然后，在不考慮設備故障概率和考慮設備故障概率時，分別根據(jù)式(3)和式(4)建立最優(yōu)路徑規(guī)劃的適應度函數(shù)。運用遺傳算法，依次通過選擇、交叉、變異、進化逆轉循環(huán)過程，選出適應度最高的個體染色體，即為最優(yōu)路徑規(guī)劃的近似解。

從初始種群出發(fā)，在選擇環(huán)節(jié)中，根據(jù)選擇概率0.9，從1 000個初始染色體中選擇900個適應度較大的個體染色體進入新種群；之后進入交叉環(huán)節(jié)，對選出的900個個體染色體兩兩分組形成450對染色體組，以0.9的交叉概率決定每對染色體組是否執(zhí)行交叉，如果執(zhí)行交叉，則在每對的兩個個體染色體中隨機選擇一個位置，將兩個染色體相應位置的基因進行互換；然后進入變異環(huán)節(jié)，以0.05的變異概率決定每個個體染色體是否執(zhí)行變異，如果執(zhí)行變異，則在該染色體上隨機選取兩個位置，互換這兩個位置的基因；然后進入進化逆轉環(huán)節(jié)，在900個個體染色體上選擇兩個位置，將兩個位置中間的基因逆向排列，比較逆轉前后的適應度，根據(jù)適應度大小決定是否進行逆轉。此時即完成1次循環(huán)。當循環(huán)次數(shù)未達到最大遺傳代數(shù)100時，以此時形成的新種群再次進入選擇、交叉、變異、進化逆轉環(huán)節(jié)，直到達到設定的最大遺傳代數(shù)。

最后，針對100次循環(huán)后得到的適應度最大的個體染色體，根據(jù)其中12個基因的順序，得出近似的最優(yōu)規(guī)劃路徑。

為比較該模型及算法的實用性及有效性，本文對無路徑規(guī)劃方案、不考慮設備故障概率的排查路徑方案和考慮設備故障概率的排查路徑方案三者進行對比。

(1)無路徑規(guī)劃方案時，搶修人員隨機選擇排查路徑(假定其按照設備編號順序排查)，此時的排查路徑為S→1→3→2→4→5→6→8→10→7→9→12→11，總路徑時間為69 min，計及設備故障概率的路徑時間為22.439 4 min。

(2)不考慮設備故障概率時，以式(3)為適應度函數(shù)建立路徑規(guī)劃模型，并運用遺傳算法進行求解。根據(jù)問題的參數(shù)設定，種群中個體染色體數(shù)目m為1 000，最大遺傳代數(shù)maxgen為200，選擇概率Ps為0.9，交叉概率Pc為0.9，變異概率Pm為0.05，將適應度函數(shù)及設定參數(shù)帶入算法中，計算得出的排查路徑為S→1→6→8→5→3→2→4→7→9→10→11→12，總路徑時間為50 min，計及設備故障概率的路徑時間為17.069 3 min。

(3)考慮設備故障概率時，以式(4)為適應度函數(shù)建立路徑規(guī)劃模型，同樣運用遺傳算法進行求解，問題參數(shù)設定值同上。此時計算得出的排查路徑為S→2→4→7→9→12→11→10→8→5→3→1→6，總路徑時間為56 min，計及設備故障概率的路徑時間為13.108 3 min。

對三種情況下排查路徑規(guī)劃方案的優(yōu)劣進行對比，如表2所示。

表2 排查路徑方案對比Tab.2 Comparison oftroubleshooting path schemes

可以看出，對排查路徑進行合理規(guī)劃后，總路徑時間和計及設備故障概率的路徑時間均得到明顯改善。

(1)與無路徑規(guī)劃方案相比，不論是否考慮設備故障概率，路徑規(guī)劃后的總路徑時間和計及設備故障概率的路徑時間均大幅降低。在“不考慮設備故障概率”的方案中，總路徑時間減少27.54%，計及設備故障概率的路徑時間減少23.93%；在“考慮設備故障概率”的方案中，總路徑時間減少18.84%，計及設備故障概率的路徑時間減少41.58%?？梢钥闯觯噍^于無規(guī)劃的設備排查，合理的搶修路徑規(guī)劃能夠大幅改善排查工作的及時性與準確性。

(2)對比分析“不考慮設備故障概率”與“考慮設備故障概率”兩種情況下的路徑規(guī)劃方案，在“考慮設備故障概率”的方案中，總路徑時間較“不考慮設備故障概率”方案增加12%，計及設備故障概率的路徑時間減少23.21%。結果表明考慮設備故障概率時的排查路徑及時性稍弱，但排查準確性明顯增強。兩種路徑規(guī)劃方案的區(qū)別具體體現(xiàn)在對設備4、設備7、設備9和設備12的排查順序上，由于設備4、設備9和設備12的故障概率(分別為0.053 4、0.067 3、0.074 5和0.168 5)較其他設備明顯增大(平均故障概率為0.0134 6)，因此，考慮設備故障概率時的路徑優(yōu)先考慮對設備4、設備7、設備9和設備12的排查，更可能優(yōu)先找到故障點，體現(xiàn)了其兼顧時間最小化和大概率故障設備優(yōu)先性的整體思路。

4 結論

本文對配電系統(tǒng)設備故障時，故障點被限定在某一區(qū)域內的排查路徑規(guī)劃問題進行了分析研究。首先，為兼顧路徑時間的最小化和大故障概率設備的優(yōu)先性，提出以計及設備故障概率的路徑時間作為規(guī)劃目標，綜合考慮“總時間最短”和“大故障概率設備優(yōu)先級最高”，進行排查路徑規(guī)劃。其次，針對該多目標組合優(yōu)化問題，分兩步進行模型建立，先不考慮設備故障概率，類比于旅行商問題(TSP)建立路徑規(guī)劃模型；在此基礎上，考慮設備故障概率，在保證路徑時間最短的前提下，確保大故障概率設備的排查有限性，對模型進行改進，得出基于配電設備故障概率的排查路徑規(guī)劃模型。然后，運用遺傳算法對該模型進行求解并對求解過程進行詳細說明。最后，以算例對所提出的模型及算法的可行性和有效性進行了分析論證。結果表明本文所提出的排查路徑規(guī)劃模型能夠大幅提升排查工作的及時性和準確性，對于提升配電系統(tǒng)應急搶修能力具有重要的參考價值。