混沌粒子群算法在應(yīng)急資源調(diào)度中的應(yīng)用

張永領(lǐng)，馬 嬌

(河南理工大學(xué) 應(yīng)急管理學(xué)院,河南 焦作 454000)

混沌粒子群算法在應(yīng)急資源調(diào)度中的應(yīng)用

張永領(lǐng)，馬 嬌

(河南理工大學(xué) 應(yīng)急管理學(xué)院,河南 焦作 454000)

為更科學(xué)合理的解決應(yīng)急資源的調(diào)度問題，根據(jù)連續(xù)性消耗應(yīng)急問題的特點，建立了以出救活動總成本最小為目標(biāo)的應(yīng)急物資優(yōu)化調(diào)度模型；針對模型的非線性特點，提出了基于混沌粒子群算法的應(yīng)急資源調(diào)度模型并給出了求解方法；最后用算例驗證了模型的合理性及算法的有效性。計算結(jié)果表明將混沌粒子群算法用于求解多約束條件的應(yīng)急物資調(diào)度問題，可以在一定程度上克服基本粒子群算法容易陷入局部最優(yōu)解的不足，算法收斂速度更快且精度更高，是解決應(yīng)急資源調(diào)度路徑問題的一種有效方法。

調(diào)度；應(yīng)急物資；連續(xù)型消耗；混沌粒子群；路徑

近年來，各種自然災(zāi)害和突發(fā)事件在全球范圍內(nèi)頻繁發(fā)生，嚴(yán)重威脅著人們的生命和財產(chǎn)安全。災(zāi)害尤其是巨災(zāi)一旦發(fā)生對應(yīng)急資源的需求量就會急速增加，這就需要將應(yīng)急資源快速合理地運送到各個受災(zāi)點，以降低災(zāi)害造成的損失。應(yīng)急物資是減少人員傷亡、降低財產(chǎn)損失的基本保障，因此如何對應(yīng)急物資進(jìn)行科學(xué)合理的調(diào)度具有重要現(xiàn)實意義。

由于科學(xué)的應(yīng)急物資調(diào)度是災(zāi)害應(yīng)急救援的保障，因此應(yīng)急物資調(diào)度受到國內(nèi)外學(xué)者的普遍關(guān)注，如Kemball-Cook等于1984年首先提出了需要對應(yīng)急物資的調(diào)度進(jìn)行針對性的研究[1]；Linet等建立了一個以最小應(yīng)急時間為目標(biāo)的數(shù)學(xué)模型，用于處理應(yīng)急物資的調(diào)度問題[2]；Barbarosoglu等研究了在需求時間最小的情況下，成本最小的應(yīng)急資源調(diào)度模型[3]；黃洪濤提出將應(yīng)急物資分為短暫性消耗物資和長期性消耗物資兩種類型進(jìn)行了調(diào)度研究[4]；劉春林等建立了連續(xù)性消耗應(yīng)急物資調(diào)度模型，并證明了模型的合理性[5]；姜昌華研究了遺傳算法在物流系統(tǒng)優(yōu)化中的應(yīng)用[6]。

目前對于應(yīng)急資源調(diào)度問題的建模大多局限于對單一目標(biāo)進(jìn)行研究，對于模型的求解方法也存在各自缺陷。胡飛虎等采用遺傳算法解決應(yīng)急物資的調(diào)度問題，但該算法通用性差無法被廣泛應(yīng)用[7]；田軍等研究了應(yīng)急物資配送的動態(tài)調(diào)度方法，但該算法的計算復(fù)雜度較高，極大地限制了其實際應(yīng)用[8]；左春榮等研究了基于粒子群算法的多應(yīng)急點資源調(diào)度問題，但該算法存在容易陷入局部最優(yōu)解的缺陷[9]。為此，本文將以連續(xù)性消耗應(yīng)急系統(tǒng)為背景，建立多出救點、多應(yīng)急資源需求約束、時間約束等多約束條件下的應(yīng)急資源調(diào)度模型，采用混沌粒子群算法對模型進(jìn)行求解，克服了以往進(jìn)行應(yīng)急資源調(diào)度研究中采用基本粒子群算法容易陷入局部最優(yōu)解的不足，可以在很大程度上降低計算程序中的迭代步數(shù)，提高求解效率，驗證了模型的合理性及算法的優(yōu)越性。

