《多層設施選址問題的理論與算法研究》是依託天津理工大學，由吳晨晨擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：多層設施選址問題的理論與算法研究
- 項目類別：青年科學基金項目
- 項目負責人：吳晨晨
- 依託單位：天津理工大學
項目摘要,結題摘要,
項目摘要
設施選址問題是組合最佳化中最經典的問題之一，受到了專家學者的廣泛關注。在設施選址問題中，顧客由一個開設的設施提供服務。在很多情況下，滿足顧客的需求也許需要一系列的設施。這樣就衍生出設施選址問題的一個重要變形——多層設施選址問題。這類問題在物流管理，應急管理，衛生保健等方面有著重要的套用。除了增加多層約束的變形外，設施選址問題還有其他的重要變形，例如帶容量限制的設施選址問題，帶懲罰的設施選址問題，k-設施選址問題等等。這些變形都可以看做在設施選址問題的基礎上對設施或顧客增加了某一類約束。而隨著經濟和社會的高速發展，實際生產中出現了更多具有複雜結構的問題。本項目考慮經典的多層設施選址問題及具有不同網路結構的變形問題。本項目研究上述NP-困難問題快速有效的近似算法。在這類算法中不要求找到問題的最優解而是可行解並分析二者之間的比值。
結題摘要
隨著經濟的高速發展，流水線工作顯得尤為重要，尤其在選址過程中體現得也尤為明顯。本項目對當今科技水平下的諸多現實問題進行抽象，得到了更為貼切的推廣模型，在前人研究基礎上加以創新和推廣，提出了一些新型近似算法。本項目圍繞多層設施選址問題中具有深刻現實意義的NP-難問題，從近似算法角度進行研究。研究的問題主要包括設施選址問題，圖劃分問題和DC-規劃問等，取得了很好的研究成果。在研究上述問題過程中將不同問題的算法設計技巧相融合，對後續研究提供了更多的思路和啟發。在本項目支持下共發表期刊論文15篇(其中SCI檢索論文14篇)，會議論文2篇。 在設施選址問題方面，我們考了2-層設施選址問題的變形--帶軟容量的設施選址問題和魯棒設施選址問題，得到原始對偶的(4+1/(e-1)+\epi)和(3+\epi)-近似算法。我們考慮軟容量多層設施選址問題，利用線性規劃捨入得到5.5053-近似算法。我們提出和研究了帶懲罰的一般設施選址問題並設計了其7.88-近似算法, 隨後此結果被我們改進到了5.83。 通過違背開設設施個數限制的要求，我們設計得到帶懲罰的k-中位問題的(1+\sqrt_3+\epi)-近似算法。此外, 我們研究了多階段設施選址問題，隨機設施選址問題，容錯設施選址問題，平方度量設施選址問題和k-設施選址問題等。 圖劃分問題方面，我們主要研究了極大k-非割問題的複雜性和近似算法以及利用譜分析方法討論極大有向割問題的近似算法。 在算法設計的技巧研究方面，我們討論了非凸問題的DC-規劃，將極大和極小的容錯的度數集中生成子圖問題分別利用DC-算法進行求解。 作為技巧的延伸，我們還研究了斯坦納樹和無關機排序的部分變形問題。
