考慮失靈風險的可靠性設施選址問題綜述

周 愉 峰

(1.重慶工商大學 商務策劃學院，重慶 400067;2.重慶工商大學 重慶市發(fā)展信息管理工程技術研究中心，重慶 400067)

?

考慮失靈風險的可靠性設施選址問題綜述

周 愉 峰1,2

(1.重慶工商大學 商務策劃學院，重慶 400067;2.重慶工商大學 重慶市發(fā)展信息管理工程技術研究中心，重慶 400067)

摘要：可靠性設施選址問題是當前選址研究領域的一類前沿性問題，分析了設施失靈風險的來源和分類，以及可靠性設施選址相關問題的研究及特點；從決策者風險權衡角度，將可靠性設施選址問題分為最小期望成本問題和最壞情形成本問題，其中前者又分為可靠性無容量約束的固定費用選址問題和可靠性P-中位問題，分別從建模及求解角度對這些問題的研究現(xiàn)狀進行了綜述；最后，總結了可靠性設施選址問題的研究現(xiàn)狀和啟示，并提出了未來的發(fā)展方向。

關鍵詞：設施選址；設施失靈；可靠性；綜述

0引言

設施選址是設施規(guī)劃的一個重要環(huán)節(jié)，國內外已有大量學者對其進行了研究[1-2]。但無容量限制的固定費用選址問題(Uncapacitated Fixed-charge Location Problem，UFLP)、P-中位問題(P-median Problem，PMP)等經典的設施選址問題都有一個隱含的假設：設施一旦建立，將一直運行而不失靈，即設施是完全可靠的?？墒聦嵣?，由于自然災害、人為災害、罷工、所有權更替及其他因素，設施失靈(Facility Disruptions，或Facility Failures)現(xiàn)象時有發(fā)生。當分派的設施發(fā)生失靈時，客戶不得不選擇距離更遠的設施為其服務，這就可能導致運輸成本增加，由此產生了可靠性設施選址問題(Reliability Facility Location Problem，RFLP)。

傳統(tǒng)的設施選址問題通常不會改變設施網絡的拓撲結構，但RFLP由于在選址階段考慮了失靈風險，設施網絡的拓撲結構是可變的。RFLP最早由Snyder等[3]提出，研究如何選擇低成本且可靠的設施點。由于設施選址屬于戰(zhàn)略性決策問題，短期內不會改變，故在設計階段就考慮失靈風險很有必要，而且這樣可以大大降低應急成本，因而研究RFLP具有非常重要的意義。

近年來，考慮設施失靈風險的RFLP引起了國外一些學者的重視，已成為當前選址研究領域的前沿性問題。本文旨在回顧這一問題的研究現(xiàn)狀和特點，并分析現(xiàn)有研究中的局限性和未來的發(fā)展趨勢。希望通過本文能引起國內學術界對該問題研究的重視，并結合我國經濟社會發(fā)展中的實際問題開展相關的研究。

1設施選址問題中的失靈風險與可靠性

1.1失靈風險的來源與分類

設施選址問題中失靈風險的研究源于對供應鏈中斷風險(Disruption Risks)的研究。Kleindorfe等[4]按照風險來源將供應鏈中斷事件分為3類：自然災害、運營事故、恐怖主義及政治不穩(wěn)定性。其中自然災害主要包括地震、颶風和暴風雪等；運營事故包括機器故障和系統(tǒng)性問題，如停電、罷工、關鍵供應商的倒閉等。Chen等[5]從供應鏈構成角度，將供應鏈中斷分為供應中斷、協(xié)調中斷和需求中斷3類。供應中斷可能是由設施容量約束和設施可靠性等因素造成；需求中斷和協(xié)調中斷通常由需求、運輸時間和成本的不確定性引起。在某些情況下，即使設施在運行也可能被認為處于失靈狀態(tài)，如擁塞，這種短期失靈在現(xiàn)實中很常見[6]。

1.2可靠性概念、分類

由于設施失靈風險的存在，就產生了系統(tǒng)可靠性問題。關于系統(tǒng)可靠性的定義在不同的學科領域不盡相同，但大多側重于考察系統(tǒng)在規(guī)定的條件下和規(guī)定的時間內完成規(guī)定功能的能力。在設施選址研究領域，大部分學者將可靠性定義為“在系統(tǒng)內部某些部分失靈的情況下，整個系統(tǒng)仍能良好運行的能力”[7]。設施系統(tǒng)可靠與否的一個標準在于“系統(tǒng)運行對設施中斷具有一定的彈性和穩(wěn)健性”[8]。

處理可靠性問題時一般把設施失靈風險分為兩類：一類假設失靈風險是由外部因素(停電，罷工等)引起的，將它看成是系統(tǒng)的外生變量；另一類假設失靈風險是由于客戶需求和擁塞等因素造成的，失靈風險是系統(tǒng)的內生變量[9]。

2RFLP相關問題的研究及其差異性

在RFLP研究之前，許多研究者對其他相關問題進行了大量研究。這些問題與RFLP既有聯(lián)系，又有區(qū)別，主要包括以下幾個方面。

2.1供應不確定下的選址問題