1 應(yīng)急資源調(diào)度

1.1 應(yīng)急資源的內(nèi)涵

應(yīng)急資源是指在突發(fā)事件應(yīng)急處置所需要的各類物資的統(tǒng)稱。廣義的應(yīng)急資源包括防災(zāi)、應(yīng)對、恢復(fù)等環(huán)節(jié)所需要的各類物資。狹義的應(yīng)急資源僅指應(yīng)急救援過程所需要的各種物資保障。應(yīng)急資源不同于一般物資它具有以下幾個特征。

(1)時效性。時效性是指應(yīng)急資源應(yīng)在突發(fā)事件發(fā)生后及時送達(dá)指定地點。因為災(zāi)害發(fā)生后的72h是救援的“黃金時間”，在“黃金時間”段內(nèi)，應(yīng)急資源應(yīng)到達(dá)受災(zāi)地區(qū)，否則可能就會失去了其應(yīng)急的意義。

(2)不確定性。突發(fā)事件類型、發(fā)生的事件、地點以及級別具有不確定性，對應(yīng)急物資需求的種類和數(shù)量也具有不確定性。這種不確定性具體表現(xiàn)在兩個方面，一是需求時間、地點的不確定性，應(yīng)急部門無法預(yù)測到需求的時間、地點，做到提前的調(diào)度；二是需求的品種和數(shù)量的不確定性，突發(fā)事件的類型、級別、發(fā)生地點的不同決定了需求的種類和數(shù)量也存在很大的差異。

(3)弱經(jīng)濟(jì)性。應(yīng)急資源最重要的特點就是要起到“應(yīng)急”的作用。在實際的應(yīng)急處置工作中，要求在既定的時間內(nèi)滿足災(zāi)民對物資的需求。所以在應(yīng)急物資的籌集、調(diào)度和配置上都是以最短時間為核心的。在應(yīng)急資源調(diào)度的研究上雖然也有考慮到費用最小問題，但都是在時間約束的條件下進(jìn)行的[10]。

1.2 應(yīng)急資源調(diào)度的特點

當(dāng)突發(fā)事件發(fā)生后，在應(yīng)急物資的種類繁多以及多出救點和多受災(zāi)點的情景下，政府應(yīng)急管理部門需要制定出科學(xué)合理的調(diào)度方案，確保資源的及時到達(dá)，使應(yīng)急救援得以有序進(jìn)行。處置突發(fā)公共事件中的應(yīng)急資源調(diào)度與一般事件中的資源調(diào)度相比具有以下幾方面的特點。

(1)事件約束性。突發(fā)事件發(fā)生以后，為了保障應(yīng)急救援的順利進(jìn)行，應(yīng)急資源調(diào)度需要在有效時間內(nèi)或規(guī)定事件內(nèi)完成，以最大限度的減少人員傷亡和財產(chǎn)損失。因此調(diào)度時間就成了應(yīng)急資源調(diào)度考慮的首要條件，即應(yīng)急物資調(diào)度必須考慮調(diào)度的時效性，及時準(zhǔn)確地將所需應(yīng)急資源運送到指定地點。

(2)動態(tài)性。突發(fā)事件大小規(guī)模不一，種類各異，對應(yīng)急資源的需求具有不確定性；而且衍生和次生的災(zāi)害有時也難以把握；再加之事件處置的每個階段所需要的應(yīng)急物資也各不相同。這就需要根據(jù)救援現(xiàn)場的實際情況及時不斷的調(diào)整調(diào)度方案，以滿足突發(fā)事件處置的動態(tài)需求。

(3)整合和協(xié)同性。當(dāng)災(zāi)害尤其是巨災(zāi)發(fā)生后，對某些物資的需求急劇增加，政府部門所儲備的應(yīng)急物資難以滿足應(yīng)急需求，這就需要在應(yīng)急物資調(diào)度時綜合考慮政府應(yīng)急物資儲備、非政府機(jī)構(gòu)如慈善機(jī)構(gòu)以及其他社會資源，整合各類物資進(jìn)行綜合配置和科學(xué)調(diào)度。

