不確定應(yīng)急物流LRP雙目標優(yōu)化模型

高榮，王純，馬業(yè)寶

(河北工業(yè)大學(xué) 經(jīng)濟管理學(xué)院，天津 300401)

自然災(zāi)害的頻繁發(fā)生極大危害了人民群眾的生命財產(chǎn)安全.自1990年起，受臺風(fēng)、地震、龍卷風(fēng)、洪水等重大自然災(zāi)害影響的人口每年高達3億人次，直接經(jīng)濟損失占世界GDP的平均比例為17%[1].在災(zāi)難發(fā)生之后，需要及時為災(zāi)民提供必要的生活和醫(yī)療等物資，所以自然災(zāi)害之后的應(yīng)急救援是一項非常重要的工作，也是一項復(fù)雜的系統(tǒng)工程.因此，應(yīng)急物資配送中如何減少時間、降低經(jīng)濟成本和減少自然災(zāi)害對人們生命財產(chǎn)造成的損失是一個值得深入研究的課題.

為降低自然災(zāi)害造成的損失，亟需科學(xué)優(yōu)化應(yīng)急物資中心選址和應(yīng)急配送車輛的路徑，達到有效快速完成應(yīng)急物資配送的目的.因此，應(yīng)急物資配送優(yōu)化中的選址-路徑問題(location-routing problem，LRP)備受關(guān)注.確定信息下，樓振凱[2]以救援時間最小和救援成本最低為目標，建立了雙層優(yōu)化模型；Vahdani等[3]考慮道路損壞和修復(fù)的影響，建立了以救援時間最少和救援成本最低的雙目標優(yōu)化模型；袁濤等[4]考慮道路損壞和修復(fù)的影響，構(gòu)建多式聯(lián)運多級應(yīng)急物流網(wǎng)絡(luò)，建立了設(shè)施點定位、路徑規(guī)劃和道路修復(fù)的一體化優(yōu)化模型.隨機信息下，考慮需求量是隨機的，Caunhye等[5]以設(shè)施建設(shè)成本最小和救援時間最短為目標，建立了2階段LRP隨機優(yōu)化模型；代穎等[6]基于機會約束方法建立了帶時間窗的隨機選址-路徑優(yōu)化模型；Vahdani等[7]考慮配送中心和倉庫的容量不確定性，建立了多周期多物資的三級LRP模型；考慮道路通行能力、供應(yīng)量和需求量是隨機的，Moreno等[8]以配送物流費用最小和災(zāi)民損失最小為目標，建立了2階段的隨機規(guī)劃模型．

在沒有數(shù)據(jù)的不確定信息情形下，需要應(yīng)用不確定理論來解決應(yīng)急物流優(yōu)化問題，如Zhang等[9]假設(shè)受災(zāi)點之間的服務(wù)時間和需求為不確定變量，建立了不確定位置集覆蓋模型，解決了應(yīng)急服務(wù)設(shè)施的定位問題.隨后，Zhang等[10]將應(yīng)急服務(wù)設(shè)施定位問題拓展到了應(yīng)急LRP優(yōu)化問題中，利用機會約束，建立了以時間最小化為目標的不確定規(guī)劃模型，解決了應(yīng)急物流中的閉環(huán)LRP問題.而在應(yīng)急物流中，時間是第1要素，但費用也不可忽視，同時考慮救援時間和費用才更符合現(xiàn)實要求，而現(xiàn)有的不確定應(yīng)急物流文獻中并沒有同時考慮這2個因素，因此，本文建立了時間最短和費用最小的雙目標模型來解決開環(huán)應(yīng)急LPR問題，進一步豐富了不確定理論成果，并為應(yīng)急物流優(yōu)化提供決策支撐.

1 預(yù)備知識

定理1[11]設(shè)η1,η2,…,ηn為獨立的不確定變量，其正則不確定分布為Φ1(x),Φ2(x) ，…,Φn(x).若函數(shù)f是連續(xù)的且嚴格單增，則η=f(η1,η2,…,ηn)有逆不確定分布

2 模型

2.1 模型建立

因為在自然災(zāi)害發(fā)生后，隨時可能會發(fā)生二次災(zāi)害甚至可能會發(fā)現(xiàn)更多的受災(zāi)人數(shù)，這就導(dǎo)致了需求點的需求量是不確定的，因此假設(shè)需求點的需求量是一個不確定變量.從救援中心到受災(zāi)點或者從受災(zāi)點到受災(zāi)點的運輸時間也是不確定變量，這是因為自然災(zāi)害后，通訊可能會中斷，使得沒辦法了解道路的實時情況等原因，造成了運輸時間的不確定性，因此假設(shè)2個節(jié)點之間的運輸時間也為一個不確定變量.

救援物資的配送是具有時效性的，將救援物資在某一時刻之前送達災(zāi)民手中是有價值的，超過某一時刻就會失去其應(yīng)有的價值，所以目標之一為救援物資送達需求點的總時間最短;在考慮應(yīng)急物資配送時效性的基礎(chǔ)上，應(yīng)該考慮整個物流系統(tǒng)的花費，在保證時間的前提下，盡可能地降低經(jīng)濟成本，所以另一個目標為整個配送系統(tǒng)的總費用最小。

