王海軍，杜麗敬，馬士華

?

震后應(yīng)急物流系統(tǒng)中雙目標(biāo)開放式選址：路徑問題模型與算法研究

王海軍，杜麗敬，馬士華

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

災(zāi)害發(fā)生后，應(yīng)急物資調(diào)度是救援工作核心。應(yīng)急配送中心選址以及車輛路徑安排在應(yīng)急物資調(diào)度中仍然有很大的挑戰(zhàn)。本文以平均車輛運(yùn)輸時(shí)間最小化和系統(tǒng)總成本最小化為目標(biāo)，建立了基于多車型、雙目標(biāo)的開放式選址-路徑問題混合整數(shù)規(guī)劃模型。采用基于非支配解排序的遺傳算法求解，得出包括若干非支配解的Pareto最優(yōu)解集，為決策者提供多樣化選擇。最后以“汶川”地震為實(shí)例進(jìn)行研究，結(jié)果論證了該模型與算法的有效性以及在實(shí)踐中的可行性。

應(yīng)急物流；多目標(biāo)優(yōu)化；開放式選址-路徑問題；基于非支配解排序的遺傳算法

0 引言

近年來地震災(zāi)害發(fā)生越來越頻繁，成為嚴(yán)重危害人類生命的自然災(zāi)害之一，如2008年汶川地震, 2010年1月海地地震、2010年2月智利地震與2011年4月日本大地震等。災(zāi)害發(fā)生后短期內(nèi)對(duì)應(yīng)急物資產(chǎn)生較大需求，將有限的資源及時(shí)、合理地分配到受災(zāi)點(diǎn)至關(guān)重要。其中，應(yīng)急配送中心選址與車輛路線安排是應(yīng)急物資調(diào)度決策的核心。一方面需要在合適地點(diǎn)建立一定數(shù)目與規(guī)模的應(yīng)急配送中心，以存儲(chǔ)、分撥和中轉(zhuǎn)來自全國各地的救災(zāi)物資；另一方面需要派遣合適的車輛選擇合理的路線以將應(yīng)急物資從配送中心配送至災(zāi)區(qū)。兩者又是高度相關(guān)的[1]，因此應(yīng)急管理人員需要對(duì)應(yīng)急物資調(diào)度集成優(yōu)化管理。

在應(yīng)急配送中心選址方面，劉春林等為滿足單一受災(zāi)點(diǎn)對(duì)應(yīng)急物資的需求，以“時(shí)間最短”、“出救點(diǎn)最少”為目標(biāo)建立模型，并提出了應(yīng)急配送中心選擇問題的模糊規(guī)劃方法[2,3]；Sheu以需求滿足率最大和總成本最小為目標(biāo)建立動(dòng)態(tài)規(guī)劃模型[4]，采用模糊聚類優(yōu)化方法將受災(zāi)點(diǎn)進(jìn)行優(yōu)先級(jí)分類，將應(yīng)急物資優(yōu)先運(yùn)送到優(yōu)先級(jí)較高的受災(zāi)點(diǎn)。在應(yīng)急車輛路線安排方面，Haghani以最小化系統(tǒng)總成本為目標(biāo)，建立了多模式應(yīng)急物資配送網(wǎng)絡(luò)流問題模型[5]，采用基于拉格朗日松弛的方法將模型劃分為車輛流和商品流兩個(gè)子問題求解；Fiedrich以地震發(fā)生后前三天總死亡人數(shù)最小為目標(biāo)，建立了考慮多車型的應(yīng)急物資分配模型[6]，采用模擬退火與禁忌搜索相結(jié)合的方法求得問題的滿意解；?zdamar以需求未滿足率最小化為目標(biāo)建立多商品動(dòng)態(tài)混合整數(shù)規(guī)劃模型[7]，松弛容量約束轉(zhuǎn)化為車輛流與商品流兩個(gè)子問題求解；Vitoriano 等最先建立了基于成本、時(shí)間、優(yōu)先權(quán)以及可靠性因素的多目標(biāo)優(yōu)化模型，采用目標(biāo)規(guī)劃的方法求解，實(shí)現(xiàn)對(duì)車型選擇以及車輛路線優(yōu)化[8]；另外，魏航等給出了時(shí)變隨機(jī)網(wǎng)絡(luò)下有應(yīng)急限制期限制的應(yīng)急路徑選擇算法[9]。在應(yīng)急配送中心選址與車輛路線安排集成優(yōu)化管理方面，Yi W 等以服務(wù)延遲最小化為目標(biāo)建立了集成的選址-配送模型[10]，并提出了基于網(wǎng)絡(luò)流的車輛路線求解算法；曾敏剛等以系統(tǒng)總成本最小為單一目標(biāo)建立選址-路徑優(yōu)化模型，并采用選址與路線安排分開的兩階段啟發(fā)式算法來求解，最后以實(shí)例驗(yàn)證模型可行性[11]。