一般意義上的物資調(diào)度問題是指把物資從存儲地運送到需求地，它是以成本最小為目標(biāo)函數(shù)。而在應(yīng)急管理中，救援物資的調(diào)度首先考慮的是物資的時效性問題，即在最短的時間內(nèi)把物資運輸?shù)街付ǖ臑?zāi)區(qū)，保證其能及時的投入到救援活動中。在應(yīng)急物資調(diào)度過程中也考慮成本問題，但是是在保證時間最小化的前提下盡量使成本最小化。

2 應(yīng)急物資調(diào)度模型構(gòu)建

2.1 問題描述及假設(shè)

當(dāng)災(zāi)害發(fā)生時，一方面在資源儲備有限的情況下需要從多個供應(yīng)點調(diào)集資源；另一方面要保證在任何時刻都不能出現(xiàn)因物資供應(yīng)不足引起的應(yīng)急活動的停止[11]。因此應(yīng)急資源調(diào)度優(yōu)化需解決3個關(guān)鍵問題：①應(yīng)急物資的優(yōu)化配置問題。根據(jù)有限的物資儲備，在多個物資供應(yīng)點間進(jìn)行物資科學(xué)合理調(diào)配，使得各應(yīng)急點物資需求滿足量最小化。②時間約束問題。在滿足各應(yīng)急點應(yīng)急物資需求的前提下，對突發(fā)應(yīng)急事件的物資救援時間最早。③應(yīng)急成本問題。災(zāi)害環(huán)境下調(diào)度路線的選取除了考慮時間因素外，還應(yīng)考慮到出救活動的總成本問題。

災(zāi)后應(yīng)急資源優(yōu)化調(diào)度屬于大空間尺度下的資源宏觀調(diào)度優(yōu)化，與微觀物流具有較大不同，故作如下假設(shè)[12-13]：

(1) 設(shè)從突發(fā)事件發(fā)生時刻到應(yīng)急活動開始時刻，沒有因施救不及時而造成損失；

(2) 如需從出救點調(diào)配應(yīng)急物資，則調(diào)配數(shù)量須大于起始運輸量下限；

(3) 應(yīng)急活動開始后，各出救點間不存在資源的相互調(diào)度。

2.2 應(yīng)急物資優(yōu)化調(diào)度模型建立

本文以連續(xù)消耗型應(yīng)急活動為背景[14]，從應(yīng)急系統(tǒng)固有成本和因施救不及時造成損失的角度考慮,建立了以出救活動總成本最小為目標(biāo)的多出救點、多應(yīng)急資源約束和時間約束的應(yīng)急物資調(diào)度模型。

設(shè)應(yīng)急系統(tǒng)中有n個出救點，m種應(yīng)急物資，應(yīng)急物資調(diào)度數(shù)學(xué)模型如下：

(1)

對于因應(yīng)急物資缺失而產(chǎn)生的損失費用本文從以下三種情況進(jìn)行考慮[15]:

(1) 第i時刻各個應(yīng)急點各類物資均充足時，即缺失量為0，則因應(yīng)急物資缺失而產(chǎn)生的損失費用Eij=0。

(2) 當(dāng)?shù)趇時刻第j類資源已經(jīng)缺失，即Ij(ti)<0，此時:

(2)

在周期[ti,ti+1]內(nèi)，Eij為：

(3)

(4)

(5)

在周期[ti,ti+1]內(nèi)，Eij為：

(6)

3 混沌粒子群算法求解

混沌粒子群算法源于對鳥群捕食行為的研究，Eberhart和Kennedy于1995年提出了一種基于隨機(jī)群體的新型智能優(yōu)化方法的粒子群算法(ParticleSwarmOptimization,PSO)用于指導(dǎo)優(yōu)化搜索[16-17]。

3.1 基本粒子群算法

在PSO算法中，每個基本粒子(Particle)代表一個可能的解且有一個由被優(yōu)化了的函數(shù)決定的適應(yīng)值(Fittness)，所有的粒子組成一個群體(Swarm)。粒子在解空間內(nèi)根據(jù)自身的飛行經(jīng)驗和群體經(jīng)驗共同來決定下一步的飛行速度和方向，以此來尋找最優(yōu)解。

