考慮時效與公平性的震后應急物資動態配送優化研究

曲沖沖，王　晶，黃　鈞，何明珂

(1.北京工商大學商學院，北京　100048;2.中國科學院大學工程科學學院　100049;3.北京物資學院物流學院　101149)

1　概述

大規模地震嚴重威脅人民生命和財產安全。加強震后應急物資保障是應對突發自然災害條件下提高救援效率的關鍵。震后物資保障需要將大量的應急物資運輸到受災區域，應急物資運輸的響應速度和分配策略是救援工作開展的重點任務。同時，根據受災區域的破壞程度，合理選擇運輸工具和穩定的配送中心是保證救援工作有序開展的前提。

震后應急配送中心選址和物資運輸分配問題是國內外學者廣泛研究的課題。震后應急救援物流不同于一般的社會性物流，其活動開展具有不確定性、突發性、時間約束較強、經濟性較弱等特點。宮華等[1]從外圍物資集散的中心選址、救災物品的分配滿意度等方面進行了研究。沈曉冰等[2]在分析震后應急物資的配送特點和應急配送中心的選址問題的基礎上，建立了一個綜合考慮應急物流運作效率和運輸路徑選擇的多目標優化模型，對震后救援效率和路徑選擇進行研究。劉長時等[3-4]在對震后應急物資運輸道路規劃問題進行研究時，通過建立多種運輸方式、多運輸周期的LRP模型，對應急物資開展運輸的時間進度進行討論；在對震后災民的非理性攀比因素進行研究時，通過構建一個靜態的運輸-分配優化模型，對靜態條件下的震后救援工作的開展進行了討論。王海軍等[5]通過建立一個雙目標的OLRP模型，對配送中心的選址和應急物資的運輸安排進行了討論。 Sheu[6]對臺灣震后救援工作開展的研究中，通過遞推機制對配送中心和受災地區進行分組分析。Najafi等[7]在對多目標、多線程、多種物資開展震后運輸和救助傷員的研究中，通過設計時間優化算法對救援工作有序開展提供建議。Yi Wei等[8]對研究震后響應活動中的協調后勤支援及疏散作業的綜合作業定位分配模式進行了研究。Haghi等[9]通過對震后受傷人員的救治路徑和健康中心布局規劃研究，提升了救助覆蓋的全面性。Arora等[10]在對公共衛生事件下開展物資、藥品分配的研究的基礎上，認為政策因素和距離因素對物資分配的公平性有一定的影響。Altay[11]認為提升救災效率和公平分配物資對傷員救治和災后區域恢復有著積極的促進作用。Liu Cong等[12]認為將救援工作從時間上劃分成若干個時段可以提升震后救援的效率。

對應急物資配送中心選址、運輸路徑選擇和物資分配公平性開展研究時，眾多文獻是通過建立數學模型進行分析的。李孟良等[13]在研究震后多式聯運問題時，對未滿足災區應急物品需求的最小懲罰系數進行了討論，提出了基于魯棒優化的聯運調配模型。鄭斌等[14]針對震后物資供不應求的狀況，通過設計一種混合遺傳算法結合汶川地震案例對物資的運輸時間規劃、物資分配方式進行了分析。Abounacer等[15]設計了一種啟發式算法—ε-約束方法，旨在確定實際所需的分配中心數量、位置和救援作業時間規劃。張偉等[16]在討論考慮運輸時間、運輸距離和道路復雜程度對路徑選擇影響的問題時設計了一種多目標非線性整數規劃模型。Mahmoudabad等[17]提出了一種基于動態風險和動態損傷烈度網絡的混沌理論解決突發情況下信息中斷時救援路徑選擇和物資分配的問題。王旭坪等[18]在借鑒前景理論的基礎上，通過構建風險感知函數，從道路運力、物資流動、決策過程等方面建立了物資調配的系統動力學模型。Haghani和Oh[19]通過交互式啟發算法解決救災物資分配和帶時間窗問題的多模態網絡流問題。Najafi等[6]用成本分析的方法提出了多目標、多模式、多商品、多周期的隨機模型為震后物資分配提供指導。

