李曉丹

1.上海應(yīng)用技術(shù)學(xué)院計算機科學(xué)與信息工程學(xué)院，上海201418

2.上海濟祥智能交通科技有限公司事業(yè)部，上海200092

1 引言

路徑誘導(dǎo)系統(tǒng)是一個復(fù)雜多目標(biāo)的大系統(tǒng)。它向不同用戶分時、分區(qū)提供不同路徑信息服務(wù)，一種誘導(dǎo)信息只適應(yīng)一定區(qū)域、一定時間和一定的用戶，當(dāng)其中一個條件變化時，誘導(dǎo)信息便不再適用。在動態(tài)路徑誘導(dǎo)時，需要著重考慮以下幾個問題：

（1）路徑的實時性，降低計算的時間復(fù)雜度。

（2）路徑的動態(tài)性，考慮動態(tài)交通狀態(tài)信息對路徑的影響。

（3）駕駛員路徑選擇行為，考慮人的出行習(xí)慣等因素的影響，而不僅僅是數(shù)學(xué)意義上的距離最短或時間最短的路徑。

在動態(tài)路徑誘導(dǎo)時，問題（1）是首先需要解決的，這決定了算法的實用性，國內(nèi)外在算法實時性方面的研究成果也較多，主要是從道路網(wǎng)絡(luò)的表達(dá)方式優(yōu)化（即降低算法搜索路網(wǎng)的規(guī)模，如采用路網(wǎng)分層分解方法[1-6]、矩形區(qū)域搜索方法[7]、橢圓區(qū)域搜索方法[3]等），網(wǎng)絡(luò)存儲結(jié)構(gòu)優(yōu)化[5，7]，搜索策略的優(yōu)化（啟發(fā)式算法[2]、基于交通流融合的蟻群算法[1]、改進(jìn)Dijkstra算法[4-5]等）等方面進(jìn)行研究，從不同程度降低了路網(wǎng)的復(fù)雜度。問題（2）也是計算動態(tài)路徑必須要解決的問題，當(dāng)前大部分的算法中都考慮了路段行程時間的估計和預(yù)測[2-3，5，7]，用于計算動態(tài)的路阻函數(shù)。將問題（3）考慮到動態(tài)路徑搜索算法中的研究并不多見，文獻(xiàn)[4]對此進(jìn)行了詳細(xì)的解析，并基于路網(wǎng)分層分解方法實現(xiàn)動態(tài)路徑誘導(dǎo)算法，但在路網(wǎng)分層方面沒有進(jìn)一步劃分路徑搜索區(qū)域，高層路網(wǎng)的規(guī)模依然很大，而且沒有將實時交通狀態(tài)考慮進(jìn)去。

據(jù)以上分析可知，當(dāng)前的動態(tài)路徑誘導(dǎo)法研究，完全充分考慮上述三個問題的研究不多見，要么是對降低計算時間復(fù)雜度方面研究不夠，要么是未考慮現(xiàn)實中駕駛員的路徑選擇習(xí)慣。本文即是在綜合考慮路徑實時性、動態(tài)性和駕駛員選擇行為的基礎(chǔ)上，提出了面向動態(tài)路徑誘導(dǎo)的路網(wǎng)動態(tài)分層優(yōu)化方法。

本文研究遵循這樣的駕駛員出行行為假設(shè)：出行者大多數(shù)愿意選擇那些他們比較熟悉，道路等級較高，連通性能較好的次優(yōu)路徑，而不是單純的距離最短路徑。

2 路網(wǎng)實時交通狀態(tài)判別

能夠及時準(zhǔn)確地獲取實時交通狀態(tài)信息，是保障動態(tài)路徑達(dá)到出行者期望的重要信息來源。出行者一般期望推薦的路徑上沒有嚴(yán)重的擁擠，行程時間在可接受的范圍內(nèi)[4]，即為最優(yōu)路徑，因此它并不是嚴(yán)格數(shù)學(xué)意義上的時間最短路或距離最短路，相反它具有更符合駕駛員行為的現(xiàn)實意義。

