基于時空分析的路口相似度計算方法

楊海清,范 琦

(浙江工業大學 信息工程學院,杭州 310023)

0 概述

城市交通路口作為城市路網的重要節點和交通梳理的關鍵,對其時空數據的分析是交通治堵的重要思路。從交通路口的海量歷史時空數據中快速檢索出與當前路口狀態相似的數據,已成為短時交通流預測和配時方案自動化推薦發展的迫切需求[1-2]。但是傳統的交通時空數據分析大多將重點放在時空軌跡的相似度匹配上[3],對于交通路口場景的時空數據匹配研究較少。

以空間場景的相似度計算模型為基礎,文獻[4]提出基于特征矩陣和關聯圖的場景相似度度量方法,該方法能夠較準確地度量不同數目空間對象的場景相似度,但根據方向關系特征向量兩兩匹配的方式增加了算法復雜度,不適用于海量數據的匹配。文獻[5-6]雖然空間場景的匹配精度也非常高,但都沒有根據空間屬性對檢索的空間場景進行約束,難以在時間維度上擴展。以時空數據相似度計算模型為基礎,文獻[7]提出基于趨勢面與SSIM的時空數據相似度算法,文獻[8]提出ST-Link可擴展鏈接算法,該算法利用有效的空間和時間過濾機制,縮小匹配用戶的搜索范圍,文獻[9]提出一種可表示空間實體屬性的時空數據模型。但以上相似度度量方法均未考慮空間關系對時空數據相似度的影響,尤其是在交通路口場景中,路口附近的學校、醫院和火車站等地點在不同的時間段上會對交通路口的動態數據產生巨大影響[10-11]。

本文提出一種基于時空分析的交通路口相似度計算方法,通過交通路口數據屬性檢索出數據庫中相匹配的路口場景,根據交通路口與周圍幾何對象的空間關系判斷滿足約束條件的數據庫中路口場景,由目標路口在時間維度上的動態數據變化匹配數據庫中路口的相似時段,并根據時空相似度計算模型得出的相似度進行排序,以提高交通路口在時間空間上的匹配精度和合理性。

1 路口靜態數據相似度計算模型

本文在分析路口靜態數據的過程中,將交通路口作為空間場景,由道路與周圍對交通流影響較大的矢量面狀幾何對象構成。本文在目標路口P與數據庫路口P′的相似度計算過程中,首先從P′中篩選出與P相同路口叉數的路口。在描述路口特征時,本文所用的特征量集合均以最接近正北方向的路段為起始,逆時針方向排序。

1.1 路口屬性相似度計算模型

在進行空間分析的過程中,交通路口具有車道功能、檢測器類型、路口類型、車道類型和檢測器位置等屬性[12-13]。其中路段上對應的車道功能是分析路口車道流量和飽和度的重要依據,所以本文將路口車道功能屬性單獨提取出來,定義路口場景中車道功能集合為F={X1,X2,…,Xn},其中,n表示路口叉數,Xi(1≤i≤n)為第i條路段上所具有的車道功能類型集合,即當相鄰車道的車道功能相同時,會被記錄為一種車道功能類型。對于目標路口P,定義其車道功能集合為Fp={X1,X2,…,Xn},并提取數據庫路口P′的車道功能集合為F′p{X′1,X′2,…,X′n}。

(1)

1.2 路口空間關系相似度計算模型

在研究交通路口的空間關系相似度度量問題時,本文將交通路口場景中的道路簡化為線類型的矢量數據,交通路口周圍的空間對象,如車站、學校和醫院對交通流影響較大的地點作為面狀矢量數據。創建一個在交通路口場景下結合拓撲關系、方位關系和距離關系的相似度計算模型。

本文采用維度擴展的九交模型[15],確定目標路口場景和數據庫路口場景中面狀空間對象A與道路R的拓撲關系,并計算數據庫路口場景與目標路口場景中兩對相同拓撲關系的空間對象間的拓撲關系相似度。

根據路口叉數n將路口場景劃分,定義A的出口點集合EA={e1,e2,…,em}(m為A的總出口數),創建拓撲關系和方位關系統一的相似度計算模型,如圖1所示。

圖1 路口場景拓撲關系與方位關系統一描述模型

當R與A為相鄰或相交關系時,道路與面狀空間對象的交集維數DDIM(R∩A)≤1,并且(R∩A)?R。由于在路口場景中,進口道交通流量的影響遠大于出口道交通流量的影響,因此當A與多條路段相交或相鄰時,選取A在R逆時針方向區域的部分為研究對象。目標路口P的拓撲關系特征值TP為:

