湯雪松，鄧 勇，劉 鑫，龔仁蘭，廖 勇

（1.國(guó)網(wǎng)重慶市電力公司銅梁供電分公司，重慶 402560；2.重慶大學(xué) 微電子與通信工程學(xué)院，重慶 400044）

隨著物聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，我國(guó)電網(wǎng)規(guī)模不斷擴(kuò)大，電力系統(tǒng)的物資需求量正在不斷增加。為保障電力系統(tǒng)安穩(wěn)運(yùn)行，面對(duì)緊急事故能夠快速解決物資供應(yīng)任務(wù)，最為理想狀態(tài)是物資供應(yīng)商不經(jīng)中轉(zhuǎn)直接向物資需求點(diǎn)進(jìn)行物資運(yùn)輸，但在實(shí)際應(yīng)用中，電力物資需先送至物資預(yù)置點(diǎn)，隨后運(yùn)輸至物資需求點(diǎn)，往往會(huì)出現(xiàn)前線電力物資緊缺，物資預(yù)置點(diǎn)中物資儲(chǔ)存量卻不足，無(wú)法滿足物資的及時(shí)供應(yīng)。因此，物資預(yù)置與調(diào)度問(wèn)題亟待解決［1－3］。

Chai［4］設(shè)計(jì)了一個(gè)基于多救點(diǎn)、多物資的應(yīng)急調(diào)度算法和最短路徑求解算法，能夠在滿足時(shí)間與出救點(diǎn)數(shù)量的同時(shí)，解決災(zāi)害地多種物資調(diào)度問(wèn)題。但是在物資調(diào)度過(guò)程中，并沒(méi)有結(jié)合時(shí)間效益和經(jīng)濟(jì)效益。Han等［5］基于優(yōu)化思想，以運(yùn)輸時(shí)間和需要物資數(shù)量安全到達(dá)目的地為對(duì)象，建立了調(diào)度模型解決緊急任務(wù)，并研究了運(yùn)輸時(shí)間和安全性，但是并沒(méi)有考慮物資預(yù)置問(wèn)題。Dawei等［6］建立了基于物資運(yùn)輸最早時(shí)間、成本最低的雙層優(yōu)化數(shù)學(xué)模型，用于解決緊急物資調(diào)度連續(xù)消耗問(wèn)題，但是在實(shí)踐中存在很多不連續(xù)消耗問(wèn)題。陳勤等［7］考慮了復(fù)雜道路環(huán)境中車(chē)速和安全性因素，將非支配排序遺傳算法（non-dominated sorting genetic algorithm-Ⅱ，NSGA-Ⅱ）應(yīng)用于解決軍事應(yīng)急物流路徑優(yōu)化問(wèn)題，結(jié)合了時(shí)效性、安全性、經(jīng)濟(jì)性，卻沒(méi)有考慮應(yīng)急物資存儲(chǔ)量不足的情況，造成軍事應(yīng)急物資無(wú)法送達(dá)問(wèn)題。

灰色模型（grey model，GM）能夠?qū)υ紨?shù)據(jù)做出高精度的預(yù)測(cè)，已在電力物資需求領(lǐng)域得到較好地應(yīng)用。史德明等［8］指出，GM近年來(lái)已被引入電力系統(tǒng)的預(yù)測(cè)中，獲得效果較好，并且具有建模信息少、運(yùn)算方便、建模精度高的優(yōu)勢(shì)。劉宇等［9］提出了一種基于改進(jìn)灰色理論的電力系統(tǒng)中長(zhǎng)期負(fù)荷預(yù)測(cè)方法，該方法將經(jīng)典灰色預(yù)測(cè)模型和三點(diǎn)平滑法相結(jié)合，首先對(duì)歷史數(shù)據(jù)進(jìn)行預(yù)處理，然后再構(gòu)建基于等維信息矩陣的灰色預(yù)測(cè)模型，最后利用殘差處理方法對(duì)預(yù)測(cè)結(jié)果進(jìn)行修正。仿真結(jié)果表明：改進(jìn)灰色預(yù)測(cè)方法在預(yù)測(cè)精度和適用性方面都具有顯著優(yōu)勢(shì)。