2.1 連線擁擠度模型

（1）城市交通網(wǎng)絡(luò)模型建立

交通網(wǎng)絡(luò)可定義為：n個交叉口和交叉口間的路段組成交通網(wǎng)絡(luò)G=(I，L)。其中I=(i1，i2，…，in)表示路口集；表示與路口相關(guān)的路段集，Lij=＜i，j＞表示存在一條從路口i到路口j的路段。

在建立交通網(wǎng)絡(luò)模型的時候，需要考慮將交叉口參數(shù)歸入路段參數(shù)，共同作為交通網(wǎng)絡(luò)連線的權(quán)，從而可以計算每個連線的擁擠系數(shù)。其中，交叉口稱為網(wǎng)絡(luò)的節(jié)點，交叉口之間的連線即路段稱為網(wǎng)絡(luò)的連線。其模型示意圖如圖1所示。

圖1 交通網(wǎng)絡(luò)連線節(jié)點模型示意圖

（2）連線擁擠度概念

“連線擁擠度”較明確地反映了交通狀態(tài)，且最容易被人理解和接受。但是擁擠度并不是一個可直接測量而得的數(shù)據(jù)，必須通過其他交通參數(shù)的轉(zhuǎn)換或計算獲得。

本文對“連線擁擠度”進(jìn)行如下定義[8]：

其中：

上式中，λ為連線擁擠度，可以表示連線k的擁擠程度，值越大表示擁擠程度越嚴(yán)重；Tk為連線k上車輛的實際平均行程時間；Tk0為連線k上車輛按照最大限速行駛的行程時間；Lk為連線k的實際長度；vˉk為連線k上車輛的平均行駛速度；vˉki為連線k上第i輛車的平均行駛速度；vˉk0為連線k上允許或設(shè)計的車輛的最大行駛速度；n為連線k上的車輛數(shù)（這里假設(shè)n滿足最小樣本量）。

式（2）中，連線實際平均行程時間，可采用移動檢測設(shè)備，如浮動車數(shù)據(jù)，作為數(shù)據(jù)源來計算獲取。一般的，浮動車都可以直接獲得車輛的瞬時行駛速度，加上與精確電子地圖的地圖匹配，可以獲得其在連線k上的平均行駛速度，具體算法可參閱文獻(xiàn)[9-10]等。

2.2 交通狀態(tài)判別方法

當(dāng)Tk≤Tk0時，，即λ≤0時，實際行程時間小于或等于期望時間，即無延誤產(chǎn)生，為用戶最期望狀態(tài)——暢通狀態(tài)。

當(dāng)Tk＞Tk0時，，即λ＞0時，實際行程時間超過期望時間，即發(fā)生了延誤。λ取值越大，延誤越大，交通狀態(tài)越擁擠，道路服務(wù)質(zhì)量越低下。

以城市主干道最大限速60 km/h為例，那么：

式（1）可進(jìn)一步推導(dǎo)為：

根據(jù)λ的取值，判斷交通狀態(tài)的流程如圖2所示。

圖2 交通狀態(tài)等級判別流程圖

3 考慮實時狀態(tài)的道路動態(tài)分級

這里的“道路動態(tài)分級”是依據(jù)對駕駛員的出行行為假設(shè)，對道路優(yōu)先級別的一個動態(tài)分級。它本質(zhì)上并不改變道路原有的道路等級，只是對路網(wǎng)分層指標(biāo)的一個動態(tài)量化過程。

正是由于交通狀態(tài)的時變性，城市高等級道路（主干道）并不總處于優(yōu)先選擇的地位，而城市低等級道路（支路、次干道）也并不總處于無優(yōu)勢的地位。一般來說，高等級道路在路徑選擇過程中具有較高的權(quán)重，從這個意義上講，本文將實時的交通狀態(tài)因素考慮到道路優(yōu)先等級再確定過程中，以便給出所有城市道路合理的權(quán)重等級。

