考慮節(jié)點(diǎn)耗費(fèi)的時(shí)變隨機(jī)網(wǎng)絡(luò)最短路徑問(wèn)題研究.pdf

1、近年來(lái),隨著中國(guó)社會(huì)經(jīng)濟(jì)的迅猛發(fā)展和人民生活水平的逐年提高,國(guó)民車(chē)輛的保有量不斷增加,因此,城市交通變得日益擁塞,因車(chē)輛慢行和發(fā)動(dòng)機(jī)空耗而引起的汽油燃燒不充分所帶來(lái)的尾氣污染日益嚴(yán)重.人們?cè)絹?lái)越希望城市智能交通系統(tǒng)（ITS）以及車(chē)載導(dǎo)航系統(tǒng)能夠迅疾快速地給出路徑規(guī)劃，使得車(chē)輛能夠高速快捷地到達(dá)目的地。因此，交通管理者和業(yè)界研究人員非常關(guān)注行車(chē)路徑規(guī)劃和車(chē)輛的實(shí)時(shí)導(dǎo)航問(wèn)題。然而，現(xiàn)有的一般車(chē)載導(dǎo)航系統(tǒng)所提供的路徑規(guī)劃存在如下問(wèn)題:第一，以

2、兩點(diǎn)之間的物理距離最短為目標(biāo)來(lái)規(guī)劃最短路徑，而不是以最短行車(chē)時(shí)間作為規(guī)劃路徑的目標(biāo)；其次，沒(méi)有重視車(chē)輛在路口處時(shí)間耗費(fèi)問(wèn)題，車(chē)輛在路口處選擇左轉(zhuǎn)、右轉(zhuǎn)、直行或掉頭，所耗費(fèi)的時(shí)間是不同的，不可以將其統(tǒng)一歸結(jié)到對(duì)應(yīng)的路段上；第三，對(duì)交通網(wǎng)絡(luò)的時(shí)變性和隨機(jī)性重視不夠。因此，本文以行車(chē)時(shí)間最短為目標(biāo)，對(duì)考慮節(jié)點(diǎn)耗費(fèi)的時(shí)變隨機(jī)網(wǎng)絡(luò)最短期望行車(chē)時(shí)間路徑問(wèn)題進(jìn)行了研究，具體內(nèi)容如下：
　　基于道路網(wǎng)絡(luò)圖是時(shí)變的、車(chē)輛于不同時(shí)間在每條路段和每個(gè)節(jié)

3、點(diǎn)處的時(shí)間耗費(fèi)均是取有限個(gè)數(shù)值的離散型隨機(jī)變量的假設(shè)，首先建立了考慮節(jié)點(diǎn)耗費(fèi)的離散型時(shí)變隨機(jī)網(wǎng)絡(luò)一般最短期望行車(chē)時(shí)間路徑預(yù)規(guī)劃問(wèn)題、出發(fā)時(shí)間確定的最短期望行車(chē)時(shí)間路徑預(yù)規(guī)劃問(wèn)題、具有最晚到達(dá)時(shí)間約束的最短期望行車(chē)時(shí)間路徑預(yù)規(guī)劃問(wèn)題的數(shù)學(xué)模型，并設(shè)計(jì)了求解以上問(wèn)題的最優(yōu)路徑搜索算法——逆序標(biāo)號(hào)法，對(duì)問(wèn)題進(jìn)行求解；為了方便數(shù)據(jù)的存儲(chǔ)和計(jì)算，引入向量標(biāo)簽描述車(chē)輛于每個(gè)時(shí)間段在路段和節(jié)點(diǎn)處的時(shí)間耗費(fèi)；再次，對(duì)逆序標(biāo)號(hào)算法的思想、步驟及其模塊進(jìn)行

4、了詳細(xì)的介紹，得到該算法的時(shí)間復(fù)雜度為此處為公式；最后，考慮到車(chē)輛在行駛過(guò)程中，道路狀況會(huì)發(fā)生實(shí)時(shí)變化，對(duì)考慮實(shí)時(shí)信息的實(shí)時(shí)路徑誘導(dǎo)問(wèn)題進(jìn)行了算法設(shè)計(jì)，并對(duì)算法的步驟進(jìn)行了詳細(xì)的介紹。
　　基于道路網(wǎng)絡(luò)圖是時(shí)變的、車(chē)輛于每個(gè)時(shí)間段在每條路段和每個(gè)節(jié)點(diǎn)處的時(shí)間耗費(fèi)均是服從三角形分布的連續(xù)型隨機(jī)變量的假設(shè)，給出了考慮節(jié)點(diǎn)耗費(fèi)的連續(xù)型時(shí)變隨機(jī)網(wǎng)絡(luò)一般最短期望行車(chē)時(shí)間路徑預(yù)規(guī)劃問(wèn)題、出發(fā)時(shí)間確定的最短期望行車(chē)時(shí)間路徑預(yù)規(guī)劃問(wèn)題、最晚到達(dá)時(shí)