基于離散粒子群算法的應(yīng)急救災(zāi)物資配送問(wèn)題

宮 華,張 彪

(沈陽(yáng)理工大學(xué) 理學(xué)院，遼寧 沈陽(yáng) 110159)

基于離散粒子群算法的應(yīng)急救災(zāi)物資配送問(wèn)題

宮 華,張 彪

(沈陽(yáng)理工大學(xué) 理學(xué)院，遼寧 沈陽(yáng) 110159)

研究自然災(zāi)害下應(yīng)急物流中的救援物資配送調(diào)度問(wèn)題，在多種運(yùn)輸工具銜接以及救援物資分配考慮的基礎(chǔ)上，建立物資運(yùn)輸與物資分配的兩階段優(yōu)化模型。目標(biāo)是最小化運(yùn)輸成本與未滿足的需求量。運(yùn)用離散粒子群算法進(jìn)行模型的求解與仿真，結(jié)果證明了算法的有效性與穩(wěn)定性，能夠?yàn)閼?yīng)急物流物資運(yùn)輸及分配提供有效方案。

應(yīng)急物流；物資運(yùn)輸；物資分配；離散粒子群算法

自然災(zāi)害主要包括氣象災(zāi)害、地震災(zāi)害、水旱災(zāi)害、地質(zhì)災(zāi)害、森林草原火災(zāi)等，大規(guī)模自然災(zāi)害的頻發(fā)使得應(yīng)急物流成為近年來(lái)應(yīng)急管理研究中的一個(gè)新課題。災(zāi)害發(fā)生后重點(diǎn)考慮如何迅速及時(shí)地將大量應(yīng)急物資運(yùn)送到災(zāi)區(qū)配送中心，再由配送中心運(yùn)往受災(zāi)地。自然災(zāi)害情況下的應(yīng)急物資配送不同于常規(guī)的物流活動(dòng)，具有信息不確定，物資需求量大等特點(diǎn)，著重滿足應(yīng)急物流中物資運(yùn)輸和調(diào)度的時(shí)效性、突發(fā)性和弱經(jīng)濟(jì)性要求。

近年來(lái)對(duì)于應(yīng)急物流中的物資配送問(wèn)題，國(guó)內(nèi)外學(xué)者進(jìn)行了大量的研究。Sheu[1]以自然災(zāi)害下的快速響應(yīng)為背景，基于受災(zāi)點(diǎn)聚類(lèi)研究應(yīng)急物資的調(diào)配。Chang等[2]以最小化物資未滿足量、延誤時(shí)間及運(yùn)輸費(fèi)用為目標(biāo)，根據(jù)受災(zāi)點(diǎn)對(duì)物資需求的變化研究應(yīng)急物資調(diào)度。Najafi等[3]針對(duì)震后響應(yīng)階段的物資調(diào)配建立多目標(biāo)魯棒優(yōu)化模型，考慮多種運(yùn)輸方式、多種物資多階段的隨機(jī)模型。Ali等人[4]研究了在不確定環(huán)境下應(yīng)急物資的調(diào)配，將物資的需求和供給以及運(yùn)送的費(fèi)用，運(yùn)送中心損害均考慮為不確定因素。Zheng等[5]使用一種協(xié)同模糊優(yōu)化方法研究應(yīng)急物流中的運(yùn)輸計(jì)劃問(wèn)題，綜合不確定性考慮三種運(yùn)輸方式銜接。

對(duì)應(yīng)急物流的研究大多集中在救援的某一個(gè)環(huán)節(jié)上，而較少考慮震后應(yīng)急物流這一全過(guò)程的物資運(yùn)輸及物資分配。本文以自然災(zāi)害為背景研究救災(zāi)物資配送問(wèn)題，分多種方式運(yùn)輸調(diào)度、物資分配兩階段進(jìn)行救援物資配送的決策。第一階段綜合考慮三種運(yùn)輸方式：直升機(jī)、火車(chē)、汽車(chē)，及災(zāi)后的實(shí)際路況，為各受災(zāi)點(diǎn)決策以何種運(yùn)輸方式向該地運(yùn)輸救援物資；第二階段綜合考慮各受災(zāi)點(diǎn)的受災(zāi)人數(shù)、物資需求量，為各受災(zāi)點(diǎn)決策救援物資分配。

1 模型的建立

1.1 模型描述