本文依據(jù)駕駛員選擇路徑道路等級優(yōu)先順序的一般規(guī)律，將實時交通狀態(tài)對道路優(yōu)先等級的影響權(quán)重ω設(shè)定為：暢通，ω=1；正常，ω=0.8；擁擠，ω=0.4；擁堵，ω=0。

假設(shè)道路的優(yōu)先等級指數(shù)G可以量化為：[2，1]，分別對應(yīng)：[高層道路，低層道路]，那么，基于交通狀態(tài)影響權(quán)重系數(shù)的道路優(yōu)先等級指數(shù)G′可表達(dá)為：

下面以當(dāng)前道路優(yōu)先等級為高等級道路，加權(quán)后道路優(yōu)先等級指數(shù)的確定方法示例：

若當(dāng)前判斷路段為暢通，則路段道路優(yōu)先等級指數(shù)維持不變，即G′=G=1×2=2；

若當(dāng)前判斷路段為正常，則新的道路優(yōu)先等級指數(shù)表達(dá)為G′=0.8×2=1.6；

若當(dāng)前判斷路段為擁擠，則新的道路優(yōu)先等級指數(shù)表達(dá)為G′=0.4×2=0.8；

若當(dāng)前判斷路段為擁堵，則新的道路優(yōu)先等級指數(shù)表達(dá)為G′=0×2=0。

依次類推，可以對所有不同等級的道路，計算考慮交通狀態(tài)影響權(quán)重系數(shù)下的新的道路優(yōu)先等級指數(shù)。

從中可以看出，由于路段交通狀態(tài)的不同，改變了道路優(yōu)先等級的原始數(shù)值。即使高等級的道路，由于其交通狀態(tài)是擁堵的，駕駛員也不會優(yōu)先選擇這些道路。

交通狀態(tài)的影響結(jié)果只考慮兩種情況：加入高層網(wǎng)絡(luò)和不加入高層網(wǎng)絡(luò)，因此將交通狀態(tài)等級模糊為二級：正常和擁擠。按照第2章討論的城市道路交通狀態(tài)判別方法，和本節(jié)討論的考慮交通狀態(tài)影響下的道路優(yōu)先等級確定方法，可以建立如圖3所示的對應(yīng)關(guān)系。

圖3 考慮交通狀態(tài)的道路動態(tài)分級

根據(jù)這種對應(yīng)法則，可以獲得城市道路的動態(tài)道路優(yōu)先等級，從而可以劃分實時的高層網(wǎng)絡(luò)。

4 道路網(wǎng)絡(luò)動態(tài)分層及規(guī)則

4.1 連線交通相似度的表達(dá)

在不考慮起止點位置時，首先是高層網(wǎng)絡(luò)的計算，也就是說，高層網(wǎng)絡(luò)是具有一定交通相似度的節(jié)點和連線的大集合。高層網(wǎng)絡(luò)完全是依據(jù)道路網(wǎng)絡(luò)的優(yōu)先等級和交通狀態(tài)的綜合系數(shù)的相似程度積聚而成的。

式中，K為連線交通相似度系數(shù)；g為原始道路優(yōu)先等級指數(shù)；s為實時交通狀態(tài)參數(shù)；g′為考慮動態(tài)因素的新的道路優(yōu)先等級指數(shù)；ω為交通狀態(tài)影響權(quán)重系數(shù)；一般，ω≥0.8時為正常或暢通狀態(tài)。

4.2 道路網(wǎng)絡(luò)的動態(tài)分層規(guī)則

在對道路優(yōu)先等級進(jìn)行再確定之后，不考慮實時交通狀態(tài)影響因素的道路網(wǎng)絡(luò)分層需要進(jìn)行局部調(diào)整。比如，對于交通擁堵的高等級道路，其行程時間延誤增大，與交通暢通的相鄰低等級道路（如次干道等）相比，大多數(shù)駕駛員會選擇低等級道路繞行，這時低等級道路的優(yōu)先級別升高，可以在網(wǎng)絡(luò)分層時將其劃入高層網(wǎng)絡(luò)；而在高等級道路恢復(fù)交通暢通后，重新劃入高層網(wǎng)絡(luò)，而原來的低等級道路劃入低層網(wǎng)絡(luò)。這個過程就是道路網(wǎng)絡(luò)的動態(tài)分層（如圖4）優(yōu)化過程。