從國內(nèi)外文獻(xiàn)分析看出，現(xiàn)有應(yīng)急物流方面文獻(xiàn)中配送中心選址與車輛路線安排通常分開研究，或者將選址-路徑問題分為選址和路線安排兩個(gè)子問題求解，無法實(shí)現(xiàn)集成優(yōu)化；模型以單一目標(biāo)函數(shù)為主，鮮有同時(shí)考慮其他相關(guān)因素。本文主要研究震后受災(zāi)點(diǎn)多物資需求下允許拆分配送基于時(shí)間與成本最小化的配送中心選址與多車型車輛路線安排問題，定義為雙目標(biāo)開放式選址-路徑問題(Open Location Routing Problem, OLRP)。地震發(fā)生后應(yīng)急路網(wǎng)不斷變化，當(dāng)前配送中心或許已不適合使用，因此應(yīng)急物流中車輛不再返回出發(fā)點(diǎn)，而是停留在其所服務(wù)的最后一個(gè)受災(zāi)點(diǎn)，等待下一個(gè)任務(wù)，即開放式車輛路徑。開放式車輛路徑問題在傳統(tǒng)物流中有專門的研究[12,13]，應(yīng)急物流選址路徑問題中研究還比較少。地震發(fā)生后，短期內(nèi)對(duì)應(yīng)急物資產(chǎn)生大量需求。當(dāng)一個(gè)車輛無法滿足某受災(zāi)點(diǎn)應(yīng)急物資的需求時(shí)，允許其他車輛再次為其配送物資，即拆分配送(Split Delivery)，在應(yīng)急物資調(diào)度中使用拆分配送更符合實(shí)際[14]。

1 雙目標(biāo)OLRP模型

1.1 模型假設(shè)

(1) 候選配送中心與受災(zāi)點(diǎn)地理位置關(guān)系已知，且道路的可用情況可以通過探測技術(shù)實(shí)時(shí)獲得。(2) 每個(gè)車輛允許同時(shí)裝載不同物資，同樣，不同物資允許由同一個(gè)車輛運(yùn)輸。(3) 僅考慮當(dāng)前網(wǎng)絡(luò)中車輛可以到達(dá)的受災(zāi)點(diǎn)，需要飛機(jī)、輪船等其他運(yùn)輸方式才能到達(dá)的受災(zāi)點(diǎn)不做考慮。

1.2 問題描述

應(yīng)急物資調(diào)度雙目標(biāo)的OLRP中，應(yīng)急物流網(wǎng)絡(luò)表示為=(,)，如圖1所示。其中包括兩個(gè)子集：候選應(yīng)急物資配送中心集合與受災(zāi)點(diǎn)集合，為可用鏈路集合。為各點(diǎn)之間距離矩陣()，滿足三角不等式，即對(duì)任意有。=()為地震災(zāi)害發(fā)生后可用鏈路上最大可以行使的速度矩陣()，具體數(shù)值根據(jù)道路的受損程度進(jìn)行估計(jì)?？紤]不同類型車輛進(jìn)行物資配送，v表示車輛的平均行使速度，c表示車輛的單位距離成本，L表示車輛的最大容積。需要配送的應(yīng)急物資為帳篷和水，考慮受災(zāi)點(diǎn)一天的需求量。需要決策的問題是建立合適數(shù)量與位置的配送中心，在配送中心和車輛容量的限制下選擇合適的車輛并優(yōu)化相應(yīng)的路線將應(yīng)急物資從配送中心運(yùn)輸?shù)礁鱾€(gè)受災(zāi)點(diǎn)。服務(wù)結(jié)束時(shí)車輛停留在其所服務(wù)的最后一個(gè)節(jié)點(diǎn)，等待下次任務(wù)的分配；當(dāng)某受災(zāi)點(diǎn)處應(yīng)急物資需求不能由單一車輛滿足時(shí)，允許拆分配送。即如圖1中，車輛1從候選配送中心0出發(fā)，依次為受災(zāi)點(diǎn)1、2提供應(yīng)急物資，其中受災(zāi)點(diǎn)2為其所服務(wù)的最后一個(gè)受災(zāi)點(diǎn)，車輛1停留在受災(zāi)點(diǎn)2處，不返回配送中心0；若受災(zāi)點(diǎn)2仍然有尚未滿足的應(yīng)急物資需求，則允許其它車輛為其提供服務(wù)。

圖1 應(yīng)急物流系統(tǒng)中OLRP示意圖

1.3 符號(hào)說明

模型中所用到的其他符號(hào)和變量定義如下：

其中決策變量為：

1.4 模型建立

