有容量限制的可靠性固定費用選址問題

周愉峰， 馬祖軍， 王恪銘

(1.重慶工商大學 商務策劃學校，重慶 400067； 2.西南交通大學 經(jīng)濟管理學院 物流與應急管理研究所，四川 成都 610031; 3.西南交通大學 峨眉校區(qū)，四川 峨眉山 614202)

?

有容量限制的可靠性固定費用選址問題

周愉峰1， 馬祖軍2， 王恪銘3

(1.重慶工商大學 商務策劃學校，重慶 400067； 2.西南交通大學 經(jīng)濟管理學院 物流與應急管理研究所，四川 成都 610031; 3.西南交通大學 峨眉校區(qū)，四川 峨眉山 614202)

設施網(wǎng)絡可能面臨各種失靈風險，而設施選址屬于戰(zhàn)略決策問題，短期內(nèi)難以改變，因而在選址設計時需要充分考慮設施的非完全可靠性。本文針對無容量限制的可靠性固定費用選址問題進行擴展，進一步考慮設施的容量約束，基于非線性混合整數(shù)規(guī)劃方法建立了一個有容量限制的可靠性固定費用選址問題優(yōu)化模型。針對該模型的特點，應用線性化技術進行模型轉(zhuǎn)化，并設計了一種拉格朗日松弛算法予以求解。通過多組算例分析，驗證了算法的性能。算例分析結(jié)果表明設施失靈風險和設施容量對于選址決策有顯著影響，因而在實際的選址決策過程中有必要充分考慮設施的失靈風險及容量約束。

設施選址；設施失靈；可靠性；容量限制；拉格朗日松弛

0 引言

經(jīng)典的無容量限制的固定費用選址問題(Uncapacitated fixed-charge location problem，UFLP)和P-中位問題(P-median Problem，PMP)都有一個隱含的假設：設施一旦建立，將一直運行而不失靈，即設施是完全可靠的?？墒聦嵣希捎谧匀粸暮?、罷工、所有權更替和其他因素的存在，設施失靈(Facility Disruptions，也稱Facility Failures)現(xiàn)象時有發(fā)生。當分派設施發(fā)生失靈時，客戶不得不選擇距離更遠的設施為其服務，這就可能導致運輸成本增加，由此產(chǎn)生了可靠性設施選址問題。傳統(tǒng)的選址問題通常不會改變設施網(wǎng)絡的拓撲結(jié)構(gòu)(布局)，而可靠性選址問題在選址階段考慮了失靈風險，網(wǎng)絡的拓撲結(jié)構(gòu)是可變的。由于設施選址屬于戰(zhàn)略性決策問題，短期內(nèi)不會改變，因而在設計階段就考慮失靈風險是十分重要的。而且在選址階段考慮失靈風險可以大大降低應急成本，因而研究可靠性設施選址問題具有重要的意義。

可靠性設施選址問題最早由Snyder和Daskin[1]提出，研究如何選擇低成本(傳統(tǒng)目標函數(shù))且可靠的設施地點。近年來，該問題引起了國外學者的關注，已成為選址研究領域的前沿性問題。通過對相關文獻的分析，可以發(fā)現(xiàn)現(xiàn)有研究主要分為兩類：最小期望成本模型和最壞情形成本模型。

最小期望成本模型是當前研究的重點，且主要是針對UFLP和PMP這兩類經(jīng)典的設施選址問題進行擴展，稱為無容量限制的可靠性固定費用選址問題(Reliability Uncapacitated Fixed-charge Location Problem，RUFLP)和可靠性P-中位問題(Reliability P-median Problem，RPMP)。如Snyder和Daskin[1]對經(jīng)典的UFLP和PMP進行擴展，在模型中考慮了設施失靈，首次提出了RUFLP和RPMP。他們假設所有設施具有相同的失靈概率，且考慮多級設施分派(每個客戶有多個梯級后備設施)，分別針對RUFLP和RPMP建立了混合整數(shù)規(guī)劃模型，并設計了拉格朗日松弛(Lagrangian Relaxation，LR)算法進行模型求解。此后，針對RUFLP，Cui等[2]放寬了所有設施具有相同失靈概率這一假設，并分別建立了基于混合整數(shù)規(guī)劃的離散優(yōu)化模型和連續(xù)近似(Continuum Approximation，CA)模型；Lee和Chang(2007)[3]也考慮所有設施的失靈概率可以不同，但每個客戶只選一個后備設施。Li和Ouyang[4]則進一步考慮了設施失靈的空間相關性。而Berman等[5]，Berman等[6]則在文獻[1]的基礎上對RPMP做了進一步的擴展研究。