(2)

(3)

EExist(dRn∩A)]

(4)

(5)

(6)

提取目標路口場景中面狀空間對象A的所有出口點集合EA,將EA構成的最大面積多邊形作為A的特征多邊形。將該特征多邊形的重心與路口中心O點的歐式距離作為路口場景的距離關系特征值DDis,則P與P′的距離關系相似度SDis為:

(7)

P與P′中兩對空間對象間的空間關系相似度為:

(8)

當空間對象R與A為相離關系時,A對相鄰路段的交通流量的影響更為直接[16],因此,對于P和P′中兩對空間對象間的空間關系相似度不做計算。

2 路口動態數據模型

交通路口的動態數據主要來源于車道檢測器,包括進口道的流量和飽和度等隨時間動態變化的數據。本文以車道流量f為例,將數據庫路口P′的車道流量按協調方案的周期時長在時間維度上進行切分。根據目標路口P的車道檢測器所提供的車道的實時流量,計算相同周期時長內P與P′的流量相似度Sf。

對于交通路口動態數據模型的相似度計算,只有兩個路口在對應路段上的車道功能類型相同時才有匹配的意義[17-18]。所以,當路口的空間屬性數據相似度Sv=0時,取流量相似度Sf=0。根據目標路口P的信號周期時長CP和輸入起始時間t0,由路口屬性數據相似度模型中的數據集合排序方式確定P的進口道特征流量集合Qp={Qp1,Qp2,…,Qpn},n為目標路口P中含有進口道的路段總數,其中,Qpi(1≤i≤n)表示該路段進口道上同種車道功能的實時特征流量集合{f1,f2,…,fξ},ξ為路段上車道功能種類總數。以新匯路長華街路口為例,路口渠化示意圖如圖2所示,流量數據如表1所示,信號周期時長為60 s。

圖2 新匯路長華街路口渠化示意圖

表1 新匯路長華街路口某段信號周期時長內流量數據

定義每種車道功能在CP上的特征流量為:

(9)

其中,v為具有該車道功能的車道數目。因為目標路口P與數據庫路口P′在同一路段上的車道功能類型相同,所以P′在對應路段進口道特征流量集合Q′pi與Qpi的個數同為ξ。計算信號周期內P與P′在相應路段上的流量相似度Sfi:

(10)

其中,f′j為數據庫路口P′在第i條進口道上第j種車道功能的特征流量。當Sfi≤0時,取Sfi=0,即0≤Sfi≤1。將n條進口道的流量相似度Sfi累加取平均值,即得目標路口與數據庫路口的起始時段相似度Sq0。當目標路口P的流量數據由車道檢測器持續輸入時,分別計算在接下來的每段信號周期時長內P與P′的流量相似度。取所有信號周期內流量相似度的均值,合成整個時段內的動態數據相似度。

3 時空數據相似度計算模型

本文通過目標路口的空間信息,提取路口屬性數據與周圍地理信息,分別建立目標路口P與數據庫路口P′的空間屬性相似度計算模型和空間關系相似度計算模型,在滿足P與P′的空間屬性相似度大于0的條件下,提取目標路口信號周期時長一定的動態數據,建立P與P′的動態數據相似度計算模型。根據P與P′的空間屬性相似度、空間關系相似度和動態數據相似度,對時間維度上的數據庫路口進行排序。目標路口場景P如圖3所示,數據庫路口場景P′如圖4所示。

圖3 目標路口場景

圖4 數據庫路口場景

在圖3、圖4中,e為空間面狀對象的出口,與路段相鄰且距離路口中心點O最近的出口點作為起點,逆時針方向排序。提取目標路口的車道功能集合及其他屬性數據,利用式(1)計算P與P′的空間屬性相似度。根據目標路口場景P的空間數據定義空間場景特征描述集合Pdes={R1,R2,…,Rn},其中,Ri(1≤i≤n)為第i條路段上的空間關系描述特征集合,Ri集合中的元素為空間面狀矢量對象A,以A的e1點與路口中心O點距離大小排序(距離越小,順序越靠前),A在路段順時針方向取負,逆時針方向取正。利用式(2)～式(8)分別計算P與P′在對應路段上的空間關系相似度。

計算P與P′的動態數據相似度的具體步驟如下:

輸入目標路口P起始時間t0和結束時間tω、該時間段Δt內的信號周期時長CP以及Δt內每條車道的流量數據{q1,q2,…,qα}