應(yīng)急物資優(yōu)化調(diào)度的目標(biāo)從兩個(gè)方面來度量，其一時(shí)間上的有效性，以平均車輛路線運(yùn)輸時(shí)間最小化表示；其二是成本上的經(jīng)濟(jì)性，以最小化系統(tǒng)總成本表示。兩個(gè)目標(biāo)是相互沖突的，為最小化所有車輛平均路線運(yùn)輸時(shí)間，將建立相對(duì)較多的配送中心，增加了成本；要減少系統(tǒng)成本，一方面選擇較少的配送中心，另一方面選擇單位運(yùn)輸成本較低的車輛等，將導(dǎo)致車輛運(yùn)輸時(shí)間增加。

平均車輛路線運(yùn)輸時(shí)間最小化可使得應(yīng)急物資盡可能快地配送給受災(zāi)人員，提高受災(zāi)人員存活率。在震后OLRP中，車輛停留在其所服務(wù)的最后一個(gè)受災(zāi)點(diǎn)，不返回配送中心，因此車輛在其服務(wù)路線上的運(yùn)輸時(shí)間為車輛從應(yīng)急配送中心出發(fā)到達(dá)其所服務(wù)的最后一個(gè)受災(zāi)點(diǎn)的時(shí)間長度。

考慮到災(zāi)害發(fā)生初期應(yīng)急資金的籌集不足，為最大程度地合理利用資金，系統(tǒng)成本最小化為另一個(gè)需要考慮的因素。震后OLRP系統(tǒng)中，總成本包括配送中心的建設(shè)費(fèi)用和車輛運(yùn)輸費(fèi)用兩個(gè)方面。其中，應(yīng)急配送中心的建設(shè)費(fèi)用為；車輛運(yùn)輸費(fèi)用為車輛從配送中心出發(fā)到達(dá)其所服務(wù)最后一個(gè)受災(zāi)點(diǎn)的運(yùn)輸費(fèi)用，也即車輛在其服務(wù)路線所有鏈路上的行駛費(fèi)用，表示為，則系統(tǒng)總運(yùn)輸費(fèi)用為。設(shè)表示系統(tǒng)總成本，表示如下：

應(yīng)急物流應(yīng)急物資調(diào)度OLRP優(yōu)化模型如下：

Min(3)

Min(4)

S.t.

,(6)

(7)

，(9)

(10)

,，(12)

(13)

=0或1,,(15)

，，，(16)

目標(biāo)函數(shù)(3)為平均車輛路線運(yùn)輸時(shí)間最小化，目標(biāo)函數(shù)(4)表示系統(tǒng)總成本最小化。

約束(5)表示在受災(zāi)點(diǎn)與配送中心處應(yīng)急物資流量均衡。約束(6)為在各點(diǎn)處車流量均衡。約束(7)表示配送結(jié)束后停留在各點(diǎn)的車輛數(shù)之和等于系統(tǒng)內(nèi)最初可用車輛數(shù)。約束(8)表示路線上最后一個(gè)點(diǎn)必須由車輛提供服務(wù)。約束(9)表示服務(wù)結(jié)束時(shí)一個(gè)車輛可以且僅可以停留在一個(gè)節(jié)點(diǎn)上。約束(10)為車輛路線連續(xù)性約束。其一，車輛從配送中心出發(fā)，則最后不再返回；其二，除路線上最后一個(gè)受災(zāi)點(diǎn)外，車輛駛出點(diǎn)必為車輛駛?cè)朦c(diǎn)；其三，在車輛停留在其所服務(wù)的最后一個(gè)節(jié)點(diǎn)，不再駛出。約束(11)要求配送到受災(zāi)點(diǎn)處應(yīng)急物資的量不超過其需求量，且不能為負(fù)。約束(12)表示向受災(zāi)點(diǎn)配送所有應(yīng)急物資總量不能超過系統(tǒng)內(nèi)應(yīng)急物資的可用量。約束(13)表示車輛所裝載的應(yīng)急物資量不能超過其容量。約束(14)-(15)為0-1整數(shù)變量約束。約束(16)為非負(fù)約束。

2 算法設(shè)計(jì)

