考慮節(jié)點屬性汽車導(dǎo)航系統(tǒng)路徑規(guī)劃問題的研究.pdf

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

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

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

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

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