城市路網(wǎng)的一種最優(yōu)路徑搜索算法

賈新春,彭登永,李雷,張敏敏

(1.山西大學 自動化系,山西 太原 030013;2.山西大學 數(shù)學科學學院,山西 太原 030006)

0 引言

隨著經(jīng)濟的發(fā)展和人們生活水平的提高,車輛人均擁有量也逐漸上升,然而城市道路等基礎設施建設并沒有隨之增加。這直接導致了城市交通擁堵現(xiàn)象的發(fā)生。為了緩解交通擁堵帶來的影響,已經(jīng)發(fā)展了兩類方法:一是宏觀調(diào)控;二是微觀誘導。前者根據(jù)城市路網(wǎng)中的實時交通狀況調(diào)節(jié)各交叉口信號燈配時方案,進而調(diào)控引導交通流,增大城市道路資源利用率,減少交通擁堵現(xiàn)象發(fā)生。后者根據(jù)實時交通狀況及車輛起點與終點信息,再結合實時交通狀況,為車輛尋找最優(yōu)路徑,以降低交通擁堵對個體車輛的影響。本文方法屬于后者。

針對城市路網(wǎng)的最優(yōu)路徑算法有多種,下面列舉一些其中有代表性的算法。楊娟等[1]應用不等式約束方法建立了同時兼顧時間和距離要素的最優(yōu)路徑模型,并應用罰函數(shù)、零權和無限權的思想給出模型的算法。徐達等[2]將城市路網(wǎng)構建成加權有向圖模型,并改進了Floyd算法用于求解該模型,提高了計算效率。楊慶芳等[3]提出一種基于云計算的并行遺傳算法來求解城市路網(wǎng)最短路徑問題,充分利用了計算資源,提高了算法計算速度。類似的基于大數(shù)據(jù)技術的方法[4],充分利用現(xiàn)有的大量交通數(shù)據(jù),其目標不是保證最優(yōu)性,而是在可接受的計算時間內(nèi)提供高質量的解決方案。孫威等[5]采用快速收斂牛頓算法獲得城市路網(wǎng)最短路徑,該算法擁有較高的精度和較快的收斂速度。趙峰等[6]提出了一種基于局部信息獲取策略的動態(tài)改進型蟻群算法,與傳統(tǒng)蟻群算法相比,提高了路徑規(guī)劃的收斂速度,擁有一定的動態(tài)路徑規(guī)劃能力。宋青等[7]提出了一種新的分層路徑計算算法,該算法利用層次圖模型的優(yōu)點,采用區(qū)域剪枝策略,在不影響搜索精度的前提下,顯著地減少了搜索空間。一些學者考察更具體因素如車道變換和轉彎限制[8-10],以求所得結果更符合實際情況。此外,自從Nordbeck[11]于1969年提出橢圓限制搜索區(qū)域的最短路徑算法,隨后出現(xiàn)了多種限制區(qū)域最短路徑算法[12-15],這些算法減小了搜索區(qū)域,進而降低了計算量。

本文首先將起點與終點所在連線為對角線的矩形區(qū)域作為限制搜索區(qū)域,綜合考慮了行車環(huán)境中影響道路阻抗的兩大主要因素:時變的交通流及定常的空間距離,同時考慮了交叉口信號燈調(diào)控的影響,建立了針對城市路網(wǎng)的限制搜索區(qū)域時變權重有向圖模型,給出了相應的最優(yōu)路徑搜索算法。此外,該算法在每次選擇最優(yōu)路段時考慮了方向問題,進而減小了搜索范圍,降低了計算量與存儲量。最后在MATLAB平臺對所提算法進行了仿真驗證,證明了其可行性、有效性、自適應性和實時性。本文創(chuàng)新點為:在建立針對城市路網(wǎng)的時變權重有向圖模型過程中,既考慮了主要時變因素——車流密度,也考慮了搜索方向因素。

1 基本原理及方法

1.1 城市路網(wǎng)模型

