付德強(qiáng)， 陳煜舟， 萬曉榆

(1.電子商務(wù)與現(xiàn)代物流重慶高校市級重點實驗室，重慶 400065；2.重慶郵電大學(xué) 經(jīng)濟(jì)管理學(xué)院，重慶 400065)

?

自然災(zāi)害風(fēng)險下區(qū)域應(yīng)急儲備設(shè)施選址可靠性研究

付德強(qiáng)1,2， 陳煜舟1， 萬曉榆1

(1.電子商務(wù)與現(xiàn)代物流重慶高校市級重點實驗室，重慶 400065；2.重慶郵電大學(xué) 經(jīng)濟(jì)管理學(xué)院，重慶 400065)

自然災(zāi)害發(fā)生時，為了保證區(qū)域應(yīng)急儲備系統(tǒng)的服務(wù)不被中斷，考慮設(shè)施被破壞數(shù)目的發(fā)生概率并提供備份庫存，以加強(qiáng)應(yīng)急儲備系統(tǒng)的可靠性。模型采用非支配排序遺傳算法(NSGA-II)進(jìn)行求解，產(chǎn)生一組選址決策方案。以四川省八大城市的人口及運(yùn)輸距離為輸入數(shù)據(jù)的仿真結(jié)果表明，與一般模型比較，本文考慮可靠性的選址模型能更好抵御自然災(zāi)害造成的中斷影響，并且能獲得更優(yōu)的應(yīng)急響應(yīng)滿意度、多重覆蓋或總成本的單目標(biāo)值。因此，在地震等災(zāi)害的破壞風(fēng)險下，該模型可成為應(yīng)急儲備設(shè)施可靠選址的有效工具。

物流設(shè)施選址；可靠性研究；NSGA-II；區(qū)域應(yīng)急儲備

0 引言

保證系統(tǒng)運(yùn)作的可靠性一直是物流和供應(yīng)鏈領(lǐng)域關(guān)注的焦點。近年來，由于各類災(zāi)害的頻繁發(fā)生，國際上管理科學(xué)、運(yùn)籌學(xué)界引發(fā)了設(shè)計具有抵御中斷風(fēng)險的物流或供應(yīng)鏈系統(tǒng)的研究熱潮[1]。從廣義上講，系統(tǒng)可靠性指的是其中各個組成元素在任何時刻都能有效運(yùn)轉(zhuǎn)的性質(zhì)。本文將具有可靠性的物流設(shè)施系統(tǒng)規(guī)定為：因為外部干擾(自然災(zāi)害)導(dǎo)致部分設(shè)施服務(wù)中斷，卻仍能及時有效地滿足物流需求，并且擁有經(jīng)濟(jì)的運(yùn)作費(fèi)用和運(yùn)輸費(fèi)用的物流系統(tǒng)。

Snyder et al.[2]最先對如何構(gòu)建具有可靠性的選址模型進(jìn)行了探討，他們發(fā)現(xiàn)如果將災(zāi)害發(fā)生的概率事先考慮入的選址模型中，可以大大減少不考慮災(zāi)害而造成的損失；為此他們設(shè)計的P-中值模型不僅能抵御中斷風(fēng)險，而且擁有最小化的成本。但是P-中值模型假設(shè)災(zāi)害發(fā)生時每個設(shè)施都有相同的失效概率，這顯然不符合實際。 Aboolian et al.[3], Shen et al.[4]和Cui et al.[5]放松這一假設(shè)，分別設(shè)計了失效概率與設(shè)施相關(guān)的模型；但采取這種方法往往會導(dǎo)致計算期望運(yùn)輸成本的算式高度的不線性，使得設(shè)計有效算法以及計算大樣本的困難加大。另一類方法是采用情景遍歷的方法[6]，考慮所有可能的中斷事件；但是其缺陷也是很明顯的：當(dāng)設(shè)施的數(shù)目不斷增大時，模型的求解難度也將更大。此外，以上的各類模型都假定當(dāng)服務(wù)設(shè)施被中斷時，其所支持的需求點將自動轉(zhuǎn)向下一個最近的設(shè)施獲取服務(wù)；然而在現(xiàn)實中，每個服務(wù)設(shè)施的庫存是固定，沒有預(yù)先的安排，該設(shè)施將很難為新的需求進(jìn)行服務(wù)。