求解多目標(biāo)優(yōu)化問題典型的方法是通過加權(quán)法、約束法與混合法等將多目標(biāo)轉(zhuǎn)化為單目標(biāo)，再使用求解單目標(biāo)的傳統(tǒng)方法求解[8,15,16]。在這種方法下要取得不同權(quán)重下多個(gè)解，需要多次運(yùn)行程序，并利用這些單目標(biāo)問題最優(yōu)解去近似Pareto最優(yōu)解集。近年來，越來越多的研究者應(yīng)用多目標(biāo)進(jìn)化算法求解多目標(biāo)問題，如Pareto包絡(luò)選擇算法[17]，強(qiáng)度Pareto進(jìn)化算法[18]，多目標(biāo)分散搜索算法[19,20]等。2002年Deb提出了基于非支配解排序的遺傳算法(Non-dominated Sorting Genetic Algorithm II，NSGA-II)，NSGA-II結(jié)合了非支配解排序機(jī)制、基于擁擠密度排序機(jī)制與遺傳算法交叉變異操作算子，能夠獲得更好的Pareto最優(yōu)解集[21]。由于LRP是NP-hard問題[22]，OLRP是LRP拓展，因此采用精確算法很難求解。本文采用NSGA-II求解，并采用多目標(biāo)分散搜索 (Multi-objective Scatter Search, MOSS)算法進(jìn)行比較。

2.1 多目標(biāo)最優(yōu)解概念

現(xiàn)實(shí)中許多問題需要同時(shí)優(yōu)化幾個(gè)目標(biāo)，而且這些目標(biāo)之間通常是相互沖突的。僅考慮一個(gè)目標(biāo)值，不能判斷所對(duì)應(yīng)優(yōu)化方案的優(yōu)劣。因此在多目標(biāo)優(yōu)化中產(chǎn)生了Pareto最優(yōu)解集概念。

2.2 NSGA-II設(shè)計(jì)

另外，文中采用的比較算法即MOSS算法也是以種群進(jìn)化為基礎(chǔ)的優(yōu)化算法。種群初始化后選擇高質(zhì)量與多樣化的個(gè)體進(jìn)入?yún)⒖技ㄟ^組合與改進(jìn)操作產(chǎn)生種群；對(duì)種群中個(gè)體進(jìn)行非劣解與擁擠密度排序，選擇參考集。相對(duì)NSGA-II而言，在選擇機(jī)制上，其對(duì)參考集與中對(duì)應(yīng)位置個(gè)體目標(biāo)值比較，選擇目標(biāo)值占優(yōu)的個(gè)體進(jìn)入下一代參考集。

圖2 NSGA-II 框架圖

2.2.1染色體編碼與初始化

本文中每個(gè)染色體有三個(gè)子串組成，且分別進(jìn)行交叉和變異操作。令表示車輛總數(shù)，表示候選配送中心總數(shù)，表示受災(zāi)點(diǎn)個(gè)數(shù)，三個(gè)子串的產(chǎn)生方式如下：

子串1 =()；

子串2 =(1,, [1,])；

子串3 =()；

子串1為個(gè)車輛的隨機(jī)排列；子串2有個(gè)基因位，每個(gè)基因位取值為1到的隨機(jī)整數(shù)；子串3為個(gè)受災(zāi)點(diǎn)的隨機(jī)排列。由此可見每個(gè)染色體長度為++。子串1中第一個(gè)基因位所代表車輛從子串2中第一個(gè)基因位所代表的配送中心出發(fā)，首先到達(dá)子串3第一個(gè)基因位代表的受災(zāi)點(diǎn)。若該受災(zāi)點(diǎn)的需求沒有超過車輛容量，則繼續(xù)配送下一基因位代表的受災(zāi)點(diǎn)；否則，該車輛停止在其所服務(wù)的最后一個(gè)受災(zāi)點(diǎn)。子串1中第二個(gè)基因位所代表的車輛從子串3中下一個(gè)基因位代表的受災(zāi)點(diǎn)開始提供救災(zāi)物資，以此類推。如果所有受災(zāi)點(diǎn)均有車輛提供服務(wù)，但車輛還有剩余且受災(zāi)點(diǎn)需求未全部滿足，則從子串3的第一個(gè)基因位開始重復(fù)以上過程。這種方式下，為盡可能滿足受災(zāi)點(diǎn)需求，一個(gè)受災(zāi)點(diǎn)可以被多個(gè)車輛服務(wù)，即拆分配送。

2.2.2變異、交叉操作與精英選擇機(jī)制

圖3 快速非支配解排序偽代碼

為了增加解的多樣性，提高Pareto最優(yōu)解集質(zhì)量，對(duì)染色體中三個(gè)子串分別進(jìn)行變異與交叉操作。本文主要采用倒置變異、以及單點(diǎn)交叉與雙點(diǎn)交叉相結(jié)合的交叉方式。NSGA-II最大的特點(diǎn)是其精英選擇機(jī)制，一方面采用快速非支配解排序方法保留性能較好的解，使得算法加快收斂于Pareto最優(yōu)解集；另一方面利用基于擁擠密度排序的方法確保解的多樣性。

(1) 快速非支配解排序

