近年來,隨著信息技術(shù)的高速發(fā)展和以物聯(lián)網(wǎng)為驅(qū)動的研究熱潮的到來,人們對應用系統(tǒng)的實時性提出了更高的要求,越來越多的實際問題變得與時間因素有著密切的聯(lián)系。帶時變特性的問題是一個與實際應用結(jié)合緊密、發(fā)展前景廣闊的研究領(lǐng)域,它能夠提供一種對現(xiàn)實問題建模更精確的方法,顯然成為一個值得去深入研究的非常具有挑戰(zhàn)性的領(lǐng)域。 本文研究的是時變網(wǎng)絡上的帶時間窗的中國郵路問題(TDCPPTW),該問題是傳統(tǒng)中國郵路問題在動態(tài)時間屬性方面的擴展。由于傳統(tǒng)的靜態(tài)網(wǎng)絡的路由算法并未對網(wǎng)絡的動態(tài)性給出有效的解決方案。因此,如何針對時間依賴網(wǎng)絡的時間約束和實時性變化進行建模,并迅速、精確的對其進行優(yōu)化求解是一類至關(guān)重要的問題。 本文首先對帶時間窗的時間依賴中國郵路問題的定義和特性進行了深入研究,并分析了時間依賴旅行時間和時間窗所引起的求解難度,發(fā)現(xiàn)傳統(tǒng)的弧路由轉(zhuǎn)換方法不再適用于時間依賴網(wǎng)絡。 然后,針對時間依賴網(wǎng)絡提出一個新的圖轉(zhuǎn)換算法,把原始時間依賴網(wǎng)絡離散為一個有著“弧集簇”結(jié)構(gòu)的靜態(tài)輔助圖。進一步基于圖轉(zhuǎn)換后的靜態(tài)輔助圖,把原始時間依賴問題轉(zhuǎn)換為靜態(tài)圖輔助圖上的廣義弧路由問題,并從理論上證明了轉(zhuǎn)換前后問題的等價性。同時,為了克服轉(zhuǎn)換后靜態(tài)網(wǎng)絡的規(guī)模嚴重增大的缺陷,設(shè)計出一個圖縮減算法,且從理論上證明了該縮減算法的正確性和有效性。 接著,建立求解廣義弧路由問題的0-1混合整數(shù)規(guī)劃模型,并分析其變量和約束的個數(shù),發(fā)現(xiàn)當問題規(guī)模增大時模型的變量會變得相當龐大；因此,進一步將模型分割為主問題和子問題,以采用列生成算法來適應大規(guī)模實例的求解。 最后,采用隨機生成的方法構(gòu)造大量TDCPPTW的測試實例,并應用本文所提出的轉(zhuǎn)換算法和數(shù)學模型對其進行求解實驗。實驗結(jié)果并得充分肯定了本文所構(gòu)造的圖轉(zhuǎn)換算法和求解模型的正確性和有效性。
【學位單位】：大連理工大學
【學位級別】：碩士
【學位年份】：2010
【中圖分類】：TP301.6;F616
【部分圖文】：

(3)旅行時間t。是一個依賴于該弧起始時刻的函數(shù)幾=f(毛)(其中毛表示離開i節(jié)點的時刻);這個函數(shù)一般是由實際問題誘導得來，例如根據(jù)實際交通的擁塞度我們可以給出旅行時間的分段函數(shù)，如下圖2.1所示。對應旅行時間函獄:X︵廠︶行時門旅的T考T舀限‘〔吩翌‘=了認’一{乓{‘黔公兇‘EL與內(nèi)」}{嘴嗎圖2.1旅行時間分段函數(shù) Fig.2.1ThePieeewisefunctionofTraveltime(4)服務時間或服務代價:每條弧的服務完成時間必須在時間窗約束內(nèi)，但如果僅對弧進行遍歷則不受時間窗限制;很自然的，每條需求弧的服務時間大于旅行時間，即凡>幾。服務時間的處理一般有以下兩種方式:①對于需求弧的服務代價可以看作是一個依賴于起始時刻的函數(shù):凡=f(心)，(i，j)。 R(2.1)②由于，服務時間或服務代價服務需求量直接相關(guān)，服務時間的函數(shù)為:q。’t。ti/(i，j)。R(i，j)必R (2.2)f!‘les‘一一凡或者像文獻【331中一樣粗略的定義為(i

圖3.1(c)狀態(tài)節(jié)點連通圖Fig3.1(e)TheeonneetedgraphforStateNodes圖3.1(d)轉(zhuǎn)換后最終得到的輔助圖Fig3.1(d)Thelastauxiliarygranh通過以上演示圖，很容易發(fā)現(xiàn)經(jīng)過圖轉(zhuǎn)換后無論是圖的節(jié)點數(shù)還是弧數(shù)都增加很多倍。從另一方面講，上圖實際上是一個時空拓展圖，每個節(jié)點都有著自己的時間屬性。因此這個圖中不僅不會有子回路的產(chǎn)生(時間不可逆轉(zhuǎn))，而且有很多節(jié)點的路徑選擇是一維的。也就是說只要確定了某個節(jié)點的某個時刻的狀態(tài)相應的兩個弧節(jié)點的狀態(tài)也就確定以及與之相關(guān)聯(lián)下一個節(jié)點的狀態(tài)就會確定。通過第五部分的實驗數(shù)據(jù)可以說明，雖然轉(zhuǎn)換后圖的規(guī)模擴大了但是求解所需要時間并沒有因此而難以接受。

}}}}}}}}}}}}}}}}}}}}}}} lllllllllllllll }}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}iii一 一 一 一 一一 一 !!!!!!!!!!!!!!! llllll下，互 互 lllllllll圖3.1(a)原始時間依賴網(wǎng)絡 Fig3.1(a)Theoriginaltime一 dependnetwork圖3.1(b)靜態(tài)擴展圖 Fig3.1(a)Thestatiegraph111一幾 幾 }}}。 。 {{{}}}lll}‘ ‘， ， 日日日 日 日 日巨 巨 紅紅紅紅紅紅紅紅紅紅紅紅紅紅紅紅、、 lllllllll{}}}}}褚褚褚褚褚褚褚褚 褚褚熟.袱 袱 袱 瀏瀏瀏 I]]]]]]]]]]]]]]]]]]]]]聲聲聲聲聲聲聲 聲聲一’ ’ 陣 陣 陣陣 陣 }}}’習 習 }}}}} :::]]]llll;;;;;}}}’〕 〕交l夕 夕廠二二 lll八.， lllllll。。匕洲蔡海卜二 ~~~~~圖3.1(c)狀態(tài)節(jié)點連通圖 Fig3.1(e)Theeon
【引證文獻】

相關(guān)碩士學位論文 前1條

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

本文編號：2884841