基于路徑搜索的交通擁堵判別研究

陳 智，孫德輝

(北方工業(yè)大學(xué)城市道路交通智能控制技術(shù)北京市重點實驗室，北京 100144)

0 引言

城市中越來越明顯的交通擁堵現(xiàn)象制約著當(dāng)今社會的發(fā)展伴隨著科技的進(jìn)步，GPS設(shè)備大范圍的應(yīng)用在私家車上，尤其是出租車. 結(jié)合浮動車GPS數(shù)據(jù)處理、挖掘、分析車輛運行的時空關(guān)聯(lián)關(guān)系，能有效并快速研判道路交通擁塞狀態(tài)，從而對交通擁堵起緩解作用.

Mennis J等[1]根據(jù)空間網(wǎng)格相關(guān)性規(guī)則，將空間矢量區(qū)分為具有同樣面積的網(wǎng)格，并詳細(xì)研究了網(wǎng)格之間的時間-空間相關(guān)性. 該方法可以有效的解決時空約束問題，但因為沒有明確的提出對網(wǎng)格規(guī)則劃分的標(biāo)準(zhǔn)，致使仍有不足之處. Florian Verhein等[2]基于車輛時間-空間位置，對空間謂詞進(jìn)行描述，將擁堵高峰區(qū)域進(jìn)行簡化，同時探索車輛在時間-空間中的移動相關(guān)性，進(jìn)而找到了其移動的規(guī)律.

岳慧穎[3]通過空間約束深度挖掘時空序列中的空間關(guān)聯(lián)項，添加時間約束條件，并獲取時間—空間的關(guān)聯(lián)項，基于此獲得對象之間的時間和空間的關(guān)聯(lián)規(guī)則. 在數(shù)據(jù)提取時分別挖掘時間和空間數(shù)據(jù). 這有利于對時空相關(guān)性規(guī)律的挖掘，而且不對結(jié)果產(chǎn)生影響，然而在一定程度上加大了算法的計算過程，擴大了數(shù)據(jù)的存儲量.

丁鐵成[4]提出“road to vector”方法，以時間軸、投影、地圖等多個視圖為基礎(chǔ)，搭建了道路相關(guān)性的可視化分析系統(tǒng)平臺，可以使用戶在多尺度、多角度下對軌跡數(shù)據(jù)進(jìn)行分析，從中提取道路之間的相關(guān)性.

張婧[5]描述了道路交通流在區(qū)域路網(wǎng)擁堵中存在的時間-空間分布特性，設(shè)計了時空相關(guān)性指標(biāo)和計算方法，提出了基于交通流時空關(guān)聯(lián)性的擁堵區(qū)域研判方法，有效應(yīng)用于鄰近道路的實時擁堵預(yù)警.

李光強等[6]在現(xiàn)有研究中，將事件影響域作為條件，劃分時間—空間域，同時引入了一個關(guān)系謂詞來構(gòu)建時空域和事件之間的關(guān)系，利用一種新方法在路段上進(jìn)行數(shù)據(jù)挖掘，從而提高挖掘的效率.

喬春凱等[7]提出了一種時序關(guān)聯(lián)規(guī)則挖掘方法，基于智能算法劃分序列流時間和空間的關(guān)聯(lián)特征，實時預(yù)測道路網(wǎng)絡(luò)的擁堵狀態(tài)，達(dá)到在復(fù)雜交通環(huán)境下?lián)矶骂A(yù)測的準(zhǔn)確度提高的目的.

劉端陽等[8]提出Ncut的交通子區(qū)劃分方法，基于交通流量和路段速度信息計算交通態(tài)勢，結(jié)合交叉口間距離獲得動靜態(tài)結(jié)合的關(guān)聯(lián)度指標(biāo)，應(yīng)用Ncut劃分算法對道路網(wǎng)絡(luò)進(jìn)行分類，調(diào)整子區(qū)邊界上的交叉口使得子區(qū)總關(guān)聯(lián)度達(dá)到最大，同時使子區(qū)內(nèi)部的交叉口交通態(tài)勢更為相似.

丁恒等[9]通過比例積分控制外部道路網(wǎng)絡(luò)的交通累積量，將實際交通的流出率與宏觀基本圖曲線相關(guān)聯(lián)的期望流出率的差值作為特征變量，建立可拓集合，路網(wǎng)入口邊界PI反饋控制量通過內(nèi)部可拓提升控制器進(jìn)行調(diào)節(jié)，控制了駛?cè)肼肪W(wǎng)的交通流以避免交通擁堵.