最壞情形成本模型則是在經(jīng)典的選址模型基礎上基于情景規(guī)劃方法構(gòu)建可靠性模型。Snyder等[7]，Snyder和Daskin[8]，Chen等[9]，Church等[10]，Hanley和Church[11]，Peng等[12]都對最壞情形成本模型進行了相應的擴展研究。

上述有關可靠性設施選址問題的研究均未考慮設施的容量約束，但在現(xiàn)實生活中設施一般都有容量限制，因而放寬這一假設將使構(gòu)建的模型更加切合實際。眾所周知，絕大多數(shù)離散設施選址問題屬于NP-hard問題，而考慮可靠性因素后問題變得更為復雜。若同時考慮容量約束，將進一步增加模型和算法的復雜性。因此，盡管有不少學者指出放寬容量約束這一假設更具現(xiàn)實意義，但一直未得到解決。本文針對RUFLP，在文獻[2]的基礎上進一步考慮設施容量限制，建立一個考慮失靈風險且有容量限制的可靠性固定費用選址問題(Reliability Capacitated Fixed-charge Location Problem，RCFLP)的離散優(yōu)化模型。該模型中客戶需求可以部分被滿足，而RUFLP中的客戶需求要么完全被滿足，要么完全未被滿足(當無可用設施服務該客戶時)。針對該模型的特點，采用線性化技術進行轉(zhuǎn)化，并設計了一種LR算法進行求解。

1 RCFLP優(yōu)化模型

1.1 問題描述與假設

RUFLP研究考慮設施失靈風險條件下的設施選址及其客戶分派，以尋求設施的固定開設成本、日常運行成本和期望失靈成本之和最小的選址方案。本文在此基礎上進一步考慮設施容量約束，即研究RCFLP。

類似于RUFLP，考慮多級設施分派，以應對失靈風險，提高系統(tǒng)可靠性。對于每個客戶，根據(jù)設施與其距離的遠近，最多在R個梯級上各分派一個常規(guī)設施為其服務。令r表示設施分派所處的級，r=0,1,…，R-1,其中r=0表示初始設施分派，其它為后備設施分派。若客戶i在第r級上被分派給了某個設施，則表明該客戶在0,1,…，r-1級上也分派有后備設施，只有這前r個更近的設施都失靈后，第r級上的設施才為其服務。

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

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

假設每個設施的失靈概率相互獨立，且均為先驗概率?？蛻魧υO施位置、設施失靈情況和設施容量狀況擁有完全信息。若某一級上分派的設施失靈，客戶總是搜索下一個最近的設施為其服務。需要解決的問題是：在考慮失靈風險的情況下，確定設施點的數(shù)量、位置以及客戶需求在各個設施點之間的分配，目標是使固定成本、期望運輸成本以及懲罰成本之和最小。

1.2 符號說明

參數(shù)：

i：客戶編號，i=0,1,…,I-1；

j：候選設施編號，j=0,1,…,J，其中j=J表示虛擬的應急設施；

hi：客戶i的需求量；

fj：設施j的固定開設成本，且fJ=0；

vj：設施j的容量，且vJ足夠大；

qj：設施j的失靈概率，且0≤qj≤1，qJ=0；

φi：客戶i的需求未被滿足時的單位需求懲罰成本；

dij：設施j到客戶i的單位需求運輸成本，且diJ=φi；

R：為每個客戶最多可分派的常規(guī)設施級數(shù)，且R≥1；

r：設施分派所處的級，r=0,1,…R，其中r=0為初始設施分派，r=0,1,…,R-1為后備設施分派，r=R為應急設施分派。

決策變量：

Xj：在j處開設設施為1，否則為0；

Yijr：設施j在r級上被分派給客戶i時為1，否則為0；

Pijr：由設施j在r級上服務客戶i的概率；

xij：設施j到客戶i的運量。

1.3 模型建立

至此，可建立RCFLP的離散優(yōu)化模型如下：

(1)

s.t.xij≤hi,?0≤i≤I-1,0≤j≤J

(2)

xij=xijYijr,?0≤i≤I-1,0≤j≤J,0≤r≤R

(3)

(4)

(5)

(6)

pij0=1-qj,?0≤i≤I-1,?0≤j≤J

(7)

(8)

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

(9)

Yijr∈{0,1},?0≤i≤I-1,0≤j≤J,0≤r≤R

(10)

xij>0,?0≤i≤I-1,0≤j≤J

(11)

