基于演化博弈的應(yīng)急物流最優(yōu)倉庫定位仿真

廖海鋒，尤妮斯.B.庫斯托迪奧

(1.廣東科技學(xué)院，廣東東莞523000；2.菲律賓布拉卡國立大學(xué)，菲律賓布拉卡馬洛洛斯)

1 引言

由于無法預(yù)測災(zāi)害發(fā)生時間和地點(diǎn)，因此應(yīng)急物流倉庫的選址過程不能依靠普通倉庫選址辦法[1-2]，應(yīng)急物流倉庫需要在災(zāi)情發(fā)生時以最快速度備貨、配送，所以需要解決在不涉及倉庫規(guī)模的前提下定位出應(yīng)急物流最優(yōu)倉庫[3]。

項寅[4]等提出基于不完全理性的應(yīng)急物流最優(yōu)倉庫定位方法，但是該方法在定位應(yīng)急物流最優(yōu)倉庫時沒有進(jìn)行雙層規(guī)劃，導(dǎo)致倉庫定位與受災(zāi)點(diǎn)之間距離較遠(yuǎn)，存在運(yùn)輸距離長的問題。馮艦銳[5]等提出基于應(yīng)急物資儲備的應(yīng)急物流最優(yōu)倉庫定位方法，利用系統(tǒng)動態(tài)演化方法將多目標(biāo)問題逐步轉(zhuǎn)化為單目標(biāo)問題實(shí)現(xiàn)應(yīng)急物流最優(yōu)倉庫定位。該方法在進(jìn)行最優(yōu)倉庫定位時雖然盡可能地縮短倉庫與受災(zāi)點(diǎn)之間的距離，但沒有保證受災(zāi)點(diǎn)之間的總加權(quán)距離最小，降低了應(yīng)急物流倉庫的反應(yīng)速度，導(dǎo)致倉庫的服務(wù)率低。郗蒙浩[6]等提出基于P-center問題的國家級應(yīng)急物流最優(yōu)倉庫定位方法，利用變鄰域(VNS)算法實(shí)現(xiàn)應(yīng)急物流最優(yōu)倉庫定位，該方法只是利用普通的設(shè)施選址模型定位倉庫，沒有將其劃分為多層模型的形式同時解決定位問題，因此加長了最優(yōu)倉庫定位時間，增加了倉庫定位的運(yùn)行時間。

為了解決上述問題，提出基于演化博弈的應(yīng)急物流最優(yōu)倉庫定位仿真。

2 應(yīng)急物流倉庫定位模型

2.1 雙層規(guī)劃

利用雙層規(guī)劃方法解決應(yīng)急物流的多層相互關(guān)聯(lián)問題[7]。將雙層規(guī)劃分為上下兩層。

2.1.1 上層規(guī)劃

應(yīng)急物流上層規(guī)劃包括隨機(jī)機(jī)會約束方程的車輛路徑規(guī)劃，其目的是最大限度地縮短車輛的運(yùn)輸時間，提高救援效率。假設(shè)gi(X)≤0(j=1，2，…，n)是目標(biāo)規(guī)劃函數(shù)的n個約束條件，可獲取m層的規(guī)劃模型為

其中，F(xiàn)i(X)是每層模型的目標(biāo)規(guī)劃函數(shù)，X是每層模型的決策向量。

利用線性加權(quán)的方法對上述模型進(jìn)行優(yōu)化[8-9]，得出評價函數(shù)的表達(dá)式為

(1)

式中，ωi表示每層目標(biāo)函數(shù)的權(quán)重，由于權(quán)重大小可隨應(yīng)急物流的變化而變化，因此可將多層規(guī)劃問題轉(zhuǎn)為單層規(guī)劃問題，其表達(dá)式為

(2)

滿足上述模型的約束條件為

(3)

保證各個受災(zāi)點(diǎn)有且僅有一輛應(yīng)急物流車輛的函數(shù)表達(dá)式為

(4)

式中，xijk表示應(yīng)急車輛k從i點(diǎn)到j(luò)點(diǎn)的距離，其中i∈S，j∈S，k∈V，i≠j，xijk=1，G表示含有R個備用應(yīng)急物流倉庫定位點(diǎn)集合，且G=(r|r=1，2，…，R)。

由于車輛所能承載的物資容量是有限的，因此受災(zāi)點(diǎn)的物資需求量需要小于等于所有車輛容量之和，則應(yīng)急物流車輛的容量約束表達(dá)式為

