為了在城市路網(wǎng)中搜索最優(yōu)路徑,建立了一種限制搜索區(qū)域的時變權重有向圖模型。在限制搜索區(qū)域上,模型首次引入了搜索方向因素,綜合考慮三個因素:時變的車流密度、定常的空間距離以及搜索方向,更加符合城市路網(wǎng)實際交通狀況。進一步,給出了相應的最優(yōu)路徑搜索算法。與傳統(tǒng)的城市路網(wǎng)最優(yōu)路徑搜索算法相比,所提算法有兩個優(yōu)點:（i）縮小了搜索范圍,進而降低了計算量;（ii）根據(jù)不斷變化的交通流自適應地選取最優(yōu)路徑,保證了最終所選路徑在當時所處環(huán)境下是最優(yōu)的。仿真實驗證明了該模型算法的有效性、自適應性和實時性。 

【文章來源】：山西大學學報(自然科學版). 2020,43(01)北大核心

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

【部分圖文】：

城市路網(wǎng)模型示意圖

前文對針對城市路網(wǎng)的最優(yōu)路徑搜索算法進行了詳細描述,包括模型基本假設及具體的算法步驟,這里按照前文所述算法步驟,可繪制流程圖如圖2,下面分析和討論本算法。確定以起點與終點連線為對角線的矩形區(qū)域為搜索區(qū)域,可減少不必要的搜索范圍,且可以保證起點到最優(yōu)路徑中任一頂點的距離不大于起點到終點的距離。在平面上,當前所在頂點到終點的向量與起點到終點的向量間的夾角θ最大取值范圍為[0, 180°]。本文算法取θ∈[0, 90°),如此可避免所走路徑連接成環(huán),從而令所選路徑方向盡可能接近起點到終點的方向;同時可以減少不必要的搜索范圍,降低算法計算量。

表1 各編號交叉口的坐標Table 1 Coordinates of numbered intersections 編號 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 橫坐標 0 1.6 2.6 3.9 5.2 0 0.6 1.6 2.6 3.9 4.6 5.2 0.6 1.6 2.6 縱坐標 3.2 3.2 3.2 3.2 3.2 2.4 2.4 2.4 2.3 2.3 2.3 2.3 1.65 1.65 1.65 編號 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 橫坐標 3.9 0 4.6 5.2 0.6 1.6 2.6 3.9 0 0.6 1.6 2.6 3.9 4.6 5.2 縱坐標 1.65 1.1 1.1 1.1 0.66 0.66 0.66 0.66 0 0 0 0 0 0 0此外,本文進行了對比仿真實驗,從圖1所示的地圖中任意選取兩個交叉口作為起點和終點,分別利用本文算法和傳統(tǒng)的Floyd算法搜索最優(yōu)路徑[2]。結果發(fā)現(xiàn)在軟件平臺MATLAB(R2014a)及硬件平臺3.2 GHz處理器(CPU)安裝內存(RAM)4 GB基礎上,在行車環(huán)境動態(tài)變化的情況下,本文算法對于圖1中的任意兩個交叉口都能搜索到最優(yōu)路徑。在相同條件下,Floyd算法(道路權重僅考慮空間距離)則由于時間復雜度(O(n3))較大,導致只能實現(xiàn)部分交叉口之間的最優(yōu)路徑搜索,多數(shù)最優(yōu)路徑搜索過程需要花費時間超過30 min,例如以第1交叉口為起點,分別以第10、11、13、16、18、19、29、30交叉口為終點的最優(yōu)路徑搜索仿真實驗消耗時間均在30 min以上。通過這一對比仿真實驗,可凸顯本文算法的實時性。

【參考文獻】：
期刊論文
[1]基于快速收斂牛頓算法的城市最短路徑分析[J]. 孫威,陳焱明,尚曉麗.  哈爾濱商業(yè)大學學報(自然科學版). 2018(02)
[2]改進蟻群算法的局部信息動態(tài)路徑規(guī)劃[J]. 趙峰,楊春曦,陳飛,黃凌云,談誠.  計算機測量與控制. 2017(08)
[3]基于改進Floyd算法的城市交通網(wǎng)絡最短路徑規(guī)劃[J]. 徐達,蔡滿春,陳悅.  電子科技. 2017(07)
[4]城市路網(wǎng)最優(yōu)路徑的不等式約束算法[J]. 楊娟,陶葉青.  導航定位學報. 2013(02)
[5]基于云計算的蟻群算法求解城市路網(wǎng)最短路徑[J]. 楊慶芳,梅朵,韓振波,張彪.  吉林大學學報(工學版). 2013(05)
[6]典型城市路網(wǎng)中的橢圓最短路徑算法[J]. 王世明,邢建平,張玉婷,柏寶華.  系統(tǒng)工程理論與實踐. 2011(06)
[7]城市道路交通流三參數(shù)關系研究[J]. 莊焰,呂慎.  深圳大學學報. 2005(04)



本文編號：3248560