潘大為 鄧 衛(wèi) 季彥婕

1.揚州市公路管理處，揚州 225000

2.東南大學(xué)，交通學(xué)院，南京 210096

0 引 言

國民經(jīng)濟的快速增長、城市化進程的加快、道路交通條件的改善帶來了機動車保有量的顯著增加，居民出行方式的機動化趨勢日趨顯著，由此所產(chǎn)生的城市交通問題也日益突出。路徑誘導(dǎo)系統(tǒng)作為智能交通系統(tǒng)的重要組成部分,在解決擁堵問題時將發(fā)揮關(guān)鍵性的作用。

目前，出行誘導(dǎo)路徑算法比較多，最基本的算法是Dijkstra 算法[1]，在此算法改進的基礎(chǔ)上，產(chǎn)生了邊帶標(biāo)號的最短路算法、A*搜索算法[2,3]、高速路分層算法[4]等。王海梅等[5]采用矩形限制區(qū)域搜索算法來提高算法的效率和精確度；吳成中等[6]應(yīng)用神經(jīng)網(wǎng)絡(luò)對交通信息進行實時預(yù)測，構(gòu)造具有時變性的路阻矩陣，并與限制搜索區(qū)域的算法結(jié)合，解決了算法的實時性差、收斂慢等問題；王亞文等[7]借助圖像學(xué)知識，利用路網(wǎng)的多比例尺數(shù)據(jù)對不同等級道路進行分層，用于降低搜索路網(wǎng)的復(fù)雜度，提高運算效率。但是，實際的路網(wǎng)規(guī)模大，路況復(fù)雜，結(jié)合已有研究成果，在深入了解路網(wǎng)結(jié)構(gòu)以及道路交通狀況的基礎(chǔ)上，建立路網(wǎng)二次分層模型，利用路網(wǎng)不同層之間的協(xié)同，提出優(yōu)化的出行路徑誘導(dǎo)方法。

1 路網(wǎng)二次分層模型的建立

1.1 基于路網(wǎng)結(jié)構(gòu)的初分層

從宏觀角度對路網(wǎng)進行初分層，即從城市路網(wǎng)的功能結(jié)構(gòu)、等級結(jié)構(gòu)以及布局結(jié)構(gòu)方面進行綜合考慮。表1 為路網(wǎng)功能、等級以及布局結(jié)構(gòu)比較。

表1 路網(wǎng)功能、等級以及布局結(jié)構(gòu)比較Tab.1 Comparative amony road network’s function,grade and layout

初分層滿足以下幾個條件：

（1）層數(shù)小于等于路網(wǎng)等級分類數(shù)，各層的路段數(shù)接近。

城市路網(wǎng)快速路較少，而且與主干路功能類似，將這兩種道路劃為同一層，因此，總層數(shù)P≤3層，各層路段數(shù)Q 大致相等。

（2）滿足道路等級的結(jié)構(gòu)要求，相近等級道路相對集中于同一層。

相鄰等級道路可以合并到同一層，例如主干路可以與次干路合并，次干路可以與支路合并，但是主干路不宜與支路合并。

（3）滿足道路功能的結(jié)構(gòu)要求，通過性、可達性類似的道路相對集中于同一層。

圖1 路網(wǎng)功能、等級以及布局結(jié)構(gòu)Fig.1 Structure of road network’s function,grade and layout

假設(shè)按照功能結(jié)構(gòu)中通過性與可達性的強弱，將各個路段從1 到10 賦值，其中賦值1 代表路段的通過性最好，可達性最差；賦值10 代表路段的可達性最好，通過性最差。依據(jù)各層路段的功能構(gòu)成賦予a 層b 路段的權(quán)值為 rab，其中a 為路網(wǎng)層編號，b 為路段編號，a≤P，b≤Q，滿足

（4）滿足道路布局的結(jié)構(gòu)要求，依據(jù)不同布局所體現(xiàn)出的交通流分布規(guī)律對路網(wǎng)分層。路網(wǎng)布局影響交通流的分布，路網(wǎng)分層要考慮流量分布的影響。

1.2 基于路網(wǎng)交通狀態(tài)的次分層

路網(wǎng)由路段以及路口組成，通過路段及路口狀態(tài)描述路網(wǎng)交通狀態(tài)更加合理。m 個路口和路口間的路段組成的路網(wǎng)，其路口集合表示為N=｛n1,n2,…nm｝；路段集合表示為 L=｛lij≤ni,nj＞｝；其中，i,j=1,2,…,m。路網(wǎng)交通狀態(tài)次分層引入如下兩個變量和四個矩陣：

變量1：路段交通狀態(tài)系數(shù) sij