針對現(xiàn)有的研究及不足，本文考慮遍歷不同設(shè)施失效數(shù)目的情景，并按經(jīng)驗分配概率，以降低情景的總個數(shù)，建立線性的算式；并在事前就為可能中斷的需求提供備份庫存?，F(xiàn)階段我國有關(guān)應(yīng)急儲備的研究，如李靜等[7]，郭子雪等[8]和陸相林等[9]，未有考慮可靠性的問題，本文擬在付德強(qiáng)等[10]的研究基礎(chǔ)上建立具有可靠性的多目標(biāo)應(yīng)急儲備選址模型：設(shè)立應(yīng)急響應(yīng)時間滿意度、備份覆蓋以及成本的三個優(yōu)化目標(biāo)，采用NSGA-II算法對多目標(biāo)模型進(jìn)行求解；由于該算法高效、易應(yīng)用的特點[11]，所設(shè)計的算例可在多項式時間內(nèi)求解完成。

1 模型的建立

1.1 問題描述及參數(shù)定義

本文假設(shè)在一個區(qū)域內(nèi)需求點的集合為I，用i標(biāo)識；應(yīng)急物資儲備庫的候選地址集合為J，用j標(biāo)識；wi代表需求點i的應(yīng)急需求權(quán)重，可根據(jù)人口權(quán)重進(jìn)行估計；用dij代表運(yùn)輸距離，c代表單位運(yùn)輸費(fèi)用；fj代表儲備庫j的單位儲備庫建設(shè)費(fèi)用，sj為單位庫存維持成本。

設(shè)tij為儲備庫j到需求點i所需的時間，可用dij近似代替；設(shè)f(x)代表每個需求點i在應(yīng)急情景下，應(yīng)急需求得到響應(yīng)的時間滿意度函數(shù)。本文參考馬云峰等[12]的研究，采用凹凸時間滿意度函數(shù)，其具體的公式可參考相應(yīng)的文獻(xiàn)。

設(shè)決策變量yijhr在情景hr下i被設(shè)施j服務(wù)時取1，否則為零；xj在候選設(shè)施j處建設(shè)儲備庫時取1，否則取零；uihr在情景hr下需求點i在被二次覆蓋時取1，否則為零。

1.2 假設(shè)條件

模型的假設(shè)條件如下：

(1)本文假設(shè)應(yīng)急儲備庫儲存和運(yùn)輸?shù)膽?yīng)急物資為同一種類型。

(2)區(qū)域內(nèi)各個儲備庫的運(yùn)作是獨(dú)立的，災(zāi)害發(fā)生時破壞一個設(shè)施不會影響其他設(shè)施的運(yùn)作。

(3)如果風(fēng)險發(fā)生時某個應(yīng)急物資儲備庫被破壞，則該設(shè)施將再無法提供任何服務(wù)，需求點需轉(zhuǎn)向其他節(jié)點以獲得應(yīng)急物資。

1.3 模型的建立

(1)

(2)

(3)

(4)

(5)

Yijhr≤xj(1-shrj) ?i∈I,?j∈J,?hr∈Hr,?r∈R

(6)

(7)

Yijhr,xj,uihr∈{0,1} ?i∈I,?j∈J,?hr∈Hr,?r∈R

(8)