災(zāi)害發(fā)生后，決策者應(yīng)在最快的時(shí)間內(nèi)根據(jù)受災(zāi)情況制定救援物資配送方案。第一階段為物資運(yùn)輸調(diào)度階段，運(yùn)輸方式包括：直升機(jī)、火車(chē)、汽車(chē)，對(duì)于三種運(yùn)輸方式的決策以最小化運(yùn)輸成本及運(yùn)輸效率為目標(biāo)。第二階段為物資分配階段，在救援物資運(yùn)輸調(diào)度確定的基礎(chǔ)上，決策為各受災(zāi)點(diǎn)救援物資的分配。目標(biāo)函數(shù)為最小化受災(zāi)點(diǎn)未滿足的需求量，即受災(zāi)點(diǎn)人均缺乏的物資數(shù)和受災(zāi)點(diǎn)轉(zhuǎn)運(yùn)傷員所缺乏的救援工具數(shù)(當(dāng)直升機(jī)、火車(chē)、汽車(chē)裝載著物資到達(dá)受災(zāi)點(diǎn)之后，可繼續(xù)作為轉(zhuǎn)運(yùn)傷員的工具)。根據(jù)決策者得到的各受災(zāi)點(diǎn)數(shù)據(jù)，考慮上述兩個(gè)指標(biāo)，并為各受災(zāi)點(diǎn)賦予不同的權(quán)值，進(jìn)而決策出能夠使現(xiàn)有救援物資發(fā)揮最大作用的救援調(diào)度方案。

1.2 符號(hào)說(shuō)明

W：救援物資集散中心物資總量；

N：受災(zāi)點(diǎn)個(gè)數(shù)；

p=1、2、3，1代表直升機(jī)，2代表火車(chē)，3代表汽車(chē)；

ei：第i個(gè)階段的權(quán)重，i=1,2；

L：三種運(yùn)輸方式均可達(dá)到的受災(zāi)點(diǎn)個(gè)數(shù)，滿足L≤N；

βlp：第l個(gè)受災(zāi)點(diǎn)使用第p種運(yùn)輸方式的風(fēng)險(xiǎn)值；

dlp：使用第p種運(yùn)輸方式從中心到第l個(gè)受災(zāi)點(diǎn)需要行駛的距離；

tlp(clp)：使用第p種運(yùn)輸方式從中心到第l個(gè)受災(zāi)點(diǎn)的時(shí)間(單位行駛距離成本)；

gl：第l個(gè)受災(zāi)點(diǎn)等待救援的單位時(shí)間造成的經(jīng)濟(jì)成本；

ωlp(Wlp)：由第p種方式運(yùn)輸救援物資的第l個(gè)受災(zāi)點(diǎn)的權(quán)值(所需的救援物資數(shù))；

Zp：救援物資集散中心當(dāng)前可調(diào)度的第p種救援工具的數(shù)量；

Z1p：第p種救援工具的運(yùn)力；

alp(blp)：第l個(gè)受災(zāi)點(diǎn)缺少第p種方式救援引起的轉(zhuǎn)運(yùn)傷員(物資)單位數(shù)量損失；

ulp：派往第l個(gè)受災(zāi)點(diǎn)使用第p種方式的運(yùn)輸工具數(shù)量；

Mlp：使用第p種方式的第l個(gè)受災(zāi)點(diǎn)的人均物資缺乏數(shù)量；

Olp：使用第p種方式的第l個(gè)受災(zāi)點(diǎn)轉(zhuǎn)運(yùn)傷員所缺乏的救援工具數(shù)量。

1.3 模型建立

mine1f1+e2f2

(1)

式中：

(2)

(3)

約束條件：

(4)

(5)

(6)

(7)

ulpZ1p≤Wlp;?l∈Zp,p=1,2,3

(8)

Mlp=max{0,Wlp-ulpZ1p};?l∈Zp,p=1,2,3

(9)

Qlp=max{0,Wlp/Z1p-ulp};?l∈Zp,p=1,2,3

(10)