通過分析上述的國內(nèi)外研究可知，多數(shù)研究聚焦于分割了時間和空間兩者的關(guān)聯(lián)性分析，缺乏構(gòu)建基于時空維度的關(guān)聯(lián)模型研究，造成了一定的局限性. 而在區(qū)域交通擁堵狀態(tài)的研判方面中，時空關(guān)聯(lián)性方法應(yīng)用鮮有涉及. 因此，本文以出租車GPS數(shù)據(jù)為基礎(chǔ)，引進(jìn)差異聚合系數(shù)，該系數(shù)由Pearson和Kendall相關(guān)系數(shù)組成，并搜索區(qū)域道路網(wǎng)絡(luò)中的高相關(guān)路徑. 結(jié)合莫蘭象限構(gòu)建了基于時空關(guān)聯(lián)分析的道路網(wǎng)絡(luò)擁堵區(qū)域研判方法，進(jìn)一步利用海南市出租車GPS數(shù)據(jù)進(jìn)行案例分析.

1 基于差異聚合系數(shù)的高相關(guān)路徑搜索

實測的GPS交通數(shù)據(jù)是指通過不間斷的觀察城市路網(wǎng)中互相關(guān)聯(lián)的道路段形成的時間序列，即交通流時間-空間數(shù)據(jù). 這些交通流數(shù)據(jù)來源于出租車實時采集，可以真實、準(zhǔn)確地反映城市交通的運行特點.

相關(guān)性分析定義為分析2個或多個有序向量之間的多維特征變化相關(guān)性，Pearson相關(guān)系數(shù)描述的是2個向量的協(xié)方差和標(biāo)準(zhǔn)差的乘積之比，分類變量間的相關(guān)性程度用Kendall相關(guān)系數(shù)來描述，以τ表示值. 本文基于現(xiàn)有的2種相關(guān)度分析方法，構(gòu)造新指標(biāo).

時間-空間相關(guān)性分析可以應(yīng)用于一條道路隨時間-空間變化的交通流相關(guān)性，也可以應(yīng)用于路網(wǎng)隨時間-空間變化的交通流相關(guān)性. 以往的研究只要集中于用道路聚類對交通區(qū)域進(jìn)行劃定，但是，傳統(tǒng)的道路聚類在劃分道路時沒有統(tǒng)一的標(biāo)準(zhǔn)，在交通擁堵區(qū)域判別應(yīng)用時取得效果小. 本文基于高相關(guān)路徑動態(tài)劃分道路網(wǎng)絡(luò)的擁堵區(qū)域，由于道路交通存在隨機性，它們之間的相關(guān)性也會隨之變化，因此只用歷史數(shù)據(jù)對路徑進(jìn)行劃分，存在時效性和片面性.

當(dāng)?shù)缆钒l(fā)生擁堵時，空間-時間也會隨之發(fā)生變化，但依然存在相關(guān)性. 在城市路網(wǎng)中迭代計算2條以上路網(wǎng)的相關(guān)性，研究路網(wǎng)間的交通流狀態(tài)時間-空間特性變化過程.

將高相關(guān)路徑的搜索與判定過程進(jìn)行約簡化，并根據(jù)融合相關(guān)系數(shù)(即Kendall和Pearson相關(guān)系數(shù))之間的關(guān)聯(lián)性，創(chuàng)建一種新的指標(biāo). 將路段鏈集合F中上下游每兩條路段間關(guān)聯(lián)度異質(zhì)與全局道路網(wǎng)絡(luò)關(guān)聯(lián)度異質(zhì)之間的比率定義為相關(guān)性差異聚合系數(shù)，如果路段鏈集合F中的道路相關(guān)度差異性越小，則表現(xiàn)為差異聚合系數(shù)越低，若為高相關(guān)路徑，則表現(xiàn)為內(nèi)部關(guān)聯(lián)性越高. 差異聚合系數(shù)見式(1)～(3)：

(1)

(2)

(3)

利用定義的相關(guān)性聚合度，通過圖1的步驟對高相關(guān)性路徑進(jìn)行搜索.

圖1 高相關(guān)路徑搜索方法流程

2 莫蘭象限

韋偉基于空間自相關(guān)理論，在傳統(tǒng)莫蘭時空指數(shù)中添加了時間維度這一指標(biāo)，構(gòu)建出新Moran’s I方法[10]，可以對路網(wǎng)的交通時空狀態(tài)進(jìn)行分析. 本文以海南?？谑械幕疖嚤闭局車?05條路段為例，研究GPS數(shù)據(jù)，分析路網(wǎng)交堵狀態(tài)的時間-空間變化特性. 采用前文提出的高相關(guān)路徑搜索算法，提取高相關(guān)路徑，對短時路網(wǎng)交通擁堵狀態(tài)進(jìn)行判別.

