《光網路規劃流量疏導最佳化》是依託華中科技大學，由呂志鵬擔任項目負責人的面上項目。
基本介紹
- 中文名：光網路規劃流量疏導最佳化
- 項目類別：面上項目
- 項目負責人：呂志鵬
- 依託單位：華中科技大學
中文摘要,結題摘要,
中文摘要
流量疏導問題是下一代光網路規劃的核心挑戰性難題。在理論上，流量疏導問題已被證明為NP難度問題，它結合了多個組合最佳化問題，如裝箱問題，路由問題，約束滿足問題等。同時，流量疏導問題在航空流量控制、城市交通流量管理等領域有著廣泛的套用。因此，設計求解流量疏導問題的高效最佳化算法具有重要的實際意義和理論價值。本課題擬研究來自通信公司的真實的光網路流量疏導問題的最佳化算法。研究工作主要包括：（1）研究光網路規劃流量疏導問題的初始解生成算法和高效局部搜尋算法；（2）將局部搜尋算法和進化算法相結合，藉助局部搜尋的局部搜尋能力和進化算法的全局尋優能力，研究求解光網路規劃流量疏導問題的混合進化算法；（3）採用鬆弛和劃分的策略，研究求解光網路規劃流量疏導問題的下界算法，以評估啟發式最佳化算法的性能。本課題的研究成果可直接套用於國內通信公司的光網路規劃，同時加深我們對挑戰性NP難度問題及其它流量疏導問題的理解和研究。
結題摘要
流量疏導問題是下一代光網路規劃的核心挑戰性難題。在理論上，流量疏導問題已被證明為NP難度問題，它結合了多個組合最佳化問題，如裝箱問題，路由問題，約束滿足問題等。同時，流量疏導問題在航空流量控制、感測器網路規劃、城市交通流量管理等領域有著廣泛的套用。因此，設計求解流量疏導問題的高效最佳化算法具有重要的實際意義和理論價值。本課題研究了來自通信公司的真實的光網路流量疏導問題的最佳化算法。研究成果主要包括：（1）結合我國通信公司（如華為）的具體業務場景，首次提出了光網路規劃流量疏導問題的數學模型，並提出了求解該問題的初始解生成算法和高效局部搜尋算法。在此基礎上，將局部搜尋算法和精確算法相結合，藉助啟發式算法的全局搜尋能力和精確算法的局部尋優能力，研究求解光網路規劃流量疏導問題的混合數學啟發式算法。通過與當前國際文獻中的最好的算法結果進行詳細地對比和分析，表明了所提出的算法在優度和效率兩方面的優勢。（2）研究了若干網路規劃流量疏導問題及與其緊密相關的子問題、如最小連通支配集問題、多維二次背包問題、負載均衡問題、路由和波長分配問題等。這些子問題是解決光網路規劃流量疏導問題的瓶頸所在，對其求解具有重要的理論意義和實際價值。對於這些相關的子問題，分別設計了求解它們的高效啟發式最佳化算法，與當前文獻中最好結果進行了詳細的對比，表明所提出的算法的有效性。特別地，本項目中所提出的算法對以上問題均改進了若干國際文獻中的最好結果。（3）參加了與本項目相關的兩個國際算法競賽——2016年ROADEF/EURO庫存路由配送問題挑戰賽以及2017年SAT國際競賽，並分別獲得了全球第三名和全球第一名的成績。本課題的研究成果可直接套用於國內通信公司的光網路規劃，同時加深我們對挑戰性NP難度問題及其它流量疏導問題的理解和研究。