圖4 道路網(wǎng)絡(luò)的動態(tài)分層示意圖

根據(jù)O、D點位置的不同，即O、D點是否是在高層網(wǎng)絡(luò)，道路網(wǎng)絡(luò)的動態(tài)分層有兩種情況：

（1）O、D點在高等級道路上

當(dāng)O、D點在高等級道路上時，道路網(wǎng)絡(luò)的動態(tài)分層較為簡單，即按照上述動態(tài)分層優(yōu)化過程，直接實現(xiàn)道路網(wǎng)絡(luò)的動態(tài)分層。這種情況大部分發(fā)生在途中動態(tài)路徑再規(guī)劃時，需要重新分層和分區(qū)。

（2）O、D點不在高等級道路上

當(dāng)O、D點不在高等級道路上時，需要考慮必須把O、D點及其所在的和周圍相關(guān)的連線都劃分到高層網(wǎng)絡(luò)中。這時需要以O(shè)點或D點為圓心，以到達(dá)周圍高等級道路的直線距離為半徑，做出圓域，將圓域范圍內(nèi)的次干道、支路等較低等級的道路路段也添加到臨時高層網(wǎng)絡(luò)中，以備最優(yōu)路徑的檢索。這種情況一般發(fā)生在初始路徑規(guī)劃或途中路徑再規(guī)劃時。

表1 交通狀態(tài)參數(shù)計算表（delinkdtatus）

以上根據(jù)道路網(wǎng)絡(luò)中道路的不同等級特性和實時交通狀態(tài)信息，將原來的整個道路網(wǎng)絡(luò)分為兩層，采用多層地圖的分級搜索技術(shù)可實現(xiàn)對搜索空間的控制。基于分層地圖的路徑搜索算法對道路網(wǎng)絡(luò)的分層規(guī)則要求具有下特征[11-12]：

（1）對不同優(yōu)化標(biāo)準(zhǔn)，層次可以按照道路優(yōu)先等級和實時交通狀態(tài)等級進(jìn)行劃分；

（2）層次細(xì)節(jié)由高到低逐漸增多，高層次是低層次的子集；

（3）每個層次的道路網(wǎng)絡(luò)是連通的，對于低層次是肯定的，在高層次中大部分情況下也是連通的，如果不連通，可以通過將低一級層次中的某些路段提取到高一級層次中，使之構(gòu)成連通網(wǎng)絡(luò)。譬如，當(dāng)高層網(wǎng)絡(luò)中某一路段處于交通擁堵時，其等級指數(shù)降低至g′=0.8或g′=0，應(yīng)將其劃入低層網(wǎng)絡(luò)中，但是此時高層網(wǎng)絡(luò)處于不連通狀態(tài)，應(yīng)該考慮將相鄰及其周圍的低層網(wǎng)絡(luò)中等級指數(shù)g′≥1或g′≥0.8的路段加入高層網(wǎng)絡(luò)，使其連通。

按照上述規(guī)則，檢查道路網(wǎng)絡(luò)動態(tài)分層的高層網(wǎng)絡(luò)的連通性，使其滿足上述規(guī)則要求。圖4中的虛線即是從低等級道路提取到高層網(wǎng)絡(luò)中的連線。

5 算例分析

本文選擇某市實際路網(wǎng)的部分區(qū)域為例，以ESRI公司A rcGIS9.0作為二次開發(fā)平臺，分析傳統(tǒng)Dijkstra算法和分層算法在誘導(dǎo)路徑計算時的優(yōu)劣。

圖5中的道路網(wǎng)絡(luò)為雙向道路網(wǎng)絡(luò)，分別用道路中心線編碼后加“1”和“2”來區(qū)別表示。圖中突出顯示的為城市部分主干道網(wǎng)絡(luò)。

選擇某時刻道路網(wǎng)絡(luò)交通狀態(tài)計算結(jié)果，按照表1結(jié)構(gòu)存儲在大型數(shù)據(jù)庫中，本文列出部分?jǐn)?shù)據(jù)內(nèi)容示例。

