周愉峰， 馬祖軍， 王恪銘

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

?

有容量限制的可靠性固定費(fèi)用選址問題

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

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

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

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

0 引言

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

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

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

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

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

1 RCFLP優(yōu)化模型

1.1 問題描述與假設(shè)

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

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

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

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

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

1.2 符號說明

參數(shù)：

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

j：候選設(shè)施編號，j=0,1,…,J，其中j=J表示虛擬的應(yīng)急設(shè)施；

hi：客戶i的需求量；

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

vj：設(shè)施j的容量，且vJ足夠大；

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

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

dij：設(shè)施j到客戶i的單位需求運(yùn)輸成本，且diJ=φi；

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

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

決策變量：

Xj：在j處開設(shè)設(shè)施為1，否則為0；

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

Pijr：由設(shè)施j在r級上服務(wù)客戶i的概率；

xij：設(shè)施j到客戶i的運(yùn)量。

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ī)劃模型，目標(biāo)函數(shù)中包含三元變量xijpijrYijr和二元變量pijrYijr，約束(8)中也包含二元變量pijrYijr，使得該模型的求解很困難。在此采用Sherali和Alameddine[13]提出的線性化技術(shù)來轉(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’的目標(biāo)函數(shù)中依然含有二元變量xijWijr。令Zij=xij/hi，表示客戶的需求由設(shè)施j滿足的比例，有0≤Zij≤1，則xij=hiZij。由于客戶i最多只可能在某一級上分派給設(shè)施j，故xij等價于xijr，則Zij等價于Zijr。因此，式(16)可改寫為

再次應(yīng)用線性化轉(zhuǎn)換技術(shù)：令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等軟件包進(jìn)行求解，但即使針對一個中等規(guī)模的問題也要花費(fèi)很長的運(yùn)算時間。為此，下面設(shè)計一種拉格朗日松弛算法來求解該模型。

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

(27)

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

為了計算最優(yōu)的客戶分派決策變量Yijr和需求分配決策變量xij，可注意到該決策問題對于每個客戶是可分的[2]。對于給定的μ，客戶i的分派問題(ASP)可以描述成如下的松弛子問題(Relaxed Subproblem，RSP)。為了簡化，模型中省略了Yijr,pijr,Wijr,Zijr,Vijr中的下標(biāo)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ī)模較大時計算效率很低。為此，設(shè)計了如下的近似算法：

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

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

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

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

②求解選址子問題；

③求解客戶分派子問題；

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

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

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

3 算例研究

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

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

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

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

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

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

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

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

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

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

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

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

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

表4 設(shè)施容量的敏感性分析

4 結(jié)論

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

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

[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

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

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

C931；O221

A

1007-3221(2015)03- 0006- 08