《不確定設施選址問題的理論與算法研究》是依託北京工業大學，由徐大川擔任項目負責人的面上項目。
基本介紹
- 中文名：不確定設施選址問題的理論與算法研究
- 項目類別：面上項目
- 項目負責人：徐大川
- 依託單位：北京工業大學
項目摘要,結題摘要,
項目摘要
設施選址問題是運籌學的核心問題之一，該問題是NP難解的，設計近似算法是處理該問題的有效途徑之一。工廠，配送中心，及其他設施通常運行若干年或更長，在這期間運作環境可能會發生實質的變化。經典的設施選址模型里的費用，需求，運輸時間，及其他參數都可能變得高度不確定。由此引起計算機科學、管理和運籌界的一些專家對不確定設施選址問題的研究興趣。對於不確定設施選址問題已經有了相當多的處理技巧。我們主要關注隨機和魯棒設施選址模型的近似算法。確定型設施選址問題近似算法的研究技巧非常豐富，可以為不確定型問題提供研究工具。設施選址問題里的模型眾多，如：經典的度量無容量約束的單層設施選址問題，多層設施選址問題，有容量約束的設施選址問題，有服務安裝費用的設施選址問題，單層設施選址對策問題，多層設施選址對策問題，容錯設施選址問題等。相應的不確定型問題都值得我們去研究。
結題摘要
設施選址問題是運籌學問題中的重要問題之一. 實際問題中, 不確定因素隨處可見, 不確定性設施選址問題受到了大量專家學者的關注. 確定和不確定設施選址問題均為NP-困難問題. 近似算法是解決此類問題的重要手段之一. 本項目研究確定和不確定設施選址問題及其相關問題的近似算法. 在不確定設施選址問題中, 兩階段隨機設施選址問題是常見的一類, 在這類問題中，顧客的分布是已知的，問題的隨機性轉化為場景及該場景出現的機率. 我們給出了帶次模懲罰的設施選址問題的原始對偶3-近似算法，該算法提出了在對偶上升過程中處理次模結構的技巧，具有很強的移植性. 沿用該算法的思想, 我們分別給出了帶次模懲罰的隨機設施選址問題，倉庫-零售商網路設計問題，以及隨機運輸-庫存網路設計問題 的原始對偶3-近似算法. 利用對偶擬合技巧，我們給出了倉庫-零售商網路設計問題的1.861-近似算法. 在倉庫-零售商網路設計問題中限制開設倉庫的個數不超過k, 則得到k-中心倉庫-零售商網路設計問題, 我們利用倉庫-零售商網路設計問題的原始對偶算法以及算法的拉格朗日乘子保持性質, 得到了k-中心倉庫-零售商網路設計問題的6-近似算法. 我們提出了帶次模懲罰的倉庫零售商問題, 並給出原始對偶3-近似算法. 基於線性規劃捨入的技巧, 我們對帶線性懲罰的設施選址問題和次模懲罰的設施選址問題分別得到了1.5148和2-近似算法. 在隨機設施選址問題的基礎上, 可以增加不同的約束得到新的變形. 如果顧客的需求是分等級的,這類問題稱為隨機優先設施選址問題，我們給出了原始對偶3-近似算法. 如果顧客需要連線到多個設施上, 這類問題稱為隨機容錯設施選址問題, 我們得到了線性規劃捨入5-近似算法. 對於隨機設施選址問題，近似比估計的是算法在平均意義下所得解的質量，單場景界可以估計每個場景下解的質量，我們給出了帶線性懲罰的隨機設施選址問題的基於線性規劃捨入的3.0294單場景界．
