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

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

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

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

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