城市道路網(wǎng)絡中包含雙向道路和單向道路,因此城市道路網(wǎng)絡可抽象為一個雙向有向圖模型,如圖1所示,其中道路交叉口作為頂點,交叉口間的路段作為有向邊。同時,城市道路中不同的路段在不同的時間點道路的擁堵程度以及不同路段的長度等因素使得車輛通過城市道路所花費的時間是動態(tài)變化的,為此引入時變路阻函數(shù)作為有向圖中邊的權函數(shù)。

圖1 城市路網(wǎng)模型示意圖Fig.1 Schematic map of urban road network model

為了縮小搜索范圍,減少計算量,這里只考慮以起點和終點連線為對角線的矩形區(qū)域。假設該區(qū)域內(nèi)有n個交叉口,則可以用n階的鄰接矩陣表示該區(qū)域的路網(wǎng)模型,如式(1)所示。該矩陣中的第i行第j列的元素表示第i個頂點到第j個頂點的權值。矩陣主對角線上的元素均為0。如果從一個頂點不能直接到達另一個頂點,則其對應的鄰接矩陣中的元素為無窮大,如此對于單行道的路段也可以包含在該模型中。鄰接矩陣中的元素,即路阻函數(shù)的確定在接下來進行。

(1)

1.2 時變路阻(權)函數(shù)

與城市道路網(wǎng)絡模型密切相關的是交通流理論,表征交通流特性的基本參數(shù)是交通流量、行車速度和車流密度。交通流量qij(t)(單位:輛/小時)是指t時刻在x點(x點在第i個交叉口到第j個交叉口方向的路段上)處單位時間內(nèi)通過的車輛數(shù)。行車速度vij(t)(單位:km/h)是指在t時刻在x點附近車輛速度的平均值。車流密度ρij(t)(單位:輛/千

米)是指t時刻在x點處每車道單位長度道路上擁有的車輛數(shù)。根據(jù)上述定義,交通流的3個參數(shù)之間符合式(2)。

q=ρv

(2)

當?shù)缆飞系能囕v增多、車流密度增大時,車輛間距將縮小,出于安全考慮,駕駛員將降低車速;當車流密度變小時,駕駛員則會提高車速。因此,車速隨著車流密度的增加呈單調(diào)下降趨勢。格林希爾茲(Green Shields)于1934年提出了v-ρ線性關系模型[16],即

(3)

(4)

(5)

(6)

(7)

路阻也稱路權,由路段阻抗和節(jié)點(交叉口)阻抗組成。對于傳統(tǒng)的路徑規(guī)劃算法,道路權重選取的是路段的長度,這是大部分路徑規(guī)劃的首選指標,因為它容易獲得,相對比較簡單。但此類指標只適應于道路暢通、路況較為一致的道路,并沒有充分考慮由于長度以外的路阻所帶來的延誤。由于大多數(shù)路阻最終都會導致時間延誤,或者與時間延誤相關,因此構造路阻函數(shù)為

(8)

結合(6)、(7)和(8)式,可得

(9)

1.3 針對城市路網(wǎng)的最優(yōu)路徑求解

針對城市路網(wǎng)的帶權雙向有向圖模型已經(jīng)建立起來,接下來需要求解從起點到終點的最優(yōu)路徑。為此,首先需要作一些必要的假設。

1.3.1 模型假設

由于所建立的模型涉及多個參數(shù),為了保證模型的嚴謹性及其求解算法的嚴密性,需要對其中一些參數(shù)作必要的假設與限定。

2) 如果能直接測算得到車流密度ρij(t),則假設可以較準確地預測未來時間段Δt內(nèi)的城市路網(wǎng)各路段的車流密度值。

3) 如果不能直接測算得到車流密度ρij(t),則必須能測算交通流量qij(t)和交通流平均速度vij(t),并且假設能較準確地預測未來時間段Δt(一般不超過15 min)內(nèi)的城市路網(wǎng)各路段的交通流量值與交通流平均速度值。