本文中根據(jù)每個(gè)染色體所對(duì)應(yīng)平均車輛運(yùn)輸時(shí)間和系統(tǒng)總成本兩個(gè)目標(biāo)函數(shù)值對(duì)種群中染色體進(jìn)行排序，得出其所屬于的Pareto前沿等級(jí)，稱之為非支配解排序。前沿包含當(dāng)前種群中所有Pareto最優(yōu)解，前沿包含除去前沿到之后的所有非支配解?？焖俜侵渑判蚓唧w參考文獻(xiàn)[17]，其偽代碼如圖3所示。

(2) 擁擠密度排序

假設(shè)在解空間中，某個(gè)解與其周圍最近的前個(gè)解的距離分別為，則該解的擁擠密度為。在本文中，即考慮當(dāng)前種群中每個(gè)解對(duì)擁擠密度的影響，以避免由于分布不均勻而對(duì)擁擠密度做出錯(cuò)誤判斷。擁擠密度用來對(duì)屬于同一Pareto前沿的解進(jìn)行評(píng)價(jià)，保留擁擠密度較大的解可以提高算法的多樣性。

2.3 NSGA-II步驟

圖4 NSGA-II流程圖

本文中NSGA-II流程圖如圖4所示。具體步驟如下：

步驟4: 計(jì)算R中每個(gè)染色體所對(duì)應(yīng)的目標(biāo)函數(shù)值。

步驟5: 對(duì)R中所有染色體對(duì)應(yīng)的目標(biāo)函數(shù)值進(jìn)行快速 非支配解排序，得出Pareto前沿等級(jí)。

步驟7: 根據(jù)Pareto前沿等級(jí)及擁擠密度，從R中選擇個(gè)染色體組成p1，即為代染色體父體；

3 算例分析

圖5 受災(zāi)區(qū)域運(yùn)輸網(wǎng)絡(luò)

表1 受災(zāi)點(diǎn)應(yīng)急物資需求量

表2 候選配送中心參數(shù)

表3 車輛參數(shù)

表4 應(yīng)急物資參數(shù)

汶川地震造成至少6萬人死亡，數(shù)千萬人受傷，且公共設(shè)施如道路、橋梁等受到嚴(yán)重?fù)p害。本文主要研究地震后第一天受災(zāi)最為嚴(yán)重的11個(gè)區(qū)域。運(yùn)輸網(wǎng)絡(luò)拓?fù)鋱D如圖5所示，其中受災(zāi)點(diǎn)為1到11，候選配送中心為12(成都)、13(綿陽)與14(廣元)，另外15(劍閣)作為轉(zhuǎn)運(yùn)點(diǎn)，不考慮其需求。

表5 運(yùn)輸網(wǎng)絡(luò)參數(shù)

圖中有34個(gè)可用鏈路，越粗則行使的最大允許速度越大。 需要配送的應(yīng)急物資為帳篷和水，每個(gè)受災(zāi)點(diǎn)物資需求如表1所示；候選配送中心容量及固定建設(shè)費(fèi)用見表2；所使用車輛中大型卡車有10輛, 另有6輛中型卡車與9輛小型卡車，具體參數(shù)見表3。表4為兩種應(yīng)急物資相關(guān)參數(shù)。

運(yùn)輸網(wǎng)絡(luò)圖的詳細(xì)信息見表5，其中(，)表示所對(duì)應(yīng)兩點(diǎn)之間鏈路的距離(千米)及最大允許行使的速度(千米/時(shí))，‘-’ 表示沒有直接鏈路。前三行數(shù)據(jù)(1,2,3)表示3個(gè)候選配送中心與11個(gè)受災(zāi)點(diǎn)之間鏈路參數(shù)，其余表示11個(gè)受災(zāi)點(diǎn)之間鏈路參數(shù)。

3.1計(jì)算結(jié)果

本文采用Matlab?6.5對(duì)算法編程，所有的計(jì)算工作在同一臺(tái)計(jì)算機(jī)上完成，表6為所使用計(jì)算機(jī)的性能參數(shù)。經(jīng)過多次試驗(yàn)，NSGA-II控制參數(shù)設(shè)置為：種群規(guī)模=66, 變異概率p=0.1，交叉概率p=0.7。

對(duì)算法運(yùn)行結(jié)果中不合理因素修正后，具體配送方案如圖6與圖7所示。其中，圖6為基于目標(biāo)1所得近似最優(yōu)解解決方案，即最小化平均車輛路線行駛時(shí)間；圖7為基于目標(biāo)2所得近似最優(yōu)解解決方案，即最小化系統(tǒng)運(yùn)行總成本。受災(zāi)點(diǎn)處(，，)表示為其提供服務(wù)的三種類型(大、中、小)車輛數(shù)量。表7為兩種配送方案下各目標(biāo)值及受災(zāi)點(diǎn)需求滿足率。

表6 計(jì)算機(jī)配置參數(shù)

圖6 最小化平均車輛路線行駛時(shí)間方案