假設(shè)在d維搜索空間內(nèi)進(jìn)行求解，群體由n個基本粒子組成，

(7)

(8)

(9)

式(8)、式(9)分別描述了該粒子在每一維空間上的運動情況。在每一次進(jìn)化中，每個粒子通過追蹤兩個局部最優(yōu)解來更新自己，一個是粒子本身所找到的最優(yōu)解(pBest)，Pi={Pi1,Pi2,…,Pid}，另一個是目前整個群體所找到的最優(yōu)解(gBest)，粒子根據(jù)如下公式來對自己的位置和速度進(jìn)行更新：

(10)

式中：w為慣性權(quán)重，c1和c2為學(xué)習(xí)因子，r1和r2為(0,1)之間的隨機(jī)數(shù)。

基本粒子群算法結(jié)構(gòu)簡單、易于實現(xiàn)，但也存在以下不足：① 算法的初始化和進(jìn)化過程均具有隨機(jī)性特點，對個體質(zhì)量難以保證，群解中一部分遠(yuǎn)離全局最優(yōu)解的局部最優(yōu)解會影響進(jìn)化過程的收斂；② 當(dāng)粒子的自身信息及個體極值信息占絕對優(yōu)勢時，該算法容易陷入局部最優(yōu)解。

3.2 混沌粒子群算法

針對基本粒子群算法的不足，本文采用一種基于混沌化思想的粒子群優(yōu)化算法，其基本思想如下：

(1) 利用混沌運動的遍歷性及對初值極為敏感的特點，從一系列隨機(jī)產(chǎn)生的初始解中擇優(yōu)選出初始群體，提高種群的多樣性和遍歷性。

(2) 每個粒子的慣性權(quán)重根據(jù)其適應(yīng)值來進(jìn)行自適應(yīng)調(diào)整，從而提高算法的“全局粗略探測”和“局部精細(xì)挖掘”能力。

(3) 從當(dāng)前種群中選取一部分適應(yīng)值較大的粒子進(jìn)行混沌優(yōu)化，以此增強(qiáng)算法跳出局部最優(yōu)解的能力，進(jìn)而提高其全局搜索能力。

混沌一般是由確定性方程通過映射得到的具有隨機(jī)性的運動狀態(tài)，Logistic映射便是一個典型的混沌系統(tǒng)，其搜索算法步驟如下：

(11)

式中：xmax,j和xmin,j分別為j維變量的搜索上下界。

(2) 計算混沌變量，

(12)

(13)

3.3 算法步驟

混沌粒子群算法的程序流程圖如圖1所示。

混沌粒子群算法步驟如下：

(1) 初始化種群中每個基本粒子的位置和速度；

(2) 計算每個粒子的適應(yīng)度，對每個粒子的個體極值pBest及種群極值gBest賦初值；

(3) 更新粒子的個體極值和種群極值；

(4) 對種群中的最優(yōu)粒子進(jìn)行局部混沌搜索；

(5) 更新下一代種群中粒子的個體極值和種群極值；

(6) 判斷是否滿足條件，若滿足則獲得最優(yōu)解gBest；否則，令k=k+1，流程轉(zhuǎn)向步驟(2)。

4 算例分析

為考察上述模型的合理性及算法的可靠性，用Matlab7.0分別編寫了基于混沌粒子群算法和粒子群算法的應(yīng)急物資優(yōu)化調(diào)度問題求解程序，并在同一計算機(jī)上進(jìn)行運行。

設(shè)某地區(qū)發(fā)生自然災(zāi)害，在應(yīng)急救援的過程中急需5種應(yīng)急物資可從10個出救點進(jìn)行調(diào)配。應(yīng)急物資需求量為X=(70,80,50,60,80)，物資消耗速率為V=(3,5,4,3,7)，物資缺失單位時間內(nèi)損失費用為D=(7,2,9,5,12)，應(yīng)急活動終止時間T為1 000，起始運輸量下線x0=2，各出救點的物資可供應(yīng)量如表1所示，物資到達(dá)應(yīng)急地點的所需時間和單位成本如表2所示。制定應(yīng)急資源調(diào)度方案在滿足事故應(yīng)急救援基本需求的情況下系統(tǒng)總出救成本最小。

