《樞紐港選址及相關問題的算法設計》是依託上海交通大學，由葛冬冬擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：樞紐港選址及相關問題的算法設計
- 項目類別：青年科學基金項目
- 項目負責人：葛冬冬
- 依託單位：上海交通大學
項目摘要,結題摘要,
項目摘要
樞紐港選址問題(hub location problem) 是一個中心輻射型(hub-and-spoke)物流運輸與網路管理的普適模型。作為運籌學的一個經典問題，對其及相關問題的研究有著重要的套用價值和理論意義。本項目計畫對樞紐港選址與相關的理論模型進行以下幾個方面的探討：首次提出討論發展其半正定規劃鬆弛的緊緻下界(Lower bounds based on Semidefinite Programming(SDP) relaxation)。對樞紐港選址及其相關的多個問題可能的近似算法進行討論，首次理論上對某些問題提出可證明的近似界。結合中國目前航空業發展的實際情況，為我國的航路設計和機場建設，以及各種物流網路運行探求成本節約的方法。
結題摘要
背景：本項目以樞紐港選址與分流問題為基礎，研究了與其相關的算法設計問題，特別是涉及到的整數規劃問題，二次規劃問題，以及稀疏最佳化問題。 樞紐港的選址與分流問題是在現實中非常重要的運籌學問題，問題的模型也具有廣泛的普適性，存在於航空，物流，通信等多個領域。 Background: 方向：樞紐港選址與分流問題的模型本質上是一個線性約束的二次非凸整數規劃問題，在難度上是一個NP-難問題。因此我們在項目開初，以及隨著進行，提出了如下的研究方向： (1) 對問題的難度分析。以及如何尋求比較好的可解的鬆弛下界。 (2) 結合實際數據的隨機最佳化問題。 (3) 我們注意到問題的最優解具有稀疏化的特點，如何針對這一特點，開展相關的稀疏最佳化理論分析？ (4) 還有哪些相關問題值得研究？ 主要內容與結果：針對以上的幾個問題，進行了深入研究： (1) 我們證明了對於此類問題常規的快速矩陣提升SDP和向量提升SDP發展出的下界一致(Mathematics of Operations research，2011)。 (2) 隨機需求下的樞紐港選址問題。我們著重關注於魯棒最佳化，將問題鬆弛為一個二次錐最佳化問題， 目前正在進行最後的數據測算。 (3) 稀疏最佳化。我們在2011年首次考慮引入稀疏解重建的方法，對問題的複雜度和算法的收斂性進行了深入理論分析(mathematical programming,2011)。在2012年裡，對結合了p模與二次函式的模型進行了複雜度分析( Mathematical Programming,2012)。論文在谷歌學術上被引用67次。 (4) 我們也對在一個樞紐港上有飛機進出時的調度問題的隨機最佳化做了研究，證明了在某些情況下，整數解存在，並且問題可以歸結為一個存在多項式算法的確定性最佳化問題。已經被Mathematics of Operations Research接受。 科學意義：我們的研究已經產生的結果均發表在最佳化與運籌的旗艦期刊上。已經涉及到的問題，在理論意義上，對二次矩陣規劃，整數規劃，Co-positive規劃，稀疏最佳化，都有著一流結果產生。在運籌學的實際模型上，對定港分流問題，調度問題，工程的信號處理問題，生產調度問題，都有指導意義。作為上海數策公司的運籌學顧問（義務諮詢），根據稀疏最佳化方法，為上海通用設計的生產調度方案，較通用傳統做法有了較大提高。
