考慮設(shè)施失效的選址問(wèn)題、模型與算法.pdf

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

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

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

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

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

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