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

（華中科技大學(xué) 管理學(xué)院，武漢 430074）

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

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

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

1 模型建立

1.1 問題描述

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

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

圖1 應(yīng)急物流網(wǎng)絡(luò)LRP示意圖

模型假設(shè)：

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

（2）每個(gè)應(yīng)急物流配送中心有若干個(gè)不同類型的運(yùn)輸車輛，車輛有容量限制。

（3）每個(gè)應(yīng)急物資需求點(diǎn)只由1輛車提供服務(wù)，并具有一定的時(shí)間窗限制。

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

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

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

1.2 變量與符號(hào)說明

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

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

S=｛A｝∪｛B｝——應(yīng)急物流網(wǎng)絡(luò)中所有節(jié)點(diǎn)集合

V｛k|k=1，2，…，K｝——運(yùn)輸車輛集合

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

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

dab——點(diǎn)a（a∈S）與點(diǎn)b（b∈S）之間距離

Ck——車輛k（k∈V）的固定運(yùn)營(yíng)成本

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

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

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

tr——車輛在需求點(diǎn)r（r∈A）處的服務(wù)時(shí)間

LTr——需求點(diǎn)r（r∈A）處最遲必須得到服務(wù)的時(shí)間

Tbk——車輛k（k∈V）到達(dá)點(diǎn)b（b∈S）的時(shí)間，Tbk=Tak+tabzabk+ta，當(dāng)b∈B時(shí)，Tbk=0

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

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

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

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

1.3 模型建立

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

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

2 模型求解

2.1 雙目標(biāo)處理

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

對(duì)雙目標(biāo)LRP模型的目標(biāo)做以下處理：

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

2.2 遺傳算法設(shè)計(jì)

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

2.2.1 編碼設(shè)計(jì) 染色體利用配送中心、應(yīng)急物資需求點(diǎn)以及應(yīng)急運(yùn)輸車輛號(hào)來編碼，用的是自然數(shù)編碼的方式。染色體編碼方式如表1所示。

表1 染色體編碼方式

染色體第1段有n個(gè)基因位，n指需求點(diǎn)個(gè)數(shù)，1個(gè)需求點(diǎn)與1個(gè)車號(hào)對(duì)應(yīng)，表示需求點(diǎn)與車輛的分配關(guān)系，由1～k的自然數(shù)，隨機(jī)生成1個(gè)，表示每個(gè)基因位，k為車輛數(shù)量，或者說線路的條數(shù)；第2段同樣是n位，是由1～n的隨機(jī)自然數(shù)排列成，表示路線中需求點(diǎn)排列的順序；第3段是k位，是1～r的自然數(shù)，r是候選配送中心數(shù)量，表示每輛車屬于哪個(gè)應(yīng)急物流配送中心，染色體總長(zhǎng)為n+n+k。

舉例說明，若候選配送中心有3個(gè)，需求點(diǎn)有15個(gè)，可用車輛數(shù)量是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，根據(jù)上文，染色體有4段，共15個(gè)需求點(diǎn)，那么染色體的第1段就有15位，為2-1-1-3-2-3-1-2-1-3-2-1-1-2-3，1個(gè)需求點(diǎn)與1個(gè)車號(hào)對(duì)應(yīng)，可見1，2，3都出現(xiàn)了，說明3輛車都用到，關(guān)系如表2所示。

表2 需求點(diǎn)與車輛對(duì)應(yīng)的關(guān)系

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

可見，應(yīng)急物流配送中心1和2出現(xiàn)了，表示選擇它們作為物流中心，1，2號(hào)車屬于應(yīng)急物流配送中心1，3號(hào)車屬于應(yīng)急物流配送中心1。

表3 車輛與應(yīng)急物流配送中心關(guān)系

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

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

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

則約束式（3）可轉(zhuǎn)化為

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

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

令

則約束式（3）轉(zhuǎn)化為H1（X）≤Qk。

在目標(biāo)中加入f（1）=M1max｛H1（X）—Qk，0｝，M1是很大的數(shù)，同理對(duì)約束式（4）進(jìn)行處理，為H2（X）≤Wixi。在目標(biāo)中加入

M2是很大的數(shù)，時(shí)間窗式（5）為

