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

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

0 引言

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

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

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

1 基本原理及方法

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

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

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

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

(1)

1.2 時(shí)變路阻(權(quán))函數(shù)

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

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

q=ρv

(2)

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

(3)

(4)

(5)

(6)

(7)

路阻也稱路權(quán),由路段阻抗和節(jié)點(diǎn)(交叉口)阻抗組成。對(duì)于傳統(tǒng)的路徑規(guī)劃算法,道路權(quán)重選取的是路段的長(zhǎng)度,這是大部分路徑規(guī)劃的首選指標(biāo),因?yàn)樗菀撰@得,相對(duì)比較簡(jiǎn)單。但此類指標(biāo)只適應(yīng)于道路暢通、路況較為一致的道路,并沒(méi)有充分考慮由于長(zhǎng)度以外的路阻所帶來(lái)的延誤。由于大多數(shù)路阻最終都會(huì)導(dǎo)致時(shí)間延誤,或者與時(shí)間延誤相關(guān),因此構(gòu)造路阻函數(shù)為

(8)

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

(9)

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

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

1.3.1 模型假設(shè)

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3.3 算法分析

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

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

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

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

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

2 仿真實(shí)驗(yàn)及結(jié)果

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

對(duì)應(yīng)于圖1中各編號(hào)交叉口的坐標(biāo)如表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;其余路段均為支路。這三級(jí)道路的自由流速度依次設(shè)為50、40、30(單位:km/h),阻塞密度依次設(shè)為125、115、105(單位:輛/千米)。兩條主干路上各交叉口信號(hào)周期時(shí)長(zhǎng)設(shè)為0.04 h,第18交叉口信號(hào)周期時(shí)長(zhǎng)設(shè)為0.02 h,其余交叉口信號(hào)周期時(shí)長(zhǎng)設(shè)為0.03 h。此外,支路中還有兩條單向路段17→20和16→18,其余各路段均為雙向路段。作為輸入變量的車流密度和交叉口時(shí)間延誤是在合理范圍內(nèi)隨機(jī)生成的。

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

表1 各編號(hào)交叉口的坐標(biāo)

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

此外,本文進(jìn)行了對(duì)比仿真實(shí)驗(yàn),從圖1所示的地圖中任意選取兩個(gè)交叉口作為起點(diǎn)和終點(diǎn),分別利用本文算法和傳統(tǒng)的Floyd算法搜索最優(yōu)路徑[2]。結(jié)果發(fā)現(xiàn)在軟件平臺(tái)MATLAB(R2014a)及硬件平臺(tái)3.2 GHz處理器(CPU)安裝內(nèi)存(RAM)4 GB基礎(chǔ)上,在行車環(huán)境動(dòng)態(tài)變化的情況下,本文算法對(duì)于圖1中的任意兩個(gè)交叉口都能搜索到最優(yōu)路徑。在相同條件下,Floyd算法(道路權(quán)重僅考慮空間距離)則由于時(shí)間復(fù)雜度(O(n3))較大,導(dǎo)致只能實(shí)現(xiàn)部分交叉口之間的最優(yōu)路徑搜索,多數(shù)最優(yōu)路徑搜索過(guò)程需要花費(fèi)時(shí)間超過(guò)30 min,例如以第1交叉口為起點(diǎn),分別以第10、11、13、16、18、19、29、30交叉口為終點(diǎn)的最優(yōu)路徑搜索仿真實(shí)驗(yàn)消耗時(shí)間均在30 min以上。通過(guò)這一對(duì)比仿真實(shí)驗(yàn),可凸顯本文算法的實(shí)時(shí)性。

3 結(jié)論

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

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