路網(wǎng)交通狀態(tài)系數(shù)為路段 lij在某個交通數(shù)據(jù)采樣時段內(nèi)單位長度上的平均行程時間sij=Tij/dij=1/vij，其中 dij為路段 lij的長度，vij為采樣時段路段平均行程速度。路段交通狀態(tài)系數(shù)綜合考慮了路段平均行程時間和路段長度，把計算路段行程時間轉(zhuǎn)化為計算路段平均速度。

變量2：路段擁擠程度值λ

路網(wǎng)擁擠程度值λ 為不同擁擠狀態(tài)對應(yīng)速度v的倒數(shù)，即λ=1/v。在進行交通狀態(tài)分析時，在擁擠程度值區(qū)間制定一個交通擁擠值作為交通擁擠程度截值 λr來評價交通狀況。根據(jù)中國道路交通管理評價指標(biāo)的規(guī)定：城市主干道機動車平均行程速度不低于30km/h 為暢通，20km/h～30km/h 之間為輕度擁擠，10km/h～20km/h 之間為擁擠，低于10km/h 為嚴重擁擠。依此標(biāo)準，可以選取交通擁擠程度截值，例如，可以取 λ1=0.1，λ2=0.2 作為嚴重擁擠程度截值；λ3=0.066，λ4=0.05 分別作為擁擠程度截值；λ5=0.04，λ6=0.033 作為輕微擁擠程度截值。

矩陣1：路口鄰接矩陣 k=｛kij｝，此矩陣表示路網(wǎng)之間物理連接關(guān)系：

矩陣 2：路網(wǎng)交通狀態(tài)鄰接矩陣M=｛mij｝，此矩陣在路口鄰接矩陣的基礎(chǔ)上，加入時變的路段交通狀態(tài)信息，包括路網(wǎng)交通參數(shù)等信息：

矩陣 3：路網(wǎng)交通狀態(tài)連通矩陣C=｛cij(λr)｝，此矩陣表示在給定路網(wǎng)擁擠截值 λr下路網(wǎng)連通狀態(tài)，包括路網(wǎng)交通參數(shù)信息以及交通狀態(tài)判定信息：

矩陣4：路網(wǎng)交通狀態(tài)可達矩陣T=｛tij(λr)｝，此矩陣表示在給定路網(wǎng)擁擠截值 λr下路網(wǎng)可達關(guān)系：路網(wǎng)交通狀態(tài)可達矩陣由路網(wǎng)交通狀態(tài)連通矩陣進行兩類布爾運算（邏輯乘，邏輯加）得到：T=Cn+1，n 其元素值為｛0，1｝，n 為運算次數(shù)。當(dāng)路口 ni與 nj之間至少存在一條通路且各路段交通狀態(tài)系數(shù)小于路網(wǎng)擁擠截值時，值為1，否則為0。

路網(wǎng)次分層方法如下：

步驟1：計算在當(dāng)前路網(wǎng)交通狀態(tài)可達矩陣中路口 ni能到達的路口集合，記為

能到達路口 ni的集合，記為

步驟2：考查與路口 ni相連通的路口，判斷與路口 ni互通的路口集合與路口能到達的路口集合是否相等，即判斷

是否成立，若成立，則 Ng｛ni|λr｝中的路口放入路網(wǎng)次分層的最上層。

步驟3：在路網(wǎng)可達矩陣中劃去步驟2 中確定的上層路口，若所有路口均劃入所屬層次中，計算結(jié)束。否則，在新的路網(wǎng)可達矩陣中，回到步驟1繼續(xù)計算。

次分層產(chǎn)生的各層路口中，處于最上層的路口可達性好，即到達該路口的道路暢通，從該路口到達其他路口擁擠。處于最下層的路口可達性差，即從該路口到達其他路口暢通，其他路口到達路口道路擁擠。處于中間層的路口能夠到達其他路口，其他路口也可以到達該路口。

2 基于路網(wǎng)二次分層的出行誘導(dǎo)路徑優(yōu)化方法

Dijkstra 算法是一種典型的單起始點的最短路徑算法，通過樹形結(jié)構(gòu)來尋找最短路徑，算法的時間復(fù)雜度為O(n2)；A*算法是在Dijkstra 算法基礎(chǔ)上的進一步改進，通過從起始點進行前向搜索且從目標(biāo)點進行后向搜索來計算最優(yōu)路徑，算法的時間復(fù)雜度為 O(bc)。與平面算法相比較，分層算法的時間復(fù)雜度從O(d4)下降到 O(logad)。其中，n 為路網(wǎng)中節(jié)點個數(shù)；b 為道路節(jié)點長度，一般不超過4；d為路徑長度；a 為與道路分層標(biāo)準有關(guān)的常量。