為了能直觀體現(xiàn)時空各元素之間的異向特性和聚合特性，引入空莫蘭散點圖，散點圖橫軸歸一化屬性值X(p, i)，該值源于時空元素ST(p, i )；縱軸為經(jīng)過歸一化后的時空屬性加權(quán)值YX(p, i)(記為時空滯后值，正值表示時間元素聚合，負(fù)值則為異向)，該值臨近時空范圍內(nèi)連接時空元素.

在散點圖中尋找時空元素所處的象限，得出時空元素對應(yīng)的時空特性：

第Ⅰ象限：X(p,i)>0,YX(p,i)>0，該象限點的時間和空間特征表征為高值聚合狀態(tài)(HH)，即時空元素及其相鄰區(qū)域范圍內(nèi)的元素本身屬性值都比較高.

第Ⅱ象限：X(p,i)<0,YX(p,i)>0，該象限點的時間和空間特征表征為低值異向狀態(tài)(LH)，即低值的時空元素被包含于其相鄰區(qū)域范圍內(nèi)屬性值較高的元素.

第Ⅲ象限：X(p,i)<0,YX(p,i)<0，該象限點的時間和空間特征表征為高值擴散(LL)，即時空元素及其相鄰區(qū)域范圍內(nèi)的元素本身屬性值都比較低.

第Ⅳ象限：X(p,i)>0,YX(p,i)<0，該象限點的時間和空間特征表征為高值異向狀態(tài)(HL)，即高值的時空元素被包含于其相鄰區(qū)域范圍內(nèi)屬性值較低的元素.

綜上分析，第Ⅰ和Ⅲ象限的時空元素全都擁有聚合性的特征，而第Ⅱ和Ⅳ象限的時空元素均擁有異質(zhì)性的特點. 也就是當(dāng)時間和空間融合的元素表現(xiàn)為共同特征時，體現(xiàn)出聚合性；而當(dāng)其表現(xiàn)為不同的特性時，則體現(xiàn)出異質(zhì)性.

3 路網(wǎng)擁堵控制區(qū)域判別

根據(jù)以上所述道路時空狀態(tài)劃分，在城市路網(wǎng)中，可將道路按照所處莫蘭象限進(jìn)行4類狀態(tài)的劃分：處于莫蘭第Ⅰ象限即HH的暢通聚合路段，為路網(wǎng)擁堵中的保障路段，保障路段往往道路狀況良好，具有較高的道路通行能力，一般不易發(fā)生擁堵，或短暫擁堵后迅速消散，可容納數(shù)量較大的上游擁堵車輛駛?cè)?，并保障交通流行駛水平；處于莫蘭第Ⅱ象限即LH的暢通異向路段，為路網(wǎng)擁堵中的預(yù)警路段，先于周邊路段出現(xiàn)擁堵，滯后于周邊路段暢通；處于莫蘭第Ⅲ象限即LL的擁堵聚集路段，為路網(wǎng)中的擁堵產(chǎn)生路段，往往為擁堵產(chǎn)生點以及擴散點，擁堵從該類路段產(chǎn)生并向周邊擴散；處于莫蘭第Ⅳ象限即HL的擁堵異向路段，為路網(wǎng)中的擁堵疏導(dǎo)路段，往往為擁堵消散點，滯后于周邊路段擁堵，先于周邊路段暢通，往往作為車輛由擁堵聚合路段駛?cè)霑惩ň酆下范蔚耐ǖ?

基于以上對于道路交通流擁堵相關(guān)性分析，可通過時空莫蘭散點圖選取擁堵聚合路段(LL)作為起點，根據(jù)前文所述方法快速并準(zhǔn)確搜索出高相關(guān)性路徑.

通過高相關(guān)路徑中相關(guān)路段所處莫蘭象限所代表的交通流擁堵時空特性，進(jìn)行擁堵區(qū)域交叉口補充，從而對路網(wǎng)擁堵控制區(qū)域進(jìn)行判別.

擁堵區(qū)域判別步驟如下：

步驟1選取路網(wǎng)中處于莫蘭第Ⅰ象限LL狀態(tài)的路段為起始路段l1，其上、下游交叉口分別設(shè)為c1,c2；

步驟2以l1為起點，進(jìn)行基于差異聚合系數(shù)的高相關(guān)路徑搜索，搜索得到以l1為起點的高相關(guān)性路徑l2,l3…ln，其中l(wèi)2的上游交叉口即為c2，下游交叉口為c3，同理，剩余的相關(guān)路徑下游交叉口將設(shè)置成c4…cn+1；

圖2 路段處于莫蘭第Ⅰ象限時擁堵區(qū)域交叉口的篩選

