基于遺傳算法的輸電線路覆冰災(zāi)害應(yīng)急響應(yīng)物資儲(chǔ)備決策 優(yōu)化模型*

何帔雨，李 鵬，謝汝生，張松海，蔣建波，曹 敏

(1.云南大學(xué) 信息學(xué)院，云南 昆明 650091；2.云南電網(wǎng)有限責(zé)任公司電力科學(xué)研究院，云南 昆明 650217)

0 引言

我國(guó)云、貴、川、渝、湘、陜等低緯度高海拔地區(qū)，由于地形地貌復(fù)雜，氣候環(huán)境多變，每年冬季在微地形和微氣候的共同影響下經(jīng)常發(fā)生冰凍災(zāi)害[1-2]，嚴(yán)重覆冰過(guò)程將導(dǎo)致架空輸變電系統(tǒng)金具損壞、導(dǎo)線斷股、桿塔折損、絕緣子翻轉(zhuǎn)破裂等機(jī)械事故，或引發(fā)絕緣子污閃、舞動(dòng)閃絡(luò)、脫冰閃絡(luò)等電氣事故，極大地威脅著輸電線網(wǎng)絡(luò)的正常運(yùn)行[3-4]。因此，如何根據(jù)氣象部門(mén)提供的氣象預(yù)報(bào)信息及時(shí)做出抗擊冰凍災(zāi)害應(yīng)急響應(yīng)，減小對(duì)電力網(wǎng)絡(luò)的影響，已成為亟需解決的問(wèn)題[5]。但由于云南、貴州、湖南等低緯度高海拔地區(qū)冬季冰雪封山，地形地貌復(fù)雜，交通狀況不佳，因此要及時(shí)調(diào)配應(yīng)急相應(yīng)物資進(jìn)行事故搶修或維護(hù)檢修較為困難，且搶險(xiǎn)期間正值春運(yùn)高峰期，而目前電網(wǎng)部門(mén)應(yīng)急物資緊急采購(gòu)、征用、調(diào)撥和配送機(jī)制不夠完善，存在著物資存儲(chǔ)設(shè)施不足、布局不盡合理、儲(chǔ)備方式單一、數(shù)量偏少等弊端。因此必須根據(jù)氣象部分的預(yù)報(bào)信息，及時(shí)做好物資儲(chǔ)備工作。

目前，已有國(guó)內(nèi)外學(xué)者對(duì)搶險(xiǎn)救災(zāi)和備品備件決策做了大量的研究。袁仲熊等[6]以備品備件的采購(gòu)、存儲(chǔ)以及缺貨成本為基礎(chǔ)，提出了用于指導(dǎo)最佳采購(gòu)量的電網(wǎng)搶修備品備件庫(kù)存模型；李世停等[7]針對(duì)在艦船的部件在航行時(shí)段是不可維修的條件下，提出了基于可靠性的艦船備件動(dòng)態(tài)規(guī)劃決策優(yōu)化模型；吳在棟等[8]以河流的突發(fā)污染為背景，建立基于Dijkstra算法的多目標(biāo)多約束應(yīng)急物資調(diào)度模型；Ayush等[9]用模因算法來(lái)優(yōu)化車(chē)隊(duì)系統(tǒng)的維修和備件決策水平，并用遺傳算法所求解的結(jié)果與之做了對(duì)比；Ren 等[10]通過(guò)灰色局勢(shì)決策分析，根據(jù)當(dāng)前的維修水平劃分來(lái)確定相應(yīng)的備件種類(lèi)和數(shù)量；趙洪山等[11]針對(duì)風(fēng)電機(jī)組部件的備品備件庫(kù)存問(wèn)題，提出了基于(s,Q)策略的庫(kù)存優(yōu)化模型。

根據(jù)已有文獻(xiàn)，本文針對(duì)輸電線路覆冰災(zāi)害應(yīng)急響應(yīng)物資儲(chǔ)備問(wèn)題，提出了基于災(zāi)害預(yù)警信息的物資儲(chǔ)備模型。此模型主要根據(jù)天氣部門(mén)的氣象播報(bào)來(lái)推測(cè)覆冰災(zāi)害時(shí)間段和程度，由此來(lái)提前對(duì)應(yīng)急物資做好儲(chǔ)備，不僅解決了以往由于地理環(huán)境、天氣情況等因素對(duì)搶險(xiǎn)物資配送的安全性和及時(shí)性問(wèn)題，還能使經(jīng)濟(jì)耗費(fèi)降到最低。以云南某供電局的冬季應(yīng)急物資儲(chǔ)備為例驗(yàn)證模型的有效性，同時(shí)證明了此模型具有提高電網(wǎng)部門(mén)應(yīng)對(duì)冰凍災(zāi)害和經(jīng)濟(jì)效益的能力。