4) 假設車流密度ρij(t)在短時間段Δt內(nèi)變化幅度較小,如此在將未來短時間段Δt內(nèi)車流密度的均值作為權重函數(shù)輸入變量時可以減小誤差。

5) 假設城市路網(wǎng)中各交叉口的位置及信號燈配時方案均是已知的。

6) 為了計算方便,假設起點和終點都在有向網(wǎng)的頂點。如果起點或終點不在頂點,則確定鄰近頂點作為代起點或代終點。鄰近頂點的確定方法為:起點的鄰近頂點選擇起點所在有限弧的終止端;終點的鄰近頂點選取終點所在有向弧的起始端。

7) 假設車輛在城市路網(wǎng)中除了在交叉口等待綠燈外,其余時間都不停車,直到到達終點。如此可以保證算法所選各路段的局部最優(yōu)性。

1.3.2 針對城市路網(wǎng)的最優(yōu)路徑算法

根據(jù)前文所述,如果將未來短時間段Δt內(nèi)車流密度的均值作為輸入變量,則可利用類似于微積分理念將具有時變特性的模型分解成若干靜態(tài)模型。根據(jù)這一思路,可利用如下針對城市路網(wǎng)的最優(yōu)路徑算法步驟求解上述模型。

2) 初始化,以某一時刻為算法初始時刻t0;計算時間段[t0,t0+Δt)內(nèi)的符合θ取值范圍的以當前所在頂點為起始端的有向弧的車流密度均值,并將其作為輸入變量;記錄當前所在頂點的編號。

3) 判斷當前所在頂點是否是終點(或代終點),若是,則停止算法,輸出所經(jīng)過的頂點序列,即為所求最優(yōu)路徑,輸出對應的行程時間;否則繼續(xù)執(zhí)行下一步。

4) 更新參數(shù),k=k+1;tk=t;計算時間段[tk,tk+Δt)(k=0,1,2,…)內(nèi)的符合θ取值范圍的以當前所在頂點為起始端的有向弧的車流密度均值,并將其作為輸入變量。

5) 根據(jù)前文公式(9)計算符合θ取值范圍的以當前所在頂點為起始端的有向弧的權重,選取其中權重最小的有向弧作為接下來行駛的路段,沿該有向弧到達下一頂點。

1.3.3 算法分析

前文對針對城市路網(wǎng)的最優(yōu)路徑搜索算法進行了詳細描述,包括模型基本假設及具體的算法步驟,這里按照前文所述算法步驟,可繪制流程圖如圖2,下面分析和討論本算法。

圖2 算法流程圖Fig.2 Flow chart of algorithm

確定以起點與終點連線為對角線的矩形區(qū)域為搜索區(qū)域,可減少不必要的搜索范圍,且可以保證起點到最優(yōu)路徑中任一頂點的距離不大于起點到終點的距離。在平面上,當前所在頂點到終點的向量與起點到終點的向量間的夾角θ最大取值范圍為[0, 180°]。本文算法取θ∈[0, 90°),如此可避免所走路徑連接成環(huán),從而令所選路徑方向盡可能接近起點到終點的方向;同時可以減少不必要的搜索范圍,降低算法計算量。

由于限定了整體的矩形搜索區(qū)域,且避免了所走路徑連接成環(huán),使得整個最優(yōu)路徑各路段的空間距離之和不大于所限定的矩形搜索區(qū)域的兩條直角邊之和。這一點保證了本文算法比傳統(tǒng)的僅將空間距離作為權重的算法更優(yōu)秀,因為本算法考慮了動態(tài)變化的行車環(huán)境,能夠自適應選取最優(yōu)路徑,而僅將空間距離作為權重的算法所選取的路徑是固定不變的,不能適應動態(tài)變化的環(huán)境。