為了解決電力物資供應(yīng)不足、不及時(shí)的問(wèn)題，設(shè)計(jì)了一個(gè)三級(jí)網(wǎng)絡(luò)模型，分層次設(shè)置大量的物資預(yù)置點(diǎn)（轉(zhuǎn)運(yùn)點(diǎn)），進(jìn)行電力物資預(yù)置，分級(jí)快速供應(yīng)電力物資。首先根據(jù)區(qū)域中的歷史電力物資需求總量數(shù)據(jù)利用GM預(yù)測(cè)出未來(lái)的物資需求總量，供應(yīng)商提前將該區(qū)域內(nèi)所需電力物資運(yùn)輸至物資預(yù)置點(diǎn)（轉(zhuǎn)運(yùn)點(diǎn)）預(yù)置充足電力物資；在出現(xiàn)供應(yīng)不足時(shí)，可以從其他區(qū)域或供應(yīng)商處進(jìn)行物資調(diào)度。在模型方面，結(jié)合實(shí)際情況，在考慮時(shí)間、隨機(jī)風(fēng)險(xiǎn)的基礎(chǔ)上，基于泊松過(guò)程建立了多目標(biāo)物資調(diào)度模型?；诖四Ｐ停岢隽艘环N基于隨機(jī)游走算法改進(jìn)的遺傳物資調(diào)度算法（random walk-genetic algorithm，RW-GA），首先通過(guò)RW算法進(jìn)行全局隨機(jī)搜索，確定最優(yōu)解候選集，再利用GA進(jìn)行局部尋優(yōu)，快速規(guī)劃得到全局最優(yōu)的電力物資配送路線。最后，通過(guò)仿真驗(yàn)證了本文所提算法的可行性和有效性。

1 物資預(yù)置及調(diào)度模型

1.1 問(wèn)題描述與說(shuō)明

電力物資需求點(diǎn)分布廣泛，物資供應(yīng)商通過(guò)對(duì)電力物資預(yù)置點(diǎn)（轉(zhuǎn)運(yùn)點(diǎn)）進(jìn)行物資儲(chǔ)備，預(yù)置點(diǎn)可進(jìn)行區(qū)域性的物資輸送，保證負(fù)責(zé)區(qū)域內(nèi)所有物資需求點(diǎn)的物資及時(shí)送達(dá)；為了避免出現(xiàn)區(qū)域物資儲(chǔ)備不足的問(wèn)題，可從其他區(qū)域進(jìn)行物資調(diào)度，供應(yīng)商也可對(duì)電力物資直接輸送。本文求解電力物資預(yù)置及配送問(wèn)題，物資供應(yīng)商可以按照預(yù)測(cè)的物資需求量提前向物資預(yù)置點(diǎn)進(jìn)行物資配送并貯存，當(dāng)該區(qū)域多處發(fā)生電力故障時(shí)，急需大量電力物資對(duì)這些地區(qū)進(jìn)行電力搶修，這時(shí)由預(yù)置點(diǎn)向需求點(diǎn)按照優(yōu)化路徑進(jìn)行輸送，同時(shí)也可從其他區(qū)域或供應(yīng)商處進(jìn)行物資調(diào)度。

1.2 三級(jí)網(wǎng)絡(luò)GM物資預(yù)置模型

為保證電力物資的及時(shí)供應(yīng)，通過(guò)建立三級(jí)網(wǎng)絡(luò)模型進(jìn)行物資預(yù)置、物資需求分解，保障物資的快速、及時(shí)供應(yīng)，如圖1所示，假設(shè)每個(gè)物資供應(yīng)商SI對(duì)應(yīng)M個(gè)物資預(yù)置點(diǎn)（轉(zhuǎn)運(yùn)點(diǎn)），物資預(yù)置點(diǎn)用Hm（m＝1，2，…，M）表示，每個(gè)物資預(yù)置點(diǎn)對(duì)該區(qū)域的物資需求點(diǎn)Dmn進(jìn)行物資輸送，其中m表示為物資預(yù)置點(diǎn)的標(biāo)號(hào)，n表示物資需求點(diǎn)的序號(hào)，在物資供應(yīng)商、物質(zhì)預(yù)置點(diǎn)以及物資需求點(diǎn)之間采用運(yùn)輸工具ki（i＝1，…，K）進(jìn)行資源運(yùn)輸。

基于建立的三級(jí)網(wǎng)絡(luò)模型，物資供應(yīng)商可向物資預(yù)置點(diǎn)提前進(jìn)行電力物資的配送及貯存，為了避免資源浪費(fèi)或資源貯存不足，采用GM對(duì)每個(gè)區(qū)域所需要的電力物資總量進(jìn)行預(yù)測(cè)。

已知x（0）＝x（0）（i），i＝1，2，…，n為參考數(shù)據(jù)列，1次累加生成序列：

式中：x（1）（k），k＝1，2，…，n中各數(shù)據(jù)表示對(duì)應(yīng)前幾項(xiàng)數(shù)據(jù)的累加，x（1）（k）的均值生成序列：

建立灰微分方程：

