交通事故、惡劣天氣以及偶發(fā)的交通擁堵等都會導(dǎo)致道路交通網(wǎng)絡(luò)中行程時(shí)間的不確定性,極大地影響了道路交通系統(tǒng)的可靠性,同時(shí)給日常生活中出行計(jì)劃的制定以及出行路徑的選擇帶來了不便。因此,本次研究將綜合考慮道路交通網(wǎng)絡(luò)中由于交通流量的全天變化所導(dǎo)致的路徑行程時(shí)間的時(shí)變特征,以及由于事故、天氣等不確定因素所導(dǎo)致的路徑行程時(shí)間的隨機(jī)特征,并以此作為路網(wǎng)環(huán)境的假設(shè)條件,對出行路徑選擇問題進(jìn)行研究。具體地,首先建立行程時(shí)間的動(dòng)態(tài)隨機(jī)變量,并在此基礎(chǔ)上模擬構(gòu)建了隨機(jī)時(shí)變網(wǎng)絡(luò)。隨后,定義了該網(wǎng)絡(luò)環(huán)境下路徑選擇過程中所考慮的成本費(fèi)用,并通過魯棒優(yōu)化的方法,將成本費(fèi)用魯棒性最強(qiáng)的路徑視為最優(yōu)路徑。隨后,在隨機(jī)一致性條件下,通過數(shù)學(xué)推導(dǎo)證明了該模型可以簡化為解決一個(gè)確定性時(shí)變網(wǎng)絡(luò)中的最短路徑問題。最終,具有多項(xiàng)式時(shí)間計(jì)算復(fù)雜度的改進(jìn)Dijkstra算法被應(yīng)用到模型的求解中,并通過小型算例驗(yàn)證模型及算法的有效性。結(jié)果表明,本研究中所提出的方法可以被高效率算法所求解,并且不依賴于先驗(yàn)行程時(shí)間概率分布的獲取,因此對后續(xù)的大規(guī)模實(shí)際城市道路網(wǎng)絡(luò)應(yīng)用提供了良好的理論基礎(chǔ)。此外,由于具有行程時(shí)間隨機(jī)時(shí)變特征的交通網(wǎng)絡(luò)更接近... 

【文章來源】：運(yùn)籌與管理. 2020年05期 第37-42頁 北大核心CSSCI

【文章頁數(shù)】：6 頁

【部分圖文】：

路徑λ的圖形表示

針對解決動(dòng)態(tài)網(wǎng)絡(luò)下最短路徑問題,許多學(xué)者已經(jīng)給出了能夠在多項(xiàng)式時(shí)間復(fù)雜度(polynomial-time complexity)下求解的算法,這也是解決大規(guī)模網(wǎng)絡(luò)問題的前提。本次研究將Sun等人[10]提出的改進(jìn)Dijkstra算法應(yīng)用到解決基于魯棒優(yōu)化的隨機(jī)時(shí)變網(wǎng)絡(luò)中最優(yōu)路徑問題,并基于圖2中的小型交通網(wǎng)絡(luò)進(jìn)行標(biāo)號法的算例測試。其中,vo代表出發(fā)的起始節(jié)點(diǎn),t1代表從vo出發(fā)的時(shí)間;vd代表需要到達(dá)的終止節(jié)點(diǎn),t*代表vd的期望到達(dá)時(shí)間,即時(shí)間窗約束。根據(jù)第3節(jié)中的證明結(jié)果,可以將原問題轉(zhuǎn)換為解決一個(gè)確定性時(shí)變網(wǎng)絡(luò)中的最短路問題,而轉(zhuǎn)換后新的時(shí)變網(wǎng)絡(luò)中的路段行程時(shí)間可以用原網(wǎng)絡(luò)中相對應(yīng)路段的行程時(shí)間上限來表示,即對應(yīng)于分段函數(shù)中每個(gè)時(shí)間段t,路段行程時(shí)間有Rtij+dtij。因此,圖2中隨機(jī)時(shí)變網(wǎng)絡(luò)的最優(yōu)路徑問題等價(jià)于在圖3中所示的確定性時(shí)變網(wǎng)絡(luò)中,求解vo至vd行程時(shí)間用時(shí)最少的最短路徑問題。

轉(zhuǎn)換后的確定性時(shí)變網(wǎng)絡(luò)算例

【參考文獻(xiàn)】：
期刊論文
[1]隨機(jī)時(shí)變車輛路徑問題的多目標(biāo)魯棒優(yōu)化方法[J]. 段征宇,雷曾翔,孫碩,楊東援.  西南交通大學(xué)學(xué)報(bào). 2019(03)



本文編號：2908597