1.4 模型轉(zhuǎn)化

上述模型是一個非線性混合整數(shù)規(guī)劃模型，目標函數(shù)中包含三元變量xijpijrYijr和二元變量pijrYijr，約束(8)中也包含二元變量pijrYijr，使得該模型的求解很困難。在此采用Sherali和Alameddine[13]提出的線性化技術來轉(zhuǎn)化該模型：引入一個新的變量Wijr來替換pijrYijr。對于任意0≤i≤I-1，0≤j≤J和0≤r≤R，為使Wijr=pijrYijr，在上述模型RCFLP中增加如下一組約束：

Wijr≤pijr

(12)

Wijr≤Yijr

(13)

Wijr≥0

(14)

Wijr≥pijr+Yijr-1

(15)

則模型RCFLP可轉(zhuǎn)化為如下模型RCFLP’：

(16)

(17)

(9)～(15)

模型RCFLP’的目標函數(shù)中依然含有二元變量xijWijr。令Zij=xij/hi，表示客戶的需求由設施j滿足的比例，有0≤Zij≤1，則xij=hiZij。由于客戶i最多只可能在某一級上分派給設施j，故xij等價于xijr，則Zij等價于Zijr。因此，式(16)可改寫為

再次應用線性化轉(zhuǎn)換技術：令Vijr=ZijrWijr，對于任意0≤i≤I-1，0≤j≤J和0≤r≤R，在上述模型RCFLP’中增加如下一組約束：

Vijr≤Zijr

(18)

Vijr≤Wijr

(19)

Vijr≥0

(20)

Vijr≥Zijr+Wijr-1

(21)

則模型RCFLP’可轉(zhuǎn)化成如下線性模型LRCFLP：

(22)

s.t. 0≤Zijr≤1,?0≤i≤I-1,0≤j≤J,0≤r≤R

(23)

Zijr=ZijrYijr,?0≤i≤I-1,0≤j≤J,0≤r≤R

(24)

(25)

(26)

(5)～(7),(9)～(15),(17)～(21)

2 模型求解

上述混合整數(shù)線性規(guī)劃模型LRCFLP可以采用CPLEX等軟件包進行求解，但即使針對一個中等規(guī)模的問題也要花費很長的運算時間。為此，下面設計一種拉格朗日松弛算法來求解該模型。

用拉格朗日乘子μ松弛約束(26)，得到如下目標函數(shù)：

(27)

原問題可以分解成選址子問題(LSP)和客戶分派子問題(ASP)。對于給定的拉格朗日乘子μ，很容易得到選址決策變量Xj的最優(yōu)值：

為了計算最優(yōu)的客戶分派決策變量Yijr和需求分配決策變量xij，可注意到該決策問題對于每個客戶是可分的[2]。對于給定的μ，客戶i的分派問題(ASP)可以描述成如下的松弛子問題(Relaxed Subproblem，RSP)。為了簡化，模型中省略了Yijr,pijr,Wijr,Zijr,Vijr中的下標i。

(28)

s.t. 0≤Zjr≤1,?0≤j≤J,0≤r≤R

(29)

(30)

(31)

(32)

pj0=1-qj,?0≤j≤J

(33)

(34)

Yjr∈{0,1}?0≤j≤J,0≤r≤R

(35)

(12)～(15),(18)～(21)

這是一個線性規(guī)劃問題，可用傳統(tǒng)的精確算法(如CPLEX等軟件包)來求解，但問題規(guī)模較大時計算效率很低。為此，設計了如下的近似算法：

Step 2 根據(jù)Yijr的值以及式(33)和(34)，計算出Pijr與Wijr；

Step 3 由于Vijr=ZijrWijr，可直接套用經(jīng)典的線性規(guī)劃算法快速求解Zijr，進而得到Vijr。

至此，可采用標準的次梯度法求解拉格朗日松弛問題，具體計算過程如下：

①初始化拉格朗日乘子μ、迭代次數(shù)n、步長θt；

②求解選址子問題；

③求解客戶分派子問題；

④計算下界解：LRUFL(μ)=LSP(μ)+ASP(μ)。判斷當前的拉格朗日解是否為可行解，如果當前解可行，則停止計算，該解即為LRCFLP的最優(yōu)解；否則，轉(zhuǎn)入⑤更新下界。

⑤根據(jù)當前解計算次梯度和步長，并按下文的拉格朗日乘子迭代方法更新μ，若滿足收斂或停止條件，則停止迭代；否則，返回步驟②。