圖7最小化系統(tǒng)總成本方案

在平均車輛行駛時(shí)間最小化方案中，候選配送中心12, 13開啟，如圖6所示。車輛最長路線運(yùn)輸時(shí)間為8.3小時(shí)，為某一小型車輛從配送中心出發(fā)經(jīng)過點(diǎn)15為受災(zāi)點(diǎn)8配送應(yīng)急物資。距離配送中心較遠(yuǎn)的受災(zāi)點(diǎn)(如點(diǎn)1，4，5，6等)較多采用大型車輛，一方面，大型車輛速度較快，用較快車輛配送較遠(yuǎn)距離可以縮短行駛時(shí)間；另外大型車輛容積較大，可以盡可能滿足受災(zāi)點(diǎn)需求，減少配送次數(shù)。

為了最小化系統(tǒng)成本，圖7中僅有候選配送中心12(成都)被選作配送中心，候選配送中心13作為轉(zhuǎn)運(yùn)點(diǎn)。從表7看出方案二的固定建設(shè)費(fèi)用為10000元，方案一為25000元。小型車輛速度較慢，但是單位距離運(yùn)輸成本較低，因此使用小型車輛配送較遠(yuǎn)受災(zāi)點(diǎn)可以降低成本，如受災(zāi)點(diǎn)4(青川)、8(平武)。比較表10中兩種方案下受災(zāi)點(diǎn)需求滿足率可知：相對(duì)于方案一，方案二中距離配送中心較遠(yuǎn)的點(diǎn)需求滿足率較小；反之，較大。

另外，比較圖6與圖7，圖6所示方案選擇了更多最大允許行駛速度較大的鏈路，如5-9，12-11，8-4，8-15；相對(duì)而言，圖7選擇1-5，即最大允許行駛速度較小的鏈路。

表7 兩種目標(biāo)下Pareto最優(yōu)方案目標(biāo)值

3.2算法比較

使用NSGA-II與多目標(biāo)分散搜索算法(MOSS)兩種方法對(duì)實(shí)例進(jìn)行運(yùn)算，得出的帕累托最優(yōu)解集如圖8所示。從圖8中可以看出，NSGA-II對(duì)應(yīng)解集中有17個(gè)解，MOSS算法對(duì)應(yīng)解集有15個(gè)，且前者支配了后者。因此，決策者可以利用NSGA-II獲得選擇性更多、質(zhì)量更高的方案。

圖8 NSGA-II與MOSS算法所得非支配解集

表8 NSGA-II與MOSS所得最優(yōu)目標(biāo)值比較

表9 NSGA-II與MOSS運(yùn)行時(shí)間

另外，本文實(shí)例在兩種算法下所獲得的時(shí)間與成本最優(yōu)值如表8所示。NSGA-II中最小平均路線時(shí)間為2.88小時(shí)，相對(duì)于MOSS算法中3.53小時(shí)縮短了18.41%；前者系統(tǒng)總成本為28242元，相對(duì)于MOSS算法最小總成本減少了2961元。由此，NSGA-II可以獲得時(shí)間上更快、經(jīng)濟(jì)上更為可行的應(yīng)急物資調(diào)度方案。表9為兩種算法分別運(yùn)行15次之后平均運(yùn)行時(shí)間。NSGA-II在一分鐘之內(nèi)運(yùn)行結(jié)束，MOSS需要78秒，兩種算法均在有效的時(shí)間內(nèi)完成。

4 結(jié)論

地震一旦發(fā)生，短期內(nèi)對(duì)應(yīng)急物資產(chǎn)生大量需求，及時(shí)將應(yīng)急物資供應(yīng)到受災(zāi)區(qū)域是災(zāi)后救援工作的核心。災(zāi)后初期是救援工作的關(guān)鍵階段，盡快地滿足受災(zāi)人員需求能夠最大可能地減少人員傷亡。由于初期物資短缺、時(shí)間有限，管理者需要對(duì)應(yīng)急物資調(diào)度工作進(jìn)行統(tǒng)籌規(guī)劃、科學(xué)管理。一方面要選擇合適的應(yīng)急配送中心，存儲(chǔ)、中轉(zhuǎn)來自其他區(qū)域的救援物資；另一方面由于地震發(fā)生后道路、橋梁等基礎(chǔ)設(shè)施部分遭到破壞，因此需要優(yōu)化路網(wǎng)中救援車輛運(yùn)輸路線，以最小化物資配送時(shí)間和系統(tǒng)總成本。