式子(1)代表在不同數(shù)量設(shè)施中斷的概率下，最大化需求點的應(yīng)急響應(yīng)時間滿意度；式(2)代表最大化對需求點的備份覆蓋期望值；式(3)代表最小化應(yīng)急物資儲備庫的各項成本，其中包括建設(shè)設(shè)施的固定成本，維持庫存Qj的庫存費(fèi)用，以及實施應(yīng)急物資需求配送的期望運(yùn)輸成本；式(4)代表實際建設(shè)儲備庫數(shù)目小于候選物資儲備庫總數(shù)目的50%，以節(jié)約成本提高效率；式(5)代表對需求點超額覆蓋的約束，使得當(dāng)ujhr=1時，需求點i至少被儲備庫覆蓋兩次，當(dāng)uihr=0時，需求點被儲備庫至少覆蓋一次；這一約束保證了當(dāng)設(shè)施被中斷后，其所覆蓋的需求點可由其他正常運(yùn)轉(zhuǎn)的設(shè)施提供服務(wù)；式(6)代表只有在j建立了物資儲備庫且沒有被損毀喪失功能時才能給i提供服務(wù)；式(7)確定設(shè)施j的總庫存，總庫存量不僅包括正常情況下對需求點提供的物資，也包含預(yù)防其他設(shè)施中斷的備份庫存；式(8)限定決策變量都為0-1整數(shù)變量。

2 算法設(shè)計

NSGA-II，又稱非支配排序遺傳算法，為現(xiàn)今學(xué)界公認(rèn)求解多目標(biāo)規(guī)劃問題十分有效的優(yōu)化算法，它由印度人KalyanmoyDebetal.[14]于2002年提出。NSGA-II算法的特點是采取了使用精英策略的非支配排序算法(non-dominatedsorting)，并設(shè)計擁擠距離(crowdingdistance)來求取優(yōu)良并多樣的多目標(biāo)規(guī)劃非劣解集。在一般NSGA-II流程基礎(chǔ)上，本文為以上模型設(shè)計的算法流程如下：

(1)遺傳編碼，設(shè)計染色體

由于本文所建規(guī)劃的決策變量都為0-1整數(shù)變量，故可直接將染色體上每段取值0或1，以代表是否建立設(shè)施或提供服務(wù)，則種群中每個個體編碼設(shè)為：Individual=(x1,…,x|I|,y11h1,…,y|I||J||HmR|,u1h1,…,u|I||HmR|)。

(2)初始化種群，滿足約束條件

根據(jù)染色體編碼規(guī)則產(chǎn)生數(shù)量為pop的初始種群，并使每條染色體上的編碼滿足約束規(guī)則，即：總共建設(shè)的設(shè)施數(shù)小于候選設(shè)施數(shù)目的一半，部分需求點的服務(wù)覆蓋大于兩次，以及在設(shè)施沒有建設(shè)或被破壞的情形下將無法提供需求。以上都可通過編碼過程中限定基因的取值來實現(xiàn)。

(3)計算適應(yīng)度，進(jìn)行首次快速非支配排序及計算擁擠距離

NSGA-II中采用快速非支配排序算法來解決在多個目標(biāo)值間進(jìn)行權(quán)衡優(yōu)化的問題。在每次算法中，每個種群的每個個體都會被排序，并分在不同的非支配前端集合(non-dominatedfronts)中：在同一個非支配前段集合中，每個個體并不絕對占優(yōu)因而組成一個front值相同的集合；而在不同的集合間，front值較低的集合一定比front值較高的集合在所有目標(biāo)函數(shù)值上都更優(yōu)。通過以上的排序分類，每個集合通過front值反映了個體的適應(yīng)度，以更加適合多目標(biāo)規(guī)劃的特性。

在進(jìn)行快速非支配排列的同時，NSGA-II同時也根據(jù)每個個體的每個目標(biāo)函數(shù)值來計算其擁擠距離：通過計算相近的解間的相對目標(biāo)函數(shù)差值，來求得擁擠度值，以此來判斷一個種群中某個特定解附近的解集密度；通常一個具有較小擁擠度值的解會被更多的解包圍，因而顯示較高的多樣性特征。