(5)

式中，qj表示受災(zāi)點(diǎn)j的物資需求量期望值，且j∈H，Qk表示應(yīng)急物流車輛k的最大容量，且k∈V，V表示所有應(yīng)急物流車輛的集合，且V=(k|k=1，2，…，K)。

應(yīng)急物流車輛到倉庫路線的連續(xù)約束方程為

(6)

式中，S表示全部備用應(yīng)急物流倉庫定點(diǎn)和受災(zāi)點(diǎn)的集合，p表示事先設(shè)置的最少應(yīng)急物資數(shù)量。

假設(shè)每輛應(yīng)急物流車輛只服務(wù)一個受災(zāi)點(diǎn)，則此時的約束方程為

(7)

式中，H表示N個受災(zāi)點(diǎn)的集合，且H=(i|i=R+1，R+2，…，R+N)。

當(dāng)相鄰兩個受災(zāi)點(diǎn)之間互相獨(dú)立約束，同時沒有任何額外的連接方式，此時的約束函數(shù)為

(?m∈G，r∈G)

(8)

式中，mi表示受災(zāi)區(qū)域i至少需要的應(yīng)急物流倉庫數(shù)量，i∈H，Zr表示受災(zāi)點(diǎn)r的一個倉庫點(diǎn)，r∈G，M表示備用應(yīng)急物流倉庫的最大供應(yīng)量。

保證所有受災(zāi)點(diǎn)都有應(yīng)急物流車輛的函數(shù)表達(dá)式為

(9)

受災(zāi)點(diǎn)各個支路消去約束后的回路有且僅有一個應(yīng)急物流倉庫的函數(shù)表達(dá)式為

uik-ujk+Nxijk=N-1

(?i∈H，?j∈H，k∈V)

(10)

式中，uik表示受災(zāi)區(qū)域i在規(guī)劃路徑k中被訪問的順序，i∈H，k∈V。

當(dāng)應(yīng)急物流的運(yùn)輸時間權(quán)重和是1時，每條回路的運(yùn)輸時間函數(shù)如下所示

(11)

式中，λj表示應(yīng)急物流車輛從受災(zāi)點(diǎn)j出發(fā)的時間權(quán)重，j∈G。

因此可得出應(yīng)急物流車輛運(yùn)輸路徑的線性加權(quán)時間函數(shù)的表達(dá)式為

(12)

式中，tij表示物資從受災(zāi)點(diǎn)i到受災(zāi)點(diǎn)j所用的運(yùn)輸時間。

(13)

2.1.2 下層規(guī)劃

每個應(yīng)急物流倉庫所提供的物資滿足受災(zāi)點(diǎn)需求量的函數(shù)公式為

(14)

(15)

式中，M-Hj表示某個應(yīng)急物流倉庫所能提供的物資總量與受災(zāi)點(diǎn)所需物資總量之差。

確保建設(shè)的應(yīng)急物流倉庫到最近的受災(zāi)點(diǎn)之間的距離小于等于a，則其表達(dá)式為

dijZij≤a?i∈H，?j∈G

(16)

受災(zāi)區(qū)的應(yīng)急物流倉庫數(shù)量必須大于等于參數(shù)b，下層模型的權(quán)重大小直接反映受災(zāi)區(qū)的嚴(yán)重程度，因此權(quán)重大小的設(shè)置可保證受災(zāi)點(diǎn)得到足夠的應(yīng)急物流倉庫服務(wù)，則此時的模型的約束條件為

(17)

則任意一個受災(zāi)點(diǎn)可獲取的最多應(yīng)急物流倉庫數(shù)量的函數(shù)表達(dá)式為

(18)

確保每個受災(zāi)點(diǎn)所能提供服務(wù)的應(yīng)急物流倉庫數(shù)量小于等于固定值p，則此時的應(yīng)急物流倉庫數(shù)量的約束條件為

(19)

模型中受災(zāi)點(diǎn)可被服務(wù)的應(yīng)急物流倉庫權(quán)重和等于1的約束條件函數(shù)表達(dá)式為

(20)

結(jié)合上層規(guī)劃模型與下層規(guī)劃模型形成雙層規(guī)劃模型，即為應(yīng)急物流倉庫的所有最優(yōu)定位。

3 演化博弈算法

