發(fā)布時(shí)間：2020-11-15 14:09

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

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

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

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

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

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

本文編號(hào)：2884841