⑥解的可行化與上界的最終確定：下界確定后，固定Xj，Yijr，Wijr的值，在線性規(guī)劃ASP問題中加入松弛的約束(26)，得到問題的可行解；同時，將各個變量代回原問題中，得到問題的上界。

3 算例研究

以文獻[1]和[2]中的美國49個和88個城市節(jié)點(既是需求點，也是候選設施點)網(wǎng)絡作為測試算例。需求hi、固定開設成本fj、懲罰成本φi的數(shù)據(jù)均從Snyder的個人主頁下載(http://www.lehigh.edu/～lvs2)。設施容量vj在[40,400]內(nèi)隨機均勻產(chǎn)生；失靈概率qj在[0,0.1]內(nèi)隨機均勻產(chǎn)生。

針對49個和88個(加上虛擬的應急設施則為50個和89個)節(jié)點的網(wǎng)絡，根據(jù)設施級數(shù)R的不同取值設計了6個不同規(guī)模的算例，計算結(jié)果和LR算法性能如表2和圖1所示?？梢钥闯?，該問題上下界的相對誤差最大為6.59%，最小為1.18%，計算精度在可接受范圍內(nèi)。結(jié)果表明，R的取值對RCFLP最優(yōu)選址方案影響很小，這與文獻[1]和[2]針對RUFLP的研究結(jié)論相一致。

此外，為了測試文中所提近似算法的性能，在LR算法中分別采用了3種策略求解客戶分派子問題(ASP)，并從求解精度和求解效率兩個方面進行了對比分析(見表3)。3種策略分別為：(1)CPLEX策略：LR算法中采用CPLEX軟件對ASP進行精確求解；(2)近似算法策略：LR算法中采用近似算法求解ASP；(3)混合策略：前期采用近似算法策略快速求解，后期采用CPLEX策略提高求解精度。

由表3可知，采用CPLEX策略求解49節(jié)點算例(R=2、3、4時)，其精度相對于近似算法策略僅分別提高1.08%、0、1.37%，但求解時間卻是后者的10倍以上，特別是隨著問題規(guī)模的不斷增大，求解時間也急劇增大；當問題規(guī)模擴大到88節(jié)點時，已無法在30min內(nèi)求得問題的解。此外，分別在g=100、g=130、g=160(g為迭代次數(shù))代時引入CPLEX提高精度的混合策略對LRCFLP進行求解，結(jié)果表明：與近似算法策略相比，49節(jié)點算例中引入混合策略雖能略提高計算精度，卻需耗費大量的計算時間，例如R=2時，求解誤差從1.08%分別縮小到0.53%、0.60%和0.91%，但求解時間卻分別增加了7.49倍、6.57倍和2.59倍；而在88節(jié)點算例中，混合策略依然無法在30min內(nèi)求解LRCFLP。綜上所述，基于近似算法的LR啟發(fā)式算法在計算效率上具有顯著優(yōu)勢，而計算精度也在可接受范圍內(nèi)，因而具有良好的計算性能。

表1 拉格朗日乘子μ取不同初值的LR算法迭代次數(shù)

注：U[a,b]表示在a與b之間隨機均勻產(chǎn)生。

表2 計算結(jié)果和LR算法性能

注：誤差=(上界-下界)/上界。

以49節(jié)點算例(R=2)為例，圖2給出了UFLP的最優(yōu)選址-分配方案，圖3給出了所有設施具有相同失靈概率時RUFLP的最優(yōu)選址-分配方案，圖4給出了不同設施的失靈概率不同時RUFLP的最優(yōu)選址-分配方案，圖5則是本文研究的設施失靈概率不同時RCFLP的最優(yōu)選址-分配方案?？梢钥闯?，從不考慮設施失靈風險的選址問題到可靠性選址問題，從無容量限制的可靠性選址問題到有容量限制的可靠性選址問題，最優(yōu)的選址-分配方案均發(fā)生了變化。因此，設施失靈風險與設施容量這兩個因素對設施選址決策都有顯著影響。

表3 采用近似算法與CPLEX分別求解ASP子問題的比較

圖1 拉格朗日對偶問題的下界收斂曲線

圖2 UFLP選址-分派方案[1] 圖3 設施失靈概率相同時RUFLP選址-分派方案[1]

為分析設施容量對選址決策的影響，以上述49點算例(R=2)為例，以各個設施的容量為基數(shù)，再將其擴大到一定的倍數(shù)，計算結(jié)果如表4所示。可以發(fā)現(xiàn)，當設施容量越小時，需要設置的設施點越多，且最優(yōu)選址方案不太穩(wěn)定；當容量逐步擴大時，問題越來越接近于RUFLP，最優(yōu)選址方案也趨于穩(wěn)定。

表4 設施容量的敏感性分析

4 結(jié)論

設施網(wǎng)絡可能面臨各種失靈風險，盡管失靈現(xiàn)象不常發(fā)生，但一旦發(fā)生，后果可能很嚴重。加上設施選址是一個戰(zhàn)略性決策問題，在短期內(nèi)一般不會改變，因而在在選址階段就考慮設施失靈風險是十分必要的。為此，本文在RUFLP現(xiàn)有研究成果的基礎上，進一步考慮設施容量限制，建立了一類RCFLP優(yōu)化模型，并設計了一種LR算法進行求解。結(jié)果表明：設施容量對RCFLP選址決策有顯著影響，即設施容量越小時，需要設置的設施數(shù)量越多，且最優(yōu)選址方案不太穩(wěn)定；設施級數(shù)R的取值對RCFLP最優(yōu)選址方案沒有影響。針對所建的非線性混合整數(shù)規(guī)劃模型，通過線性轉(zhuǎn)化技術和LR算法求解，計算效率較高。

進一步的研究可考慮非完全信息以及客戶最優(yōu)搜索決策行為條件下的RCFLP。此外，還可在選址與庫存、路徑等的集成決策問題(如定位-路徑問題、定位-路徑-庫存問題)中考慮設施失靈風險。

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

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

[3] 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.

[4] 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.

[5] 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.

[6] Berman O, Krass D, Menezes M. Locating facilities in the presence of disruptions and incomplete information[J]. Decision Sciences, 2009, 40(4): 845- 868.

[7] Snyder L V, Caparra M, Daskin M S. Planning for disruptions in supply chain networks[J]. Operations Research, 2006, 25(10): 234-259.

[8] 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.

[9] 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.

[10] Church R L, Scaparra M P, Hanley J. Optimizing passive protection in facility systems[R]. Working paper, Isoldex, Spain, 2006.

[11] 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.

[12] 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.

[13] Sherali H D, A Alameddine. A new reformulation-linearization technique for bilinear programming problems[J]. Global Optimization, 1992, 2(4): 379- 410.

[14] Fisher M L. The Lagrangian relaxation method for solving integer programming problems[J]. Management Science, 1981, 27(1): 1-18.

[15] Lim C, Sherali H D. Convergence and computational analyses for some variable target value and sub-gradient deflection methods[J]. Computational Optimization and Applications, 2006, 34(3): 409- 428.

Reliability Capacitated Fixed-charge Location Problem

ZHOU Yu-feng1, MA Zu-jun2, WANG Ke-ming3

(1.School of Business Planning, Chongqing Technology and Business University, Chongqing 400067, China; 2.Institute for Logistics and Emergency Management, School of Economics and Management, Southwest Jiaotong University, Chengdu 610031, China; 3.Emei Campus, Southwest Jiaotong University, Emeishan 614202, China)

Infrastructure networks have the risk of disruptions. Because facility location is a strategic decision that can not be changed in a short time, it is critical to account for the non-complete reliability of facility in designing the network. The classical reliability uncapacitated fixed-charge location problem is extended by considering the capacity constraint. And the reliability capacitated fixed-charge location problem under the risk of disruptions is formulated as a mixed integer nonlinear programming model. Considering the characteristics of the model, a linearization technique is applied to convert the model and a lagrangian relaxation algorithm is developed to solve the problem. A numerical example is given to verify the model and algorithm performance. The results show that facility capacity has a notable impact on location decision, and the unexpected failures of facility and capacity constraint of facility should be fully considered in real-life location decision process.

facility location; facility disruptions; reliability; capacitated; Lagrangian relaxation

2012-12-16

國家自然科學基金項目(90924012,71090402,71271227);教育部新世紀優(yōu)秀人才支持計劃資助項目(NCET-10- 0706)；四川省哲學社會科學研究規(guī)劃項目(SC11B049)；四川省學術和技術帶頭人培養(yǎng)資金項目(川人社辦發(fā)[2011]441號)；中央高?；究蒲袠I(yè)務費專項資金資助項目(SWJTU11CX152,2682013CX073)

周愉峰(1984-)，男，湖南雙峰人，講師，博士，研究方向：應急物流、物流系統(tǒng)優(yōu)化;馬祖軍(1974-)，男，浙江開化人，教授，博士生導師，研究方向：物流與供應鏈管理、應急管理、產(chǎn)品回收管理。

C931；O221

A

1007-3221(2015)03- 0006- 08