1 遺傳算法決策優(yōu)化模型

遺傳算法是1種基于生物進(jìn)化理論的優(yōu)化算法[12]，對(duì)于1個(gè)需要優(yōu)化的問(wèn)題f(x),遺傳算法將每1個(gè)決策x等同于染色體的基因編碼，經(jīng)過(guò)不斷的基因重組和變異等操作，尋找最優(yōu)解。

1)初始化種群。隨機(jī)產(chǎn)生1個(gè)初始化種群M={m1,m2,,mn},對(duì)該種群中的每個(gè)個(gè)體的染色體進(jìn)行編碼。

2)適應(yīng)度計(jì)算。適應(yīng)度大小表征了個(gè)體的生存能力。使用適應(yīng)度函數(shù)f(t)來(lái)評(píng)估種群M中每個(gè)個(gè)體的適應(yīng)度大小，用fi代表個(gè)體mi的適應(yīng)度。

3)親代選擇。根據(jù)種群個(gè)體的適應(yīng)度計(jì)算出每個(gè)個(gè)體被選擇為親代的概率。其選擇概率如下：

(1)

4)基因交叉重組。將選擇的染色體mi和mj進(jìn)行基因重組。重組后的染色體分別為mi′，mj′，其重組后的編碼如式(2)所示。式中a為重組因子，且a∈(0,1)。

(2)

5)基因突變。生成的新染色體編碼序列中的某一位編碼xi有一定的概率發(fā)生變異。

重復(fù)步驟2)～5),直到完成最大迭代次數(shù)時(shí)終止操作。

2 覆冰應(yīng)急物資儲(chǔ)備模型

2.1 問(wèn)題描述

覆冰災(zāi)害中搶修材料和消耗品是覆冰搶險(xiǎn)救災(zāi)的重要物資，主要包括導(dǎo)線、天線、拉線、絕緣子串、線夾、塔材和變電站的電流互感器、支柱瓷瓶等輸變電設(shè)備。同時(shí)也包括給除冰人員配備的除冰工具和保障工具，如竹竿、絕緣棒、橡皮錘、照明設(shè)備、保暖設(shè)備(衣服、鞋子)等。

根據(jù)云南東北部某供電局近幾年提供的數(shù)據(jù)，覆冰災(zāi)害發(fā)生主要集中于11月末至第2年3月初的約5個(gè)月時(shí)間里，如何確定每個(gè)月對(duì)輸變電設(shè)備、除冰工具和保障工具的采購(gòu)量，使得既能滿(mǎn)足每月的需求量，保證一定的應(yīng)急物資安全，又能使采購(gòu)成本和存儲(chǔ)費(fèi)用達(dá)到最小，是科學(xué)儲(chǔ)備和科學(xué)管理物資需要解決的問(wèn)題。

2.2 建模及求解過(guò)程

1)數(shù)據(jù)定義[13]

sk為第k階段開(kāi)始的物資存儲(chǔ)數(shù)，是狀態(tài)變量，萬(wàn)套；uk為第k階段的采購(gòu)數(shù)量，萬(wàn)套，是決策變量；qk為第k階段的需要量，萬(wàn)套；ck為采購(gòu)單位成本(因?yàn)楣┣箨P(guān)系的變化，采購(gòu)成本為變數(shù))，元；rk為每月的需求量，萬(wàn)套。

2)約束條件

應(yīng)急必需品采購(gòu)數(shù)量以10的倍數(shù)進(jìn)行采購(gòu)，公司每月最多采購(gòu)Pmax單位；存儲(chǔ)費(fèi)用為每單位Tp。每個(gè)月的需求量和每件應(yīng)急必需品的單位采購(gòu)成本如表1所示。

表1 月需及單位成本Table 1 Monthly demand and unit cost

3)數(shù)學(xué)模型

總費(fèi)用=每月的采購(gòu)費(fèi)用+庫(kù)存費(fèi)用，即目標(biāo)函數(shù)：

