史曉峰，趙耀紅

(1.長(zhǎng)春工程學(xué)院現(xiàn)代教育技術(shù)中心，長(zhǎng)春 130012； 2.長(zhǎng)春大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春 130022)

0 引言

電力系統(tǒng)的穩(wěn)定運(yùn)行對(duì)維持社會(huì)秩序非常重要，一旦發(fā)生大規(guī)模甚至長(zhǎng)時(shí)間的停電事故，將對(duì)社會(huì)穩(wěn)定和經(jīng)濟(jì)發(fā)展帶來(lái)嚴(yán)重的不良后果。因此，當(dāng)停電發(fā)生后，如何快速及時(shí)地對(duì)電力系統(tǒng)進(jìn)行恢復(fù)意義重大。其中，應(yīng)急搶修物資的調(diào)度最耗費(fèi)車輛、人力和時(shí)間，在非常時(shí)期如何能夠合理、高效地調(diào)度物資，節(jié)省時(shí)間和費(fèi)用等，值得深入研究。

國(guó)內(nèi)外學(xué)者對(duì)應(yīng)急物資調(diào)度問(wèn)題進(jìn)行了一系列研究，Shi等[1]以距離最短為目標(biāo)構(gòu)建調(diào)度模型，一車服務(wù)一需求點(diǎn)。Vidal等[2]建立的調(diào)度模型帶有時(shí)間限制，考慮了多個(gè)供應(yīng)點(diǎn)問(wèn)題，實(shí)現(xiàn)了物資的多次配送。蘇濤等[3]建立了物流配送模型，注重配送費(fèi)用最小化。Berkoune等[4]建立的模型考慮了多需求點(diǎn)和多供貨點(diǎn)，以總運(yùn)輸時(shí)間最少為目標(biāo)。陳勤等[5]建立了多目標(biāo)模型，考慮了運(yùn)送費(fèi)用、運(yùn)送時(shí)間和安全性指數(shù)，但對(duì)需求量和車輛運(yùn)輸能力考慮不周。

目前針對(duì)應(yīng)急物資調(diào)度模型的研究大多數(shù)以耗時(shí)最少、費(fèi)用最小或者路程最短為目標(biāo)來(lái)展開(kāi)，但對(duì)運(yùn)輸能力考慮較少，在解決實(shí)際問(wèn)題時(shí)，滿足應(yīng)急調(diào)度時(shí)間和費(fèi)用最少的同時(shí)，應(yīng)考慮同一應(yīng)急資源供應(yīng)點(diǎn)可能多次參與調(diào)運(yùn)，這樣更加貼近現(xiàn)實(shí)。

1 輸電線路應(yīng)急搶修物資調(diào)度模型

通常的應(yīng)急搶修物資調(diào)度思路是選擇最近的物資供應(yīng)點(diǎn)進(jìn)行物資供應(yīng)。這種選擇要求該物資供應(yīng)點(diǎn)貯存的物資量必須大于等于應(yīng)急點(diǎn)的需求量，但在實(shí)際大規(guī)模應(yīng)急搶修中是不能滿足的，因此便出現(xiàn)了多個(gè)物資供應(yīng)點(diǎn)優(yōu)化調(diào)度問(wèn)題。由于是應(yīng)急搶修，因此應(yīng)急資源調(diào)度總時(shí)間最短是首先要考慮和滿足的目標(biāo)。

在大多數(shù)實(shí)際搶修中，各供應(yīng)點(diǎn)都存在運(yùn)輸能力(單次能運(yùn)送物資的最大量)的限制問(wèn)題，必須考慮多次運(yùn)送。因此，在滿足調(diào)度時(shí)間和費(fèi)用最少的前提下，同時(shí)需考慮同一應(yīng)急物資供應(yīng)點(diǎn)可能會(huì)參與多次調(diào)運(yùn)，這更加貼近實(shí)際。同時(shí)，需要一種調(diào)度算法對(duì)該模型進(jìn)行求解。