圖5 某市部分實際分層路網(wǎng)

表2列出了兩種算法路徑搜索結(jié)果的部分性能對比，從上面的路徑結(jié)果顯示（圖6和圖7）和表2可以看出傳統(tǒng)Dijkstra算法計算復(fù)雜度較高，所規(guī)劃出的路徑主要在低級網(wǎng)絡(luò)上，路徑長度最短，平均行車速度低；動態(tài)分層算法計算復(fù)雜度相對較低，所規(guī)劃出路徑基本都在高層網(wǎng)絡(luò)上，路徑長度稍長，平均行車速度較高。利用動態(tài)分層的路徑算法，其規(guī)劃結(jié)果更符合實際誘導(dǎo)系統(tǒng)需求，更能體現(xiàn)駕駛員的選路偏好。

表2 兩種算法部分性能對比分析

圖6 按照傳統(tǒng)Dijkstra算法計算路徑結(jié)果

表7 按照道路動態(tài)分層算法計算路徑結(jié)果

6 結(jié)束語

本文提出了基于實時交通狀態(tài)因素的動態(tài)道路優(yōu)先等級指數(shù)的確定方法，建立了連線交通相似度的模型，研究了道路網(wǎng)絡(luò)的動態(tài)分層規(guī)則和方法，并通過算例進(jìn)行了簡單的驗證分析。應(yīng)該說，基于路網(wǎng)動態(tài)分層優(yōu)化方法的路徑選擇是有很大優(yōu)勢的，并且更符合駕駛員的選擇行為，也與道路規(guī)劃者期望的道路功能相一致，在實際工程中具有現(xiàn)實意義。

[1]廖志斌.基于網(wǎng)格的城市動態(tài)路徑誘導(dǎo)系統(tǒng)研究[D].上海：華東師范大學(xué)，2007.

[2]劉名龍.城市交通動態(tài)路徑誘導(dǎo)算法研究及系統(tǒng)設(shè)計[D].昆明：昆明理工大學(xué)，2005.

[3]蘇海濱，王繼東，侯朝楨.道路網(wǎng)絡(luò)分層的快速路徑誘導(dǎo)算法[J].火力與指揮控制，2008，33（7）：108-111.

[4]曾松.城市道路網(wǎng)絡(luò)交通導(dǎo)行策略研究[D].上海：同濟大學(xué)，2000.

[5]范東凱.城市動態(tài)路徑誘導(dǎo)算法研究[D].西安：長安大學(xué)，2006.

[6]Huang Y W，Ning J，Rundensteiner E A.A hierarchical path view model for path finding in Intelligent Transportation System s[J].Geolnformatica，1997，1（2）：l25-159.

[7]陳曉紅.交通網(wǎng)絡(luò)動態(tài)路徑誘導(dǎo)算法研究及其在GIS環(huán)境下的仿真實現(xiàn)[D].長沙：長沙理工大學(xué)，2005-04.

[8]李曉丹，劉好德，楊曉光，等.城市道路網(wǎng)絡(luò)交通狀態(tài)時空演化量化分析[J].系統(tǒng)工程，2008，26（12）：66-70.

[9]童小華，陳建陽，吳淑琴.基于GIS和GPS的交通狀態(tài)參數(shù)估計仿真分析[J].同濟大學(xué)學(xué)報：自然科學(xué)版，2006，34（1）：47-52.[10]張和生，張毅，溫慧敏，等.利用GPS數(shù)據(jù)估計路段的平均行程時間[J].吉林大學(xué)學(xué)報：工學(xué)版，2007，37（3）：533-537.

[11]Jagadeesh G R，Srikanthan T，Quek K H.Combining hierarchical and heuristic techniques for high-speed route computation on road networks[J].Computing and Control Engineering Journal，2002（2）：120-126.

[12]吳京，景寧，陳宏盛.最佳路徑的層次編碼及查詢算法[J].計算機學(xué)報，2000，22（2）：184-189.