本文研究了地震發(fā)生后不完全連通的路網(wǎng)下應(yīng)急配送中心選址與車輛路徑安排問題, 考慮了兩種(帳篷和水)應(yīng)急物資需求,以及三種類型運(yùn)輸車輛，在允許拆分配送的策略下建立了以平均車輛行駛時(shí)間和系統(tǒng)總成本為目標(biāo)的開放式選址-路徑問題數(shù)學(xué)模型。采用NSGA-II求解，得到包含多個(gè)支配解的Pareto解集，決策者可以根據(jù)實(shí)際情況和個(gè)人偏好選擇合適的物資調(diào)度方案。最后以“汶川地震”作為算例，驗(yàn)證了模型的合理性與算法有效性，對(duì)災(zāi)害后應(yīng)急物資調(diào)度有較大的實(shí)用價(jià)值。考慮災(zāi)后應(yīng)急物流網(wǎng)絡(luò)內(nèi)各因素的隨機(jī)性與動(dòng)態(tài)性，下一步將進(jìn)行基于時(shí)空網(wǎng)絡(luò)的多周期選址-路徑問題研究。

[1] Ballou RH, Masters JM. Commercial software for locating warehoused and other facilities [J]. Journal of business logistics, 1993, 14(2): 70-107.

[2] 劉春林，何建敏，盛昭瀚.應(yīng)急系統(tǒng)多出救點(diǎn)選擇問題的模糊規(guī)劃方法[J].管理工程學(xué)報(bào)，1999，13(4): 23-24.

[3] 劉春林，施建軍，李春雨.模糊應(yīng)急系統(tǒng)組合優(yōu)化方案選擇問題的研究[J].管理工程學(xué)報(bào)，2002，16(2): 25-28.

[4] Sheu JB. An emergency logistics distribution approach for quick response to urgent relief demand in disasters [J]. Transportation Research Part E: Logistics and Transportation Review, 2007, 43: 687-709.

[5] Haghani A, Oh SC. Formulation and solution of a multi-commodity multi-modal network flow model for disaster relief operation [J]. Transportation research part A: Policy and Practice, 1996, 30(3): 231-250.

[6] Fiedrich F, Gehbauer F, Rickers U. Optimized resource allocation for emergency response after earthquake disasters [J]. Safety Science, 2000, 35: 41-57.

[7] ?zdamar L, Ekinci E, Kü?ükyazici B. Emergency logistics planning in natural disasters [J]. Annals of operations research, 2004, 129(14): 217-245.

[8] Vitoriano B, Ortu?o M. T, Tirado G,. A multi-criteria optimization model for humanitarian aid distribution [J]. Journal of Global Optimization, 2011, 51(2): 189-208.

[9] 魏航，劉璇.時(shí)變隨機(jī)網(wǎng)絡(luò)下基于成功和風(fēng)險(xiǎn)的應(yīng)急路徑選擇研究[J].管理工程學(xué)報(bào)，2010，24(2)：68-74．

[10] Yia W, ?zdamar L. A dynamic logistics coordination model for evacuation and support in disaster response activities [J]. European Journal of Operational Research, 2007, 179( 3): 1177-1193

[11] 曾敏剛，崔增收，余高輝.基于應(yīng)急物流的減災(zāi)系統(tǒng)LRP研究[J].中國管理科學(xué)，2010，18(2)：75-80．

[12] Schrange L. Formulation and structure of more complex/realistic routing and scheduling problems [J]. Networks, 1981, 11(2): 229-232.

[13] Sariklis D, Powell S. A heuristic method for the open vehicle routing problem [J]. Journal of the Operation Research Society, 2000, 51(5): 564-573.

[14] Dror M, Trudeau P. Split Delivery Routing [J]. Naval Research Logistics, 1990, 37(3):383-402.

[15] Tzeng GH, Cheng HJ, Huang TD. Multi-objective optimal planning for designing relief delivery systems [J]. Transportation research part E, 2007, 43: 673-686.

[16] Chanta S, Mayorga ME, McLay LA. Improving emergency service in rural areas: a bi-objective covering location model for EMS systems [J]. Annual operation research, 2011, DOI 10.1007/s10479-011-0972-6.

[17] Corne DW, Knowles JD, Oates MJ. The Pareto envelope-based selection algorithm for multi-objective optimization.Parallel Problem Solving from Nature PPSN VI (Lecture Notes in Computer Science), 2000, 1917: 839-848.

[18] Paraskevi SG, Loannis AP, Chris TK,. Multi-objective evolutionary emergency response optimization for major accidents [J]. Journal of Hazardous Materials, 2010, 178: 792-803.

[19] Tavakkoli-Moghaddam R, Makui A, Mazloomi Z. A new integrated mathematical model for a bi-objective multi-depot location-routing problem solved by a multi-objective scatter search algorithm [J]. Journal of Manufacturing Systems, 2010, 29: 111-119.

[20] Antonio J. Nebro, Francisco Luna, Enrique Alba. New ideas in applying scatter search to multiobjective optimization [J]. Evolutionary Multi-Criterion Optimization, 2005, 3410: 443-458.