在演化博弈算法中，每個受災(zāi)點(diǎn)記錄一個決策向量，所有受災(zāi)區(qū)域i中含有m個不同受災(zāi)群體，一個群體代表一個受災(zāi)點(diǎn)集合。令i為Xi，且X=X1∪X2…∪Xm，Xi∩Xj=Φ，其中，i∈(1，2，…，m)，j∈(1，2，…，m)，當(dāng)某個受災(zāi)點(diǎn)記錄決策向量時，標(biāo)記著這個受災(zāi)點(diǎn)的群體也被當(dāng)作信息而記錄。

所有受災(zāi)群體之間存在物資競爭行為，當(dāng)兩個受災(zāi)點(diǎn)為同一個應(yīng)急物流倉庫進(jìn)行博弈時，設(shè)最大化多目標(biāo)倉庫優(yōu)化問題中受災(zāi)點(diǎn)x和x′進(jìn)行博弈，其中x′∈Xj，x∈Xi，則x可獲取最多應(yīng)急物流倉庫服務(wù)點(diǎn)的有效函數(shù)表達(dá)式為

(21)

式中，fi表示Xi的優(yōu)化目標(biāo)，mini表示受災(zāi)區(qū)域中最小的fi值，且mini=min(fi)。

x可獲取最少應(yīng)急物流倉庫服務(wù)點(diǎn)的有效函數(shù)表達(dá)式為

(22)

當(dāng)受災(zāi)區(qū)域中所有受災(zāi)點(diǎn)fi和fj之間都相等，即minj=maxj，mini=maxi，這時的有效函數(shù)的分母均為0，則有效函數(shù)U(x)=1。

每次進(jìn)行演化博弈算法時，任意選取兩個受災(zāi)點(diǎn)進(jìn)行多次博弈，結(jié)束博弈后，從多次博弈的平均效用中選取出受災(zāi)點(diǎn)x的基本適應(yīng)度，則基本適應(yīng)度的表達(dá)式為

BF(x)=(∑U(x)/N)×100%

(23)

式中，N表示受災(zāi)點(diǎn)進(jìn)行博弈的次數(shù)，BF(x)表示所有受災(zāi)區(qū)域的基本適應(yīng)度。

為保證進(jìn)行多次博弈后受災(zāi)點(diǎn)的應(yīng)急物流倉庫分布穩(wěn)定，需要修正所有受災(zāi)區(qū)域基本適應(yīng)度以獲取個體受災(zāi)點(diǎn)的適應(yīng)度，其修正函數(shù)方程為

(24)

式中，F(xiàn)(x)表示個體受災(zāi)點(diǎn)x的適應(yīng)度，pi表示原始受災(zāi)區(qū)域中屬于Xi受災(zāi)點(diǎn)的概率，以輪盤賭形式選擇生成下一代子受災(zāi)點(diǎn)。

經(jīng)過演化博弈后生成的下一代子受災(zāi)點(diǎn)自帶上一代的策略信息和所有受災(zāi)點(diǎn)區(qū)域信息。假如互相博弈的兩個父代受災(zāi)點(diǎn)均屬于受災(zāi)區(qū)域Xi，則兩個子代受災(zāi)點(diǎn)均屬于受災(zāi)區(qū)域Xi，假如互相博弈的兩個父代受災(zāi)點(diǎn)一個屬于受災(zāi)區(qū)域Xi，另一個屬于受災(zāi)區(qū)域Xj，則子代受災(zāi)點(diǎn)均有一半屬于受災(zāi)區(qū)域Xi，一半屬于受災(zāi)區(qū)域Xj，令經(jīng)過多次博弈后獲取的第t代受災(zāi)區(qū)域中屬于受災(zāi)區(qū)域Xi的受災(zāi)點(diǎn)的概率為pi，且∑pi=1，由此可知第t+1代受災(zāi)區(qū)域中屬于受災(zāi)區(qū)域Xi的受災(zāi)點(diǎn)的概率為

(25)

因此可將演化博弈算法總結(jié)為。

1)產(chǎn)生任意原始受災(zāi)區(qū)域。

2)隨機(jī)選取兩個受災(zāi)點(diǎn)進(jìn)行博弈，并運(yùn)算出受災(zāi)點(diǎn)中的效用函數(shù)。

3)反復(fù)進(jìn)行2)，博弈到最大次數(shù)停止博弈。