在進(jìn)行了以上非支配排序和擁擠度操作后，NSGA-II結(jié)合front值和擁擠度值的大小對種群中個體進(jìn)行適應(yīng)排序：首先擁有較低front值的個體排在前面，隨后擁有相同front值的個體按照擁擠度值進(jìn)行逆序排列。

(4)選擇、重組、變異產(chǎn)生子代

從父輩中抽取一定數(shù)目的個體進(jìn)行重組，重組概率設(shè)為γ，由于本文中基因編碼采用0-1編碼，選擇兩點交叉的重組方法。子代種群產(chǎn)生后，還需要更進(jìn)一步的對子代進(jìn)行變異操作，變異概率為μ，采用按位變異的方法實現(xiàn)。

(5)重新對子代進(jìn)行度量，選擇最優(yōu)產(chǎn)生新的種群

對新的種群重新進(jìn)行非支配排序以及計算擁擠度，對擁有較高排位的個體進(jìn)行保留而去除較低排位的個體，以此產(chǎn)生新一代大小為pop的種群。

(6)種群優(yōu)化結(jié)束，取得非劣解集

重復(fù)以上的生成新種群—計算適應(yīng)度—重組變異的過程，直到迭代到達(dá)一定標(biāo)準(zhǔn)停止(本文選擇迭代至100代為停止條件)，最終得到最優(yōu)的非劣解集。

3 算例設(shè)計以及結(jié)果分析3.1 算例設(shè)計

設(shè)I=(1,2,3,4,5,6,7,8)，分別順序代表四川省的八大城市：成都，達(dá)州，綿陽，宜賓，瀘州，內(nèi)江，遂寧，樂山；設(shè)J=(1,2,3,4,5,6,7,8)，代表由上述八大城市組成的設(shè)施候選集合；設(shè)單位運(yùn)輸成本c=2萬元/一百公里·萬個物資，固定建設(shè)費(fèi)用fj=350萬元，單位庫存維持成本sj=2萬元/萬個(數(shù)據(jù)來源：根據(jù)民政部《救災(zāi)物資儲備庫建設(shè)標(biāo)準(zhǔn)》中相關(guān)數(shù)據(jù)平均推算)；最大設(shè)施失效數(shù)目R=2；表1顯示了城市間距離dij以及人口權(quán)重wi的取值。本文采用NSGA-II對模型進(jìn)行求解時，設(shè)pop=300，迭代次數(shù)n=100，重組概率γ=0.9，變異概率μ=0.1。

3.2 帕累托選址方案

根據(jù)以上設(shè)計的算例，利用matlab軟件對模型進(jìn)行仿真，并采用NSGA-II算法求解，運(yùn)行環(huán)境為：CPU3.30GHz,內(nèi)存4G。最終得到的解集在各空間中的分布如圖1所示，可看出這是一組滿足多目標(biāo)決策問題部分最優(yōu)條件的Pareto解集。使用NSGA-II算法對300個個體進(jìn)行100次的迭代后，解集來到了最終的Pareto前端。在由80個點形成的弧形區(qū)域中，沒有一個方案可以在三個目標(biāo)函數(shù)值上全部占優(yōu)。比如在(成本，時間滿意度)象限中，擁有較低成本的方案在時間滿意度上的值也較低，這與要達(dá)到更及時的應(yīng)急響應(yīng)必須進(jìn)行更大投資的現(xiàn)實相符合；而在其他象限中，在兩個目標(biāo)值上占優(yōu)的方案卻在第三個目標(biāo)上處于劣勢，從而證明了由算例得出的多目標(biāo)解集的可效性。

表1 八大候選城市間的運(yùn)輸距離以及人口權(quán)重值表 距離單位：公里

