不確定條件下的應急物資配送選址-路徑問題

王海軍，杜麗敬，胡 蝶，王 婧

（華中科技大學 管理學院，武漢 430074）

當突發(fā)事件發(fā)生時，要快速啟動救助行動，向受到危害的地區(qū)和人員運送充足的物資，而這種突發(fā)事件一般無法提前預見，因此，受到危害的地方通常缺乏充足的物資實施救助，那么就需要選擇合適的物資供應點收集物資，來集中對這些需求點進行供貨。有的突發(fā)事件會導致道路毀壞，使得應急物資無法順利運到需求點，在這種情況下，如何有效地用車輛將應急物資運到每個需求點對救援起到關鍵的作用。因此，本文基于此背景研究應急物流系統中的 選 址-路 徑 問 題（Location-Routing Problem，LRP）。

目前，國內外學者對LRP問題研究較多［1-5］。Ozdamar［6］對應急物流定義進行了介紹。以總成本最小化為目標，Alumur等［7］建立了一個多目標LRP模型，確定了廢物回收站的選址，對不同類別廢棄物到這些不同回收站的路線做了安排。以成本最小化和社會影響最小化為目標，Caballero等［8］研究了多車型有容量限制的多目標LRP模型。Ozdamar［9］探討了在自然災害發(fā)生時，傷員運送救治與物資配送的問題，研究了災區(qū)臨時的醫(yī)療點選址、醫(yī)務人員分配、應急物資分配以及車輛路徑選擇等問題，建立了一種確定型情況下的應急物流網絡模型，并利用CPLEX軟件對模型進行求解，目標是最小化物資送達及傷員救治的延誤，但該文中將車輛當成一種物資進行分配，是整數變量，而不是0-1變量，且未考慮自然災害應急物流系統中的不確定性。汪壽陽等［10］在國內提出LRP，并介紹了這一領域的重要研究成果，這才引起國內學者對集成物流管理系統的重視，開展LRP方面的研究。徐琴［11］考慮了在自然災害發(fā)生后，城市道路毀壞造成交通擁堵情況下，建立LRP模型，其中應急運輸時間是模糊數，目標是要總的應急救援時間滿意度最大。曾敏剛［12］研究災害發(fā)生后的選址路徑問題，將該問題分為選址與路線安排2個子問題，并且建立了最小化運輸成本和災害損失的模型，用一個兩階段的啟發(fā)式算法解決。文獻［14-15］中介紹了求解LRP問題的相關啟發(fā)式算法。

可見，學者們對于LRP的研究已經得出不少成果，但在應急物流的信息不確定性、對此種不確定信息的處理，以及求解算法方面還有不足，本文就基于此不足進行建模與求解算法的設計。在應急物流活動中，需求點的物資需求是不確定的，由于道路毀壞，車輛在道路上的運輸時間也不確定，而由于應急物流對時間要求高，故需求點是具有一定時間窗的。在突發(fā)事件發(fā)生時，短時間內難以籌集到足夠的資金，為了在有限的資金條件下達到更好的救援效果，本文基于機會約束規(guī)劃方法建立一個帶時間窗的LRP模型，目標是最小化救援的成本以及救援的時間，并提出基于整體的遺傳算法來求解模型。

1 模型建立

1.1 問題描述

當自然災害、突發(fā)公共事件等發(fā)生時，要快速從若干候選的應急物流配送中心中選出合適的配送中心，并且要在滿足一定的時間與資源量的情況下，將物資從配送中心，按照一定路線運到應急物資需求點。本文研究自然災害發(fā)生后，單一應急物資調配問題，應急物流網絡如圖1所示。文中僅研究陸地車輛運輸，需要飛機、輪船等其他運輸方式才能達到的受災點不在考慮范圍內。本文特點是受災點應急物資的需求是高度不確定的，且具有較高的時間限制；另外，由于道路受損，車輛行駛時間也具有高度的不確定性?？紤]到受災點對應急物資需求的緊迫性，時間是考慮的目標之一；還由于短期內籌集到的資金有限，合理利用有關資金至關重要，故成本作為第2個要考慮的目標。

綜上，本文主要研究選擇合適數目與位置的配送中心以及合理安排車輛路線2個問題，在高度不確定的條件下，以較低的成本盡可能快地將應急物資配送到受災人員手中。

圖1 應急物流網絡LRP示意圖