模型說(shuō)明：式(1) 為總目標(biāo)函數(shù)。式(2) 為第一階段目標(biāo)函數(shù)，最小化總運(yùn)輸時(shí)間成本(即受災(zāi)點(diǎn)等待第一批物資到達(dá)的時(shí)間)以及運(yùn)輸費(fèi)用成本。式(3) 為第二階段目標(biāo)函數(shù)，最小化所有受災(zāi)點(diǎn)的未滿足需求量，包括人均物資缺乏量引起的費(fèi)用損失以及轉(zhuǎn)運(yùn)傷員的運(yùn)輸工具缺乏量引起的損失。式(4) 為所有運(yùn)輸數(shù)量的約束；式(5)表示三種方式均可采用的受災(zāi)點(diǎn)只采用其中一種方式。式(6)表示每種運(yùn)輸工具數(shù)量的可調(diào)度約束。式(7)表示救援物資集散中心在當(dāng)前物資可調(diào)度量基礎(chǔ)上進(jìn)行分配，允許有剩余。式(8)表示各受災(zāi)點(diǎn)所需救援物資滿足條件。式(9)、(10)表示人均物資缺乏數(shù)量和轉(zhuǎn)運(yùn)傷員所缺乏的救援工具數(shù)量。

2 算法設(shè)計(jì)

粒子群算法[6-7]是近些年應(yīng)用比較廣泛的一種智能算法，計(jì)算簡(jiǎn)單，收斂速度快。離散粒子群算法，其速度更新公式與原始PSO算法一樣：

(11)

式中ω為慣性權(quán)重，表示粒子更新過(guò)程對(duì)上一代的依賴(lài)程度，采用如下線性變化公式進(jìn)行更新效果更佳：

ω=ωmax-(k×(ωmax-ωmin))/Dmax

(12)

式中：ωmax為最大權(quán)重值0.9；ωmin為最小權(quán)重值0.1；k為當(dāng)前迭代次數(shù)；Dmax為最大迭代次數(shù)。針對(duì)應(yīng)急物資配送模型，本文提出采用兩種不同編碼方式的離散粒子群算法對(duì)運(yùn)輸調(diào)度及物資分配兩個(gè)階段進(jìn)行求解，為決策者提供可行性較高的救援安排方案。

2.1 第一階段

第一階段運(yùn)輸調(diào)度中，采用二進(jìn)制編碼的離散粒子群算法簡(jiǎn)稱(chēng)BPSO。將粒子設(shè)計(jì)為一個(gè)XL×p的0-1矩陣，xlp=1表示第l個(gè)受災(zāi)點(diǎn)使用第p種運(yùn)輸方式，xlp=0表示不采用。按照初始解的規(guī)則產(chǎn)生一個(gè)粒子種群，依照速度和位置更新在解空間搜索尋優(yōu)，直至算法結(jié)束找到適應(yīng)度最高的粒子。初始種群的產(chǎn)生要滿足隨機(jī)性及解的可行性，初始解產(chǎn)生規(guī)則如下：

Step 1 將1,0,0三個(gè)數(shù)字全排列，A，B，C為三個(gè)矩陣，其中A=[1,0,0]；B=perms(A)；C共有6行，每一行是1,0,0的一個(gè)全排列；

Step 2 初始解設(shè)為X=zeros(L,p);L為地點(diǎn)數(shù)目，p為運(yùn)輸方式的種類(lèi)；

Step 3 產(chǎn)生1～6的隨機(jī)數(shù)，存儲(chǔ)在c向量：a=rand(1,6)；b=a×5+1；c=floor(b)；

Step 4 以c中第一個(gè)數(shù)字作為角標(biāo)，取出B中對(duì)應(yīng)行的數(shù)據(jù)作為X中的第一行數(shù)據(jù)，以此類(lèi)推，便可生成初始解X。

為表示速度值是二進(jìn)制位取1的概率，速度值采用sigmoid函數(shù)被映射到區(qū)間[0,l]：

(13)

s(vid)表示位置xlp取1的概率，通過(guò)下式改變粒子的位值

(14)

規(guī)定速度的范圍[-vmax,vmax]，根據(jù)經(jīng)驗(yàn)值，文中取vmax=4。

本文采用改進(jìn)的BPSO算法[8]：將sigmoid函數(shù)表達(dá)式作如下修改：

(15)

對(duì)粒子的位值改變函數(shù)作修改：

(16)

(17)

此時(shí)算法收斂速度較快，局部搜索能力強(qiáng),但全局搜索能力變?nèi)?。為使算法后期具有較強(qiáng)的局部搜索能力，仍需要對(duì)上述改進(jìn)的BPSO算法繼續(xù)改進(jìn)。

Ifk<γ×Dmax選用式(13)、式(14)進(jìn)行粒子位置更新；

Else 選用式(15)、式( 16)、式(17)進(jìn)行粒子位置更新。

其中k為當(dāng)前迭代次數(shù)，γ為系數(shù)，取值范圍為[0,1]。