鑒于以上分析，論文在路網(wǎng)二次分層模型基礎(chǔ)上，采用限制區(qū)域的 A*算法尋找最短路徑，進行最優(yōu)出行路徑的“三段尋徑”過程，具體計算步驟如下：

步驟1：對路網(wǎng)進行初分層，形成的各層路網(wǎng)分別為子網(wǎng)0，子網(wǎng)1，子網(wǎng)2,…，各層子網(wǎng)內(nèi)的道路等級高低由子網(wǎng)0 依次遞減，子網(wǎng)數(shù)量原則上不大于3。

步驟2：判斷起點S 與終點D 所在的子網(wǎng)是否為子網(wǎng)0，如果不是，分別尋找與起點及終點最近的子網(wǎng)0 上的節(jié)點 S' 以及 D'。

步驟3：以起點S 與終點D 之間的路網(wǎng)為出行路徑搜索區(qū)域，去除不必要的道路數(shù)據(jù)。

步驟4：進行出行路徑的“三段尋徑”，巡徑路段共分三段：尋找起點S 到高層次路網(wǎng)較近節(jié)點S '之間的最優(yōu)路徑route(S→S')，尋找高層次路網(wǎng)較近節(jié)點 D '到終點D 之間的最優(yōu)路徑route(D'→D)，尋找 S '到 D '之間的最優(yōu)路徑route(S'→D')。

步驟5：每段尋徑過程均采用限制區(qū)域的雙向A*算法，得到初始優(yōu)化路徑。

步驟6：引入交通狀態(tài)閾值，分別對S→S'，S'→D'，D'→D之間的路網(wǎng)進行次分層，判斷初始優(yōu)化路徑中各個路段的可達性。

步驟7：將路徑中不可達路段的兩端節(jié)點降入低一級子網(wǎng)，在低一級子網(wǎng)重新進行路徑搜索，直至優(yōu)化路徑中所有路段均符合路段可達性標(biāo)準，算法結(jié)束。

圖2 為最優(yōu)出行誘導(dǎo)路徑搜索示意。

圖2 最優(yōu)出行誘導(dǎo)路徑搜索示意Fig.2 Searching chart of the optimal travel route

3 示例應(yīng)用及分析

以圖3 中的路網(wǎng)布局為例，進行出行路徑誘導(dǎo)選擇的實例分析：出行者駕車從圖中S 點出發(fā)，停車地點為D 點。

圖3 S' 與 D' 之間路網(wǎng)拓撲Fig.3 Topological graph of the road between S' and D'

在路網(wǎng)初分層時將路網(wǎng)分成兩個層次：①子網(wǎng)0 層為路網(wǎng)等級較高層，主要包括快速路、主干路以及通過性好的次干路；②子網(wǎng)1 層為路網(wǎng)等級較低層，主要包括可達性好的次干路以及支路。分層結(jié)果如圖4 所示。

圖4 路網(wǎng)初分層Fig.4 Initial Hierarchy of the road network

按照S→D 的路徑搜索方向，在子網(wǎng)0 上尋找節(jié)點 S' 以及 D'，利用限制區(qū)域的雙向A*算法，在子網(wǎng)1 搜尋路徑：

route(S→S')，route(D'→D)，在子網(wǎng)0 搜尋路徑：route(S'→D')；

由于篇幅限制，下面以搜尋route(S'→D')為例，對算法進行具體說明：

利用 S' 與 D' 之間的矩形區(qū)域縮小路網(wǎng)的搜索范圍，路網(wǎng)拓撲結(jié)構(gòu)圖以及各路段參數(shù)如圖3 與表2 所示。

表2 矩形搜索區(qū)域內(nèi)各路段交通參數(shù)Tab.2 Road parameters of the rectangle searching district

在矩形搜索區(qū)域內(nèi)，利用 A*搜索算法很容易計算出route(S'→D')=①-②-⑤-⑥

下面在子網(wǎng)0 層，對 S' 與 D' 之間的路網(wǎng)進行次分層，計算相關(guān)矩陣，并判斷路網(wǎng)中各節(jié)點間的可達性。

計算路口鄰接矩陣如下：

計算路網(wǎng)交通狀態(tài)鄰接矩陣如下：

通過表2 可知路段上車輛的平均行程速度介于20km/h～30km/h，屬于輕微擁堵。選擇路網(wǎng)擁擠截值λr=0.05，計算路網(wǎng)交通狀態(tài)連通矩陣以及路網(wǎng)交通可達矩陣如下：

表3 為路網(wǎng)次分層迭代計算。

表3 路網(wǎng)次分層迭代計算表Tab.3 Calculating table of the second hierarchy of the road net