在進行優(yōu)化的過程中，做以下假設(shè)：1)每一輛車裝載的救援物資的數(shù)量不超過車輛容量的可能性不低于預(yù)設(shè)的置信水平α1；2) 從每一個救援中心運輸出來的救援物資的數(shù)量不超過救援中心容量的可能性不低于預(yù)設(shè)的置信水平α2；3) 每一個需求點僅被一輛車服務(wù)；4) 只有開設(shè)的救援中心擁有配送車輛且必須發(fā)車；5) 各需求點的需求量是獨立的且其救援物資到達的時間滿足限制期要求；6) 每個車輛出發(fā)1次，完成自身的配送任務(wù)后，須就近停靠在救援中心.因此，救援時間最短和費用最小的雙目標模型為

(1)

(2)

(3)

(4)

(5)

2.2 模型轉(zhuǎn)化

在上述模型中，由于D和V中的點數(shù)都是有限的，根據(jù)定理1和定理2可將式(1)轉(zhuǎn)化為

由于G、V和U中的點數(shù)都是有限的，根據(jù)定理1和定理2可將式(2)轉(zhuǎn)化為

(6)

同理，可將約束條件式(4)轉(zhuǎn)化為其等價形式

(7)

根據(jù)定理1和定理2，可將約束條件式(5)轉(zhuǎn)化為

(8)

3 算法設(shè)計與算例

3.1 算法設(shè)計

由于應(yīng)急物流系統(tǒng)的LRP問題屬于NP-hard問題，所以無法得到其精確解，這就需要用智能算法來求解該模型.而求解多目標、非線性規(guī)劃模型時通常使用遺傳算法，并能求得不錯的解，所以本文設(shè)計了遺傳算法來求解.

3.1.1 染色體編碼

在該模型中，采用自然數(shù)編碼.3個子串構(gòu)成一條染色體，子串1代表物資需求點，有n個基因位，對應(yīng)的數(shù)值(從1到K中隨機生成的自然數(shù)值)表示服務(wù)需求點的車輛，且1個需求點只對應(yīng)1輛救援車.子串2有n個基因位，對應(yīng)的數(shù)值(從1到n隨機生成的自然數(shù)值)表示需求點的排列順序.子串3有K個基因位，對應(yīng)的數(shù)值(從n+1到n+m隨機生成的自然數(shù)值)表示擁有車輛的救援中心的編號.

利用懲罰函數(shù)的方法對約束條件進行處理：如果約束不被滿足，將給出一個特定的懲罰值，它反映在目標函數(shù)和適應(yīng)度函數(shù)中，即將一個極大的數(shù)加入目標函數(shù)，以降低適應(yīng)值和被選擇的可能性.本文選擇對應(yīng)急救援車輛和應(yīng)急物資救援中心的容量約束以及時間窗口的約束增加懲罰值.

假設(shè)N1、N2、N3是很大的正數(shù)，針對約束(6)，在目標函數(shù)中加入

針對約束(7)，在目標函數(shù)中加入

針對約束(8)，在目標函數(shù)中加入

3.1.3 初始化種群和適應(yīng)度函數(shù)

種群規(guī)模設(shè)置為N，隨機產(chǎn)生初始種群，方法如下：根據(jù)需求點的數(shù)量、候選救援中心的數(shù)量以及車輛的數(shù)量等，使得染色體的每個基因位都隨機產(chǎn)生1個自然數(shù)，從而隨機產(chǎn)生1條染色體，判斷是否滿足車輛容量、救援中心的容量限制以及時間窗約束.若滿足，則保留；若不滿足，則另外生成1條染色體.循環(huán)往復(fù)，直到生成N條染色體.針對上述的雙目標不確定LRP優(yōu)化模型，采用加權(quán)法處理，2個目標的權(quán)重分別是ω1和ω2，且ω1+ω2=1.因此目標函數(shù)變?yōu)?/p>

minF=ω1F1/minF1+ω2F2/minF2.

加入懲罰值之后的目標函數(shù)為

minF*=ω1F1/minF1+ω2F2/minF2+s(1)+s(2)+s(3).

由于目標函數(shù)為Z=minF*，所以取適應(yīng)度函數(shù)g(x)=Mmax-Z，其中Mmzx是一個非常大的正數(shù)，因此染色體對應(yīng)的目標函數(shù)值越小其適應(yīng)度就越大.

3.1.4 交叉和變異操作

高職學(xué)生的英語基礎(chǔ)相對較弱，跨文化知識欠缺，習(xí)慣性用中文的思維和模式交際，文化“休克”現(xiàn)象時有發(fā)生；在傳播本土文化時，失語現(xiàn)象嚴重；對合作辦學(xué)的中小國家的文化缺乏了解。

為了保持群體的多樣性，對染色體中的各個字串進行交叉和變異的操作.由于子串1、2、3分別包含了不一樣的信息，所以對3個子串采取的交叉方法和變異方法也不同.對子串2采取交叉方法為部分匹配交叉，變異方法為逆轉(zhuǎn)變異；對子串1和3采取的交叉方法為雙點交叉，變異方法為對換變異.

