【摘要】：設(shè)施選址問題是供應(yīng)鏈網(wǎng)絡(luò)、后勤網(wǎng)絡(luò)和服務(wù)網(wǎng)絡(luò)設(shè)計(jì)的基礎(chǔ)性問題,合理地確定設(shè)施的位置有利于高效、經(jīng)濟(jì)地為客戶提供產(chǎn)品、信息或服務(wù)。在現(xiàn)實(shí)生活中,設(shè)施因?yàn)樽匀换蛉藶樵?如地震、恐怖襲擊等,而無法正常工作的情況常有發(fā)生,這種情況被稱為設(shè)施失效或設(shè)施中斷(facility disruption)。設(shè)施失效的危害很大,它導(dǎo)致供應(yīng)中斷、服務(wù)中斷、顯著提高設(shè)施系統(tǒng)的服務(wù)成本、延遲客戶需求滿足、導(dǎo)致客戶流失,甚至可能對(duì)供應(yīng)鏈或服務(wù)網(wǎng)絡(luò)造成全局性和災(zāi)難性的影響。設(shè)施選址規(guī)劃是戰(zhàn)略決策,設(shè)施網(wǎng)絡(luò)建立后難以在短時(shí)間內(nèi)重建和調(diào)整。當(dāng)設(shè)施失效發(fā)生后,補(bǔ)救措施往往很有限,且恢復(fù)時(shí)間較長。因此,決策者在建立設(shè)施網(wǎng)絡(luò)之初就需要考慮到設(shè)施失效的可能性,采用各種手段提高設(shè)施系統(tǒng)可靠性。此外,設(shè)施選址問題是NP難問題。隨著整數(shù)規(guī)劃理論的發(fā)展,很多大規(guī)模商業(yè)優(yōu)化軟件可以比較快速地求解大規(guī)模的經(jīng)典選址問題,但對(duì)于考慮設(shè)施失效可能性的模型,這些商業(yè)軟件仍然只能有效求解小到中等規(guī)模的問題,隨著問題規(guī)模增加其求解效率顯著下降,甚至無法求解。因此,需要針對(duì)具體的模型設(shè)計(jì)特定的算法,使之能又好又快地求解大規(guī)模問題。針對(duì)這些問題,論文首先研究了一個(gè)考慮設(shè)施失效和保護(hù)的選址問題,該問題通過對(duì)設(shè)施進(jìn)行保護(hù)和為需求節(jié)點(diǎn)分配備份設(shè)施來提高設(shè)施網(wǎng)絡(luò)的可靠性。我們指出針對(duì)該問題的已有模型只適合處理所有設(shè)施失效概率都相同的情況,進(jìn)而提出了一種簡潔的、可以處理不同設(shè)施具有不同失效概率的擴(kuò)展模型,并基于擴(kuò)展模型分析了問題最優(yōu)解的結(jié)構(gòu)性質(zhì)。由于當(dāng)前最好的數(shù)學(xué)規(guī)劃軟件CPLEX不能直接求解該模型的大規(guī)模實(shí)例。因此,我們提出了一種結(jié)合拉格朗日松弛和局部搜索啟發(fā)式求解算法,通過分析原問題的結(jié)構(gòu)特點(diǎn),把原問題松弛并分解為多個(gè)獨(dú)立子問題分別求解。另一方面,采用了基于貪婪策略的局部搜索啟發(fā)式方法對(duì)可行解進(jìn)行改進(jìn)。通過對(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ì)加固的投入。論文繼而提出了考慮加固預(yù)算約束的選址和加固問題。給出了預(yù)算約束下的選址和加固模型,并給出了一個(gè)多階段加固模型,指出兩者的聯(lián)系與區(qū)別。提出了三個(gè)結(jié)合拉格朗日松弛和局部搜索的求解算法。三個(gè)算法松弛了不同的約束,采用不同的方法求解松弛問題和構(gòu)造可行解。通過大量計(jì)算實(shí)驗(yàn)對(duì)三個(gè)算法的求解效率和求解質(zhì)量進(jìn)行了對(duì)比,分析了三個(gè)算法各自的特點(diǎn),證明了所提算法在求解中等到大規(guī)模問題時(shí)相對(duì)CPLEX有非常明顯的優(yōu)勢(shì)。最后,論文提出了考慮設(shè)施能力受限和單源分配約束的可靠性選址問題。該問題考慮到現(xiàn)實(shí)中設(shè)施能力往往有限,并且在正常情況下客戶一般由某特定設(shè)施單源服務(wù)的情況,通過合理地決定設(shè)施的數(shù)目和位置,將系統(tǒng)的冗余能力用于需求備份。提出了一個(gè)期望值模型和一個(gè)兩階段隨機(jī)規(guī)劃模型,討論了兩個(gè)模型的異同。分析了模型的結(jié)構(gòu)性質(zhì)并提出了一個(gè)拉格朗日松弛求解算法。通過對(duì)松弛問題結(jié)構(gòu)的分析,對(duì)變量進(jìn)行了約減,降低松弛問題的求解難度,并提出了構(gòu)造可行解的啟發(fā)式方法。通過對(duì)上百組標(biāo)準(zhǔn)數(shù)據(jù)集的計(jì)算,證明了所提算法對(duì)各種規(guī)模的算例都可以求得高質(zhì)量的解。對(duì)上述三個(gè)模型,都基于湖南省的一個(gè)具體選址案例進(jìn)行了深入分析。通過對(duì)模型各重要參數(shù)的靈敏度分析深入剖析了模型的性質(zhì),揭示了一些符合直覺和反直覺的規(guī)律,并給出了合理的分析與解釋,這些為決策者科學(xué)決策提供了管理上的啟示。
[Abstract]:Facility location is a fundamental problem in the design of supply chain network, logistics network and service network. Reasonable location of facilities is conducive to efficient and economical provision of products, information or services to customers. This is called facility disruption. Facility failure is very harmful. It can lead to supply disruption, service disruption, significantly increase the service cost of the facility system, delay customer demand satisfaction, lead to customer churn, and may even have a global and catastrophic impact on the supply chain or service network. Facility location planning is a strategic decision, and it is difficult to reconstruct and adjust the facility network in a short time after its establishment. When the facility failure occurs, the remedial measures are often limited and the recovery time is long. Therefore, decision makers need to consider the possibility of facility failure at the beginning of the establishment of the facility network, and adopt various means to improve the reliability of the facility system. In addition, facility location problem is NP-hard. With the development of integer programming theory, many large-scale commercial optimization software can solve large-scale classical location problem more quickly, but for the model considering the possibility of facility failure, these commercial software can only effectively solve small to medium-scale problems, with the problem planning. In order to solve large-scale problems quickly and efficiently, we need to design specific algorithms for specific models. To solve these problems, we first study a site selection problem considering facilities failure and protection, which protects facilities and serves as demand section. We point out that the existing models for this problem are only suitable for all facilities with the same failure probability, and then we propose a simple extended model which can handle different facilities with different failure probability. Because the best mathematical programming software CPLEX can not directly solve large-scale examples of the model, we propose a heuristic algorithm combining Lagrange relaxation and local search. By analyzing the structural characteristics of the original problem, the original problem is relaxed and decomposed into several independent sub-problems to solve respectively. A greedy strategy based local search heuristic method is used to improve the feasible solution. Experiments on standard data sets show that the proposed algorithm has fast convergence speed, high efficiency and high quality. This paper then proposes a location and reinforcement problem with budget constraints. A multi-stage reinforcement model is presented, and the relationship and difference between the two models are pointed out. The three algorithms relax different constraints and use different methods to solve relaxation problems and construct feasible solutions. The efficiency and quality of the three algorithms are compared through a large number of computational experiments. The characteristics of the three algorithms are analyzed. It is proved that the proposed algorithm is very good compared with CPLEX in solving medium to large scale problems. Finally, the paper proposes a reliability location problem considering the limitation of facility capacity and single-source allocation constraints. Considering the fact that facility capacity is often limited in reality and that customers are usually served by a single-source facility under normal circumstances, the system is redundant by reasonably determining the number and location of facilities. An expected value model and a two-stage stochastic programming model are proposed. The similarities and differences between the two models are discussed. The structural properties of the model are analyzed and a Lagrange relaxation algorithm is proposed. By calculating hundreds of sets of standard data sets, it is proved that the proposed algorithm can obtain high-quality solutions for all kinds of numerical examples. The above three models are all based on a specific location case in Hunan Province. Degree analysis deeply analyzes the nature of the model, reveals some intuitive and counter-intuitive laws, and gives reasonable analysis and explanation, which provides management inspiration for decision makers in scientific decision-making.
【學(xué)位授予單位】：國防科學(xué)技術(shù)大學(xué)
【學(xué)位級(jí)別】：博士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP301.6

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 周靜嫻;胡志華;張夢(mèng)君;;面向地震災(zāi)害的社會(huì)帳篷募集點(diǎn)預(yù)選址問題[J];計(jì)算機(jī)應(yīng)用;2014年04期