模型假設：

（1）有若干候選應急物流配送中心，容量有限。

（2）每個應急物流配送中心有若干個不同類型的運輸車輛，車輛有容量限制。

（3）每個應急物資需求點只由1輛車提供服務，并具有一定的時間窗限制。

（4）每輛車屬于一個應急物流配送中心，從該中心出發(fā)，運送完物資以后回到該中心。

（5）需求點的物資需求量是不確定的，是隨機變量，服從正態(tài)分布。

（6）由于道路可能毀壞，故車輛運輸時間是隨機變量，服從正態(tài)分布。

1.2 變量與符號說明

A｛r|r=1，2，…，n｝——需求點集合

B｛i|i=n+1，n+2，…，n+m｝——候選配送中心集合

S=｛A｝∪｛B｝——應急物流網絡中所有節(jié)點集合

V｛k|k=1，2，…，K｝——運輸車輛集合

Fi——候選配送中心i（i∈B）處的固定建設費用

Wi——候選配送中心i（i∈B）的最大容量

dab——點a（a∈S）與點b（b∈S）之間距離

Ck——車輛k（k∈V）的固定運營成本

Qk——車輛k（k∈V）的可用容量

qr——需求點r（r∈A）處的需求量，服從正態(tài)分布

tab——車輛k（k∈V）從a（a∈S）到b（b∈S）的行駛時間，服從正態(tài)分布

tr——車輛在需求點r（r∈A）處的服務時間

LTr——需求點r（r∈A）處最遲必須得到服務的時間

Tbk——車輛k（k∈V）到達點b（b∈S）的時間，Tbk=Tak+tabzabk+ta，當b∈B時，Tbk=0

C——單位距離車輛行駛成本

xi——1，如果被選作配送中心；0，否則

yik——1，車輛k（k∈V）分配到配送中心i（i∈B）；0，否則

zabk——1，車輛k（k∈V）從節(jié)點a（a∈S）到b（b∈S），且a≠b；0，否則

1.3 模型建立

約束條件中含有隨機變量，且必須在觀測到隨機變量實現之前做出決策的問題，可以用機會約束規(guī)劃方法解決［13］。一般采用的原則是：允許決策在一定程度上不滿足約束條件，但該決策要保證約束條件成立的概率不小于某一置信水平。這里將物資需求和車輛運輸時間的約束處理成機會約束條件。模型如下：

目標式（1）使得物資到達需求點的時間總和最小；式（2）使應急物流總成本最小，包括應急物流配送中心固定成本、車輛運輸成本以及車輛運營成本。約束式（3）表示每車物資配送量小于車輛容量的概率不小于α1；式（4）表示物資配送量小于應急物流配送中心的容量的概率不小于α2；式（5）表示物資到達時間滿足時間窗的概率不小于α3；式（6）表示選上的配送中心可以發(fā)車；式（7）表示未選上的配送中心無車輛發(fā)出；式（8）表示車輛只能分給選上的配送中心；式（9）表示每輛車只從它被分到的配送中心發(fā)出；式（10）表示車輛不在配送中心之間來往；式（11）表示每輛車從一個點駛入，也要從該點駛出；式（12）表示物資需求點一定有且只有1輛車服務；式（13）表示車輛行駛時間具有先后；式（14）～（16）是0-1變量。

2 模型求解

2.1 雙目標處理

由于該模型中，成本目標和時間目標是存在沖突性的，而在實際的應急物流過程中，響應階段不同，決策者對于成本和時間的要求也不同，從而導致了兩者的重要程度不同，故本文采用加權的方法對成本和時間目標予以權重，根據災害發(fā)生的不同時間，決策者可以根據經驗和實際狀況來賦權，如應急物流響應初期，時間的權重大，而在響應后期，成本的權重可以增大，將雙目標問題轉化為單目標問題，增強了決策的柔性。

對雙目標LRP模型的目標做以下處理：

式中：a和b分別為時間與成本的權重；minT和minC分別為最小時間與最小成本，是在該模型的目標分別為最小化時間與最小化成本的單目標時，得到的最小目標值，將其代入式（17），再運行雙目標模型程序time和cost是程序運行得到的當前解，即是要求的雙目標模型的解。

2.2 遺傳算法設計