minz=(c1u1+c2u2++c5u5) +Tp(s1+s2++s5)

(3)

下月初庫(kù)存=本月初庫(kù)存量+本月采購(gòu)量-本月需求量。各月的具體情況如表2所示。初始月為準(zhǔn)備期，初始庫(kù)存由給定值a確定，s1=a。

表2 每月需求情況Table 2 Monthly demand situation

3月份之后，氣候回暖，與覆冰應(yīng)急相對(duì)應(yīng)的物資消耗將為零，得s6=0。這是隱含的約束條件，是問(wèn)題的約束邊界。每月的最大采購(gòu)限額為Pmax，采購(gòu)量限制為10的整數(shù)倍，可令uk=10m，m為整數(shù)且10m≤Pmax。最終得到的數(shù)學(xué)模型：

(4 )

3 基于遺傳算法的覆冰應(yīng)急物資儲(chǔ)備優(yōu)化模型

本文提出的基于災(zāi)害預(yù)警信息的物資儲(chǔ)備遺傳算法模型總體框架如圖1所示。該模型首先根據(jù)氣象部門(mén)給出的覆冰災(zāi)害月度預(yù)報(bào)信息，依據(jù)線路規(guī)模和抗災(zāi)經(jīng)驗(yàn)確定覆冰災(zāi)害應(yīng)急物資需求數(shù)量，參與每月月初的采購(gòu)決策，決定物資的采購(gòu)量，作為該模型的輔助決策與輔助分析。

模型中，以覆冰應(yīng)急物資儲(chǔ)備的最小成本為目標(biāo)函數(shù)，以每月采購(gòu)量為決策變量，結(jié)合每月的存儲(chǔ)量、需求量等因素建立多約束條件。在遺傳算法中，初始化相關(guān)參數(shù)，并以目標(biāo)函數(shù)的倒數(shù)為適應(yīng)度函數(shù)，經(jīng)過(guò)不斷迭代，最終找到每月采購(gòu)數(shù)量的最優(yōu)決策和目標(biāo)函數(shù)的最優(yōu)值。其遺傳算法的偽代碼如下：

圖1 模型總體框架Fig.1 Model overall framework

{pc：基因交叉重組概率 pm：基因變異概率

m：種群大小g：最大迭代次數(shù)

初始化pm，pc，m，g等參數(shù)。隨機(jī)產(chǎn)生初始種群pop

do

{對(duì)每個(gè)染色體進(jìn)行二進(jìn)制編碼

以模型中的目標(biāo)函數(shù)的倒數(shù)為適應(yīng)度函數(shù)

計(jì)算種群中每一個(gè)體的適應(yīng)度f(wàn)i

初始化空種群newpop

do

{

根據(jù)選擇概率從種群中選出2個(gè)親代

if ( random ( 0 , 1 ) < pc )

{

對(duì)2個(gè)親代個(gè)體按交叉概率進(jìn)行交叉操作

}

if ( random ( 0 , 1 ) < pm )

{

對(duì)2個(gè)親代個(gè)體按變異概率進(jìn)行變異操作

}

將2個(gè)新個(gè)體加入種群newpop中

}

until (m個(gè)子代被創(chuàng)建 )

用newpop取代pop

}

until (繁殖次數(shù)超過(guò)g)

找到適應(yīng)度函數(shù)最大時(shí)對(duì)應(yīng)的目標(biāo)函數(shù)值

output (應(yīng)急物資儲(chǔ)備最小成本及5個(gè)月的最優(yōu)采購(gòu)決策)}

4 結(jié)果測(cè)試及分析

4.1 遺傳算法優(yōu)化

以除冰人員保障物資(衣服、鞋、手套等)為例，假設(shè)初始庫(kù)存為20萬(wàn)套，庫(kù)存成本為2元/套，其每月采購(gòu)的數(shù)量最大值為150萬(wàn)套(Pmax=150)，根據(jù)以往的覆冰情況和物資需求統(tǒng)計(jì)數(shù)據(jù)，11月至第2年3月物資的需求情況和各月的采購(gòu)成本分別如表3和表4所示。

表3 每月物資需求數(shù)量Table 3 Monthly demand for materials

表4 每月采購(gòu)成本Table 4 Monthly purchase cost

