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

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

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

【部分圖文】：

路徑λ的圖形表示

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

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

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



本文編號：2908597