則目標(biāo)就轉(zhuǎn)化為

2.2.3 適應(yīng)度函數(shù) 由于本文的目標(biāo)函數(shù)是最小值，故要最大化適應(yīng)度函數(shù)，通過如下方式得到：適應(yīng)函數(shù)值=A/目標(biāo)函數(shù)值，這里A是個(gè)常數(shù)。目標(biāo)函數(shù)U=minZ，則適應(yīng)度函數(shù)f（x）=1/U。

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

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

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

（3）變異方法。進(jìn)行基因變異操作時(shí)，同樣要將選址與路徑基因分開進(jìn)行。由于選址與路徑基因不同，這里將選址基因用對(duì)換變異法，路徑基因用逆轉(zhuǎn)變異法。

（4）停止準(zhǔn)則。本文采用停止準(zhǔn)則為算法的遺傳代數(shù)達(dá)到程序設(shè)置的最大迭代數(shù)，則停止運(yùn)算。

3 算例分析

3.1 運(yùn)算結(jié)果分析

用Solomon的RC題目的RC208部分?jǐn)?shù)據(jù)作為算例。方法為：從RC208的100個(gè)數(shù)據(jù)中隨機(jī)選3個(gè)作備用的配送中心，隨機(jī)生成1～100中的3個(gè)數(shù)，將原數(shù)據(jù)庫(kù)中的這3個(gè)編號(hào)的需求點(diǎn)坐標(biāo)視為備用應(yīng)急物流配送中心的坐標(biāo)。同理得到20個(gè)需求點(diǎn)。

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

表4 候選配送中心信息

表5 運(yùn)輸車輛信息

表6 需求點(diǎn)的數(shù)據(jù)

表7 各點(diǎn)之間的運(yùn)輸時(shí)間μ表

表8 各點(diǎn)之間的運(yùn)輸時(shí)間σ表

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

選出1和2作為應(yīng)急物流配送中心，運(yùn)輸車輛3，4，5，10屬于應(yīng)急物流配送中心1，運(yùn)輸車輛1，2，6，7，8屬于應(yīng)急物流配送中心2，也得出了每個(gè)車輛配送需求點(diǎn)的順序。

圖6 目標(biāo)值收斂圖

表9 車輛路線結(jié)果

3.2 敏感性分析

下面對(duì)運(yùn)算結(jié)果進(jìn)行敏感性分析，改變模型中置信水平的取值，應(yīng)急時(shí)間和應(yīng)急成本的權(quán)重，得出的運(yùn)算結(jié)果也不同，結(jié)果變化如表10所示。

表10 不同置信水平及權(quán)重下的運(yùn)算結(jié)果

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

圖7 應(yīng)急時(shí)間與成本隨權(quán)重變化趨勢(shì)圖

當(dāng)時(shí)間和成本的權(quán)重一定，而置信水平增大時(shí)，表示要求物資送達(dá)需求點(diǎn)的時(shí)間滿足時(shí)間窗的概率越大，故應(yīng)急時(shí)間越短，同時(shí)也表示物資運(yùn)送量滿足配送中心容量與車輛容量的概率越大，因此，選中的配送中心個(gè)數(shù)越多，且啟用的車輛個(gè)數(shù)也增多，導(dǎo)致應(yīng)急總成本越大，配送中心增多，能夠快速地響應(yīng)需求點(diǎn)對(duì)物資的需求，從而使得應(yīng)急時(shí)間也變短。

由此可見，置信水平和時(shí)間成本權(quán)重的取值是非常重要的，決策者應(yīng)該在應(yīng)急過程的不同階段根據(jù)實(shí)際狀況對(duì)參數(shù)賦予合適的值，這樣得到的方案結(jié)果是可行有效的。

4 結(jié)語

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

但是本研究也存在不足之處，實(shí)際應(yīng)急物流中可能涉及到多種物資，而且運(yùn)輸?shù)姆绞娇赡苁嵌嗍铰?lián)運(yùn)。因此，在后續(xù)的研究中，將進(jìn)一步考慮多物資與多式聯(lián)運(yùn)的LRP模型，從而為應(yīng)急物資調(diào)度決策提供更充分更科學(xué)的依據(jù)。