考慮設施失效的選址問題、模型與算法.pdf

1、設施選址問題是供應鏈網(wǎng)絡、后勤網(wǎng)絡和服務網(wǎng)絡設計的基礎性問題，合理地確定設施的位置有利于高效、經(jīng)濟地為客戶提供產(chǎn)品、信息或服務。在現(xiàn)實生活中，設施因為自然或人為原因，如地震、恐怖襲擊等，而無法正常工作的情況常有發(fā)生，這種情況被稱為設施失效或設施中斷(facility disruption)。設施失效的危害很大，它導致供應中斷、服務中斷、顯著提高設施系統(tǒng)的服務成本、延遲客戶需求滿足、導致客戶流失，甚至可能對供應鏈或服務網(wǎng)絡造成全局性和災難

2、性的影響。設施選址規(guī)劃是戰(zhàn)略決策，設施網(wǎng)絡建立后難以在短時間內(nèi)重建和調(diào)整。當設施失效發(fā)生后，補救措施往往很有限，且恢復時間較長。因此，決策者在建立設施網(wǎng)絡之初就需要考慮到設施失效的可能性，采用各種手段提高設施系統(tǒng)可靠性。此外，設施選址問題是NP難問題。隨著整數(shù)規(guī)劃理論的發(fā)展，很多大規(guī)模商業(yè)優(yōu)化軟件可以比較快速地求解大規(guī)模的經(jīng)典選址問題，但對于考慮設施失效可能性的模型，這些商業(yè)軟件仍然只能有效求解小到中等規(guī)模的問題，隨著問題規(guī)模增加其求解

3、效率顯著下降，甚至無法求解。因此，需要針對具體的模型設計特定的算法，使之能又好又快地求解大規(guī)模問題。
　　針對這些問題，論文首先研究了一個考慮設施失效和保護的選址問題，該問題通過對設施進行保護和為需求節(jié)點分配備份設施來提高設施網(wǎng)絡的可靠性。我們指出針對該問題的已有模型只適合處理所有設施失效概率都相同的情況，進而提出了一種簡潔的、可以處理不同設施具有不同失效概率的擴展模型，并基于擴展模型分析了問題最優(yōu)解的結構性質(zhì)。由于當前最好的數(shù)學

4、規(guī)劃軟件CPLEX不能直接求解該模型的大規(guī)模實例。因此，我們提出了一種結合拉格朗日松弛和局部搜索啟發(fā)式求解算法，通過分析原問題的結構特點，把原問題松弛并分解為多個獨立子問題分別求解。另一方面，采用了基于貪婪策略的局部搜索啟發(fā)式方法對可行解進行改進。通過對標準數(shù)據(jù)集的計算實驗證明了所提算法收斂速度快，求解效率和求解質(zhì)量都非常高。
　　考慮到在現(xiàn)實中加固資金和資源往往是有限的，并且決策者對設施失效風險的態(tài)度也會影響對加固的投入。論文繼

5、而提出了考慮加固預算約束的選址和加固問題。給出了預算約束下的選址和加固模型，并給出了一個多階段加固模型，指出兩者的聯(lián)系與區(qū)別。提出了三個結合拉格朗日松弛和局部搜索的求解算法。三個算法松弛了不同的約束，采用不同的方法求解松弛問題和構造可行解。通過大量計算實驗對三個算法的求解效率和求解質(zhì)量進行了對比，分析了三個算法各自的特點，證明了所提算法在求解中等到大規(guī)模問題時相對CPLEX有非常明顯的優(yōu)勢。
　　最后，論文提出了考慮設施能力受限和

6、單源分配約束的可靠性選址問題。該問題考慮到現(xiàn)實中設施能力往往有限，并且在正常情況下客戶一般由某特定設施單源服務的情況，通過合理地決定設施的數(shù)目和位置，將系統(tǒng)的冗余能力用于需求備份。提出了一個期望值模型和一個兩階段隨機規(guī)劃模型，討論了兩個模型的異同。分析了模型的結構性質(zhì)并提出了一個拉格朗日松弛求解算法。通過對松弛問題結構的分析，對變量進行了約減，降低松弛問題的求解難度，并提出了構造可行解的啟發(fā)式方法。通過對上百組標準數(shù)據(jù)集的計算，證明了所