1.3 多目標(biāo)物資調(diào)度模型

運(yùn)輸時(shí)間分為直達(dá)路線時(shí)間分量與轉(zhuǎn)運(yùn)路線時(shí)間分量［10］。當(dāng)物資需要轉(zhuǎn)運(yùn)時(shí)，每一段轉(zhuǎn)運(yùn)路程采用不同的運(yùn)輸工具，但為了方便起見(jiàn)，要求每一段路程只能使用一種運(yùn)輸工具。電力物資通過(guò)預(yù)置點(diǎn)轉(zhuǎn)運(yùn)帶來(lái)不同的轉(zhuǎn)運(yùn)時(shí)間，轉(zhuǎn)運(yùn)時(shí)間與物資運(yùn)輸量有關(guān)。總運(yùn)輸時(shí)間如式（7）所示：

式中：T表示電力物資總的運(yùn)輸時(shí)間；xid表示供應(yīng)商i向需求點(diǎn)d直達(dá)的物資量；disid表示供應(yīng)商i和需求點(diǎn)d的直達(dá)距離；disih表示供應(yīng)商i和轉(zhuǎn)運(yùn)點(diǎn)h的距離；dishd表示轉(zhuǎn)運(yùn)點(diǎn)h和需求點(diǎn)d的距離；vk表示交通工具k的速度；tzz表示轉(zhuǎn)運(yùn)速率；λid表示供應(yīng)商i到需求點(diǎn)d的各直達(dá)路段泊松強(qiáng)度；λih表示供應(yīng)商i到轉(zhuǎn)運(yùn)點(diǎn)h的各路段泊松強(qiáng)度；λhd表示轉(zhuǎn)運(yùn)點(diǎn)h到需求點(diǎn)d的路線上的泊松強(qiáng)度；“？”表示選擇下標(biāo)，即對(duì)“？”后的離散變量進(jìn)行選擇；λi？d為布爾變量，供應(yīng)商i選擇任意需求點(diǎn)d且不經(jīng)過(guò)任意轉(zhuǎn)運(yùn)點(diǎn)情況下為1，否則為0；λi？k為布爾變量，在λi？d＝1前提下，選擇運(yùn)輸工具k為1，否則為0；λi？h為布爾變量，如果供應(yīng)商i選擇轉(zhuǎn)運(yùn)點(diǎn)h為1，否則為0；λih？k為布爾變量，在λi？h＝1前提下，如果選擇運(yùn)輸工具k為1，否則為0；λhd？k為布爾變量，在λi？h＝1前提下，從轉(zhuǎn)運(yùn)點(diǎn)h到需求點(diǎn)d，選擇運(yùn)輸工具k為1，否則為0；I表示供應(yīng)商集合，?i∈I；H表示物資轉(zhuǎn)運(yùn)點(diǎn)（物資預(yù)置點(diǎn)），集合?h∈H；D表示物資需求點(diǎn)集合，?d∈D；K表示運(yùn)輸工具集合，?k∈K。

E0是運(yùn)輸工具在行駛過(guò)程中發(fā)生突發(fā)狀況的概率。對(duì)電力物資運(yùn)輸過(guò)程中的隨機(jī)風(fēng)險(xiǎn)進(jìn)行考量，即針對(duì)該過(guò)程的某個(gè)特征函數(shù)進(jìn)行考察。本文選取泊松過(guò)程的均值函數(shù)為考量對(duì)象，即在一段路線中，發(fā)生突發(fā)狀況的期望值越低，則安全到達(dá)的概率越大，隨機(jī)風(fēng)險(xiǎn)則會(huì)越小，得到電力物資前隨機(jī)風(fēng)險(xiǎn)如式（8）所示：

1.4 目標(biāo)函數(shù)

目標(biāo)函數(shù)是由時(shí)間消耗量與隨機(jī)風(fēng)險(xiǎn)2個(gè)要素加權(quán)得到，因?yàn)?個(gè)指標(biāo)具有不同的量綱，故本文對(duì)其進(jìn)行標(biāo)準(zhǔn)化。為樣本的均值，σ為樣本的標(biāo)準(zhǔn)差。本文對(duì)多目標(biāo)函數(shù)進(jìn)行處理，通過(guò)加權(quán)求和得到綜合適應(yīng)度Z*。得到的目標(biāo)函數(shù)如式（9）所示：

在滿足上述約束條件的同時(shí)，要求每個(gè)物資需求點(diǎn)有且只有一次被配送物資，增加的約束條件為

2 RW-GA物資調(diào)度算法