由求得的帕累托解集，決策者可根據(jù)自身的主觀判斷來選取方案進(jìn)行選址：如果對成本目標(biāo)值較為敏感，可在弧區(qū)下部尋找方案；如關(guān)心備份覆蓋的范圍更大，可從弧區(qū)上部選取；而如果關(guān)心應(yīng)急響應(yīng)的滿意度，需從弧區(qū)前部挑選；決策者也可以設(shè)計主觀評價工具，為三個目標(biāo)值賦予權(quán)值，將多目標(biāo)值整合為單目標(biāo)值并選取最滿意的方案。

圖1 最終的帕累托解集在各個空間的分布圖

3.3 可靠性模型對比一般模型

以下將本文考慮可靠性的模型與不考慮災(zāi)害風(fēng)險的一般模型在各單目標(biāo)規(guī)劃中進(jìn)行比較。所謂一般模型，即不考慮各種中斷情景及其發(fā)生的概率，且沒有公式(6)中(1-ahrj)的約束；如果設(shè)施被中斷，其服務(wù)的各個需求點將轉(zhuǎn)向提供備份覆蓋的設(shè)施，否則應(yīng)急需求將無法得到滿足。具體比較結(jié)果見表2,3,4。

表2 災(zāi)害發(fā)生時考慮可靠性的模型與一般模型時間滿意度值比較

表3 災(zāi)害發(fā)生時考慮可靠性的模型與一般模型多重覆蓋值比較

表4 災(zāi)害發(fā)生時考慮可靠性的模型與一般模型成本值比較

從以上各表的對比可以看出，災(zāi)害發(fā)生時考慮可靠性的模型比一般模型能獲得更優(yōu)的單目標(biāo)值，并能在部分設(shè)施服務(wù)被中斷的情形下，滿足全部需求點的應(yīng)急需求，從而保證了應(yīng)急儲備系統(tǒng)的可靠性。如表2中，當(dāng)應(yīng)急儲備系統(tǒng)中設(shè)施4遭到中斷時，一般模型得到的方案(4,6,7)無法滿足設(shè)施8的需求，而考慮可靠性的模型可以保證所有的應(yīng)急需求得到滿足；當(dāng)設(shè)施6遭到中斷時，兩個模型都可以滿足全部需求，但考慮可靠性的模型能比一般模型獲得更高的時間滿意度值；從表3和表4中也可以看出，本文設(shè)計的模型可以得到更加可靠的選址方案，并且在滿意度或多重覆蓋的單目標(biāo)上也可以獲得較優(yōu)的值。

4 結(jié)論

本文考慮解決自然災(zāi)害可能導(dǎo)致應(yīng)急儲備系統(tǒng)服務(wù)被中斷的問題，建立了一個可以保證可靠性的應(yīng)急儲備庫多目標(biāo)選址模型。模型中引入不同失效數(shù)目概率并對各情形進(jìn)行枚舉，較前人的方法更易于求解；采用在事前備份庫存的方法，以更符合真實情況。本文根據(jù)模型特點設(shè)計NSGA-II算法進(jìn)行求解，并采用真實數(shù)據(jù)仿真得到帕累托解集，驗證了模型的有效性，并為決策者提供了可行的方案。最后，在與一般模型的比較后發(fā)現(xiàn)，考慮可靠性的模型能更好的抵御災(zāi)害中斷造成的影響，在保證應(yīng)急儲備系統(tǒng)正常運(yùn)轉(zhuǎn)的同時，也能提供更及時、經(jīng)濟(jì)、高效的物資調(diào)配。

本文未來的研究方向包括：(1)本文假設(shè)各個儲存設(shè)施的運(yùn)作是獨(dú)立的，而災(zāi)害發(fā)生時，破壞是可以傳遞的，所以設(shè)施間應(yīng)存在關(guān)聯(lián)。(2)本文假設(shè)一個儲備設(shè)施被損毀后就會完全喪失所有的運(yùn)作性能，而在實際情況下，這種損失并不一定是完全的，設(shè)施可能只是喪失了部分的性能。

[1] Snyder L V, Atan Z, Peng P, et al. OR/MS models for supply chain disruptions: a review[J]. Available at SSRN 1689882, 2012.

