【摘要】： 中國郵路問題是圖論中的經(jīng)典問題,得到了廣泛的研究。該問題有著眾多的應(yīng)用領(lǐng)域,如郵件投遞路線,掃雪車路線,警車出巡安排,機(jī)器人檢測路線路線以及軟、硬件系統(tǒng)的測試序列優(yōu)化等等,因此吸引了眾多學(xué)者的研究興趣。 近年來,由于計(jì)算機(jī)網(wǎng)絡(luò)與通信、智能交通系統(tǒng)以及混合系統(tǒng)實(shí)時(shí)測試等復(fù)雜應(yīng)用領(lǐng)域的需求,時(shí)變網(wǎng)絡(luò)中國郵路問題的研究具有更為重要的現(xiàn)實(shí)應(yīng)用意義。帶時(shí)間窗的中國郵路問題、時(shí)間依賴服務(wù)代價(jià)中國郵路問題以及時(shí)間依賴旅行時(shí)間中國郵路問題均屬于時(shí)變網(wǎng)絡(luò)中國郵路問題。其中,前兩個(gè)問題已經(jīng)得到了較好的研究,但由于時(shí)間依賴旅行時(shí)間中國郵路問題建模十分困難,因此,一直鮮有研究。然而,本文將致力于時(shí)間依賴旅行時(shí)間中國郵路問題的研究。 本文首先對(duì)傳統(tǒng)的中國郵路問題和時(shí)變網(wǎng)絡(luò)中國郵路問題的研究方法進(jìn)行了歸納總結(jié),并介紹了列生成算法的原理及其在時(shí)變網(wǎng)絡(luò)中的應(yīng)用。然后,通過將中國郵路可行解看成是圖中圈的排列組合,設(shè)計(jì)了以基本圈為決策變量的整數(shù)線性規(guī)劃模型,并從理論上證明了該模型中基本圈數(shù)的上界為m-n+1。由于該整數(shù)規(guī)劃模型的規(guī)模比較大,因此,本文設(shè)計(jì)了列生成算法求解該問題。首先,將圈變量整數(shù)規(guī)劃模型抽象為帶偏序關(guān)系的集合覆蓋主問題模型,降低了解空間的維數(shù)；然后,通過對(duì)偶理論設(shè)計(jì)了時(shí)間依賴最短路子問題,并應(yīng)用遺傳算法求解,從而進(jìn)一步確定了最優(yōu)解的搜索方向。但是,這個(gè)模型只能解決所有圈均過原點(diǎn)的特例,針對(duì)存在圈不過原點(diǎn)的網(wǎng)絡(luò)拓?fù)?文章針對(duì)可行解的特點(diǎn)給出了另外一個(gè)“層路徑”數(shù)學(xué)規(guī)劃模型,同時(shí)對(duì)該模型的上界進(jìn)行了理論分析,算例驗(yàn)證了該模型的正確性。
【圖文】：

;若該路徑是投遞路線的最后一層路徑，則規(guī)定其下一層路徑為路徑不為空。將給出一個(gè)例子，來說明上面的思想。例如在圖6.2的有向圖一1一2一O一3一2一O。我們用圖6.3的形式來描述這條郵路。很容易看出徑連接而成的。O一1一2是第一層路徑，O一3一2是第二層路徑，第;2一O是第一層路徑和第二層路徑之間的連接弧，2一0是第二層連接弧。把每一層的圖補(bǔ)全后，可以得到更直觀的圖6.4。圖6.2TDCPP實(shí)例Fig.6，2TheInstaneeofTDCPP

;若該路徑是投遞路線的最后一層路徑，則規(guī)定其下一層路徑為路徑不為空。將給出一個(gè)例子，來說明上面的思想。例如在圖6.2的有向圖一1一2一O一3一2一O。我們用圖6.3的形式來描述這條郵路。很容易看出徑連接而成的。O一1一2是第一層路徑，O一3一2是第二層路徑，，第;2一O是第一層路徑和第二層路徑之間的連接弧，2一0是第二層連接弧。把每一層的圖補(bǔ)全后，可以得到更直觀的圖6.4。圖6.2TDCPP實(shí)例Fig.6，2TheInstaneeofTDCPP
【學(xué)位授予單位】：大連理工大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2010
【分類號(hào)】：F616;TP399-C6

【引證文獻(xiàn)】

相關(guān)碩士學(xué)位論文 前2條

1 曲宏磊;時(shí)變網(wǎng)絡(luò)鄉(xiāng)村郵路問題割平面及蟻群算法研究[D];大連理工大學(xué);2011年

2 孟憲超;兩階段法求帶時(shí)間窗的時(shí)間依賴鄉(xiāng)村郵路問題[D];大連理工大學(xué);2011年

本文編號(hào)：2625750