2.2 第二階段

物資分配中，采用自然數(shù)編碼的離散粒子群算法，其核心在于對(duì)粒子位置進(jìn)行取整計(jì)算。將粒子設(shè)計(jì)為一個(gè)Ip維向量，Ip為使用第p種運(yùn)輸方式的地點(diǎn)個(gè)數(shù)，向量中元素均為自然數(shù)，其和為救援物資集散中心當(dāng)前可調(diào)度的第p種運(yùn)輸工具的數(shù)量Zp。按照初始解的規(guī)則產(chǎn)生一個(gè)粒子種群，依照速度和位置更新方式在解空間搜索尋優(yōu)，直至算法結(jié)束找到適應(yīng)度最高的粒子。

初始解產(chǎn)生：

Step 1 隨機(jī)產(chǎn)生Ip個(gè)(0,1)內(nèi)的隨機(jī)數(shù)，存入a向量：a=rand(1,Ip)；

Step 2 對(duì)a中所有元素求和記為b，計(jì)算a中每個(gè)元素與b的比值，結(jié)果存入c向量：b=sum(a)；c(i)=a(i)/b；

Step 3 救援物資集散中心當(dāng)前可調(diào)度的第p種運(yùn)輸工具數(shù)量為Zp，將c中每個(gè)元素與Zp相乘，結(jié)果存入向量d:d(i)=c(i)×Zp;

Step 4 對(duì)d中各元素取整，結(jié)果存入向量e：e(i)=round(d(i))；

Step 5 判斷e中元素之和是否等于第p種運(yùn)輸工具數(shù)量Zp，若不等于則重復(fù)Step 1～4，若等于則e中數(shù)據(jù)即為一個(gè)初始解。

速度更新公式為式(11)，位置更新公式如下：

(18)

之后對(duì)位置進(jìn)行取整操作：

(19)

3 模型求解

3.1 數(shù)值算例

為驗(yàn)證離散粒子群算法性能，在Matlab 7.0平臺(tái)上進(jìn)行仿真實(shí)驗(yàn)。以土耳其地震災(zāi)區(qū)為例，地震災(zāi)區(qū)有1個(gè)救援物資集散點(diǎn)，8個(gè)受災(zāi)點(diǎn)。采用直升機(jī)運(yùn)輸?shù)氖転?zāi)點(diǎn)5個(gè)，直升機(jī)運(yùn)力13架次；采用火車(chē)運(yùn)輸?shù)氖転?zāi)點(diǎn)4個(gè)，火車(chē)運(yùn)力12節(jié)車(chē)廂；采用汽車(chē)運(yùn)輸?shù)氖転?zāi)點(diǎn)8個(gè)，汽車(chē)運(yùn)力50輛。算法參數(shù)設(shè)置如下：最大迭代次數(shù)1 000次，粒子群規(guī)模20，學(xué)習(xí)因子c1,c2均為2。其他參數(shù)如表1～表4所示。

表1 三種方式均可采用的受災(zāi)點(diǎn)參數(shù)表

表2 使用直升機(jī)運(yùn)輸?shù)母魇転?zāi)點(diǎn)參數(shù)表

表3 使用火車(chē)運(yùn)輸?shù)母魇転?zāi)點(diǎn)參數(shù)表

表4 使用汽車(chē)運(yùn)輸?shù)母魇転?zāi)點(diǎn)參數(shù)表

3.2 求解結(jié)果

第一階段運(yùn)輸調(diào)度求解過(guò)程及結(jié)果如圖1、表5所示。

圖1 第一階段求解過(guò)程示意圖

表5 第一階段三種決策方案

第二階段汽車(chē)、直升機(jī)和火車(chē)運(yùn)輸物資分配方案求解過(guò)程及結(jié)果如圖2、表6～表8所示。

由此可得，兩個(gè)子目標(biāo)分別給出了三個(gè)參考解，方案1中：f1=507.07，f2=3922.9；方案2中：f1=509.18，f2=4033.9；方案3中：f1=517.31，f2=4055.8。對(duì)于總目標(biāo)e1f1+e2f2，子問(wèn)題的權(quán)重分別為0.4,0.6，可以求得最小目標(biāo)值e1f1+e2f2=2556.57；相應(yīng)救援方案為：第一階段在8個(gè)受災(zāi)點(diǎn)中選出第1、2、3、6、7個(gè)采用直升機(jī)運(yùn)輸，第5、8個(gè)采用火車(chē)，第4個(gè)采用汽車(chē)；第二階段從集散點(diǎn)向5個(gè)受災(zāi)點(diǎn)派直升機(jī)救援，采用方案1；向4個(gè)受災(zāi)點(diǎn)派火車(chē)救援，采用方案1；向8個(gè)受災(zāi)點(diǎn)派汽車(chē)運(yùn)輸，采用方案1。