S′到D′初始優(yōu)化路徑為①-②-⑤-⑥，表3 中次分層結(jié)果顯示：節(jié)點②處于最上層的路口，可達性好；節(jié)點⑤處于最下層的路口，可達性差。因此，由節(jié)點②駛往節(jié)點⑤的可達性差，需要在低一等級的路網(wǎng)——子網(wǎng)1 中搜索②→⑤的最優(yōu)路徑，同樣，用A*算法很容易子網(wǎng)1 中得到②→⑤的優(yōu)化路徑，并用同樣的方法進行路網(wǎng)次分層分析②→⑤的優(yōu)化路徑上節(jié)點之間的可達性，得到route②→⑤。（表3 中，每次迭代過程中Ng與Ng∩Na數(shù)值時，用方框標(biāo)注以示區(qū)別）

以上巡徑過程對于route(S→S')以 及route(D'→D)同樣也適用。最終S 到D 的最優(yōu)出行誘導(dǎo)路徑為：

如圖5 所示。

圖5 最優(yōu)路徑搜尋結(jié)果Fig.5 Result of the optimal travel route

4 結(jié)束語

平面算法是求解最短出行路徑的傳統(tǒng)方法，但是其效率會隨著路網(wǎng)規(guī)模的擴大、節(jié)點數(shù)的增加而急劇下降。論文采用基于路網(wǎng)二次分層的出行誘導(dǎo)路徑優(yōu)化算法，通過對道路網(wǎng)進行分層抽象，再選擇合適的路網(wǎng)層進行搜索，由于其本質(zhì)上大幅度縮減路網(wǎng)的規(guī)模，解決了大規(guī)模路網(wǎng)路徑搜索效率低的問題。

算法在宏觀方面考慮了路網(wǎng)的結(jié)構(gòu)（等級結(jié)構(gòu)、功能結(jié)構(gòu)、布局結(jié)構(gòu)），在微觀方面考慮路網(wǎng)運行的交通參數(shù)（平均行程時間、平均行程速度、路段擁擠狀況），擁擠狀態(tài)閾值的選取與交通流狀態(tài)保持一致，達到在暢通狀態(tài)下，滿足出行者使用高等級道路出行的傾向（此時，大部分路段的交通狀態(tài)系數(shù)都小于擁擠狀態(tài)閾值，高等級路網(wǎng)不存在不可達節(jié)點，不用下降到低等級路網(wǎng)搜尋路徑）；在擁擠狀態(tài)下，調(diào)節(jié)擁擠的高等級路段上交通流的作用（此時，擁擠路段的交通狀態(tài)系數(shù)大于擁擠狀態(tài)閾值，部分節(jié)點間路徑下降到低等級路網(wǎng)進行搜尋，優(yōu)化的出行路徑將減輕高等級道路上的交通壓力）。因此，該算法搜索效率高、搜索結(jié)果優(yōu)，可以較好的應(yīng)用于出行誘導(dǎo)、交通控制等系統(tǒng)中。

[1]Zhan F.B.,Noon C.E.Shortestpath algorithms:An evaluation using real road networks[J].Transportation,1998,32(1):65-73.

[2]Huang B.,Wu Q.,Zhan F.B.A Shortest path algorithm with novel heuristics for dynamic transportation net-works[J].International Journal of Geographical Information Science,2007,21(6):625-644.

[3]Goldgerg A.V.,Kaplan H.,Werneck R.F.Reach forA*:Efficient point-to-point shortest path algorithms[A].Proceedings of the 8thWorkshop on Algorithm Engineering and Experiment Vancouver SIAM,2006.

[4]Sanders P,Schulters D.Engineering highway hierarchies[A].Proceedings of the 14thAnnual European Symposium on Algorithms Berlin:Springer,2006:804-816.

[5]王海梅，周獻中.一種限制搜索區(qū)域的最短路徑改進算法[J].南京理工大學(xué)學(xué)報，2009，33（5）：638-642.

[6]吳成東，韓中華，張穎等.基于并行遺傳神經(jīng)網(wǎng)絡(luò)算法的限制搜索區(qū)域最優(yōu)路徑方法[J].公路交通科技，2006，23（8）：126-142.

[7]王亞文，汪西莉，曹 菡.一種限制搜索區(qū)域的多比例尺最優(yōu)路徑規(guī)劃算法[J].計算機應(yīng)用研究，2007，24(12)：66-71.

[8]Jagadeesh G.R.,Srikanthan T.,Quek K.H.Heuristic techniques for accelerating hierarchical routing on road networks[J].IEEE Transactions on Intelligent Transportation System,2002,3(4):301-309.