不確定環境下魯棒網路設計最佳化模型的研究及套用

《不確定環境下魯棒網路設計最佳化模型的研究及套用》是依託武漢大學，由胡捷擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：不確定環境下魯棒網路設計最佳化模型的研究及套用
• 項目類別：青年科學基金項目
• 項目負責人：胡捷
• 依託單位：武漢大學

項目摘要

不確定環境下的最佳化問題一直是一個研究熱點和難題，而網路設計問題作為與實際生活的各個方面息息相關的一個經典數學問題，一直受到研究者的關注。但是網路設計的優劣受到多種不確定因素的影響，例如不確定的流量需求或者突發事件造成的網路局部中斷等，這些不利影響會對網路的使用者造成一定的困擾，因此不確定環境下的網路設計問題成為了新的研究熱點。而近十年來興起的魯棒最佳化技術為解決不確定數據下的最佳化問題提供了一個嶄新的思路和方法。本項目就將利用魯棒最佳化技術對不確定環境下的網路設計問題進行研究。 本項目將利用理論分析和實例分析相結合的方法，提取不確定環境中的關鍵參數和數據，定義輸入數據的不確定集合，提出並依據相應的魯棒最佳化準則，建立網路設計問題的魯棒最佳化模型，設計快速有效的算法，並利用軌道交通網路為背景的實例對模型與算法進行測試。本項目將為網路設計者提供應對不確定環境的最佳化決策，具有重要的理論價值和實際意義。

結題摘要

在項目支持的這三年，一共完成論文3篇，其中發表兩篇，投稿後修改一篇。第一篇是研究的wireless mesh network的最佳化問題，具體通過改變網關的數目或者位置來最佳化網路的結構，使得網路的數據傳輸效率得到提高。我們建立了數學規劃模型，並且設計了基於k-median的算法來求解問題，最後通過數值模擬展示了算法的有效性。第二篇是研究的環狀網路中的不對稱原子的自私路由問題，即在有線性延遲的情況下，連結上的收發點之間的最小化最大延遲。通過分析我們發現，存在一個9-近似的納什均衡的最優解，而且通過設計的算法，我們把穩定代價的上下界的差距縮小至0.7436。第三篇研究的是網路突發障礙情形下的軌道交通網路的魯棒設計問題。我們使用區間集合來刻畫不確定的輸入數據，然後用兩種魯棒準則——最小化和最小最大，建立了相應的數學規劃模型，然後設計了求解模型的啟發式算法。最後我們以京廣線中部主要城市的鐵路交通網路為例對算法進行了數值模擬。我們給出了網路中某段鐵路斷線情形下的模擬方案，實驗結果標明，如果網路中運行列車的數目在10^2量級上，網路中支線中斷時間在4、8、12、24小時時，算法都能在10分鐘內給出列車調整方案。