時變、隨機網(wǎng)絡(luò)最優(yōu)路徑算法及其應(yīng)用研究.pdf

1、最短路徑問題是網(wǎng)絡(luò)優(yōu)化的核心技術(shù).在傳統(tǒng)的最短路徑問題中,假設(shè)網(wǎng)絡(luò)中的權(quán)值是靜態(tài)的、確定的,這些假設(shè)在ITS、計算機網(wǎng)絡(luò)與通信等許多應(yīng)用領(lǐng)域是不現(xiàn)實的.時變、隨機網(wǎng)絡(luò)最優(yōu)路徑問題突破了傳統(tǒng)的最短路徑問題的局限性,成為ITS的基礎(chǔ)理論.新的現(xiàn)實問題使得最優(yōu)路徑的計算變得非常困難.本文針對出現(xiàn)的新問題及前人研究中存在的問題,重點研究了時變網(wǎng)絡(luò)中的最小時間路徑問題、隨機時間依賴網(wǎng)絡(luò)期望最短路徑問題、大規(guī)模網(wǎng)絡(luò)模型與高效的路徑計算問題,并針對計

2、算機網(wǎng)絡(luò)與通信的路由問題、智能交通系統(tǒng)的路徑選擇問題進行了應(yīng)用研究.在時變網(wǎng)絡(luò)方面,該文的工作分為三部分:(1)首次從理論上證明了傳統(tǒng)的最短路徑算法在時變網(wǎng)絡(luò)中是不正確的并提出了時變網(wǎng)絡(luò)中路徑最優(yōu)化的充分必要條件.在此基礎(chǔ)上,在沒有限制條件下設(shè)計實現(xiàn)了時間依賴的網(wǎng)絡(luò)求解最小時間路徑的算法并證明了算法的正確性.(2),利用該文給出的線性獨立函數(shù)的智能神經(jīng)元模型構(gòu)成的廣義神經(jīng)網(wǎng)絡(luò),對交通流進行預(yù)測,進而給出了時變網(wǎng)絡(luò)中每條弧的旅行時間預(yù)測方

3、法,為時變網(wǎng)絡(luò)最優(yōu)路徑算法及其在ITS的應(yīng)用提供了完整的解決方案.(3)開展了時變網(wǎng)絡(luò)在計算機路由協(xié)議的應(yīng)用的研究,給出了時間依賴的混合型網(wǎng)絡(luò)模型(HTDN模型),有效地描述了網(wǎng)絡(luò)中鏈路權(quán)值隨時間變化的特性,并且網(wǎng)絡(luò)中的結(jié)點可以采用不同的等待策略,設(shè)計了一個新的、有效的時變網(wǎng)絡(luò)分布式路由協(xié)議并證明了協(xié)議的正確性.在時變、隨機網(wǎng)絡(luò)方面,該文解決的問題是邊耗費具有潛在的隨機相關(guān)性和時間依賴性的路徑規(guī)劃問題,這樣的問題使得問題求解變的非常困難

4、.在這方面本文的主要工作是:(1)將隨機時間依賴網(wǎng)絡(luò)的路徑規(guī)劃問題轉(zhuǎn)化成系統(tǒng)可靠性問題,給出了一個較弱的一致可靠性條件,確?；诳煽績?yōu)先權(quán)的廣義動態(tài)規(guī)劃方法的正確性,給出了基于可靠性理論的求解最優(yōu)路徑問題的新方法和算法;(2)提出了新的隨機優(yōu)勢判別法,使傳統(tǒng)判別法的參數(shù)由二維降到一維,首次給出了K期望最路徑的兩種求解方法:基于可靠性理論的K期望壽命最短算法和基于隨機優(yōu)勢的K期望最短路徑算法;(3)首次給出了隨機時間依賴網(wǎng)絡(luò)K期望路徑的并