早期針對該問題的研究主要考慮由于隨機需求引起的設施擁塞現(xiàn)象，通常借助大量過剩供應來保證系統(tǒng)的可用性。近年來，由設施失靈引起的供應不確定性越來越受到關注，因而考慮這一情況下的設施選址問題也逐漸得到重視[10]。RFLP是對此類問題的延伸與擴展，可有效解決隨機設施失靈情況下的設施選址及客戶分派問題。

2.2防御性選址問題

網絡中關鍵設施一旦遭到攻擊而失靈，會導致整個網絡系統(tǒng)性能的重大損失，由此產生了防御性R-中斷型中位問題(R-interdiction Median Problem with Fortification，RIMF)，即識別出網絡中R個關鍵設施，并保證在這些設施中斷后每個需求點仍有一個后備設施為其服務，從而提高系統(tǒng)的抗攻擊能力和安全性。文獻[11-15]都對RIMF進行過研究。不過，這類問題重在識別現(xiàn)存網絡中的關鍵設施及其中斷后的補救措施，而RFLP則是在選址階段就考慮設施的可靠性，因此前者往往需要付出更高的成本。

另有一些文獻是研究基礎設施系統(tǒng)中保護性裝置的最優(yōu)安裝位置問題，以降低可能的破壞事件帶來的影響。如Carr等[16]研究了供水網絡中用來檢測是否有蓄意注入污染物的傳感器的最優(yōu)安裝位置優(yōu)化模型。James等[17]研究了電網中保護性裝置的最優(yōu)安裝位置問題，以減少由于意外引起的斷電時間。截流(Flow Interception)模型常被用來解決保護性設施選址問題，如Gendreau等[18]和Teodorovic等[19]都采用截流模型研究運輸網絡中檢查站的選址問題，以盡量避免危險和降低風險。

2.3網絡可靠性問題

網絡可靠性理論主要研究網絡(如通訊網絡、電網等)在遭遇擁塞或中斷等引起隨機失效后仍然保持連通的概率最大化?，F(xiàn)有研究大多考慮網絡中斷現(xiàn)象發(fā)生在線路上，較少考慮網絡節(jié)點的失靈或兩者兼有的情況[20]。鑒于給定網絡的可靠性計算較困難，現(xiàn)有研究通常尋找具有期望性能(如二連通、k連通、特殊的環(huán)結構等)且構建成本最低的網絡[21]。網絡可靠性模型與RFLP模型之間的區(qū)別在于：前者主要關心網絡的連通性，只考慮網絡構建成本，不涉及網絡中斷后引起的成本；而后者同時考慮兩類成本，并保證網絡遭遇中斷后仍然連通。

綜上所述，雖然RFLP與上述問題有一定聯(lián)系，卻有著明顯的區(qū)別。RFLP的特點是在選址階段就考慮了設施的可靠性且只需增加少量系統(tǒng)成本，從而保證設施一旦失靈后系統(tǒng)仍然能良好運行。

3RFLP建模及求解

從決策者風險權衡的角度，可以將現(xiàn)有對RFLP的研究分為最小期望成本模型(Minimum Expected Cost Model)和最壞情形成本模型(Worst-case Cost Model)兩類。其中，最小期望成本模型是當前研究的重點，主要源于對無容量限制的固定費用選址問題(UFLP)和P-中位問題(PMP)這兩類經典的設施選址問題的擴展，分別稱為可靠性無容量限制的固定費用選址問題(Reliability Uncapacitated Fixed-charge Location Problem，RUFLP)和可靠性P-中位問題(Reliability P-median Problem，RPMP)。

3.1最小期望成本模型

3.1.1RUFLP模型

經典的UFLP給定以下條件：已知客戶點集，候選設施點集，在每個候選點構建設施的固定成本，以及從每個設施點到每個客戶點的單位運輸成本。目標是確定待建設施點的數(shù)量、位置以及將每個客戶點分派給一個設施，使設施構建成本與運輸成本之和最小。

Snyder等[3]擴展了經典的UFLP，在模型中考慮設施失靈風險，首次提出了RUFLP，研究考慮設施失靈風險條件下的設施選址及其客戶分派，以尋求設施開設成本、日常運行成本和期望失靈成本之和最小的選址方案。該問題描述如下：

設I是客戶集(i∈I)；J是候選設施集合(j∈J)；NF表示不會失靈的候選設施集，F(xiàn)是可能會失靈的候選設施集，有NF∪F=J。hi為客戶i在單位時間內的需求量；fj表示設施j的初始設置成本；dij表示設施j到客戶i的單位運輸成本；q表示可能失靈設施的失靈概率。決策變量：Xj=1表示在j處開設設施，否則為0；Yijr=1表示r級分派中設施j服務于客戶i，否則為0。

對于每個客戶i，根據(jù)設施與其距離的遠近，最多在m個梯級上各分派一個常規(guī)設施為其服務。令r表示設施分派所處的級，r=0,1,…,m-1，其中r=0表示初始設施分派，其他為后備設施分派。若客戶i在第r級上被分派給了某個設施，則表明該客戶在0,1,…,r-1級上也分派有后備設施，只有這前r個更近的設施都失靈后，第r級上的設施才為其服務。