本模型解決的是從多供應(yīng)點(diǎn)往多需求點(diǎn)運(yùn)往的多種物資調(diào)度問(wèn)題。從輸電線路應(yīng)急搶修物資調(diào)度的特點(diǎn)出發(fā)，首先考慮應(yīng)急搶修時(shí)間，以時(shí)間最短作為優(yōu)化目標(biāo)；運(yùn)輸費(fèi)用也是優(yōu)化目標(biāo)之一，目的是在保證搶修時(shí)間的前提下，最小化調(diào)度中的運(yùn)輸費(fèi)用；因?yàn)槊恳还?yīng)點(diǎn)可能存在多次調(diào)運(yùn)，因此應(yīng)將各供應(yīng)點(diǎn)物資的調(diào)運(yùn)能力作為一個(gè)約束條件。根據(jù)前述優(yōu)化目標(biāo)和約束條件建立有運(yùn)輸能力約束的時(shí)間和費(fèi)用最優(yōu)的應(yīng)急資源調(diào)度模型。

記V1，V2，…，Vm為m個(gè)故障發(fā)生區(qū)域可選的應(yīng)急物資供應(yīng)點(diǎn)，A1，A2…，An為n個(gè)故障發(fā)生點(diǎn)，即需求點(diǎn)；需求點(diǎn)共需要k種應(yīng)急物資，記X=(Xi1，Xi2，…，Xik)表示故障發(fā)生點(diǎn)Ai需要k種物資的量，Xij(j=1，2，…，k)表示需求點(diǎn)Ai對(duì)第j種物資的需求量；從Vi一次調(diào)度第j種應(yīng)急物資的最大量為Mij(i=1，2，…，m；j=1，2，…，k)，到達(dá)Aj所需的單次調(diào)度時(shí)間為tij(i=1，2，…，m；j=1，2，…，n)。ttij為Vi到Aj可應(yīng)急調(diào)運(yùn)的最長(zhǎng)時(shí)間，ttij為tij的整數(shù)倍；T為規(guī)定的應(yīng)急調(diào)運(yùn)限制期；cij為從Vi調(diào)度單位第j種應(yīng)急物資所需的費(fèi)用，i=1，2，…，m，j=1，2，…，k；VXij為供應(yīng)點(diǎn)Vi的物資j的供應(yīng)能力(即存貨量)。

模型建立說(shuō)明：

1)每個(gè)供應(yīng)點(diǎn)每次調(diào)度的應(yīng)急物資的數(shù)量≥0，且不全為0，每次調(diào)度不超過(guò)自身運(yùn)輸能力。

2)各種不同的應(yīng)急物資的調(diào)度互不影響，可單獨(dú)調(diào)度，也可以一起調(diào)度。

3)需求點(diǎn)需要的物資種類和數(shù)量事先已經(jīng)確定，調(diào)度中不會(huì)發(fā)生變化。

4)所有供應(yīng)點(diǎn)的各種物資總量大于等于需求點(diǎn)所需物資總量。

5)所有供應(yīng)點(diǎn)與需求點(diǎn)的道路都是聯(lián)通的，每個(gè)供應(yīng)點(diǎn)單次運(yùn)輸物資所需的時(shí)間事先已計(jì)算得出。

應(yīng)急搶修物資調(diào)度數(shù)學(xué)模型：

(1)

T)，

(2)

(3)

∑VXij≥∑Xj(i=1，2，…，m，j=1，2，…，k)，

(4)

(5)

Mij≥0(i=1，2，…，m，j=1，2，…，k)，

(6)

(7)

前述模型的建立綜合考慮了調(diào)度的時(shí)間、費(fèi)用及運(yùn)輸能力，目的是讓應(yīng)急調(diào)度的總時(shí)間和運(yùn)輸費(fèi)用最小化。式(1)～(2)為目標(biāo)函數(shù)，代表物資運(yùn)輸時(shí)間和費(fèi)用的最小值。約束條件(3)表示第j種物資需求量小于等于其供應(yīng)總量。約束條件(4)表示對(duì)所有供應(yīng)點(diǎn)的第j種物資的需求量小于等于其庫(kù)存量。約束條件(5)表示供應(yīng)點(diǎn)的第j種物資供應(yīng)總量小于等于第j種物資供應(yīng)能力。約束條件(6)表示每次調(diào)度的物資數(shù)量≥0。約束條件(7)表示當(dāng)運(yùn)輸能力小于等于庫(kù)存量時(shí)，每次按運(yùn)送能力運(yùn)送，否則按庫(kù)存數(shù)量運(yùn)送。

