李曉丹

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

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

1 引言

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

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

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

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

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

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

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

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

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

2.1 連線擁擠度模型

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

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

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

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

（2）連線擁擠度概念

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

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

其中：

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

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

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

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

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

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

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

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

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

3 考慮實(shí)時(shí)狀態(tài)的道路動(dòng)態(tài)分級(jí)

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

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

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

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

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

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

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

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

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

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

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

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

圖3 考慮交通狀態(tài)的道路動(dòng)態(tài)分級(jí)

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

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

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

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

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

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

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

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

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

（1）O、D點(diǎn)在高等級(jí)道路上

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

（2）O、D點(diǎn)不在高等級(jí)道路上

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

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

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

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

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

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

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

5 算例分析

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

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

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

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

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

表2 兩種算法部分性能對(duì)比分析

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

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

6 結(jié)束語(yǔ)

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

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

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

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

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

[5]范東凱.城市動(dòng)態(tài)路徑誘導(dǎo)算法研究[D].西安：長(zhǎng)安大學(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ò)動(dòng)態(tài)路徑誘導(dǎo)算法研究及其在GIS環(huán)境下的仿真實(shí)現(xiàn)[D].長(zhǎng)沙：長(zhǎng)沙理工大學(xué)，2005-04.

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

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