眾多文獻設計的目標函數通常考慮救援成本和時間效率，對受災點物資需求滿足程度與分配公平性考慮較少。本文在解決多時段、多種運輸方式共同參與的應急物資保障問題的過程中兼顧時效性與公平性，在綜合物資運輸與配送的兩階段、多時段的動態救援特點和多種運輸方式共同參與的基礎上，建立了保證救災物資運輸時效性和實現災區物資分配公平的最優的應急物資配送中心選址與運輸配送路徑優化模型。針對此模型設計了一種帶精英策略的非支配排序的遺傳算法，結合九寨溝地區震后災難情景對模型進行實證研究，通過結合Pareto前沿面分析，驗證了模型和算法的有效性，為震后應急物資保障提供了理論指導與決策支持。

2　模型建立

2.1　問題描述

震后應急物資保障工作是依托于物資集散地、應急物資配送中心和受災點之間的相互聯系展開的。災區所需的大批量、多批次、多品種的物資需要從災區外圍的救災物資集散地通過公路和直升飛機向災區周圍的臨時救災物資存放地應急物資配送中心進行分配中轉，這是應急物資運輸的第一階段；再由臨時配送中心通過公路運輸向災區進行分配，這是應急物資運輸的第二階段。在兩個階段中根據不同時段的道路狀況、運輸裝備性能開展的運輸路線調整和應急物資配送中心的備選工作是該階段的重點。兩階段劃分示意圖如圖1所示：

圖1　災后應急物資運輸系統示意圖

震后救災物資主要的供應模式是區域儲備倉庫和外圍物資集散地整合物資-區域應急物資配送中心分配中轉-受災點，受到運輸車數量和車輛的負荷裝載能力、路況、環境、救援人員數量變化等一系列客觀因素的制約以及隨著震后救援工作不斷深入，對災區實際狀況逐漸了解，需要對較長時間的救援工作進行時間細分，通過多時段的動態救援滿足災區的物資供應。

通過將應急物資保障分為若干時段，可以及時的調整救援工作，從而保證救援工作的高效率運作。同時要兼顧物資運輸的時效性和物資分配的的公平性。

2.2　模型構建

2.2.1模型假設

針對特定條件下救災物資的配送特征，作出如下假設：

(1)備選配送中心都是不易受到余震以及其他次生災害影響且距離受災區域距離較短的的交通樞紐區域點，可以長時間進行救災作業。

(2)應急物資從區域儲備倉庫和外圍集散地還未運輸到區域應急配送中心時，受災區域儲備的物資可以滿足自身的最低需求；區域應急配送中心向受災點運輸的應急物資數量可以滿足所有受災點的最低需求。

2.2.2符號說明

(1)參數

W：救援物資種類的集合(w∈W)

I：應急物資集散點的集合(i∈I)

J：應急物資配送中心的集合(j∈J)

K：受災點的集合(k∈K)

Ξ：需要決策的時段的集合(ξ∈Ξ)

M=

T(ξ)：決策時段ξ重新決策的時刻

qwi(ξ)：ξ時段下集散點i供給物資w在的量

dwk(ξ)：受災區域k在ξ時段對物資w的實際需求量

Pijm(ξ)：在ξ時段下從集散點i到配送中心j通過運輸方式m單次最大運輸量

Tijm(ξ)：在ξ時段道路未修復情況下，從集散點i到配送中心j通過運輸方式m所需要的時間

Pjk(ξ)：ξ時段下從配送中心j到受災點k的單次最大運輸量

Tjk(ξ)：ξ時段道路未修復情況下，從配送中心j到受災點k所需要的時間

ITijm：從集散點i到配送中心j通過運輸方式m發車的時間間隔

θw：受災點人均需求救災物資w的最少量

LTkw(ξ)：ξ時段下受災點k對救濟物資w供應滿意度最大時，所能夠接受的最長等待時間

STkw(ξ)：ξ時段下受災點k對救濟物資w供應不滿意度最大時，所能接受的最短等待時間

N(ξ)：ξ時段下允許配送中心運營的最多數量

PDkw(ξ)：ξ時段下進行下一時段(ξ+1)決策時，受災點k接收救災物資w必須等待的時間

Tkw(ξ)：ξ時段下受災點k完全接受救災物資w的時刻

QKw(ξ)：ξ時段下計劃分給受災區域K的救災物資w的總量

Θ：可用車輛總數