結(jié)合1.3節(jié)提出的多目標(biāo)調(diào)度模型，進(jìn)一步提出了一種基于隨機(jī)游走算法改進(jìn)的遺傳物資調(diào)度算法（RW-GA）。RW算法針對(duì)全局進(jìn)行大范圍的隨機(jī)搜索［11］，確定最優(yōu)解候選集，結(jié)合GA尋優(yōu)的特點(diǎn)［12－14］，解決GA尋優(yōu)抖振問(wèn)題，能夠保證在電力故障發(fā)生的緊急情況下，快速規(guī)劃出全局最優(yōu)的電力物資配送路線，將電力物資及時(shí)送達(dá)所有電力故障點(diǎn)。該算法流程如圖2所示。

圖2 RW-GA算法流程框圖

1）生成初始序列

假設(shè)有若干運(yùn)輸車(chē)輛，N個(gè)物資需求點(diǎn)，物資運(yùn)送車(chē)輛從物資預(yù)置點(diǎn)Hi出發(fā)，按照｛Dip，…，Diq｝的順序進(jìn)行物資配送，將物資配送給所有物資需求點(diǎn)后回到物資預(yù)置點(diǎn)，初始化序列表示為｛Hi，Dip，…，Diq，Hi｝，其中，Hi表示物資預(yù)置點(diǎn)，Dij，j＝1，…，N表示物資需求單位。

2）隨機(jī)游走確定解候選集

隨機(jī)游走算法是一種全局搜索算法。通過(guò)設(shè)置步長(zhǎng)和閾值，在迭代過(guò)程中計(jì)算函數(shù)值，得到更優(yōu)初始值。若在迭代次數(shù)內(nèi)仍找不到更優(yōu)值，則認(rèn)為最優(yōu)解在以當(dāng)前最優(yōu)解為中心，步長(zhǎng)為半徑的球內(nèi)。

3）適應(yīng)度函數(shù)

選取式（9）中構(gòu)建的多目標(biāo)函數(shù)作為適應(yīng)度函數(shù)。適應(yīng)度高的染色體在進(jìn)化過(guò)程中往往被保留下來(lái)，更有可能接近最優(yōu)解。

4）交叉與變異

交叉與變異促使生成新的個(gè)體，保證群體多樣性。父代的基本特征通過(guò)交叉操作使子代繼承保留，從而使種群的優(yōu)良特性延續(xù)下去。變異操作是指群體中的個(gè)體基因根據(jù)設(shè)定的變異率發(fā)生突變，從而保證全局優(yōu)化。

RW-GA算法的具體步驟如下：

?

3 仿真實(shí)驗(yàn)與分析

為了驗(yàn)證模型的準(zhǔn)確性和算法的實(shí)用性，根據(jù)所建立的三級(jí)網(wǎng)絡(luò)模型，由歷史需求量的數(shù)據(jù)利用灰色模型預(yù)測(cè)出區(qū)域物資預(yù)置點(diǎn)（轉(zhuǎn)運(yùn)點(diǎn)）未來(lái)所需的電力物資總量，然后模擬在該區(qū)域中某些地區(qū)發(fā)生電力故障，需要盡快將電力物資送達(dá)所有物資需求點(diǎn)，通過(guò)RW-GA算法確定物資輸送的最優(yōu)路徑，以期保證電力物資在短時(shí)間內(nèi)送達(dá)物資需求點(diǎn)，快速修復(fù)電力故障。假設(shè)時(shí)間、隨機(jī)風(fēng)險(xiǎn)權(quán)重分別為α＝0.8、β＝0.2，轉(zhuǎn)運(yùn)速率tzz＝0.3 h／t。其他相關(guān)參數(shù)見(jiàn)表1和表2。

表1 物資預(yù)置點(diǎn)（轉(zhuǎn)運(yùn)點(diǎn)）H1物資儲(chǔ)存量

表2 物資需求點(diǎn)的模擬位置坐標(biāo) km

3.1 物資預(yù)置與輸送路線

通過(guò)所建立的GM模型，利用表1數(shù)據(jù)運(yùn)用Matlab求出預(yù)測(cè)結(jié)果曲線，如圖3所示，從而通過(guò)該曲線圖預(yù)測(cè)出未來(lái)幾個(gè)月物資預(yù)置點(diǎn)所需的物資量，電力物資供應(yīng)商能夠提前將電力物資運(yùn)輸?shù)皆撐镔Y預(yù)置點(diǎn)進(jìn)行儲(chǔ)存。

圖3 物資預(yù)測(cè)曲線