步驟3根據(jù)相關(guān)路徑中各路段所處莫蘭象限，按路徑順序進(jìn)行交叉口篩選補充與剔除. 共計4種路段情況：①若路段處于莫蘭第Ⅰ象限，即HH暢通聚合狀態(tài)，則將該路段上下游交叉口從擁堵控制區(qū)域中去除，并將高相關(guān)性路徑由此進(jìn)行分割，如圖2所示，實線框中為擁堵控制區(qū)域交叉口；②如路段處于莫蘭第Ⅱ象限，即LH暢通異向狀態(tài)，則保留該路段上下游交叉口，如圖3所示實線框中為擁堵控制區(qū)域交叉口；③如路段處于莫蘭第Ⅲ象象限，即LL擁堵聚合狀態(tài)，則保留該路段上下游交叉口，且將該路段所有相連交叉口劃分為擁堵控制區(qū)域，如圖4所示實線框中為擁堵控制區(qū)域交叉口；④如路段處于莫蘭第Ⅳ象限，即HL擁堵異向狀態(tài)，則僅保留該路段上游交叉口，將下游交叉口從擁堵控制區(qū)域中去除，并將高相關(guān)性路徑由此進(jìn)行分割，如圖5所示實線框中為擁堵控制區(qū)域交叉口；

圖3 路段處于莫蘭第Ⅱ象限時擁堵區(qū)域交叉口的篩選

圖4 路段處于莫蘭第Ⅲ象限時擁堵區(qū)域交叉口的篩選

圖5 路段處于莫蘭第Ⅳ象限時擁堵區(qū)域交叉口的篩選

步驟4若出現(xiàn)由于LL或LH路段保留交叉口與HH或HL路段剔除交叉口發(fā)生沖突時，對交叉口進(jìn)行保留；

步驟5依次篩選高相關(guān)路徑中所有交叉口至交叉口cn+1結(jié)束，根據(jù)篩選結(jié)果即為擁堵控制區(qū)域A，包含所有保留交叉口. 實際判別流程見圖6.

圖6 路網(wǎng)擁堵控制區(qū)域判別流程

4 實例驗證

以自2016-11-01—12-31期間的海南?？谑姓苓吂灿?05條路段3 000多輛出租車產(chǎn)生的GPS數(shù)據(jù)為研究對象，提取道路拓?fù)浣Y(jié)構(gòu)：

圖7 實際道路網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)圖

以2016-11-03，13：00-14：00數(shù)據(jù)為基礎(chǔ)，通過計算路網(wǎng)中路段局部時空莫蘭指數(shù)，選取莫蘭象限為第Ⅲ象限的?？谑姓苓呴L濱東四街西向東方向作為起始路段進(jìn)行高相關(guān)性路徑搜索. 獲得高相關(guān)性路徑l1-l7.

圖8 高相關(guān)路徑搜索示例

計算城市路徑中所有路段在莫蘭象限的所屬位置.

圖9 城市路段所處莫蘭象限計算示例

根據(jù)前文所述擁堵區(qū)域判別步驟進(jìn)行交叉口篩選，確定擁堵控制區(qū)域. 圖10中方框所表示交叉口為擁堵控制交叉口，其中由于c6交叉口下游南側(cè)交叉口為高架橋，故不納入擁堵控制區(qū)域. 藍(lán)色圓框即為剔除交叉口. 虛線部分即為擁堵控制區(qū)域.

圖10 擁堵控制區(qū)域判別示例

5 結(jié)論

以出租車的GPS數(shù)據(jù)為研究對象，在已有的通過Pearson系數(shù)進(jìn)行的交通擁堵時空特性研究基礎(chǔ)上，通過引入Kendall相關(guān)系數(shù)彌補Pearson系數(shù)針對道路網(wǎng)絡(luò)擁堵狀態(tài)研判的不足. 引進(jìn)差異聚合系數(shù)，該系數(shù)由Pearson和Kendall相關(guān)系數(shù)組成，并搜索區(qū)域道路網(wǎng)絡(luò)中的高相關(guān)路徑. 將時間維度約束條件添加到莫蘭指數(shù)，構(gòu)建出時空的莫蘭象限，分析了城市路網(wǎng)中交通流的時間-空間聚合消散相關(guān)性. 提出了基于高相關(guān)度路徑搜索的擁堵區(qū)域研判方法. 計算路網(wǎng)中所有路段局部時空莫蘭指數(shù)，選擇處于莫蘭第Ⅰ象限的路段的上游交叉口為起點進(jìn)行高相關(guān)路徑搜索，依次判斷路段所處的莫蘭象限，輸出擁堵區(qū)域. 最后，采用?？谑虚L濱4路實例數(shù)據(jù)進(jìn)行實例驗證，證明了該方法判別的效果，且具備大數(shù)據(jù)應(yīng)用的前景.