Ω：一個大數

(2)決策變量

Qijwm(ξ)：ξ時段下計劃采用運輸方式m從物資集散點i運輸到配送中心j物資w的數量

?j(ξ)：ξ時段下計劃分配給配送中心j進行運輸物資的車輛數目

Qjkw(ξ)：ξ時段下計劃從配送中心j運輸到受災點k的救災物資w的量

2.2.3數學模型構建

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

Qijwm(ξ)≥0,i∈I,j∈J,w∈W,m∈M

(13)

uijmw(ξ)=(0,1),i∈I,j∈J,w∈W,m∈M

(14)

(15)

(16)

(17)

Tjk(ξ),k∈K,w∈W,(j,k)∈Ak(ξ)

(18)

(19)

Qjkw(ξ)≤Ω·zjkw(ξ),j∈J,k∈K,w∈W

(20)

(21)

(22)

zjkw(ξ)=(0,1)

(23)

目標函數(1)表示在ξ時段下，各種應急物資配送到災區的加權時刻最短，進而保證應急物資的時效性。目標函數(2)表示最大化所有受災點各種物資滿意度的最小值，保證救援物資分配的公平性。約束(3)表示在ξ時段下計劃運輸物資到配送中心的總量等于該集散點物資總供應量；約束(4)表示受災點物資最小滿足率；約束(5)表示配送中心的最大承載量；約束(6)表示在不同運輸方式下，將救災物資從集散點運輸到配送中心所需時間表達式；約束(7)表示第一階段物資運輸時間函數表達式；約束(8)表示受災點完全接收救災物資時刻的函數表達式；約束(9)表示ξ時段下只有選擇某個配送中心時，才會把物資運輸到該配送中心。約束(10)表示救災物資只能向運轉的配送中心運輸救災物資；約束(11)表示配送中心開始運轉后，任何階段都不會關閉；約束(12)表示可以運轉的配送中心小于等于初始設定的最大數目限制；約束(13)表示非負約束；約束(14)、(15)表示0-1約束。約束(16)表示配送中心接受物資的量與輸出給災區的量均等；約束(17)表示各個受災點的物資接收量總和等于配送中心運往災區的量；約束(18)表示通過公路運輸從配送中心到受災點的時間函數表達式；約束(19)表示由于物資的供不應求，運輸到受災地區的物資總量小于災區實際需求量；約束(20)表示只有選擇為某個受災點服務時，才會輸送物資到該點；約束(21)表示受災點接受的救災物資只能來自于已經開啟運轉的配送中心。約束(22)表示受災點接受的物資只能來自于一個配送中心。約束(23)表示0-1約束。震后應急響應時間滿意度通過以下線性時間滿意度函數表達式描述：

在第一階段中，公路運輸與直升飛機運輸共同參與到應急物資的輸送工作，救援車輛從集散點到配送中心的出發時刻根據物資運輸方式的不同可以分為以下兩種情況：

i.當運輸方式為公路運輸且當前時段沒有救援車輛向災害地點運輸救災物資。

ii.運輸方式為公路運輸，且在下一時段開始

決策時，當前時段的運輸工作已經完成。

i.當運輸方式為公路運輸時，且下一時段救援工作開始時，當前時段的車輛仍在途中。

ii.運輸方式為直升飛機時，由于受到航線的限制，下一時段的車輛發出時刻是當前時段車輛返回的最早時刻。

(24)

(25)

同時由于災后救援物資需求具有持需時間長、多時段等特點，本文將救援過程細化成若干時段，目標函數考慮各個時段配送方案的設計與評價，保證在任意時段下救援物資配送的時效性與公平性。模型可轉化為：

s.t.(1)-(25)

3　算法設計

為了實現災后應急物資運輸與分配的時效性與公平性，構建了包括多時段動態的配送中心選址和應急物資配送路徑優化的多目標規劃模型，并設計了一種基于Pareto最優解基礎上改進的帶精英策略非支配排序的多目標遺傳算法，將精英策略引入到模型中，提升了算法了運算效率和準確率。通過基因交叉、多點變異將父代種群與子代種群組合，保證優良的種群個體在進化過程中不會被丟棄，進一步提高優化結果的精度。通過對所有個體的分層存放，迅速提高種群水平。

3.1　初始化參數