通過(guò)遺傳算法對(duì)上述模型進(jìn)行優(yōu)化。在遺傳算法中，種群大小為200；基因交叉重組概率為0.9;變異概率為0.05；迭代次數(shù)為300。遺傳算法優(yōu)化的迭代收斂圖如圖2所示，所得出的最優(yōu)決策如表5所示，總成本最小值為25 380元。

4.2 動(dòng)態(tài)規(guī)劃優(yōu)化

動(dòng)態(tài)規(guī)劃是運(yùn)籌學(xué)的1個(gè)分支，是求解決策過(guò)程較

圖2 遺傳算法迭代收斂曲線Fig.2 Genetic algorithm iterative convergence graph

月份需求量/萬(wàn)套117012150011002130030

為優(yōu)化的數(shù)學(xué)方法。基本思想是將待求解的多階段問(wèn)題分解為單階段決策問(wèn)題，利用各階段之間的關(guān)系，逐個(gè)求解，前一子問(wèn)題的解為后一子問(wèn)題的求解提供有用的信息。

將該模型動(dòng)態(tài)的視為按各個(gè)階段(各月)先后做出決策(采購(gòu)量)的過(guò)程，在每個(gè)月做決策時(shí)，不能僅考慮本月的費(fèi)用(階段指標(biāo))，因?yàn)楸驹碌臎Q策會(huì)對(duì)以后的各月的決策產(chǎn)生影響，應(yīng)優(yōu)先考慮從開(kāi)始到結(jié)束的總費(fèi)用(總指標(biāo))，而每月的決策可以依賴(lài)于各月月初倉(cāng)庫(kù)中的存貨量以及需要量(對(duì)以往數(shù)據(jù)作分析和預(yù)測(cè))，而與以前各月如何造成這一存貨量的情況無(wú)關(guān)(無(wú)后效性)。其動(dòng)態(tài)規(guī)劃模型框架如圖3所示。

圖3 動(dòng)態(tài)規(guī)劃模型框架Fig.3 Dynamic programming model framework

由圖3可知，動(dòng)態(tài)規(guī)劃分為5個(gè)階段。根據(jù)逆序解法，第1階段為11月份，第2階段是12月份，依此類(lèi)推。通過(guò)動(dòng)態(tài)規(guī)劃方法對(duì)上述模型進(jìn)行決策優(yōu)化，求解的每月最優(yōu)采購(gòu)決策如表6所示，總成本最小值為26 430元。

表6 動(dòng)態(tài)規(guī)劃優(yōu)化結(jié)果Table 6 Dynamic programming optimization results

通過(guò)對(duì)遺傳算法和動(dòng)態(tài)規(guī)劃優(yōu)化的實(shí)驗(yàn)結(jié)果比較分析可知，二者5個(gè)月的總采購(gòu)量是相同的，由于受每個(gè)月的采購(gòu)成本、存儲(chǔ)成本的不同，二者在各月的采購(gòu)量上產(chǎn)生了差別，最終導(dǎo)致了在總成本上的差異。在都滿(mǎn)足約束的條件下，從總成本的角度來(lái)看，遺傳算法所求得的采購(gòu)決策優(yōu)于動(dòng)態(tài)規(guī)劃，通過(guò)動(dòng)態(tài)規(guī)劃結(jié)果也驗(yàn)證了遺傳算法在此模型上的正確性和有效性。

5 結(jié)論

1)針對(duì)電網(wǎng)物資儲(chǔ)備中的易耗品、消耗品和應(yīng)急保障物資提出了預(yù)警模型。根據(jù)天氣預(yù)測(cè)，提前對(duì)應(yīng)急物資做以?xún)?chǔ)備，解決了應(yīng)急物資采購(gòu)、運(yùn)輸?shù)确矫娴碾y題，也使得電力部門(mén)在應(yīng)急物資儲(chǔ)備設(shè)施和布局方面更加合理，消除儲(chǔ)備數(shù)量偏少等弊端，最終提高應(yīng)對(duì)電網(wǎng)災(zāi)害的可靠性和及時(shí)性。

2)根據(jù)覆冰預(yù)測(cè)計(jì)算，物資還處于實(shí)驗(yàn)階段，但是隨著覆冰預(yù)測(cè)模型的精確，月初物資的需求量也將逐漸明確，對(duì)成本的控制也會(huì)越來(lái)越精確。