[21] Deb K., Pratab A, Agarwal S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-II [J]. IEEE Transactions on Evolutionary Computation, 2002, 6:182-197.

[22] 汪壽陽，趙秋紅，夏國平.集成物流管理系統(tǒng)中定位-運(yùn)輸路線安排問題的研究[J].管理科學(xué)學(xué)報(bào)，2000, 3(2)：69-74．

Model and Algorithms for Integrated Open Location and Routing Problem in Emergency Logistics under Earthquake

WANG Hai-jun, DU Li-jing, MA Shi-hua

(School of Management, Huazhong University of Science and Technology, Wuhan 430074, China)

Earthquakes have already been major fatal disasters that threaten humankind’s life. Rescue efforts can reduce the impact of damage after an earthquake occurs. Distribution of relief goods is the focus of rescue work. Emergency managers need to find an optimal schedule for distributing relief to disaster areas with limited time and funds. The location of distribution centers and routes scheduling of vehicles are vital to the relief items distribution, which remains challenging in emergency logistics research and related fields.

In this paper we focus on the coordination of location of distribution centers (DCs) and vehicle routes scheduling for distributing relief items to disaster areas efficiently. The problem can be classified as an integrated open location-routing problem (OLRP) with bi-objective. In emergency logistics, with higher uncertainty and dynamic the former DC may not work in the next order in OLRP. Each dispatching vehicle stays at the last disaster areas it serves without returning to DC until the next mission is received. With large demand for relief items in disaster areas after earthquake, the capacity of vehicles may not be enough for fulfillment. Thus, disaster areas can be served more than once. This is called split delivery, which is a big feature from typical vehicle routing problem. It makes the research problem more realistic.

In the first part, we review literature on relief items distribution in emergency logistics. There is a lack of studies on the design of mathematical models and solution algorithms for OLRP in a post-disaster situation.

In the second part, we describe the bi-objective OLRP in emergency logistics. Sleeping bags and water are relief items mainly considered in this study. The relief items are considered for one day needed by disaster areas. Split deliveries are required once the demands of disaster area break the capacity of the serving vehicle. Two objectives are considered: (1) minimizing the average vehicle route time, and (2) minimizing the total cost, including the fixed establishing costs of DCs and the vehicle travelling cost. Objective (1) and (2) are conflict with each other. In the test instance section, we take this fact into account by considering the two objectives simultaneously. Mixed integer programming mathematic models of OLRP are presented.

In the third part, Non-dominated Sorting Genetic Algorithm (NSGA-II) is designed to solve the bi-objective model.Series of sets solutions called generations are computed by NSGA-II. Each generation consists of several individuals called chromosomes. Each chromosome denotes one strategy for relief distribution. Fast-Non-Dominated-Sort and Crowding-Density–Sort are used to select the elites into the offspring, which can guarantee the convergence and diversity of Pareto optimal solutions.

In the fourth part, ‘Wenchuan earthquake’ is conducted to illustrate the efficiency and potential advantages of the proposed method. The approximate optimal DC location and vehicles scheduling according to the above two objectives (minimize the average route travelling time and the total cost) are given. The results show that DC location and vehicle scheduling depend on each other. To minimize the average vehicle travelling time, more DCs are located, and vehicles with higher normal velocity are chosen. The higher normal velocity, the higher cost per kilometers the vehicles are. Thus, the total cost including the fixed location cost and vehicle travelling cost will increase. In contrary, to minimize the total cost fewer DCs are open and vehicles with lower cost per unit of travelling are scheduled. The solutions will support decision makers to direct the distribution of relief items under adverse conditions.

Comparisons are made between NSGA-II and Multi-Objective Scatter Search (MOSS) algorithm. The results have shown that the approximate Pareto optimal solutions obtained by NSGA-II dominate most of all the solutions obtained by MOSS, which verifies the strengths of the NSGA-II in solving multi-objective problems. This provides a profound basis to extend our method to more realistic assumptions.

Finally, it is expected that the proposed relief items distribution approach can improve the performance of emergency logistics managements. In the next step, multi-periods OLRP will be considered.

emergency logistics; multi-objective optimization; open location and routing problem; non-dominated sorting genetic algorithm

中文編輯：杜 ??；英文編輯：Charlie C. Chen

F542

A

1004-6062(2016)02-0108-08

10.13587/j.cnki.jieem.2016.02.013

2013-04-08

2013-12-22

國家自然科學(xué)基金資助項(xiàng)目（70972020，71372135）

王海軍(1970 — )，男，江蘇如東人。華中科技大學(xué)管理學(xué)院副教授，博士生導(dǎo)師，研究方向：物流與供應(yīng)鏈管理。