約束條件不變，分別求得：

可以將目標(biāo)函數(shù)(1)和(2)合并為單目標(biāo)函數(shù)：

(8)

取適應(yīng)度函數(shù)為目標(biāo)函數(shù)(8)式的值。p1和p2分別為運(yùn)輸時(shí)間和運(yùn)輸成本在模型中的重要程度，即權(quán)值，可根據(jù)需要和不同情況人為確定二者的值，且p1+p2=1，例如：時(shí)間和費(fèi)用同樣重要時(shí)，二者的值均取0.5。

2 輸電線路應(yīng)急搶修物資調(diào)度算法

粒子群算法(Particle Swarm Optimization，PSO)基于對(duì)鳥(niǎo)群等覓食的模擬，同遺傳算法類似。算法初始時(shí)隨機(jī)選取一組解，通過(guò)多次循環(huán)迭代尋找最優(yōu)解，但該算法的特點(diǎn)是沒(méi)有交叉和變異的過(guò)程，而是經(jīng)過(guò)所有個(gè)體之間的協(xié)作來(lái)尋找最優(yōu)解的，即每個(gè)粒子不斷地在其解空間追蹤最優(yōu)粒子來(lái)進(jìn)行搜索[6]。

PSO初始化為一個(gè)種群，由m個(gè)隨機(jī)選擇的粒子組成。每個(gè)粒子有一個(gè)適應(yīng)度值，由事先建立的優(yōu)化函數(shù)求得，定義所有粒子飛行的方向與距離，粒子搜索的原則是不斷追蹤最優(yōu)粒子。每個(gè)粒子依據(jù)自己找到的最優(yōu)解(個(gè)體極值)和整個(gè)種群的最優(yōu)解(全局極值)或一部分鄰居粒子中找到的極值(局部極值)來(lái)更新自己。

第i個(gè)粒子的位置表示為

(9)

第i個(gè)粒子的速度表示為

(10)

第i個(gè)粒子經(jīng)歷過(guò)的歷史最好點(diǎn)表示為

(11)

粒子根據(jù)式(12)～(13)來(lái)更新其速度和位置：

(12)

(13)

粒子群優(yōu)化基本算法流程圖如圖1所示。

圖1 粒子群算法流程圖

粒子群算法的特點(diǎn)：結(jié)果與初始解無(wú)關(guān)，因?yàn)槌跏冀怆S機(jī)產(chǎn)生。算法具有很好的平衡全局搜索與局部搜索能力，式(12)既體現(xiàn)了搜索的多樣性，又保證了搜索向全局最優(yōu)的方向進(jìn)行；算法概念易于理解，程序?qū)崿F(xiàn)簡(jiǎn)單，能夠在復(fù)雜的、非線性區(qū)域搜索。

遺傳算法存在很多問(wèn)題：

1)易產(chǎn)生未成熟收斂點(diǎn)，收斂到局部最優(yōu)解，找不到全局最優(yōu)解，原因是未得到最優(yōu)解之前，群體已經(jīng)失去了多樣性。

2)快接近最優(yōu)解時(shí)，收斂速度較慢。遺傳算法在進(jìn)化初期能快速收斂，但在進(jìn)化后期，收斂速度變慢，影響了算法的效率。

混合粒子群遺傳算法(Particle Swarm Optimization-Genetic Algorithm，PSO-GA)能夠解決遺傳算法不成熟收斂問(wèn)題。算法首先的初始種群為K個(gè)家族；通過(guò)家族間交叉繁衍保持種群多樣性；通過(guò)家族內(nèi)交叉繁衍提高算法的收斂速度；同時(shí)進(jìn)行粒子群交叉，讓粒子以一定的“速度”(交叉概率)向本家族適應(yīng)度值最小的個(gè)體靠攏，加速收斂?；旌狭Ｗ尤哼z傳算法流程圖如圖2所示。

