基于演化博弈的應急物流最優倉庫定位仿真

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

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

1 引言

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

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

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

2 應急物流倉庫定位模型

2.1 雙層規劃

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

2.1.1 上層規劃

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

其中，Fi(X)是每層模型的目標規劃函數，X是每層模型的決策向量。

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

(1)

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

(2)

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

(3)

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

(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)。

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

(6)

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

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

(7)

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

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

(?m∈G，r∈G)

(8)

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

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

(9)

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

uik-ujk+Nxijk=N-1

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

(10)

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

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

(11)

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

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

(12)

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

(13)

2.1.2 下層規劃

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

(14)

(15)

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

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

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

(16)

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

(17)

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

(18)

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

(19)

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

(20)

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

3 演化博弈算法

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

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

(21)

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

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

(22)

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

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

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

(23)

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

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

(24)

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

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

(25)

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

1)產生任意原始受災區域。

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

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

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

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

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

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

4 實驗與結果

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

4.1 運輸距離

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

圖1 不同方法的運輸距離

4.2 倉庫服務率

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

圖2 最優倉庫可服務的受災點

4.3 生成最優倉庫定位的運行時間

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

圖3 生成最優倉庫定位的運行時間

5 結束語

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

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

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