遺傳算法的實質是模擬生物界遺傳規(guī)律和生物進化論，采取并行隨機搜索的優(yōu)化方法。遺傳算法的概率搜索機制增加了搜索過程的靈活性，運算速度較快，不受函數約束條件的限制，且采用多種機制保證搜索過程不陷入局部極值，例如，通過調整交叉和變異概率消除早熟的現象，它可以很好地將全局和局部搜索結合起來，因此，本文采用遺傳算法求解。

2.2.1 編碼設計 染色體利用配送中心、應急物資需求點以及應急運輸車輛號來編碼，用的是自然數編碼的方式。染色體編碼方式如表1所示。

表1 染色體編碼方式

染色體第1段有n個基因位，n指需求點個數，1個需求點與1個車號對應，表示需求點與車輛的分配關系，由1～k的自然數，隨機生成1個，表示每個基因位，k為車輛數量，或者說線路的條數；第2段同樣是n位，是由1～n的隨機自然數排列成，表示路線中需求點排列的順序；第3段是k位，是1～r的自然數，r是候選配送中心數量，表示每輛車屬于哪個應急物流配送中心，染色體總長為n+n+k。

舉例說明，若候選配送中心有3個，需求點有15個，可用車輛數量是3，則有如下的染色體：2-1-1-3-2-3-1-2-1-3-2-1-1-2-3-15-3-4-11-1-5-9-8-2-7-10-13-14-12-6-1-1-2，根據上文，染色體有4段，共15個需求點，那么染色體的第1段就有15位，為2-1-1-3-2-3-1-2-1-3-2-1-1-2-3，1個需求點與1個車號對應，可見1，2，3都出現了，說明3輛車都用到，關系如表2所示。

表2 需求點與車輛對應的關系

同理，第2段也有15位，為15-3-4-11-1-5-9-8-2-7-10-13-14-12-6，每一位表示1個需求點，數字順序表示需求點接受服務的先后，因此，需求點15是第1個接收到物資，接著是需求點3，依次類推。因此，車輛行駛經過的路徑為車1：3→9→2→7→13→12，車2：11→1→5→8→14，車3：15→4→10→6，接著，車的數量是3，那么染色體第3段就有3位，為1-1-2，表示3輛車與應急物流配送中心的關系，如表3所示。

可見，應急物流配送中心1和2出現了，表示選擇它們作為物流中心，1，2號車屬于應急物流配送中心1，3號車屬于應急物流配送中心1。

表3 車輛與應急物流配送中心關系

上述分析表示應急物流配送中心與車輛的分配關系，車輛與物資需求點的分配關系。初始種群是隨機生成的，根據候選應急物流配送中心的數量及車輛數量等，染色體每個基因位隨機生成一個自然數，如果滿足配送中心與車輛容量約束，即可得到一個初始的染色體，按照這種方法得到初始種群。

2.2.2 約束條件處理 采用罰函數的思想來處理約束：如果有染色體不滿足約束，就給它一定懲罰值，將懲罰值在目標函數上體現，同時也在適應度函數值上體現，即在目標函數增加一個極大的數，使得適應值減小，減少選中的概率。在本文中，有應急物流配送中心容量、車輛容量以及時間窗的約束，對這些約束增加一個懲罰值。

每個需求點的需求量qr滿足正態(tài)分布N（μ，σ），且彼此獨立，則也服從正態(tài)分布

則約束式（3）可轉化為

η服從正態(tài)分布，當

時，約束才成立。φ—1（α1）可以查正態(tài)分布表得到。

令

則約束式（3）轉化為H1（X）≤Qk。

在目標中加入f（1）=M1max｛H1（X）—Qk，0｝，M1是很大的數，同理對約束式（4）進行處理，為H2（X）≤Wixi。在目標中加入

M2是很大的數，時間窗式（5）為

則目標就轉化為

2.2.3 適應度函數 由于本文的目標函數是最小值，故要最大化適應度函數，通過如下方式得到：適應函數值=A/目標函數值，這里A是個常數。目標函數U=minZ，則適應度函數f（x）=1/U。

2.2.4 遺傳操作 本文遺傳操作有選擇、交叉、變異3種。隨機生成一個初始的種群，再經過預定的代數進化，優(yōu)化后的結果就是適應值最佳的染色體代表的結果。

（1）選擇方法。本文使用精英法與輪盤法兩種方法。