對(duì)PSO-GA算法的描述：1)初始種群生成。隨機(jī)生成n個(gè)個(gè)體的初始種群。2)劃分家族。將種群分成K個(gè)家族(按適應(yīng)度值)。3)族間交叉。隨機(jī)選擇兩個(gè)家族的最優(yōu)個(gè)體交叉。4)族內(nèi)交叉。在同一家族內(nèi)隨機(jī)選擇不同的個(gè)體交叉。5)粒子群交叉。最優(yōu)個(gè)體與該家族的其他個(gè)體交叉。6)變異。除了種群中最優(yōu)的個(gè)體(一般為兩個(gè))，其他個(gè)體按定義好的變異概率執(zhí)行變異操作。7)若終止條件滿足，則結(jié)束算法，否則轉(zhuǎn)到2)。

圖2 PSO-GA流程圖

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

設(shè)某地區(qū)電力桿塔A1、A2、A3發(fā)生故障，需運(yùn)送搶修物資及時(shí)搶修。周邊共有3個(gè)電力物資供應(yīng)點(diǎn)V1，V2，V3，搶修物資的供應(yīng)能力分別為VX1，VX2，VX3。故障點(diǎn)A1、A2、A3需要的搶修物資的量分別為AX1，AX2，AX3。3個(gè)電力物資供應(yīng)點(diǎn)為3個(gè)搶修點(diǎn)運(yùn)送搶修物資的運(yùn)輸能力(單次運(yùn)輸?shù)淖畲罅?分別為M1，M2，M3。3個(gè)電力物資供應(yīng)點(diǎn)運(yùn)送搶修物資的單次調(diào)度時(shí)間分別為t1，t2，t3。3個(gè)電力物資供應(yīng)點(diǎn)運(yùn)送搶修物資的單次運(yùn)輸費(fèi)用分別為c1，c2，c3。前述詳細(xì)數(shù)據(jù)分別見(jiàn)表1～4。

表1 3個(gè)供應(yīng)點(diǎn)搶修物資的運(yùn)輸能力

表2 搶修物資從3個(gè)供應(yīng)點(diǎn)到需求點(diǎn)的單次調(diào)度時(shí)間 單位:h

表3 搶修物資從3個(gè)供應(yīng)點(diǎn)到需求點(diǎn)單位的運(yùn)輸費(fèi)用 單位:萬(wàn)元

表4 搶修物資供應(yīng)量與需求量

基于前述數(shù)據(jù)集，比較GA算法和PSO-GA算法的性能。參數(shù)設(shè)置為：p1=0.7，p2=0.3，分別代表運(yùn)輸時(shí)間和運(yùn)輸成本在模型中的重要程度；種群規(guī)模n=100；循環(huán)迭代次數(shù)=20；定義變異概率Pm=0.1；定義交叉概率Pc=0.7。算法的對(duì)比結(jié)果見(jiàn)表5。與GA算法相比，PSO-GA算法在應(yīng)急物資調(diào)度過(guò)程中，能夠獲得較少的運(yùn)輸時(shí)間及運(yùn)輸費(fèi)用，使搶修更高效。

表5 算法對(duì)比結(jié)果

由圖3可知，PSO-GA算法比GA算法收斂速度更快，能得到更優(yōu)解。經(jīng)大量實(shí)驗(yàn)驗(yàn)證，通過(guò)該模型算法獲得的最優(yōu)調(diào)度方案優(yōu)于由遺傳算法獲得的調(diào)度方案，所用時(shí)間和費(fèi)用較少，平均減少大約10%，效果較好。

圖3 進(jìn)化20代的種群平均適應(yīng)度值比較

4 結(jié)語(yǔ)

高效的輸電線路應(yīng)急搶修物資調(diào)度模型及算法能夠指導(dǎo)搶修人員和物資到達(dá)故障點(diǎn)，縮短搶修時(shí)間，減輕勞動(dòng)強(qiáng)度，提高工作效率，節(jié)約開(kāi)支。有運(yùn)輸能力約束的時(shí)間和費(fèi)用最優(yōu)的應(yīng)急資源調(diào)度模型更符合輸電線路應(yīng)急搶修實(shí)際，改進(jìn)的混合粒子群遺傳算法更優(yōu)于經(jīng)典遺傳算法，收斂速度快，減少了調(diào)度時(shí)間和費(fèi)用。新的智能算法不斷涌現(xiàn)，未來(lái)可進(jìn)一步探索應(yīng)用于應(yīng)急搶修物資調(diào)度的新算法的結(jié)合與優(yōu)化。