圖2 汽車(chē)運(yùn)輸救援物資分配方案求解過(guò)程示意圖

表6 汽車(chē)運(yùn)輸救援物資的三種分配方案

表7 直升機(jī)運(yùn)輸救援物資的三種分配方案

表8 火車(chē)運(yùn)輸救援物資的三種分配方案

4 結(jié)束語(yǔ)

以自然災(zāi)害為背景，建立應(yīng)急物資運(yùn)輸及分配的兩階段優(yōu)化模型，第一階段以運(yùn)輸成本最小化為目標(biāo)，決策運(yùn)輸工具的使用；第二階段在確定應(yīng)急物資運(yùn)輸方案后，以未滿足的需求量最小化為目標(biāo)，研究救援物資分配問(wèn)題。基于離散粒子群算法，分別采用二進(jìn)制和自然數(shù)編碼設(shè)計(jì)算法。仿真結(jié)果證明了算法的有效性與穩(wěn)定性。對(duì)于應(yīng)急物流調(diào)度，可以進(jìn)一步研究按照物資需求隨時(shí)間的變化進(jìn)行劃分救援過(guò)程，汽車(chē)在地震發(fā)生后的行駛時(shí)間的隨機(jī)性，以及汽車(chē)運(yùn)送救援物資時(shí)的路徑選擇等問(wèn)題。

[1]Sheu J B.An emergency logistics distribution approach for quick response to urgent relief demand in disasters[J].Transportation Research Part E,2007,43(6):687-709.

[2]Chang F S,Wu J S,Lee C N,et al.Greedy-search-based multi-objective genetic algorithm for emergency logistics scheduling[J].Expert Systems with Applications,2014,41(6):2947-2956.

[3]Najafi M,Eshghi K,Dullaert W.A multi-objective robust optimization model for logistics planning in the earthquake response phase[J].Transportation Research Part E,2013,49(1):217-249.

[4]Ali B A,Mohammad S J,Mehdi A,et al.A modified particle swarm optimization for disaster relief logistics under uncertain environment[J].The International Journal of Advanced Manufacturing Technology,2012,60(4):357-371.

[5]Zheng Y J,Ling H F.Emergency transportation planning in disaster relief supply chain management:a cooperative fuzzy optimization approach[J].Soft Computing,2013,17(7):1301-1314.

[6]Kennedy J,Eberhart R C.Particle swarm optimization[C].In proceedings of IEEE International Conference on Neural Networks,IV.Pis-cataway,NJ:IEEE Service Center,1995:1942-1948.

[7]Kennedy J,Eberhart R C.A discrete binary version of the particle swarm algorithm[C].In proceeding of the World Multi conference Systemics,Cybemeties and Information,NJ:Pis-cataway,1997:4104-4108.

[8]劉建華.粒子群算法的基本理論及其改進(jìn)研究[D].長(zhǎng)沙:中南大學(xué),2009.

(責(zé)任編輯：馬金發(fā))

An Emergency Relief Supplies Distribution Problem Based on the Discrete Particle Swarm Optimization Algorithm

GONG Hua，ZHANG Biao

(Shenyang Ligong University,Shenyang 110159,China)

A relief supplies distribution problem in emergency logistics in the natural disasters is studied.A two-stage supplies optimization model of transportation and allocation is considered that takes into consideration the connection of various transportation facilities and the allocation of the relief supplies.The objective is to minimize transportation cost and the unmet demand.A discrete particle swarm optimization algorithm is applied to solve the model.The simulation results show the effective and stability of the proposed algorithm and provide the scheme of transportation and allocation for the emergency supplies.

emergency logistics;supplies transportation;supplies allocation;DPSO

2015-01-04

國(guó)家自然科學(xué)基金資助項(xiàng)目(71101097)；遼寧省“百千萬(wàn)人才工程”培養(yǎng)資助項(xiàng)目(2014921043)

宮華(1976—)，女，副教授，博士，研究方向：生產(chǎn)調(diào)度與物流優(yōu)化.

1003-1251(2015)02-0065-06

O224

A