中國郵路問題是著名的圖論問題,也是組合優(yōu)化、運籌規(guī)劃領(lǐng)域經(jīng)典的問題之一在通信系統(tǒng)、交通管理、機器人探測、交互式系統(tǒng)分析、網(wǎng)站可用性和軟件測試等領(lǐng)域有著重要的應(yīng)用。然而,隨著通信技術(shù)與分布式系統(tǒng)的發(fā)展,混合系統(tǒng)測試和智能交通等復(fù)雜領(lǐng)域的應(yīng)用都在關(guān)注實際問題中的時間特性,即網(wǎng)絡(luò)中弧的權(quán)值依賴于時間變化而變化,我們稱具有這種性質(zhì)的網(wǎng)絡(luò)為時變網(wǎng)絡(luò)。在以往中國郵路問題的研究中,都是假設(shè)網(wǎng)絡(luò)中的權(quán)值是靜態(tài)的、確定的,而實際問題中網(wǎng)絡(luò)往往是動態(tài)的,比如現(xiàn)實交通網(wǎng)絡(luò)中,交通事故和天氣變化等偶然事件都有可能造成道路交通狀況的變化,那么郵遞員送信沿途所經(jīng)過街道的旅行時間也會隨之變化。中國郵路問題的傳統(tǒng)模型和算法只能求解固定弧權(quán)條件下的問題,在時變網(wǎng)絡(luò)中應(yīng)用傳統(tǒng)算法求得的解根本不符合實際情況的要求。因此,研究時變網(wǎng)絡(luò)中國郵路問題的模型和優(yōu)化算法具有更為重要的現(xiàn)實意義。然而,引入時間因素后新問題的求解變得非常困難,時變網(wǎng)絡(luò)有向中國郵路問題已被證明是NP難的,直接求解最優(yōu)解往往是不實際的。本文從數(shù)學(xué)規(guī)劃優(yōu)化方法的角度出發(fā)研究時變網(wǎng)絡(luò)有向中國郵路問題,首先借鑒時變網(wǎng)絡(luò)旅行商問題的建模思想結(jié)合圈覆蓋相關(guān)理論建立了時... 

【文章來源】：大連理工大學(xué)遼寧省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：62 頁

【學(xué)位級別】：碩士

【部分圖文】：

弧路由轉(zhuǎn)換算法示例

的最優(yōu)解不符合整數(shù)要求，假設(shè)是分量氣一b不符合要求，其中b取分?jǐn)?shù)。那么，分支限界法則會將問題分為兩部分，增加兩個約束條件xi‘[bl和xi、[bl+1，分別將不等式并入上級松弛問題中，如圖2.3所示，從而形成兩個分支。兩個分支問題的可行域中包含原整數(shù)規(guī)劃問題的所有可行解，圖2.3中灰色陰影部分被去掉了，因為它們不會包含任何整數(shù)規(guī)劃的可行解。依此類推，根據(jù)需要，分支問題也可以產(chǎn)生自己的分支問題，如此

直到獲得整數(shù)最優(yōu)解。而對于割平面算法，此時會根據(jù)分?jǐn)?shù)分量xi一b產(chǎn)生一個新的約束(通常稱為割平面約束)，并將其添加到線性松弛問題中繼續(xù)求解，再次求解后若還遇到分?jǐn)?shù)變量，則繼續(xù)添加割平面約束，如圖2.4所示直到找到最優(yōu)整數(shù)解。占圖 2.3右十1丫分支限界算法示意圖 Fig.2.3AsimPlediagramofbranehandboundalgorithm毛圖2.4割平面算法示意圖 Fig.2.4AsimPlediagramofcuttingPlanealgorithm分支限界法其實是一種隱枚舉法或者部分枚舉法，它不是一種有效算法，只是枚舉法基礎(chǔ)上的改進。整數(shù)規(guī)劃問題一般有無限多個可行解，隨著問題規(guī)模的擴大，其可行解的數(shù)目也將急劇增加。因此，即使通過添加良好的剪枝條件使其枚舉部分可行解，也

【參考文獻】：
期刊論文
[1]動態(tài)網(wǎng)絡(luò)最短路問題的復(fù)雜性與近似算法[J]. 林瀾,閆春鋼,蔣昌俊,周向東.  計算機學(xué)報. 2007(04)
[2]時間依賴的網(wǎng)絡(luò)中最小時間路徑算法[J]. 譚國真,高文.  計算機學(xué)報. 2002(02)
[3]中國投遞員問題綜述[J]. 管梅谷.  數(shù)學(xué)研究與評論. 1984(01)

碩士論文
[1]時間依賴的無向中國郵路問題分支切割算法[D]. 武雪平.大連理工大學(xué) 2009
[2]時間依賴網(wǎng)絡(luò)中國郵路問題的分支限界算法[D]. 呂凱.大連理工大學(xué) 2008
[3]時間依賴中國郵路問題的智能算法研究[D]. 閆超.大連理工大學(xué) 2008
[4]時間依賴網(wǎng)絡(luò)中國郵路問題研究[D]. 金運通.大連理工大學(xué) 2006



本文編號：3464879