城市道路網絡動態優化選擇方法研究

李曉丹

1.上海應用技術學院計算機科學與信息工程學院，上海201418

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

1 引言

路徑誘導系統是一個復雜多目標的大系統。它向不同用戶分時、分區提供不同路徑信息服務，一種誘導信息只適應一定區域、一定時間和一定的用戶，當其中一個條件變化時，誘導信息便不再適用。在動態路徑誘導時，需要著重考慮以下幾個問題：

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

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

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

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

據以上分析可知，當前的動態路徑誘導法研究，完全充分考慮上述三個問題的研究不多見，要么是對降低計算時間復雜度方面研究不夠，要么是未考慮現實中駕駛員的路徑選擇習慣。本文即是在綜合考慮路徑實時性、動態性和駕駛員選擇行為的基礎上，提出了面向動態路徑誘導的路網動態分層優化方法。

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

2 路網實時交通狀態判別

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

2.1 連線擁擠度模型

（1）城市交通網絡模型建立

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

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

圖1 交通網絡連線節點模型示意圖

（2）連線擁擠度概念

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

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

其中：

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

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

2.2 交通狀態判別方法

當Tk≤Tk0時，，即λ≤0時，實際行程時間小于或等于期望時間，即無延誤產生，為用戶最期望狀態——暢通狀態。

當Tk＞Tk0時，，即λ＞0時，實際行程時間超過期望時間，即發生了延誤。λ取值越大，延誤越大，交通狀態越擁擠，道路服務質量越低下。

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

式（1）可進一步推導為：

根據λ的取值，判斷交通狀態的流程如圖2所示。

圖2 交通狀態等級判別流程圖

3 考慮實時狀態的道路動態分級

這里的“道路動態分級”是依據對駕駛員的出行行為假設，對道路優先級別的一個動態分級。它本質上并不改變道路原有的道路等級，只是對路網分層指標的一個動態量化過程。

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

本文依據駕駛員選擇路徑道路等級優先順序的一般規律，將實時交通狀態對道路優先等級的影響權重ω設定為：暢通，ω=1；正常，ω=0.8；擁擠，ω=0.4；擁堵，ω=0。

假設道路的優先等級指數G可以量化為：[2，1]，分別對應：[高層道路，低層道路]，那么，基于交通狀態影響權重系數的道路優先等級指數G′可表達為：

下面以當前道路優先等級為高等級道路，加權后道路優先等級指數的確定方法示例：

若當前判斷路段為暢通，則路段道路優先等級指數維持不變，即G′=G=1×2=2；

若當前判斷路段為正常，則新的道路優先等級指數表達為G′=0.8×2=1.6；

若當前判斷路段為擁擠，則新的道路優先等級指數表達為G′=0.4×2=0.8；

若當前判斷路段為擁堵，則新的道路優先等級指數表達為G′=0×2=0。

依次類推，可以對所有不同等級的道路，計算考慮交通狀態影響權重系數下的新的道路優先等級指數。

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

交通狀態的影響結果只考慮兩種情況：加入高層網絡和不加入高層網絡，因此將交通狀態等級模糊為二級：正常和擁擠。按照第2章討論的城市道路交通狀態判別方法，和本節討論的考慮交通狀態影響下的道路優先等級確定方法，可以建立如圖3所示的對應關系。

圖3 考慮交通狀態的道路動態分級

根據這種對應法則，可以獲得城市道路的動態道路優先等級，從而可以劃分實時的高層網絡。

4 道路網絡動態分層及規則

4.1 連線交通相似度的表達

在不考慮起止點位置時，首先是高層網絡的計算，也就是說，高層網絡是具有一定交通相似度的節點和連線的大集合。高層網絡完全是依據道路網絡的優先等級和交通狀態的綜合系數的相似程度積聚而成的。

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

4.2 道路網絡的動態分層規則

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

圖4 道路網絡的動態分層示意圖

根據O、D點位置的不同，即O、D點是否是在高層網絡，道路網絡的動態分層有兩種情況：

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

當O、D點在高等級道路上時，道路網絡的動態分層較為簡單，即按照上述動態分層優化過程，直接實現道路網絡的動態分層。這種情況大部分發生在途中動態路徑再規劃時，需要重新分層和分區。

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

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

表1 交通狀態參數計算表（delinkdtatus）

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

（1）對不同優化標準，層次可以按照道路優先等級和實時交通狀態等級進行劃分；

（2）層次細節由高到低逐漸增多，高層次是低層次的子集；

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

按照上述規則，檢查道路網絡動態分層的高層網絡的連通性，使其滿足上述規則要求。圖4中的虛線即是從低等級道路提取到高層網絡中的連線。

5 算例分析

本文選擇某市實際路網的部分區域為例，以ESRI公司A rcGIS9.0作為二次開發平臺，分析傳統Dijkstra算法和分層算法在誘導路徑計算時的優劣。

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

選擇某時刻道路網絡交通狀態計算結果，按照表1結構存儲在大型數據庫中，本文列出部分數據內容示例。

圖5 某市部分實際分層路網

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

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

圖6 按照傳統Dijkstra算法計算路徑結果

表7 按照道路動態分層算法計算路徑結果

6 結束語

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

[1]廖志斌.基于網格的城市動態路徑誘導系統研究[D].上海：華東師范大學，2007.

[2]劉名龍.城市交通動態路徑誘導算法研究及系統設計[D].昆明：昆明理工大學，2005.

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

[4]曾松.城市道路網絡交通導行策略研究[D].上海：同濟大學，2000.

[5]范東凱.城市動態路徑誘導算法研究[D].西安：長安大學，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]陳曉紅.交通網絡動態路徑誘導算法研究及其在GIS環境下的仿真實現[D].長沙：長沙理工大學，2005-04.

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

[9]童小華，陳建陽，吳淑琴.基于GIS和GPS的交通狀態參數估計仿真分析[J].同濟大學學報：自然科學版，2006，34（1）：47-52.[10]張和生，張毅，溫慧敏，等.利用GPS數據估計路段的平均行程時間[J].吉林大學學報：工學版，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].計算機學報，2000，22（2）：184-189.