圖1 混沌粒子群算法流程圖

A1A2A3A4A5A6A7A8A9A10Xi151395108137116Xi248717510415139Xi311851371036812Xi4961016819102076Xi512915104221291510

表2 物資到達(dá)應(yīng)急地點的所需時間和單位成本

粒子群算法參數(shù)：粒子數(shù)n=50；學(xué)習(xí)因子c1=c2=2；慣性權(quán)重w=0.8；最大迭代數(shù)200。

混沌粒子群算法參數(shù)：粒子數(shù)n=50；學(xué)習(xí)因子c1=c2=2；慣性權(quán)重w=0.8；混沌最大迭代步數(shù)為10，粒子群最大迭代步數(shù)取200。

由基本粒子群算法得出的最佳調(diào)度方案為：

相應(yīng)的最小出救成本為Z=781 263。由混沌粒子群算法得出的最佳調(diào)度方案為：

相應(yīng)的最小出救成本為Z=729125。

基本粒子群算法和混沌粒子群算法的目標(biāo)函數(shù)收斂曲線如圖2所示，縱軸表示出救費用，以10萬元為單位，橫軸表示迭代次數(shù)。從圖2可知，對于應(yīng)急資源優(yōu)化調(diào)度問題，標(biāo)準(zhǔn)粒子群算法在第130代左右收斂，混沌粒子群算法在第45代左右收斂且結(jié)果更優(yōu)，結(jié)果表明混沌粒子群算法求解效率及精度均明顯優(yōu)于基本粒子群算法。

圖2 不同算法下目標(biāo)函數(shù)的收斂曲線

5 結(jié)語

應(yīng)急物資的及時供應(yīng)是災(zāi)害救援的物質(zhì)基礎(chǔ)。對于突發(fā)事件的應(yīng)對處置實際上就是一個連貫的合理的應(yīng)急物資協(xié)調(diào)與調(diào)度的過程。本文以連續(xù)性消耗應(yīng)急系統(tǒng)為背景，在充分考慮出救固有成本及因施救不及時所造成損失費用的基礎(chǔ)上，建立了以出救活動總成本最小為目標(biāo)的多出救點、多應(yīng)急資源約束和時間約束的應(yīng)急物資調(diào)度模型，針對模型的非線性特點及基本粒子群算法容易陷入局部最優(yōu)解的不足，設(shè)計了基于混沌粒子群算法的調(diào)度模型，并給出了求解方法和步驟，最后用算例驗證了模型的合理性及求解算法的優(yōu)越性。

本文所設(shè)計的調(diào)度模型便于使用計算機(jī)求取更優(yōu)解，所采用的混沌粒子群算法與單純的粒子群算法相比求解效率更高且結(jié)果更優(yōu)，是解決應(yīng)急資源調(diào)度路徑問題的一種有效方法。

[1] Kemball-Cook D, Stephenson R. Lesson in logistics from Somalia[J]. Disaster, 1984,8(1):57-66.

[2] Linet O, Ediz E, Beste K. Emergency logistics planning in natural disasters[J]. Annals of Operations Research, 2004,129(7):217-245.

[3] Barbarosoglu G, Arda Y. A two-stage stochastic programming framework for transportation planning in disaster response[J]. Journal of the Operational Research Society,2004,55(1):43-53.

[4] 黃洪濤.應(yīng)急物流系統(tǒng)研究[D].大連:大連海事大學(xué),2006.

[5] 劉春林,何建敏,施建軍.一類應(yīng)急物資調(diào)度的優(yōu)化模型研究[J].中國管理科學(xué)，2001,9(3):29-36.

[6] 姜昌華.遺傳算法在物流系統(tǒng)優(yōu)化中的應(yīng)用研[D].上海:華東師范大學(xué),2007.

[7] 胡飛虎,田朝輝,李威,等.基于遺傳算法的應(yīng)急物資分層調(diào)度研究[J].計算機(jī)工程,2015,41(10):53-58.