設該遺傳算法的種群規模popsize，最大迭代次數為max gen，交叉概率Pc，變異概率Pm。

3.2　染色體編碼

通過矩陣編碼策略描述每個時段配送中心到受災點的指派關系zjkw(ξ)和分配量Qjkw(ξ)。每個受災點在每個時段內的需求滿足情況是通過列向量基因位表現在染色體上。在每個列向量中第一個基因位是通過在1到|J|的整數內隨機產生，表示配送中心到受災點之間的指派關系。第二基因位到第(w+1)位是在[1，dwk(ξ)]的整數內隨機產生，表示在每個時段下配送中心向受災點運送的不同物資的具體的數量。因此，染色體編碼的總長度為(1+w)×(1+ξ)。

假設受災點的數量是16個，即K={k|1,2,3,4,5,6,7,8,…14,15,16}，受災點對應急物資的需求種類為2種：食品和生活用品。救援分為3個時段，即Ξ={ξ|1,2,3}。配送中心候選地點有8個，即|J|=8,選從中選出4個點作為開放的配送中心。因此，可以得出以下染色體編碼，見圖3。

圖3　染色體矩陣編碼示意圖

圖3矩陣含義：選擇2，5，6，8物資配送中心進行運營為16個受災地點運輸生活用品和食品。當ξ=1時，物資配送中心5為災區1和災區15服務，向災區1運送24單位和40單位的應急物資。同時向災區15運輸27單位和33單位的應急物資。

配送中心所屬車輛的數量是其向受災點運輸物資的數量來決定的，具體的運算公式為：

3.3　種群初始化及適應度函數計算

為了使初始種群中染色體數量盡可能豐富，在滿足約束條件的基礎上隨機均勻產生各基因位上的值，使得每個受災點K都能夠得到救援。在遺傳算法程序設計上，對各個受災點救援次數進行跟蹤，對于觀測到救援次數偏少的受災點將隨機選擇種群中沒有對其進行救助的個體，隨機將若干個基因位設置為其對應的受災點序號。

3.4　帶精英策略的非支配排序解集構造

非支配解排序的流程如下：

對于種群中每一個個體i，設都有兩個參數ni和Si，ni是指種群中支配個體i的解的個體數量，Si是指被個體i支配的解的個體集合。

步驟1：找出種群中所有ni=0的個體，表示個體i支配其他個體，將他們存入當前非支配集合Z1中；

步驟2：非支配集合Z1中的每一個個體j，遍歷其所支配的個體集合Sj中每一條染色體t，令nt=nt-1。若nt=0，將個體t存入集合H。

步驟3：Z1作為第一級非支配個體的集合，在Z1中的解得個體都是最優的。令其非支配序rank(i)=1，在此基礎對集合H作上述分級操作，直到所有的個體都被分級，同時賦予相應的非支配排序。

3.5　擁擠度與比較算子

擁擠度的計算是確保種群多樣性的一個重要因素，計算步驟如下：

(1)每個點的擁擠度id置為0；

(2)根據每個優化目標，令邊界上的兩個個體擁擠度為無限大，即od=ld=∞；

(3)對種群中的其它個體的擁擠度進行運算：

其中，id表示i點的擁擠度，fji+1表示i+1點的第j個目標函數值，fji-1表示i-1點的第j個目標函數值。

個體i與另一個體j進行比較，只要有以下一個條件滿足，則個體i勝利。

(1)個體i所處的支配層優于個體j所處的支配層，即ranki

(2)若種群中有兩個個體有相同等級(處在相同的非支配層)，且個體i比個體j有一個更大的擁擠距離，即irank=jrank且id>jd。

3.6　精英策略與遺傳操作

將父代種群與其產生的子代種群混合后進行非支配排序，可以有效的避免父代種群中的精英個體流失。通過輪盤選舉對個體進行選擇操作，采用單點、多點交叉和基因互換進行變異操作。設計算法的流程圖如圖2。

圖2　帶精英策略的非支配模型遺傳算法流程

4　算例分析

4.1　算例介紹與參數設置

根據四川九寨溝地震區域的災難情景，選取8個應急物資配送中心(編號為1～8)，以及16個受災點(編號1～16)同時選取2中主要的應急物資(選取食品和生活用品)。震后救援初始階段選擇4個應急配送中心開放運營。九寨溝縣各應急物資配送中心的倉庫容量如表1，主要受災點的物資需求量見表2。