（2）交叉方法。文中染色體含有選址與路徑兩類信息，因此，不能將染色體框架成整體直接交叉，而要分別對選址與路徑基因實施交叉。由于路徑基因中需求點只能顯示1次，故路徑基因用部分匹配交叉的方法，而選址基因則是雙點交叉法。

（3）變異方法。進行基因變異操作時，同樣要將選址與路徑基因分開進行。由于選址與路徑基因不同，這里將選址基因用對換變異法，路徑基因用逆轉變異法。

（4）停止準則。本文采用停止準則為算法的遺傳代數達到程序設置的最大迭代數，則停止運算。

3 算例分析

3.1 運算結果分析

用Solomon的RC題目的RC208部分數據作為算例。方法為：從RC208的100個數據中隨機選3個作備用的配送中心，隨機生成1～100中的3個數，將原數據庫中的這3個編號的需求點坐標視為備用應急物流配送中心的坐標。同理得到20個需求點。

參數設置為車輛單位運輸成本C為9元/km，賦予時間和成本的權重a、b分別為0.6和0.4，3個置信水平為95%，其他數據信息如表4～8所示。

表4 候選配送中心信息

表5 運輸車輛信息

表6 需求點的數據

表7 各點之間的運輸時間μ表

表8 各點之間的運輸時間σ表

使用MATLAB軟件編程，設置迭代次數為1 000次，初始種群數為200，交叉概率pc=0.8，變異概率pm=0.2。對算例計算50次，平均計算時間為278.55 s，計算效率較高，得到結果比較穩(wěn)定，均是選擇配送中心1和2；對運算結果進行統計分析得到，目標函數的平均值為1.045 1，最差解和最優(yōu)解的目標函數值分別為1.054 6和1.034 9，與平均值的偏差僅為0.91%和0.98%，說明算法的魯棒性較好；最優(yōu)目標值1.034 9對應的最小應急物流成本為61 821元，最小應急物流時間為575 m。得出模型目標值收斂圖如圖6所示，結果表示的選址和路徑分配如表9所示。

選出1和2作為應急物流配送中心，運輸車輛3，4，5，10屬于應急物流配送中心1，運輸車輛1，2，6，7，8屬于應急物流配送中心2，也得出了每個車輛配送需求點的順序。

圖6 目標值收斂圖

表9 車輛路線結果

3.2 敏感性分析

下面對運算結果進行敏感性分析，改變模型中置信水平的取值，應急時間和應急成本的權重，得出的運算結果也不同，結果變化如表10所示。

表10 不同置信水平及權重下的運算結果

由圖7可見，當時間權重增加，應急總時間呈下降趨勢，應急總成本呈上升趨勢。由表10可見，當置信水平一定，隨著時間的權重增大，選出的配送中心的數量是遞增的，這是由于多設置一些配送中心，能夠使得應急物資盡快送達需求點處，圖中當置信水平增加到90%，配送中心由1個增加到2個，由于配送中心固定成本較大，故總的應急成本也增大。

圖7 應急時間與成本隨權重變化趨勢圖

當時間和成本的權重一定，而置信水平增大時，表示要求物資送達需求點的時間滿足時間窗的概率越大，故應急時間越短，同時也表示物資運送量滿足配送中心容量與車輛容量的概率越大，因此，選中的配送中心個數越多，且啟用的車輛個數也增多，導致應急總成本越大，配送中心增多，能夠快速地響應需求點對物資的需求，從而使得應急時間也變短。

由此可見，置信水平和時間成本權重的取值是非常重要的，決策者應該在應急過程的不同階段根據實際狀況對參數賦予合適的值，這樣得到的方案結果是可行有效的。

4 結語

本文研究了大規(guī)模突發(fā)事件發(fā)生時，在需求點的物資需求量與車輛行駛時間不確定、需求點有時間窗限制的條件下的LRP模型，以總運輸時間最小化和應急成本最小化為目標建立了雙目標模型，采用賦權將兩目標轉變?yōu)閱文繕?，增加了決策的柔性。給出了求解的遺傳算法，并用算例驗證了模型和算法的有效性。

但是本研究也存在不足之處，實際應急物流中可能涉及到多種物資，而且運輸的方式可能是多式聯運。因此，在后續(xù)的研究中，將進一步考慮多物資與多式聯運的LRP模型，從而為應急物資調度決策提供更充分更科學的依據。