步驟1利用式(9)確定Δt內P在每個信號周期時長中進口道上同種車道功能的特征流量集合Qp。

步驟2取出目標路口P在t0至t0+CP時段內的特征流量集合,并利用式(10)計算數據庫路口P′的所有CP時段與該時段的相似度。

步驟3隨著持續輸入結束時間的推移,合成整個時間段內兩路口的流量數據相似度并輸出數據庫路口對應的時段。

4 實驗結果與分析

本文實驗包含兩部分內容,一是根據杭州市區內2 781個路口的空間數據,驗證路口靜態數據相似度計算方法,二是根據杭州市區內50個路口一周內的所有車道檢測器數據(車道流量),驗證路口動態數據相似度計算方法。

4.1 路口空間數據相似度計算模型實驗

本文實驗將杭州路口矢量數據導入數據庫中,并根據路口的車道信息、路段空間信息及路口屬性等數據構建表關聯。將杭州市區內的所有學校空間數據(包括學校出入口)作為路口場景中的空間矢量面狀對象實驗數據,如圖5所示。

圖5 杭州市區內實驗路口、學校及路段的空間數據

本文實驗選取杭州市文一西路益樂路口作為目標路口,提取其車道功能屬性集合,檢索出數據庫中有68個杭州路口符合車道功能約束。分別使用場景相似性檢索方法[19]和空間數據檢索方法[20]對68個路口場景進行檢索,得到查全率和查準率如表2所示。場景相似性檢索方法和空間數據檢索方法均使用了方位關系與拓撲關系約束,且場景相似性檢索方法中還使用了空間對象的形狀約束,而本文對于路口場景中的空間對象使用了空間對象的出入口作為特征描述量,因此查全率相對較高,同時本文針對交通路口的空間特點,利用交通路口場景中的道路作為場景描述坐標,因此提高了查準率。

表2 檢索方法的查準率和查全率對比

根據目標路口的空間數據,在數據庫路口場景中進行匹配,得到實驗結果如表3所示。從實驗結果中可以看出,本文中的算法對于未能與目標路口場景完全匹配的數據庫路口場景,仍能根據局部匹配程度得出空間關系相似度,因為路口場景受到車道功能類型約束,所以導致檢索出的路口場景相似度較低。

表3 空間場景相似路口檢索結果

4.2 路口動態數據相似度計算模型實驗

本文實驗從杭州2 000多個路口中選取車道檢測器較靈敏,且路口進口車道覆蓋較全面的50個路口在一周內的動態流量數據作為實驗數據。選取崇義路文二西路路口北向路段周二上午9時30分—10時的路口進口車道實時流量作為實驗數據,如圖6所示。

圖6 崇義路文二西路路口北向路段流量數據

由車道檢測器數據可知,目標路口實時信號周期時長為140 s,提取目標路口所有路段起始信號周期內的特征流量集合為{[11,10,0],[0,14],[11,19]}。從數據庫路口中提取出與目標路口靜態數據相似度最高的路口,并計算其信號周期時長同為140 s的時間段內路口流量數據與目標路口起始信號周期內流量數據的相似度,當相似度滿足指定閾值(本文實驗取0.5)后,分別計算在下個信號周期內的流量數據相似度。由路口靜態數據模型計算得出之江路姚江路路口的靜態相似度最高。若數據庫路口中存在該目標路口,則本文將分別選擇該路口和與該路口靜態數據相似度最高的路口,進行動態數據相似度計算,實驗結果如圖7、圖8所示。

圖7 相同路口動態數據實驗結果

圖8 不同路口動態數據實驗結果

從實驗結果可以看出,本文將交通路口的靜態數據作為動態數據匹配的約束條件,能夠有效地提高算法效率。相較于時空索引檢索算法[21],本文方法能夠更有效地匹配相似的時段,具有較強的實用性。

5 結束語

本文提出一種基于時空分析的交通路口相似度計算方法,從空間場景相似度和動態數據相似度等角度綜合分析了交通路口時空數據間的差異,在計算交通路口相似度的過程中,構建適用于交通路口的靜態數據模型,提高交通路口相似度分析的合理性及魯棒性,在構建時空數據模型時,研究動態數據在時間維度上的變化趨勢,以使算法適用于智能交通領域中單點路口配時方案。實驗結果表明,相較于時空索引檢索算法,該算法能夠有效提高交通路口檢索的查全率以及在時間空間上的匹配精度。