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

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

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

1 引言

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

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

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

2 應急物流倉庫定位模型

2.1 雙層規(guī)劃

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

2.1.1 上層規(guī)劃

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

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

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

(1)

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

(2)

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

(3)

保證各個受災點有且僅有一輛應急物流車輛的函數(shù)表達式為

(4)

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

由于車輛所能承載的物資容量是有限的，因此受災點的物資需求量需要小于等于所有車輛容量之和，則應急物流車輛的容量約束表達式為

(5)

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

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

(6)

式中，S表示全部備用應急物流倉庫定點和受災點的集合，p表示事先設置的最少應急物資數(shù)量。

假設每輛應急物流車輛只服務一個受災點，則此時的約束方程為

(7)

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

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

(?m∈G，r∈G)

(8)

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

保證所有受災點都有應急物流車輛的函數(shù)表達式為

(9)

受災點各個支路消去約束后的回路有且僅有一個應急物流倉庫的函數(shù)表達式為

uik-ujk+Nxijk=N-1

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

(10)

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

當應急物流的運輸時間權重和是1時，每條回路的運輸時間函數(shù)如下所示

(11)

式中，λj表示應急物流車輛從受災點j出發(fā)的時間權重，j∈G。

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

(12)

式中，tij表示物資從受災點i到受災點j所用的運輸時間。

(13)

2.1.2 下層規(guī)劃

每個應急物流倉庫所提供的物資滿足受災點需求量的函數(shù)公式為

(14)

(15)

式中，M-Hj表示某個應急物流倉庫所能提供的物資總量與受災點所需物資總量之差。

確保建設的應急物流倉庫到最近的受災點之間的距離小于等于a，則其表達式為

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

(16)

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

(17)

則任意一個受災點可獲取的最多應急物流倉庫數(shù)量的函數(shù)表達式為

(18)

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

(19)

模型中受災點可被服務的應急物流倉庫權重和等于1的約束條件函數(shù)表達式為

(20)

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

3 演化博弈算法

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

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

(21)

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

x可獲取最少應急物流倉庫服務點的有效函數(shù)表達式為

(22)

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

每次進行演化博弈算法時，任意選取兩個受災點進行多次博弈，結束博弈后，從多次博弈的平均效用中選取出受災點x的基本適應度，則基本適應度的表達式為

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

(23)

式中，N表示受災點進行博弈的次數(shù)，BF(x)表示所有受災區(qū)域的基本適應度。

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

(24)

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

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

(25)

因此可將演化博弈算法總結為。

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

2)隨機選取兩個受災點進行博弈，并運算出受災點中的效用函數(shù)。

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

4)根據(jù)基本適應度函數(shù)方程求解出受災點的適應度值。

5)利用受災點適應度和輪盤賭選擇產(chǎn)生下一代子受災點。

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

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

4 實驗與結果

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

4.1 運輸距離

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

圖1 不同方法的運輸距離

4.2 倉庫服務率

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

圖2 最優(yōu)倉庫可服務的受災點

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

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

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

5 結束語

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

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

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