[8] 田軍,馬文正,汪應(yīng)絡(luò),等.應(yīng)急物資配送動態(tài)調(diào)度的粒子群算法[J].系統(tǒng)工程理論與實踐,2011,31(5):898-906.

[9] 左春榮,周玉琴.基于粒子群算法的多應(yīng)急點資源調(diào)度研究[J].微電子學(xué)與計算機(jī),2012,29(7):135-137.

[10]唐偉勤,張敏,張隱,大規(guī)模突發(fā)事件應(yīng)急物資調(diào)度的過程模型[J].中國安全科學(xué)學(xué)報,2009,19(1):33-37.

[11]唐偉勤.大規(guī)模突發(fā)事件應(yīng)急物資調(diào)度基本模型研究[D].武漢:華中科技大學(xué),2009.

[12]文仁強(qiáng),鐘少波,袁宏永,等.應(yīng)急資源多目標(biāo)優(yōu)化調(diào)度模型與多蟻群優(yōu)化算法研究[J].計算機(jī)研究與發(fā)展,2013,50(7): 1464-1472.

[13]龐海云,劉南,吳橋.應(yīng)急物資運輸與分配決策模型及改進(jìn)粒子群優(yōu)化算法[J].控制與決策,2012,27(6):871-874.

[14]Marina Yusoff, Junaidah Ariffin, Azlinah Mohamed. A Two-tier Solution for Disaster Relief Management[C]// 2013 IEEE Symposium on Industrial Electromics and Applications, Kuching, Malaysia, 2013,9.

[15]潘郁,余佳,達(dá)慶利.基于粒子群算法的連續(xù)性消耗應(yīng)急資源調(diào)度[J].系統(tǒng)工程學(xué)報,2007,22(5):556-560.

[16]龔純,王正林.精通MATLAB最優(yōu)化計算(第二版)[M].北京：電子工業(yè)出版社，2012.

[17]周孝法,陳陳,楊帆,等.基于自適應(yīng)混沌粒子群優(yōu)化算法的多饋入直流輸電系統(tǒng)優(yōu)化協(xié)調(diào)直流調(diào)制[J].電工技術(shù)學(xué)報,2009,24(4):193-200.

Emergency Resources Scheduling Based onChaotic Particle Swarm Optimization

ZHANG Yongling and MA Jiao

(HenanPolytechnicUniversity,EmergencyManagementSchool,Jiaozuo454000,Henan)

Amorescientificandreasonablesolutiontotheemergencyresourceschedulingproblem,accordingtothecharacteristicofcontinuousconsumptionemergencyproblem,aoptimizationschedulingmodelisproposedaimsatminimizingthetotalcost;Inviewofthenonlinearcharacteristics,achaoticparticleswarmalgorithmanditsstepsisproposedtoimprovetheabilitytofindthebestswarmandavoidbeingtrappedinlocalminima;Finally,thepracticalexampleispresentedtoverifythevalidityofthemodelandalgorithm,anditisshownthatthealgorithmisbetterthantraditionalparticleswarmoptimizationtodealwithemergencysuppliesschedulingproblemwithmulticonstraintconditions.Itisaneffectivewaytosolvetheproblemofemergencyresourceschedulingpath.

scheduling;emergencysupplies;continuousconsumption;chaoticparticleswarm;thepath

10.3969/j.issn.1000-811X.2017.02.032.]

2016-08-13

2016-10-08

2012年河南省高?？萍紕?chuàng)新人才項目“基于情景分析的應(yīng)急物資保障能力評價研究”

張永領(lǐng)(1975-),男,山東成武人，博士，副教授,主要從事應(yīng)急管理研究.E-mail:zhyongling@126.com

X43；N945.25

A

1000-811X(2017)02-0185-05

10.3969/j.issn.1000-811X.2017.02.032

張永領(lǐng)，馬嬌. 混沌粒子群算法在應(yīng)急資源調(diào)度中的應(yīng)用[J]. 災(zāi)害學(xué)，2017，32(2)：185-189. [ZHANG Yongling and MA Jiao.Emergency Resources Scheduling Based on Chaotic Particle Swarm Optimization[J]. Journal of Catastrophology，2017，32(2)：185-189.