4)根據(jù)基本適應(yīng)度函數(shù)方程求解出受災(zāi)點(diǎn)的適應(yīng)度值。

5)利用受災(zāi)點(diǎn)適應(yīng)度和輪盤賭選擇產(chǎn)生下一代子受災(zāi)點(diǎn)。

6)反復(fù)進(jìn)行2)、3)、4)、5)，當(dāng)所有受災(zāi)區(qū)域達(dá)到最大演化代數(shù)或者達(dá)到演化穩(wěn)定策略(ESS)時停止演化。

7)停止演化后即可得到應(yīng)急物流倉庫定位中的最優(yōu)定位。

4 實(shí)驗與結(jié)果

為了驗證所提方法的整體有效性，在Window7操作系統(tǒng)中對基于演化博弈的應(yīng)急物流最優(yōu)倉庫定位仿真方法、文獻(xiàn)[4]方法、文獻(xiàn)[5]方法進(jìn)行運(yùn)輸距離、倉庫服務(wù)率和生成最優(yōu)倉庫定位的運(yùn)行時間測試。

4.1 運(yùn)輸距離

由圖1中的數(shù)據(jù)可知，通過文獻(xiàn)[4]方法、文獻(xiàn)[5]方法和所提方法利用同種容積的車輛將同等重量的物資運(yùn)輸?shù)酵坏攸c(diǎn)，文獻(xiàn)[4]方法和文獻(xiàn)[5]方法選取出的最優(yōu)倉庫位置到受災(zāi)點(diǎn)的距離均不穩(wěn)定且高于所提方法的運(yùn)輸距離，而所提方法定位的最優(yōu)倉庫位置到達(dá)任何受災(zāi)點(diǎn)的距離均不超過30km，這是因為所提方法在定位應(yīng)急物流最優(yōu)倉庫時利用雙層規(guī)劃模型選取出應(yīng)急物流車輛路徑規(guī)劃，最大限度縮短車輛的運(yùn)輸時間，即縮短運(yùn)輸距離。

圖1 不同方法的運(yùn)輸距離

4.2 倉庫服務(wù)率

分析圖2可知，對比不同方法的最優(yōu)應(yīng)急物流定位點(diǎn)在已規(guī)劃的路徑中應(yīng)急車輛從最優(yōu)倉庫出發(fā)到終點(diǎn)所能服務(wù)的受災(zāi)點(diǎn)數(shù)量，所提方法可服務(wù)的受災(zāi)點(diǎn)個數(shù)均高于其他兩種辦法，因為所提方法利用受災(zāi)點(diǎn)之間的總加權(quán)距離最小的雙層規(guī)劃方式定位應(yīng)急物流的最優(yōu)倉庫，提高可應(yīng)急物流倉庫的反應(yīng)速度，加強(qiáng)了倉庫的服務(wù)率。

圖2 最優(yōu)倉庫可服務(wù)的受災(zāi)點(diǎn)

4.3 生成最優(yōu)倉庫定位的運(yùn)行時間

由圖3可知，生成最優(yōu)倉庫定位時所提方法與文獻(xiàn)[4]方法和文獻(xiàn)[5]方法相比用時最少，因為所提方法在選出所有最有利的應(yīng)急物流倉庫定位后，綜合上層規(guī)劃模型及時篩選出更加優(yōu)秀的倉庫定位，即以最短時間選取出最優(yōu)倉庫定位，減少倉庫定位的運(yùn)行時間。

圖3 生成最優(yōu)倉庫定位的運(yùn)行時間

5 結(jié)束語

1)提出基于演化博弈的應(yīng)急物流最優(yōu)倉庫定位仿真方法，采用雙層規(guī)劃的方法，將應(yīng)急物流分成上下兩層約束模型，最優(yōu)倉庫位置到達(dá)任何受災(zāi)點(diǎn)的距離均不超過30km，其運(yùn)輸距離較短。

2)通過演化博弈算法對結(jié)合在一起的雙層規(guī)劃模型進(jìn)行博弈直到ESS，實(shí)現(xiàn)應(yīng)急物流最優(yōu)倉庫定位，可服務(wù)的受災(zāi)點(diǎn)個數(shù)最高可到9個。

3)倉庫服務(wù)率高和生成最優(yōu)倉庫定位的運(yùn)行時間少，最高不超過0.2s，而接下來會進(jìn)一步以節(jié)省開銷為目的，研究實(shí)用性更高的倉庫定位方法。