由于為客戶i分派的各級常規(guī)設施有可能都失靈，為此引入一個虛擬的應急設施u，且u∈NF，其固定開設成本和失靈概率均為零，無容量限制。若客戶i在某一級中被分派給應急設施，則產生懲罰成本θi，令diu=θi。即客戶的需求未被滿足時都將產生懲罰成本，該成本可理解為訂單流失成本或為滿足該客戶需求而從競爭者處緊急采購的成本。產生懲罰成本的情形包括兩類：分派給該客戶的所有設施都失靈(即無可用設施服務該客戶)；由任何一個分派設施為該客戶服務的成本均超過懲罰成本。

理想情況下，每個客戶i恰好分派有m個常規(guī)設施，除非客戶i在s(s

表示期望的設施失靈成本；α為權重系數(shù)，0≤α≤1。

則RUFLP可描述為

minαw1+(1-α)w2

(1)

r=0,…,m-1

(2)

Yijr≤Xj，?i∈I,j∈J,r=0,…,m-1

(3)

(4)

Xu=1

(5)

Xj∈{0,1}，?j∈J

(6)

Yijr∈{0,1}，?i∈I,j∈J,r=0,…,m-1

(7)

其中，目標式(1)表示使設施固定成本、運輸成本和期望失靈成本之和最小。約束式(2)表示對于每一后備分派級r，客戶i要么分派給級r上的可能失靈設施，要么分派給級s上的不失靈設施(s

Snyder等[3]提出了一種拉格朗日松弛(Lagrangian Relaxation，LR)算法來求解該模型，并且討論了如何用該模型產生一條日常運營成本與期望失靈成本之間的平衡曲線，以證明在選址階段考慮設施的可靠性，通過少量增加系統(tǒng)成本可以大大提高系統(tǒng)可靠性，從而實現(xiàn)期望運輸成本與系統(tǒng)可靠性的協(xié)調優(yōu)化，得到更加可靠的并且近似最優(yōu)的UFLP解決方案。

Li等[22]在文獻[3]的基礎上考慮設施設防與預算約束，只設立一個后備設施的RUFLP模型，并設計了相應的LR算法。與之相似，同樣只考慮設立一個后備設施。Bahri等[23]將分銷中心分為失靈與不失靈兩類(兩類設施的建設成本不同)，研究了三階段的分銷網絡設計問題。

但上述模型有一個明顯的缺陷：假設設施失靈基于一個相同的失靈概率，該假設在多數(shù)現(xiàn)實情況下是不合理的。Lee等[29]放寬這一假設，建立了一類RUFLP模型。Cui等[25]則提出了一個混合整數(shù)規(guī)劃(Mixed Integer Program，MIP)模型和連續(xù)近似(Continuum Approximation，CA)模型來研究設施具有不同失靈概率下的RUFLP。針對MIP模型和SA模型，分別設計了一種LR算法和快速啟發(fā)式算法來求解。結果表明：LR算法可以得到解的上下界，而CA方法只能得出一個近似最優(yōu)解。LR算法對于解決中小規(guī)模的RUFLP更為有效，但對于大規(guī)模問題，CA模型的快速啟發(fā)式算法比LR算法好，計算效率較高。此外，通過CA模型還可方便地進行靈敏性分析，為決策者提供一些有益的管理啟示。Aboolian等[26]在文獻[25]的基礎上針對離散的RUFLP研究了更為有效的精確算法與近似算法。Hong等[27]以設施失靈下救災物資損失量最小作為可靠性目標(但未進行后備設施指派)，以不考慮失靈風險下的系統(tǒng)總成本最小作為經濟性目標，建立了一個多目標的應急物流網絡設計模型。Yun等[28]研究了失靈信息不確定條件下的RUFLP。

上述文獻均未考慮設施失靈的空間相關性。但Li等[29-30]認為現(xiàn)實世界中許多失靈事件表現(xiàn)出很強的空間(位置)相關性(site-dependent or spatially-correlated)，原因在于相鄰的設施很有可能受同一災害的影響。指出這種相關性極大地影響了設施失靈的空間模式以及系統(tǒng)的運行模式：在正相關下，鄰近的設施更有可能同時失靈；在負相關下，相鄰設施可以相互支援以避免客戶長距離旅行。由此擴展了Snyder等[3]和Cui等[25]的研究，建立了一個RUFLP的CA模型。此外，絕大多數(shù)文獻在處理設施失靈概率時都將其視為確定的參數(shù)。

以上文獻考慮了設施失靈風險，研究低成本且可靠的選址方案，但是沒有對系統(tǒng)可靠性進行定量描述。Berman等[7]基于可靠性沖突理論提出了系統(tǒng)可靠性的計算方法，且認為可靠度是指系統(tǒng)能夠提供滿意的客戶服務的概率，是設施點與客戶之間距離的單調減函數(shù)。在此基礎上，Tang等[31]針對傳統(tǒng)選址模型片面追求物流成本最小化而忽視物流服務水平的情況，將可靠性作為物流服務水平的一種測度，建立了一個基于可靠性的物流設施選址優(yōu)化模型。

3.1.2RPMP模型

經典的PMP是通過建立P個設施來滿足所有客戶的需求，目標是使所有客戶點到設施的加權平均距離最短。Snyder等[3]擴展了傳統(tǒng)的PMP，提出了RPMP，這是當前RFLP研究的另一個熱點。

令

表示客戶由其初始分派設施服務的運輸成本；

表示期望的設施失靈成本。則RPMP可描述為

minαw1+(1-α)w2

(8)

?i∈I,r=0,…,P-1

(9)

Yijr≤Xj，?i∈I,j∈J,r=0,…,P-1

(10)

(11)

(12)

Xu=1

(13)

Xj∈{0,1}，?j∈J

(14)

Yijr∈{0,1}，?i∈I,j∈J,r=0,…,P-1

(15)

與RUFLP模型相比，RPMP模型中少了固定成本fj，設施數(shù)量變成了確定的P。Snyder等[3]通過平衡曲線分析發(fā)現(xiàn)，RPMP模型同樣說明了在少量增加系統(tǒng)成本的條件下，可以顯著提高系統(tǒng)的可靠性。但該文也是假設所有設施具有相同的失靈概率。Li等[22]也建立了一個考慮相同失靈概率、設施設防與預算約束、單個后備設施的RPMP模型及其LR算法。

在文獻[22]的基礎上Li等[32]擴展研究了不同失靈概率下的RPMP，并設計了一種求解大規(guī)模問題的禁忌搜索算法。Berman等[33]也允許不同的設施有不同的失靈概率，假設設施失靈概率是設施設計的函數(shù)，但是獨立于設施位置。他們提出一個類似的可靠性P-中位選址問題，構建了一個非線性規(guī)劃模型，并采用一種改進的貪婪算法來求解。研究發(fā)現(xiàn)，失靈概率對最優(yōu)設施選址決策有重要影響：當失靈概率大時，設施點變得更加集中，以便在失靈事件發(fā)生時提供更好的支撐條件。但該模型假設客戶擁有設施的運行情況信息，能夠相應地規(guī)劃旅行線路。Berman等[8]放寬了這一假設，研究了不完全信息條件下的RFLP。An等[34]基于兩階段魯棒優(yōu)化方法進一步改進了RPMP。

3.2最壞情形成本模型

當失靈概率等信息也不確定時，無法應用期望(概率)模型，此時，基于情景規(guī)劃的建模方法具有更好的適用性[35]?，F(xiàn)有的基于情景的RFLP研究模型大多為最壞情形成本模型。風險中立者在不確定性環(huán)境下進行決策時往往選擇期望成本最小模型，而風險規(guī)避者則傾向于最壞情形成本模型。由于設施修復以及網絡重構的成本太高，最壞失靈情景模型更加具有現(xiàn)實意義[36]。

最壞情形成本模型需要考慮所有可能出現(xiàn)的情景，但考慮所有可能的情景顯然是不現(xiàn)實的。由于最壞的情景在理論上是指所有設施都失靈的情況，因而在研究最壞情形成本模型時，通常采取兩種處理方法：一是假設所有的情景中最多有若干個設施失靈；二是假設所有的情景概率至少為某一定值。

基于Snyder等[3]研究的問題，Snyder等[37]提出一個極小化最大成本RFLP模型(Minimax-cost RFLP，MMRFLP)，考慮各種失靈情景下設施的最優(yōu)選址以及客戶分派問題，目標是使最大的系統(tǒng)成本最小。

設U表示最大的系統(tǒng)成本；S表示失靈情景集。若設施j在情景s中失靈，ajs=1，否則為0；若客戶i在情景s中分派給設施j，Yijs=1，否則為0。則MMRFLP可描述為

minU

(16)

(17)

(18)

Yijs≤(1-ajs)Xj，?i∈I,j∈J,s∈S

(19)

Xj∈{0,1}，?j∈J

(20)

Yijs∈{0,1}，?i∈I,j∈J,r=0,s∈S

(21)

其中，目標式(16)表示使最大的系統(tǒng)成本最小。約束式(17)表示U為最大的系統(tǒng)成本；約束式(18)保證每個客戶在每種情景中都有一個設施為其服務；約束式(19)保證客戶在每種情景中只能分配給已開設且未失靈的設施。

Shen等[38]考慮失靈概率依賴于設施，基于情景規(guī)劃方法構建了一個兩階段隨機規(guī)劃模型。在失靈概率依賴于設施時，通過界定不同情景可以很容易地獲得不同設施的失靈概率。如果情景數(shù)量足夠多，基于情景規(guī)劃所描述的可靠性無容量限制的設施選址問題是合理的，并且能夠有效求解。但當失靈概率獨立時，可能的情景集規(guī)模巨大，模型的變量和約束條件數(shù)量將呈指數(shù)級增長，從而使得問題難以得到有效求解。為此，他們又構建了一個非線性整數(shù)規(guī)劃模型來描述它，并采用樣本均值逼近啟發(fā)式(Sample Average Approximation)、貪婪增加(Greedy Adding)、貪婪增加和替代(Greedy Adding and Substitution)等啟發(fā)式算法來求解。Zhang等[39]基于最壞失靈情景，建立了預期成本最小及最大覆蓋范圍最大的兩類雙層規(guī)劃模型。Peng等[40]則采用魯棒優(yōu)化(Robust Optimization)方法研究了考慮設施失靈風險的可靠性多級物流網絡設計問題，建立了一種MIP模型，并設計了一種結合局部改進(Local Improvement)和最短增廣路(Shortest Augmenting Path)方法的混合遺傳算法。

與極小化最大成本模型相比，極小化最大后悔模型(Minimax Regret Model)可能需要更多的情景數(shù)量，因為哪些情景會產生最大的后悔值在失靈發(fā)生前是不明確的。為此，Snyder等[41]進一步討論了RFLP的極小化最大成本模型和極小化最大后悔模型。Chen等[5]擴展研究了隨機距離情況下的極小化最大后悔模型。此外，Church等[42]、Hanley等[43]也進行了類似的研究。

總體而言，當前關于最壞情形成本模型的研究尚不多見。在此類模型中，最壞情景的設定通常具有較強的主觀性，情景設定依賴于模型、參數(shù)結構和數(shù)據(jù)。當情景數(shù)量較多時，模型的變量和約束條件數(shù)量增長很快，此時對算法性能的要求很高。

3.3其他RFLP模型

最小期望成本模型與最壞情形成本模型之外，也有少量文獻研究了其他的RFLP模型。例如，Hassani等[44]在傳統(tǒng)的軸輻式網絡設計(Hub-and-spoke network)及樞紐站選址(Hub Location)模型中引入中斷風險與可靠性概念，提出了可靠性中心樞紐站選址問題(Reliable Center Hub Location problem,RCHLP)。Lim等[45-46]基于CA模型研究了考慮隨機失靈概率、概率不完全估計、失靈概率與容量相關條件下的RFLP，研究發(fā)現(xiàn)：與高估風險相比，低估風險引起的預期成本增長更快 ；若規(guī)劃得當，降低誤判風險的成本不會太高；失靈概率的誤判風險大于失靈概率的相關程度，因此管理者應更加注重失靈概率的準確估計。Aydin等[35]研究了一類有容量限制的可靠性固定費用選址問題(Capacitated Reliable Facility Location Problem,CRFLP)。通過線性0～1整數(shù)規(guī)劃模型來對問題加以描述。由于采用了情景設定，降低了模型的復雜性。盡管考慮了容量限制，但該文不允許多個設施服務于同一個客戶(即協(xié)同定位)。

3.4RFLP求解

與RFLP模型方面的研究相比，目前對RFLP求解算法的研究成果較有限。

現(xiàn)有對RFLP的研究絕大多數(shù)都考慮離散設施選址問題，一般采用MIP方法予以描述。求解此類模型時，常用LR算法，而且一般都將原問題分解為兩個線性化的子問題。對于給定的拉格朗日乘子，這兩個子問題都比較容易求解。但是針對不同的選址問題，松弛的約束條件不盡相同。對于RUFLP和RPMP模型，LR算法通常松弛設施開放約束，將原問題分解為設施選址子問題和客戶分派子問題，然后通過拉格朗日乘子的迭代更新來協(xié)調兩個子問題的求解，得到原問題的上下界(如文獻[25])。也有文獻針對RPMP模型，采用LR算法松弛客戶分派約束，將模型轉化成一個求解最優(yōu)下界的子問題，如文獻[3]。

LR算法可以求得較精確的計算結果，但它僅適用于模型不太復雜的情況以及中小規(guī)模問題。放寬各種建模假設后，模型的復雜性會顯著增加，LR算法的應用就受到很大的局限。為此，不少學者設計了各種啟發(fā)式算法來求解復雜的MIP模型(如文獻[38，40]等)?？梢灶A見，隨著對RFLP的進一步深入研究，各種啟發(fā)式算法的設計也將成為研究重點。

也有個別文獻研究了連續(xù)空間上的RFLP，基于CA方法進行建模，并采用解析法，如文獻[29，47]；或近似算法進行快速求解，如文獻[25]。CA模型的實際應用意義較小，但在解決大規(guī)模復雜問題時效率較高，而且便于進行靈敏性分析，從而得出一些管理啟示。

4研究展望

綜上所述，RFLP已日漸引起學者們的關注，相關研究正在逐步深入和拓展。通過對以往研究的分析可以發(fā)現(xiàn)：

(1) 在研究目標方面，現(xiàn)有研究主要集中于兩個方面：一是在考慮設施失靈風險的條件下，探討系統(tǒng)中不可靠設施的最優(yōu)選址；二是從中得出一些有益的管理啟示，以幫助決策者更好地進行系統(tǒng)管理。目標一主要通過各種模型的建模求解來實現(xiàn)，而目標二則主要通過靈敏性分析來探討各個參數(shù)和系統(tǒng)目標之間的關系。

(2) 在模型構建方面，現(xiàn)有研究大多針對離散空間的RFLP，建立線性或非線性的MIP模型。也有少量文獻采用了隨機規(guī)劃等方法進行建模。

(3) 在求解算法方面，不少學者都采用LR算法來求解RFLP。若問題規(guī)模不大，LR算法很有效；但對于大規(guī)模問題，LR算法的效果也不太理想。為此，不少學者傾向于設計啟發(fā)式或亞啟發(fā)式算法來求解，以提高計算效率。事實上，絕大多數(shù)離散設施選址問題都屬于NP-hard問題，考慮設施可靠性因素后，問題變得更為復雜，因而采用各種啟發(fā)式算法求解是未來的趨勢。

相對于已有百年研究歷史的傳統(tǒng)選址問題，RFLP還是一個新興研究領域。鑒于RFLP的復雜性，現(xiàn)有研究通常設置了一些與現(xiàn)實情況不符的假設條件，如無容量限制、確定性參數(shù)、完全信息條件等。因此，對該問題的研究還存在許多有待完善的地方：

(1) 設施容量限制與協(xié)同定位。現(xiàn)有研究大都假設設施容量是無限的。在模型中考慮設施容量限制，盡管會增加模型和算法的復雜性，卻更加切合實際。此外，在有容量限制的情況下，設施間的協(xié)同定位成為可能，這是一個很具吸引力的研究方向。

(2) 內生性假設。目前不少文獻關于設施失靈風險的外生性假設是一個明顯的缺陷，且大多認為設施失靈風險與可靠性是獨立的，只有個別文獻(如文獻[7，30])將可靠性視為設施點與客戶之間距離的函數(shù)。但設施的可靠性應該是由多個因素(如距離、需求規(guī)模、地理位置等)綜合決定的，而不是某一單個因素的函數(shù)。因此，如何對各種內生性因素進行綜合分析，為后續(xù)的研究提供了一個新的視角。

(3) 客戶行為假設。現(xiàn)有文獻對客戶行為存在兩個基本假設：一是針對客戶搜索行為，假設客戶總是搜索下一個最近的設施，而不是規(guī)劃最優(yōu)的路徑(這條路徑使總的期望旅行成本最低)?？梢?，基于最優(yōu)客戶行為研究RFLP具有重要前景，當然也相當困難。另一個假設是客戶知道所有設施的位置，這一點在很多情況下是不合理的(如對于ATM機、加油站等情況)，因此放寬這一假設將使構建的模型更加切合實際。

(4) 隨機性與魯棒性?，F(xiàn)有研究大多建立確定性模型，但事實上研究各種不確定信息(如需求、風險信息)條件下的RFLP更具現(xiàn)實意義，對此可采用隨機優(yōu)化、魯棒優(yōu)化等方法進行研究。

(5) 動態(tài)決策?，F(xiàn)有研究僅考慮靜態(tài)決策規(guī)則，忽略了設施失靈的頻率和持續(xù)時間，有必要進一步研究動態(tài)環(huán)境下的最優(yōu)決策規(guī)則。

(6) 集成決策。在選址與庫存、路徑等的集成決策問題中也應考慮設施失靈風險。已有少量文獻在RFLP決策中引入庫存成本，建立了考慮失靈風險的定位-庫存問題(Location-Inventory Problem)優(yōu)化模型[48-50]。而考慮失靈風險的定位-路徑問題(Location-Routing Problem)、定位-路徑-庫存問題(Location-Routing-Inventory Problem)等尚未見研究。

(7) 有效算法。RFLP大多屬于NP-hard問題，在模型方面進行諸多擴展后，問題將變得更為復雜。因此，設計更加有效的算法來求解復雜的RFLP模型將是今后研究的重點。

5結語

設施網絡可能面臨各種失靈風險，因而在進行選址時有必要充分考慮設施的非完全可靠性。盡管現(xiàn)實中設施失靈現(xiàn)象不會經常發(fā)生，但一旦發(fā)生，后果可能很嚴重?？偨Y以往有關RFLP的研究成果，可以得到以下啟示：

(1) 設施選址是一個戰(zhàn)略決策問題，在短期內一般不會改變，因而在選址階段就考慮其失靈風險和相應的保護性措施是十分必要的，可以顯著降低將來的應急成本。

(2) 盡管系統(tǒng)成本與系統(tǒng)可靠性之間存在悖反關系，但通過增加少量的系統(tǒng)成本就可以顯著提高系統(tǒng)的可靠性，從而實現(xiàn)系統(tǒng)成本與系統(tǒng)可靠性之間的協(xié)調優(yōu)化。

(3) 設施失靈概率的準確估計具有重要作用。若失靈概率的準確估計困難，則適度高估風險更有利于構造可靠的設施網絡，因為低估失靈概率的造成的后果更嚴重。

(4) 最優(yōu)選址決策受多種因素的影響。當設施失靈概率較大時，應該選擇較集中的選址模式，以便在設施失靈發(fā)生后可以實現(xiàn)有效的相互支援。在某 些特殊情況下，甚至可以考慮將幾個設施定位在相同的網絡節(jié)點上。此外，不同類型風險的相關性及其強度也會影響選址模式。設施選址應充分考慮空間(位置)、距離和服務需求等失靈風險相關的因素。

RFLP已成為選址研究領域的一個重要研究方向，其研究成果對于提高設施網絡的可靠性具有重要的意義。但目前國內關于這一問題的研究成果匱乏，亟待加強這方面的研究。為此，本文系統(tǒng)地回顧了考慮設施失靈風險的RFLP研究現(xiàn)狀，并結合實際提出了今后應重視的幾個發(fā)展方向。盡管所涉及的范圍較廣，解決問題的難度也很大，未來對該問題的研究應建立更切合實際情況的模型，并探索是否有一種普遍適用的算法，允許相關專業(yè)人員用其有效地解決現(xiàn)實中的問題，以便有效提高設施網絡的可靠性。

參考文獻(References)：

[1]SNYDER L V.Facility Location under Uncertainty:A Review[J].IIE Transactions,2006,38(7):537-554

[2] FARAHA R Z,SteadieSeifib M,Asgari N.Multiple Criteria Facility Location Problems:A Survey[J].Applied Mathe-matical Modelling,2010,34(7):1689-1709

[3] SNYDER L V,Daskin M S.Reliability Models for Facility Location:The Expected Failure Cost Case[J].Transporta-tion Science,2005,39(3):400-416

[4] KLEINDORFER P R,Saad G H.Managing Disruption Risks in Supply Chains[J].Production and Operations Management,2005,14(1):53-68

[5] CHEN G,DASKIN M S,SHEN Z.The ?-Reliable Mean-Excess Regret Model for Stochastic Facility Location Modeling[J].Naval Research Logistics,2006,53(7):617-626

[6] WITLIN D.Ambulance Diverted Each Minute[J].Boston Herald,2006,17(2):11-14

[7] BERMAN O,KRASS D,MENEZES M.Locating Service Facilities Whose Reliability Is Distance Dependent[J].Com-puters & Operations Research,2003,30(11):1683-1695

[8] RAFIEI M,MOHAMMADI M,TORABI S.Reliable Multi Period Multi Product Supply Chain Design with Facility Disruption[J].Decision Science Letters,2013,2(2):81-94

[9] BERMAN O,KRASs D,MENEZES M.Locating Facilities in The Presence of Disruptions and Incomplete Information[J].Decision Sciences,2009,40(4):845-868

[10]王國利,胡丹丹,楊超.需求和供應不確定下的選址研究[J].工業(yè)工程與管理,2011,16(1):74-78

WANG G L,HU D D,YANG C.Location Problem with Uncertain Demands and Supplies[J].Industrial Engineer-ing and Management,2011,16(1):74-78

[11] CHURCH R L,SCAPARRA M P,MIDDLETON R S.Identifying Critical Infrastructure:the Median and Covering Facility Interdiction Problem[J].Annals of the Association of American Geographers,2004,94(3):491-502

[12] CHURCH R L,SCAPARRA M P.Protecting Critical Assets:the R-Interdiction Median Problem with Fortification[J].Geographical Analysis,2006,39(2):129-46

[13] SCAPARRA M P,CHURCH R L.A Bilevel Mixed-Integer Program for Critical Infrastructure Protection Planning[J].Computers & Operations Research,2008,35(6):1905-1923

[14] FEDERICO L,MARIA P,DASKIN M S.Analysis of Facility Protection Strategies Against An Uncertain Number Of Attacks:the Stochastic R-Interdiction Median Problem with Fortification[J].Computers & Operations Research,2011,38(1):357-366

[15] ZHU Y,ZHENG Z,ZHANG X,et al.The R-Interdiction Median Problem with Probabilistic Protection and Its Solution Algorithm[J].Computers & Operations Research,2013,40(1):451-462

[16] CARR R D,GREENBERG H J,HART W E,et al.Robust Optimization of Contaminant Sensor Placement For Community Water Systems[J].Mathematical Program-ming,2005,107(1-2):337-356

[17] JAMES J C,SALHI S.A Tabu Search Heuristic for The Location of Multi-Type Protection Devices on Electrical Supply Tree Networks[J].Journal of Combinatorial Optimization,2002,6(1):81-98

[18] GENDREAU M,LAPORTE G,PARENT I.Heuristics for the Location of Inspection Stations on A Network[J].Naval Research Logistics,2000,47(4):287-303

[19] TEODOROVIC D,SELMIC M.Locating Flow-Capturing Facilities in Transportation Networks:A Fuzzy Sets Theory Approach[J].International Journal for Traffic & Transport Engineering,2013,3(2):103-111

[20] PAN Y,DU Y,WEI Z.Reliable facility systems design subject to edge failures:based on the uncapacitated fixed-charge location problem[J].American Journal of Opera-tions Research,2014,4(3):164

[21] FORTZ B,LABBE M.Polyhedral Results for Two-Connected Networks with Bounded Rings[J].Mathematical Program-ming Series,2002,93(1):27-54

[22] LI Q,SAVACHKIN A.Reliable Distribution Networks Design with Nonlinear Fortification Function[J].International Journal of Systems Science,2014 (ahead-of-print):1-9

[23] BAHRI S,RUSMAN M.Reliable Facility Location Model Considering Disruption Risk in Logistic Model[J].Journal of Engineerir1g and Applied Sciences,2013,8(6):177-182

[24] LEE S D,CHANG W.On Solving the Discrete Location Problems When the Facilities Are Prone to Failure[J].Applied Mathematical Modeling,2007,31(5):817-831

[25] CUI T,OUYANG Y,SHEN Z.Reliable Facility Location Design under the Risk of Disruptions[J].Operations Research,2010,58(4):998-1011

[26] 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

[27] HONG J D,JEONG K,XIE Y,et al.A Multi-Objective Approach to Modeling Cost-Effective,Reliable and Robust Emergency Logistics Networks[J].Reliable and Robust EmergencyLogisticsNetworks,2013(12):1-11

[28] YUN L,JI C,LI X,et al.A Reliability Model for Facility Location Design under Imperfect Information[C]∥Transpor-tation Research Board 93rd Annual Meeting,2014:14-4267

[29] LI X,OUYANG Y.A Continuum Approximation Approach to Reliable Facility Location Design under Correlated Probabilistic Disruptions[J].Transportation Research Part B:Methodological,2010,44(4):535-548

[30] LI X,OUYANG Y,PENG F.A Supporting Station Model for Reliable Infrastructure Location Design under Interdependent Disruptions[J].Procedia-Social and Behavioral Sciences,2013,80(1):25-40

[31] TANG X,MAO H.Logistics Facility Location Model Based on Reliability Within the Supply Chain[C]∥Proceedings of the 4th IEEE International Conference on Management of Innovation and Technology,2008:1099-1103

[32] LI Q,SAVACHKIN A.A Fast Tabu Search Algorithm for The Reliable P-Median Problem[M].Advances in Global Optimization.Springer International Publishing,2015

[33] BERMAN O,KRASS D,MENEZES M.Facility Reliability Issues in Network P-Median Problems:Strategic Centralization and Co-Location Effects[J].Operations Research,2007,55(2):332-350

[34] AN Y,ZENG B,ZHANG Y,et al.Reliable P-Median Facility Location Problem:Two-Stage Robust Models and Algorithms[J].Transportation Research Part B:Methodo-logical,2014,64(10):54-72

[35] AYDIN N,MURAT A.A Swarm Intelligence Based Sample Average Approximation Algorithm for the Capacitated Reliable Facility Location Problem[J].International Journal of Production Economics,2013,145(1):173-183

[36] LI Q,ZENG B,SAVACHKIN A.Reliable Facility Location Design under Disruptions[J].Computers & Operations Research,2013,40(4):901-909

[37] SNYDER L V,CAPARRA M,DASKIN M S.Planning for Disruptions in Supply Chain Networks[C]∥Tutorials in Operations Research,INFORMS,2006:234-259

[38] SHEN Z,ZHAN R,ZHANG J.The Reliable Facility Location Problem:Formulations,Heuristics and Approximation Algorithms[R].INFORMS Journal on Computing,2011,23(3):470-482

[39] ZHANG M,HUANG J,ZHU J.Reliable Facility Location Problem Considering Facility Failure Scenarios[J].Kyber-netes,2012,41(10):1440-1461

[40] 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

[41] SNYDER L V,DASKIN M S.Models for Reliable Supply Chain Network Design.In Murray A,Grubesic T H.(Ed),Reliability and Vulnerability In Critical Infrastructure:A Quantitative Geographic Perspective[M].Springer,New York,2006

[42] CHURCH R L,SCAPARRA M P,HANLEY J.Optimizing Passive Protection in Facility Systems[R].Working paper,ISOLDEX,Spain,2006

[43] HANLEY J,CHURCH R L.Planning for Facility-Loss:A Bilevel Decomposition Algorithm for The Maximum Covering Location-Interdiction Problem[R].Working paper,Oxford University,Oxford,England,2005

[44] HASSANI A,KHATAMI M,TABRIZI P H.Reliable Center Hub Location Problem:Formulation and Methodology[J].Expert Systems with Applications,2014

[45] LIM M K,BASSAMBOO A,CHOPRA S,et al.Facility Location Decisions with Random Disruptions and Imperfect Estimation[J].Manufacturing & Service Operations Manage-ment,2013,15(2):239-249

[46] LIM M,DASKIN M S.A Facility Reliability Problem:Formulation,Properties and Algorithm[J].Naval Research Logistics,2010,57(1):58-70

[47] WANG X,OUYANG Y.A Continuum Approximation Approach to Competitive Facility Location Design under Facility Disruption Risks[J].Transportation Research Part B:Methodological,2013,50:90-103

[48] JEON H M.Location-Inventory Models with Supply Disruptions[D].PhD thesis,Lehigh University,2008

[49]QI L,SHEN Z,SNYDER L V.The Effect of Supply Disruptions on Supply Chain Design Decisions[J].Trans-portation Science,2010,44(2):274-289

[50] CHEN Q,LI X,OUYANG Y.Joint Inventory-Location Problem under the Risk of Probabilistic Facility Disruptions[J].Transportation Research Part B:Methodolo-gical,2011,45(7):991-1003

責任編輯：天虹

A Review of Reliability Facility Location Problem under theRisk of Facility Disruptions

ZHOU Yu-feng1,2

(1.School of Business Planning,Chongqing Technology and Business University,Chongqing 400067,China；2.Chongqing Engineering Technology Research Center for Information Management in Development,Chongqing Technology and Business University,Chongqing 400067,China)

Abstract：The reliability facility location problem is a frontier problem of the current location research area.The sources and classifications of disruption risk,as well as the characteristics of some issues related to reliability facility location problem (RFLP) were analyzed.Based on the decision-maker's risk attitude,RFLP was categorized as minimum expected cost problem and worst-case cost problem.And the former was further divided into two categories:reliability uncapacitated fixed-charge location problem and reliability P-median problem.Then the state-of-art of these studies was reviewed from the aspects of models and algorithms. Finally,the current status and managerial insights of RFLP were summarized,and its future research directions were put forward.

Key words:facility location; facility disruptions; reliability; literature review

中圖分類號：O221.2

文獻標志碼：A

文章編號：1672-058X(2016)02-0058-10

作者簡介：周愉峰(1984-)，男，湖南雙峰人，講師，博士，從事應急物流與應急管理、物流系統(tǒng)優(yōu)化研究.

*基金項目：教育部人文社會科學研究項目(15XJC630009)；重慶市教委科學技術研究項目(KJ1500603)；重慶市自然科學基金項目(CSTC2013JCYJA0998).

收稿日期：2015-11-02；修回日期：2015-12-12.

doi:10.16055/j.issn.1672-058X.2016.0002.013