2 劉玉堂;方奇志;;限制設(shè)施選址問題的近似算法[J];計(jì)算機(jī)工程與科學(xué);2013年04期

3 程魁;馬良;;平面選址問題的螢火蟲算法[J];上海理工大學(xué)學(xué)報(bào);2013年03期

4 劉煥平，林曉東，，楊義先,毛敏;網(wǎng)上數(shù)據(jù)庫的選址問題[J];計(jì)算機(jī)工程與應(yīng)用;1999年02期

5 申瑞玲;霍佳震;李旭芳;;基于混合需求的設(shè)施選址問題研究[J];計(jì)算機(jī)應(yīng)用研究;2013年11期

6 王雪蓮;汪波;;品牌推廣動(dòng)態(tài)選址問題及其混合算法研究[J];系統(tǒng)仿真學(xué)報(bào);2009年09期

7 陶莎;胡志華;;需求與物流網(wǎng)絡(luò)不確定下的應(yīng)急救援選址問題[J];計(jì)算機(jī)應(yīng)用;2012年09期

8 周靜嫻;肖玲;胡志華;;基于雙層隨機(jī)規(guī)劃的多時(shí)段募集點(diǎn)選址問題[J];廣西大學(xué)學(xué)報(bào)(自然科學(xué)版);2014年02期

9 陳光亭,丁巍,張固;帶禁區(qū)約束的直線上選址問題[J];杭州電子工業(yè)學(xué)院學(xué)報(bào);2004年04期

10 翁克瑞;許自豪;;帶覆蓋需求約束的設(shè)施選址問題[J];數(shù)學(xué)的實(shí)踐與認(rèn)識(shí);2014年11期

相關(guān)會(huì)議論文 前8條

1 趙一新;;淺談博物館的選址問題[A];浙江省博物館學(xué)會(huì)2001年學(xué)術(shù)研討會(huì)文集[C];2001年

2 王文峰;郭波;劉新亮;;多級(jí)覆蓋設(shè)施選址問題建模及求解方法研究[A];第九屆中國管理科學(xué)學(xué)術(shù)年會(huì)論文集[C];2007年

3 張敏;楊s

本文編號(hào)：2241805