1、隨著中國(guó)經(jīng)濟(jì)的發(fā)展和人民生活水平提高，個(gè)人汽車的保有量逐年增加，這是方便了人們的出行，但也給交通帶來(lái)了巨大的壓力，尤其是在大城市，交通擁堵、交通事故的增加、汽車尾氣污染的日益加劇是中國(guó)最嚴(yán)重的城市病之一。為了解決這個(gè)迫切的問(wèn)題，智能交通系統(tǒng)(IntelligenceTransportationSystem，簡(jiǎn)稱ITS)已被廣泛應(yīng)用，其最廣泛的技術(shù)是車載行車導(dǎo)航系統(tǒng)的使用。但是現(xiàn)有的行車導(dǎo)航系統(tǒng)的路徑規(guī)劃存在下列問(wèn)題:一是以起始地到目的地

2、之間的行駛距離最短為目標(biāo)，實(shí)際上距離最短的路徑行駛時(shí)間并不一定是最小的，不能滿足人們對(duì)出行時(shí)間的要求;二是將行車時(shí)間歸集為交叉口之間路段上的行車時(shí)間，忽略了汽車在交叉口的等待時(shí)間和汽車在交叉路口處不同轉(zhuǎn)向具有不同時(shí)間耗費(fèi)的特點(diǎn)，不符合城市交通的實(shí)際情況。為此，本文以城市交通中行車時(shí)間最小化為目標(biāo)，對(duì)考慮節(jié)點(diǎn)屬性（權(quán)重或時(shí)間花費(fèi)）網(wǎng)絡(luò)的最短路徑問(wèn)題進(jìn)行了研究，主要工作如下:
　　基于網(wǎng)絡(luò)圖是時(shí)不變的、網(wǎng)絡(luò)圖中每條邊和每個(gè)節(jié)點(diǎn)的權(quán)都是

3、確定的數(shù)值的假設(shè)，建立了考慮節(jié)點(diǎn)屬性（權(quán)重或花費(fèi)）的時(shí)不變確定性網(wǎng)絡(luò)最短路徑問(wèn)題的數(shù)學(xué)模型，通過(guò)對(duì)問(wèn)題的分析，證明了問(wèn)題的解具有最優(yōu)子結(jié)構(gòu)性;利用動(dòng)態(tài)規(guī)劃方法設(shè)計(jì)求解考慮節(jié)點(diǎn)屬性（權(quán)重或花費(fèi)）的時(shí)不變確定性網(wǎng)絡(luò)的最優(yōu)路徑搜索算法——逆序標(biāo)號(hào)算法;經(jīng)證明該算法可以在多項(xiàng)式時(shí)間內(nèi)搜索到問(wèn)題的最優(yōu)解，并證明了該算法的時(shí)間復(fù)雜度為O(N·|E|+|V|)。
　　基于網(wǎng)絡(luò)圖是時(shí)變的、網(wǎng)絡(luò)圖中每條邊和每個(gè)節(jié)點(diǎn)的權(quán)在任意一個(gè)時(shí)間段都是確定的數(shù)值

4、的假設(shè)，建立了考慮節(jié)點(diǎn)屬性（權(quán)重或花費(fèi)）的時(shí)變確定性網(wǎng)絡(luò)最短路徑問(wèn)題的數(shù)學(xué)模型，為了清楚說(shuō)明網(wǎng)絡(luò)圖中節(jié)點(diǎn)和邊在不同時(shí)間段的權(quán)重（花費(fèi)）是不同的特點(diǎn)，引入向量標(biāo)簽方法對(duì)其進(jìn)行描述，將逆序標(biāo)號(hào)算法推廣到時(shí)變確定性網(wǎng)絡(luò)，得到了求解考慮節(jié)點(diǎn)屬性（權(quán)重或花費(fèi)）的時(shí)變確定性網(wǎng)絡(luò)最短路徑問(wèn)題的搜索算法，并指出了該算法的時(shí)間復(fù)雜度為O(I·(N·|E|+|V|))。
　　基于網(wǎng)絡(luò)圖是時(shí)不變的、網(wǎng)絡(luò)圖中每條邊和每個(gè)節(jié)點(diǎn)的權(quán)在任意一個(gè)時(shí)間段都是取有限

5、個(gè)數(shù)值的離散型隨機(jī)變量的假設(shè)，建立了考慮節(jié)點(diǎn)屬性（權(quán)重或花費(fèi)）的時(shí)不變隨機(jī)網(wǎng)絡(luò)最短路徑問(wèn)題的數(shù)學(xué)模型。首先，針對(duì)不考慮實(shí)時(shí)信息變化的最短路徑問(wèn)題，將逆序標(biāo)號(hào)算法推廣到時(shí)不變隨機(jī)網(wǎng)絡(luò)，設(shè)計(jì)了解決該問(wèn)題的最優(yōu)路徑搜索算法，并得到該算法的時(shí)間復(fù)雜度為O(N·(M+K)·|E|+|V|），此外，還給出改進(jìn)Q-method算法來(lái)解決該問(wèn)題，并證明了該算法的時(shí)間復(fù)雜度為O((K+M+N)·N·|E|2)。為了滿足車輛行駛過(guò)程中實(shí)現(xiàn)動(dòng)態(tài)導(dǎo)航的需要，給