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

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

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

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

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

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

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

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

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

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

(1)

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

1.2 考慮設(shè)備故障概率時的排查路徑

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

(2)

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

2 模型求解

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

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

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

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

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

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

不考慮設(shè)備故障概率時：

(3)

考慮設(shè)備故障概率時：

(4)

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

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

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

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

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

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

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

3 算例分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)論

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