表1　應急物資配送中心庫存容量

表2　主要受災點的物資需求如下

圖3　Pareto前沿面解的分布圖

帶精英策略的遺傳算法的參數設置如下：種群規模popsize=400,最大迭代次數maxgen400，交叉概率pc=0.92，變異概率為pm=0.01。

4.2　運算結果分析

通過Matlab2017a編程，在2.9 GHz Intel Core i5，8 GB內存，macOS操作系統的計算機上進行運算。算法終止時，所有解收斂到Pareto前沿面上，得到140個Pareto解，Pareto最優解分布見圖3。表3是從中抽取的5組(A-E)典型Pareto解。

4.3　結果對比與分析

為了保證算法運算的穩定性與可操作性，文章根據不同種群數量和算法迭代次數設計了4組參照組。表4是參照組1、2、3、4各主要指標的具體數值以及不同種群數量和迭代次數下的解數量和運算時間，各參照組Pareto前沿面結果如圖4。

表3　典型Pareto解

表4　各參照組主要指標及運行時長

通過對結果的分析我們可以得出以下論：

(1)通過帶精英策略的非支配排序的遺傳算法的運算，我們得出不同參數下的Pareto前沿面解集，證明了模型和算法的有效性。

(2)Pareto解的運算時間與種群數量和迭代次數有關。伴隨著種群數量和迭代次數的不斷增加，Pareto解的數量呈現著遞增趨勢，通過參照組的對比分析，種群規模越大，迭代次數越多，得到的結果就更加豐富，分布也更加均勻。

(3)通過表4發現，在迭代次數相同的情況下，種群數量越多，Pareto解的集合也就越多，但消耗更多的運算時間；在種群規模相同的情況下，迭代次數越多，Pareto解的數量更加豐富，同時消耗更多的運算時間。Pareto解的數量和種群規模以及迭代次數在一方面條件確定的情況下存在著正相關的關系。

圖4　各參照組Pareto前沿面解的分布圖

通過圖4三個參照組的對比可以發現，公平性目標與時效性目標存在著悖反現象。從Pareto前沿面的參照圖來看，救災物資的時效性目標波動較小，其分配物資的公平性目標波動較大。從圖3可以看出，當公平性目標越大，時效性目標略微增加時，公平性目標則大幅度降低。同時災區需求的增加會使公平性目標受到損失。

在救援的初級階段，決策者更多的關注時效性目標，在救援的后期階段，決策者更多的關注公平性目標。通過Pareto前沿面的分析，為救援決策者根據在不同階段對決策目標的偏好提供了更多的選擇。

5　結語

震后應急物資的分配與運輸是震后救援保障工作的重要環節，配送中心的選址的穩定性與物資保障效率的提升對于減少財產損失、保證生命安全有著重要意義。震后物資運輸與配送過程包括將應急物資從區域儲備倉庫和外圍物資集散地運輸到區域應急配送中心、區域配送中心配送到各個受災點兩個階段。但是應急物資保障具有持續時間長、需求緊迫性強和物資相對短缺的特點，因此將物資分配時效性與公平性，多時段、多種運輸方式共同參與的應急物資保障策略有機的結合起來，綜合考慮震后應急物資的運輸與分配特性，建立了一個考慮時效性-公平性的震后配送中心選址和物資動態分配的多目標規劃模型。基于模型設計了一種帶精英策略的非支配排序的遺傳算法，通過非線性混合整數規劃結合Pareto前沿面對時效性-公平性雙目標動態救援模型進行求解。通過算法對實際案例的求解分析，發現模型可以產生有效的Pareto最優解和前沿面，準確反映了時效性目標和公平性目標的悖反現象，通過數學模型的計算將時效性與公平性的關系通過數學結果對模型和算法的有效性進行了驗證，為今后進一步研究該問題奠定了基礎。

在構建的模型中，救援過程涉及的相關系數的是確定的數值，但是在實際的運輸過程中是隨機變化的。如道路安全系數、車輛的安全性能、運輸時間受道路清障的影響等因素，這些帶有隨機參數的目標函數模型是未來研究的方向。