3.1.5 選擇操作

本文利用精英保留以及輪盤賭相結(jié)合的選擇方法，即在下一代的種群生成時，先將上一代的種群中適應(yīng)度最高的個體直接保留到下一代種群，并且用這些個體替換上一代種群中經(jīng)過交叉和變異之后所產(chǎn)生的新一代種群中適應(yīng)度最低的個體；采用輪盤賭的方法在當代種群中選擇新一代種群中的其他個體.

3.1.6 算法終止條件

當算法的迭代次數(shù)達到程序預(yù)先設(shè)置的最大迭代次數(shù)，則終止運算，即假設(shè)預(yù)先設(shè)定MAXGEN為遺傳算法的最大迭代次數(shù)，當算法迭代次數(shù)大于MAXGEN 時，則算法結(jié)束.

3.2 算例分析

假設(shè)有10個需求點，編號為1～10；有3個候選的救援中心，編號為11～13；有3輛不同型號的車.救援中心的容量以及建設(shè)成本見表1，各需求點的需求量為不確定線性變量見表2，救援車輛的各個參數(shù)見表3，各節(jié)點之間的運輸時間為不確定線性變量見表4.

表1 待選救援中心的參數(shù)Tab.1 Data of candidate relief centers

表2 應(yīng)急物資需求點的參數(shù)Tab.2 Data of points needing emergency materials

表3 救援車輛的參數(shù)Tab.3 Data of rescue vehicles

表4 2節(jié)點之間的時間參數(shù)Tab.4 Time data between two nodes

本文采用MATLAB軟件進行編程，迭代次數(shù)設(shè)置為300，初始種群設(shè)置為40，交叉概率Pc=0.8，變異概率Pm=0.1，此時取時間權(quán)重ω1=0.6，成本權(quán)重ω2=0.4，預(yù)設(shè)的置信水平α1=α2=0.95,程序運行50次，顯示計算的結(jié)果相對比較穩(wěn)定，選擇的救援中心均為11、12和13，得到目標函數(shù)收斂于1.017 5，對應(yīng)最優(yōu)的時間為214 min，最低成本為25 145元.當?shù)螖?shù)增加時，目標函數(shù)值是收斂的.對應(yīng)的配送中心選址和車輛分配結(jié)果為:救援中心11、12 和13被啟用，使用3輛車進行運輸，其中車輛3分配給救援中心11，車輛1分配給救援中心12，車輛2分配給救援中心13.需求點的服務(wù)順序和配送路徑分別為：車輛1的路徑為12-7-4-6-11；車輛2的路徑為13-3-8-10-13；車輛3的路徑為11-5-1-2-9-11.

目標函數(shù)收斂速度較快，在100代時可求得最優(yōu)解，滿足模型的快速求解要求.如果模型中置信水平發(fā)生改變，經(jīng)濟成本和配送時間也會發(fā)生改變，其中經(jīng)濟成本隨置信水平增大而增大，總的配送時間隨置信水平增大而減少.這是因為置信水平增大，則應(yīng)急救援中對車輛容量以及救援中心容量的約束更加嚴格，因此選中的救援中心數(shù)量隨之增多，且啟用的車輛數(shù)也隨之增多，導(dǎo)致應(yīng)急救援的經(jīng)濟成本增大；同時，救援中心以及車輛數(shù)增加，會使得需求點的需求能夠得到快速的響應(yīng)，從而縮短應(yīng)急時間.所以在應(yīng)急物資配送優(yōu)化問題中，要根據(jù)災(zāi)情和實際情況給出合適的置信水平，保證時效的同時降低經(jīng)濟成本.

4 結(jié)論與展望

考慮到自然災(zāi)害造成的不確定性，本研究認為需求點的需求量和救援車輛的行駛時間是不確定變量且其分布是正則的，以配送救援物資的總時間最少和配送系統(tǒng)總經(jīng)濟成本最小為目標，提出了不確定雙目標機會約束LRP模型，以此對應(yīng)急物流配送系統(tǒng)進行分析和決策.采用加權(quán)法和懲罰函數(shù)的思想對模型的目標進行處理，利用遺傳算法得到模型的解，給出數(shù)值例子對模型的有效性進行驗證，算例表明配送時間與置信水平成正相關(guān)，而成本與置信水平成負相關(guān).因此，在決策中管理者必須根據(jù)實際情況給出合理的置信水平，以保證應(yīng)急物資及時配送，并控制經(jīng)濟成本.

本研究并未考慮多種配送方式、需求為動態(tài)情形的配送以及多級配送中心的配送.在后續(xù)的研究中，考慮不確定因素影響，建立多級配送中心，多種車型以及多種運輸方式聯(lián)合的形式進行配送和動態(tài)需求下的多階段的不確定配送模型，以期更快解決實際救援問題并完善不確定理論成果.此外，本研究利用已有的遺傳算法進行求解，并未對算法進行改進，之后將算法也作為一個新方向進行研究.