根據(jù)多目標(biāo)物資調(diào)度模型，結(jié)合RW-GA算法，利用Matlab編程求解得出物資輸送路徑，如圖4所示。物資預(yù)置點(diǎn)即轉(zhuǎn)運(yùn)點(diǎn)（圖中圓圈處）與物資供應(yīng)商位置（圖中矩形框處）的坐標(biāo)分別為（30，20）、（20，25），其中藍(lán)線為經(jīng)過(guò)轉(zhuǎn)運(yùn)點(diǎn)的輸送路線，紅線為由供應(yīng)商直達(dá)運(yùn)輸?shù)穆肪€，分別按箭頭指示方向出發(fā)，經(jīng)過(guò)每個(gè)物資需求點(diǎn)，進(jìn)行物資輸送，最后回到各自出發(fā)點(diǎn)，從而完成電力物資調(diào)度任務(wù)。

圖4 物資輸送路徑優(yōu)化曲線

3.2 結(jié)果分析

電力物資預(yù)置的精確度檢測(cè)誤差指標(biāo)為殘差和級(jí)比偏差，對(duì)比了指數(shù)平滑法與GM方法的預(yù)測(cè)精度與效果。指數(shù)平滑法［15］是數(shù)據(jù)預(yù)測(cè)模型中的重要方法之一，在經(jīng)濟(jì)方面應(yīng)用廣泛。表3給出了2種方法的計(jì)算誤差結(jié)果，經(jīng)過(guò)分析驗(yàn)證，相比指數(shù)平滑法，GM方法的預(yù)測(cè)誤差較低、精度較高，能夠?qū)Φ谝粚泳W(wǎng)絡(luò)中的電力物資預(yù)置做出較好地預(yù)測(cè)與預(yù)報(bào)。

表3 模型預(yù)測(cè)精度

圖5是30次隨機(jī)產(chǎn)生初始群體適應(yīng)度累積分布曲線，以此觀察所提RW-GA算法的收斂情況。從圖中可以看出：加入隨機(jī)游走算法改進(jìn)交叉的遺傳算法主要密集分布在0附近。在20次迭代之前，種群進(jìn)化速度較快，RW-GA算法進(jìn)入快速收斂階段；在40次迭代之后，開(kāi)始出現(xiàn)逐漸收斂的狀態(tài)；迭代次數(shù)到80次后，RW-GA算法基本進(jìn)入了收斂穩(wěn)定期。在20次迭代之前，由于RW算法的作用，算法能夠快速進(jìn)入收斂期。從圖中也可以看出：通過(guò)隨機(jī)游走算法改進(jìn)的遺傳算法有著較好的穩(wěn)定性和收斂性，可以確保算法的收斂精度與速度。

圖5 運(yùn)行30次收斂分布曲線

為了驗(yàn)證算法的有效性，在不同運(yùn)行時(shí)間下比較了RW-GA算法與GA算法適應(yīng)度的均值和方差，結(jié)果如表4所示。

表4 RW-GA與GA算法性能對(duì)比

從表4中可以看出：在不同運(yùn)行次數(shù)下，RWGA算法的均值和方差的結(jié)果均優(yōu)于GA算法。從方差可以看出：RW-GA算法的穩(wěn)定性比GA算法表現(xiàn)更好，RW-GA算法程序運(yùn)行時(shí)長(zhǎng)相比GA算法更短。針對(duì)上述結(jié)果，一方面說(shuō)明了本文所提RW-GA算法的穩(wěn)定性；另一方面說(shuō)明運(yùn)用隨機(jī)游動(dòng)改進(jìn)的遺傳算法收斂性好，能夠在短時(shí)間內(nèi)得到穩(wěn)定、滿意的電力物資配送路線。

4 結(jié)論

提出了一種基于RW-GA的電力物資配送多目標(biāo)路徑優(yōu)化方案。建立三級(jí)網(wǎng)絡(luò)GM物資預(yù)置模型，通過(guò)求解該模型得到物資轉(zhuǎn)運(yùn)點(diǎn)的最優(yōu)預(yù)置方案；建立以時(shí)間短、風(fēng)險(xiǎn)小為目標(biāo)的多目標(biāo)資源調(diào)度模型；提出了一種RW-GA電力物資調(diào)度算法，從而快速規(guī)劃得到全局最優(yōu)的電力物資配送路線。通過(guò)搭建仿真實(shí)驗(yàn)，驗(yàn)證了提出的三級(jí)網(wǎng)絡(luò)GM在電力物資預(yù)置中有更高的精度，更適合于電力物資的預(yù)置；所提的RW-GA算法收斂速度快，能夠在多目標(biāo)約束條件下規(guī)劃電力物資輸送路徑，從而有效保障及時(shí)修復(fù)電力故障與提升電網(wǎng)的整體安全性。