城市路網(wǎng)中各處的行車環(huán)境時刻在變化,這對最優(yōu)路徑的搜索造成較大的影響。本文算法利用短時預測得到的未來短時間段Δt內(nèi)車流密度的均值作為輸入變量,選取下一步要走的路段。當通過所選取的路段到達下一頂點后,重新預測未來短時間段Δt內(nèi)車流密度。重復這一過程,直到到達終點為止。在這一過程中,每次循環(huán)所選取的路段均是綜合考慮當時行車環(huán)境的最優(yōu)路段,這保證了所選整體路徑在當時所處行車環(huán)境下的最優(yōu)性。

2 仿真實驗及結果

根據(jù)上節(jié)描述的算法,利用MATLAB軟件進行了仿真實驗。在實驗過程中,采用圖1所示的簡化城市路網(wǎng)圖。為了盡可能接近實際的城市道路網(wǎng)絡系統(tǒng),將圖1 中的各路段分成了三級:主干路、次干路、支路,并按照《城市交通運行狀況評價規(guī)范》[18]中的標準給出各路段設置了基本參數(shù)。

對應于圖1中各編號交叉口的坐標如表1所示。主干路包括1-2-3-4-5和24-25-26-27-28-29-30;次干路包括1-6-17-24、2-8-14-21-26、3-9-15-22-27、4-10-16-23-28、5-12-19-30;其余路段均為支路。這三級道路的自由流速度依次設為50、40、30(單位:km/h),阻塞密度依次設為125、115、105(單位:輛/千米)。兩條主干路上各交叉口信號周期時長設為0.04 h,第18交叉口信號周期時長設為0.02 h,其余交叉口信號周期時長設為0.03 h。此外,支路中還有兩條單向路段17→20和16→18,其余各路段均為雙向路段。作為輸入變量的車流密度和交叉口時間延誤是在合理范圍內(nèi)隨機生成的。

根據(jù)上述所設參數(shù),將上一節(jié)描述的算法在MATLAB平臺上進行編程實現(xiàn),選取第1個交叉口為起點、第30個交叉口為終點,得到結果如圖3所示(實線為本文算法所求最優(yōu)路徑,上三角標記起點,下三角標記終點),驗證了所提算法的可行性與有效性。如果是傳統(tǒng)的最短路徑搜索算法,只考慮空間距離這類定常因素,則所搜索的路徑將是固定不變的,不適用于實際情況中城市道路網(wǎng)絡多變復雜的行車環(huán)境。從這一角度也證明了本文模型算法的自適應特性。

表1 各編號交叉口的坐標

圖3 不同行車環(huán)境中的最優(yōu)路徑圖Fig.3 Optimal path diagram in different driving environments

此外,本文進行了對比仿真實驗,從圖1所示的地圖中任意選取兩個交叉口作為起點和終點,分別利用本文算法和傳統(tǒng)的Floyd算法搜索最優(yōu)路徑[2]。結果發(fā)現(xiàn)在軟件平臺MATLAB(R2014a)及硬件平臺3.2 GHz處理器(CPU)安裝內(nèi)存(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以上。通過這一對比仿真實驗,可凸顯本文算法的實時性。

3 結論

本文綜合考慮了城市路網(wǎng)中影響道路阻抗的時變因素與定常因素,結合限制搜索區(qū)域方法,同時引入搜索方向因素,建立了針對城市路網(wǎng)的限制搜索區(qū)域的時變權重有向圖模型,并給出了相應的最優(yōu)路徑搜索算法。該模型算法更符合城市路網(wǎng)中的實際交通狀況,能夠在不斷變化的交通流影響下,自適應地選取最優(yōu)路徑,保證了車輛在當時所處環(huán)境下所選路徑是最優(yōu)的。仿真實驗驗證了該模型算法的有效性、自適應性和實時性。

雖然考慮了城市路網(wǎng)中影響最優(yōu)路徑搜索的交通流的主要時變因素,但同樣還存在其他時變因素未能考慮,如天氣等。此外,本文模型算法是建立在多個基本假設基礎之上的,尤其是需要較準確地預測未來短時間內(nèi)車流密度,可能使得算法存在一定局限性。因此,我們下一步工作是從以上兩方面來改進模型算法。