中國郵路問題問題是一類著名的弧路由問題,在信件投遞、校車路線規(guī)劃、軟件測試等領(lǐng)域有著重要的應(yīng)用。近年來,隨著分布式處理、智能交通、物聯(lián)網(wǎng)等技術(shù)的興起,許多問題變得具有實(shí)時(shí)性,傳統(tǒng)中國郵路問題的理論面臨著前所未有的挑戰(zhàn)。因此,我們有必要研究時(shí)間依賴的中國郵路問題來適應(yīng)這些需求。然而,時(shí)間依賴的中國郵路問題的研究面臨著以下一些難點(diǎn)。由于加入了時(shí)間因素,問題的求解變得很困難,即使是歐拉圖上的時(shí)間依賴中國郵路問題也是NP-hard問題。而求解NP-hard問題的最優(yōu)化算法中,基于多面體部分描述設(shè)計(jì)的方法是很效的算法。但是,時(shí)間依賴的點(diǎn)路由問題很難直接應(yīng)用或修正傳統(tǒng)問題的多面體結(jié)果,然而,更困難的是時(shí)間依賴的弧路由問題,國際上至今還沒有其進(jìn)行直接建模求解的研究,國內(nèi)學(xué)者給出的方法大都存在求解規(guī)模不大、效率不高等局限性。本文的研究正是圍繞上述問題展開的,主要包含以下三方面工作。首先,分析了圈向量和問題可行解的聯(lián)系,依此建立了便于對(duì)時(shí)間依賴中國郵路問題進(jìn)行多面體分析的數(shù)學(xué)規(guī)劃模型,對(duì)其進(jìn)行了線性化處理,然后分析了模型規(guī)模的上界,并給出了兩個(gè)更有效的時(shí)間不等式用于加強(qiáng)模型。其次,由于模型不等式約束集中... 

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

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

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

【部分圖文】：

TDCPP可行解不能寫成圈排列的形式

圖3.3時(shí)間依賴的旅行函數(shù)Fig.3.3Travelfunetionwithtime一dePendent

原始圖

【參考文獻(xiàn)】：
期刊論文
[1]時(shí)間窗-時(shí)間依賴中國郵路問題的圖轉(zhuǎn)換算法[J]. 陳加萍,孟憲超,孫景昊,譚國真.  計(jì)算機(jī)與數(shù)字工程. 2010(08)
[2]隨機(jī)時(shí)間依賴網(wǎng)絡(luò)的K期望最短路徑[J]. 譚國真,柳亞玲,高文.  計(jì)算機(jī)學(xué)報(bào). 2003(03)
[3]時(shí)間依賴的網(wǎng)絡(luò)中最小時(shí)間路徑算法[J]. 譚國真,高文.  計(jì)算機(jī)學(xué)報(bào). 2002(02)
[4]奇偶點(diǎn)圖上作業(yè)法[J]. 管梅谷.  數(shù)學(xué)學(xué)報(bào). 1960(03)

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



本文編號(hào)：2933565