[2] Snyder L V, Daskin M S. Reliability models for facility location: the expected failure cost case[J]. Transportation Science, 2005, 39(3): 400- 416.

[3] Aboolian R, Cui T, Shen Z J M. An efficient approach for solving reliable facility location models[J]. INFORMS Journal on Computing, 2012, 25(4): 720-729.

[4] Shen Z J M, Zhan R L, Zhang J. The reliable facility location problem: Formulations, heuristics, and approximation algorithms[J]. INFORMS Journal on Computing, 2011, 23(3): 470- 482.

[5] Cui T, Ouyang Y, Shen Z J M. Reliable facility location design under the risk of disruptions[J]. Operations Research, 2010, 58(4-part-1): 998-1011.

[6] Peng P, Snyder L V, Lim A, et al. Reliable logistics networks design with facility disruptions[J]. Transportation Research Part B: Methodological, 2011, 45(8): 1190-1211.

[7] 李靜,趙林度.基于時間滿意的應(yīng)急物資儲備庫雙容量限制選址模型[J].東南大學(xué)學(xué)報:自然科學(xué)版,2007,37(2):393-396.

[8] 郭子雪,齊美然,張強(qiáng).基于區(qū)間數(shù)的應(yīng)急物資儲備庫最小費(fèi)用選址模型[J].運(yùn)籌與管理,2010,(1):15-20.

[9] 陸相林,侯云先.基于設(shè)施選址理論的中國國家級應(yīng)急物資儲備庫配置[J].經(jīng)濟(jì)地理,2010,30(7):1091-1095.

[10] 付德強(qiáng),張偉,等.基于NSGA-II的災(zāi)害隨機(jī)環(huán)境下應(yīng)急儲備庫多目標(biāo)選址決策模型研究[J].軟科學(xué),2013,27(11):48-52.

[11] 衛(wèi)田,范文慧.基于NSGAII的物流配送中車輛路徑問題研究[J].計算機(jī)集成系統(tǒng)制造,2008,14(4):778-784.

[12] 馬云峰,張敏,楊珺.物流設(shè)施選址問題中時間滿意度函數(shù)的定義及應(yīng)用[J].物流技術(shù),2005,(9):26-29.

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

The Study on the Reliable Model for the Regional Emergency Storage Facility under the Risk of Natural Disaster

FU De-qiang1,2, CHEN Yu-zhou1, WAN Xiao-yu1

(Key Laboratory of Online-business and Modern Logistic, Chongqing 400065, China; Chongqing University of Posts and Telecommunications, Chongqing 400065, China)

In order to protect services of regional emergency storage from being interdicted by large-scale natural disasters, we consider the probabilities of the number of facilities being interdicted and store back-up storage to enhance the reliability of location decision. The model is solved with Non-dominated Sorting Genetic Algorithm(NSGA)and a Pareto solution is obtained. The results from the instance of eight major cities in Si-Chuan province suggest that, compared to the generic model, our reliable model can deter the interdiction effect brought by natural disasters in a better way; it can also get better emergency response satisfaction value, multiple coverage value and total cost. Thus, under the chance of being interdicted by earthquake, this model should be a reliable tool to locate the emergency storage facilities.

logistic facility location; reliability study; NSGA-II; regional emergency storage

2014- 09-24

國家自然科學(xué)基金資助項目(60905066/F030707)；重慶市教委自然科學(xué)基金資助項目(KJ070509)；重慶郵電大學(xué)青年科學(xué)研究項目(A2012-95)；電子商務(wù)與現(xiàn)代物流重慶高校市級重點實驗室開放基金資助項目(ECML201411)

付德強(qiáng)(1976-)，男，博士，研究方向：物流與供應(yīng)鏈管理；陳煜舟(1988-)，男，碩士，研究方向：應(yīng)急物流規(guī)劃。

F251.2

A

1007-3221(2015)03- 0014- 06