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

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

1.揚(yáng)州市公路管理處，揚(yáng)州 225000

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

0 引 言

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

目前，出行誘導(dǎo)路徑算法比較多，最基本的算法是Dijkstra 算法[1]，在此算法改進(jìn)的基礎(chǔ)上，產(chǎn)生了邊帶標(biāo)號(hào)的最短路算法、A*搜索算法[2,3]、高速路分層算法[4]等。王海梅等[5]采用矩形限制區(qū)域搜索算法來提高算法的效率和精確度；吳成中等[6]應(yīng)用神經(jīng)網(wǎng)絡(luò)對(duì)交通信息進(jìn)行實(shí)時(shí)預(yù)測(cè)，構(gòu)造具有時(shí)變性的路阻矩陣，并與限制搜索區(qū)域的算法結(jié)合，解決了算法的實(shí)時(shí)性差、收斂慢等問題；王亞文等[7]借助圖像學(xué)知識(shí)，利用路網(wǎng)的多比例尺數(shù)據(jù)對(duì)不同等級(jí)道路進(jìn)行分層，用于降低搜索路網(wǎng)的復(fù)雜度，提高運(yùn)算效率。但是，實(shí)際的路網(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)的初分層

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

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

初分層滿足以下幾個(gè)條件：

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

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

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

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

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

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

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

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

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

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

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

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

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

路網(wǎng)擁擠程度值λ 為不同擁擠狀態(tài)對(duì)應(yīng)速度v的倒數(shù)，即λ=1/v。在進(jìn)行交通狀態(tài)分析時(shí)，在擁擠程度值區(qū)間制定一個(gè)交通擁擠值作為交通擁擠程度截值 λr來評(píng)價(jià)交通狀況。根據(jù)中國道路交通管理評(píng)價(jià)指標(biāo)的規(guī)定：城市主干道機(jī)動(dòng)車平均行程速度不低于30km/h 為暢通，20km/h～30km/h 之間為輕度擁擠，10km/h～20km/h 之間為擁擠，低于10km/h 為嚴(yán)重?fù)頂D。依此標(biāo)準(zhǔn)，可以選取交通擁擠程度截值，例如，可以取 λ1=0.1，λ2=0.2 作為嚴(yán)重?fù)頂D程度截值；λ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ǔ)上，加入時(shí)變的路段交通狀態(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)可達(dá)矩陣T=｛tij(λr)｝，此矩陣表示在給定路網(wǎng)擁擠截值 λr下路網(wǎng)可達(dá)關(guān)系：路網(wǎng)交通狀態(tài)可達(dá)矩陣由路網(wǎng)交通狀態(tài)連通矩陣進(jìn)行兩類布爾運(yùn)算（邏輯乘，邏輯加）得到：T=Cn+1，n 其元素值為｛0，1｝，n 為運(yùn)算次數(shù)。當(dāng)路口 ni與 nj之間至少存在一條通路且各路段交通狀態(tài)系數(shù)小于路網(wǎng)擁擠截值時(shí)，值為1，否則為0。

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

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

能到達(dá)路口 ni的集合，記為

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟7：將路徑中不可達(dá)路段的兩端節(jié)點(diǎn)降入低一級(jí)子網(wǎng)，在低一級(jí)子網(wǎng)重新進(jìn)行路徑搜索，直至優(yōu)化路徑中所有路段均符合路段可達(dá)性標(biāo)準(zhǔn)，算法結(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)布局為例，進(jìn)行出行路徑誘導(dǎo)選擇的實(shí)例分析：出行者駕車從圖中S 點(diǎn)出發(fā)，停車地點(diǎn)為D 點(diǎn)。

圖3 S' 與 D' 之間路網(wǎng)拓?fù)銯ig.3 Topological graph of the road between S' and D'

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

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

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

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

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

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

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

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

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

計(jì)算路口鄰接矩陣如下：

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

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

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

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

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

以上巡徑過程對(duì)于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)方法，但是其效率會(huì)隨著路網(wǎng)規(guī)模的擴(kuò)大、節(jié)點(diǎn)數(shù)的增加而急劇下降。論文采用基于路網(wǎng)二次分層的出行誘導(dǎo)路徑優(yōu)化算法，通過對(duì)道路網(wǎng)進(jìn)行分層抽象，再選擇合適的路網(wǎng)層進(jìn)行搜索，由于其本質(zhì)上大幅度縮減路網(wǎng)的規(guī)模，解決了大規(guī)模路網(wǎng)路徑搜索效率低的問題。

算法在宏觀方面考慮了路網(wǎng)的結(jié)構(gòu)（等級(jí)結(jié)構(gòu)、功能結(jié)構(gòu)、布局結(jié)構(gòu)），在微觀方面考慮路網(wǎng)運(yùn)行的交通參數(shù)（平均行程時(shí)間、平均行程速度、路段擁擠狀況），擁擠狀態(tài)閾值的選取與交通流狀態(tài)保持一致，達(dá)到在暢通狀態(tài)下，滿足出行者使用高等級(jí)道路出行的傾向（此時(shí)，大部分路段的交通狀態(tài)系數(shù)都小于擁擠狀態(tài)閾值，高等級(jí)路網(wǎng)不存在不可達(dá)節(jié)點(diǎn)，不用下降到低等級(jí)路網(wǎng)搜尋路徑）；在擁擠狀態(tài)下，調(diào)節(jié)擁擠的高等級(jí)路段上交通流的作用（此時(shí)，擁擠路段的交通狀態(tài)系數(shù)大于擁擠狀態(tài)閾值，部分節(jié)點(diǎn)間路徑下降到低等級(jí)路網(wǎng)進(jìn)行搜尋，優(yōu)化的出行路徑將減輕高等級(jí)道路上的交通壓力）。因此，該算法搜索效率高、搜索結(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]王海梅，周獻(xiàn)中.一種限制搜索區(qū)域的最短路徑改進(jìn)算法[J].南京理工大學(xué)學(xué)報(bào)，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].計(jì)算機(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.