一種改進的快速浮動車地圖匹配方法

張健欽，李明軒，段穎超，杜明義

(1. 北京建筑大學測繪與城市空間信息學院，北京 100044； 2. 現代城市測繪國家測繪地理 信息局重點實驗室，北京 100044)

一種改進的快速浮動車地圖匹配方法

張健欽1,2，李明軒1,2，段穎超1,2，杜明義1,2

(1. 北京建筑大學測繪與城市空間信息學院，北京 100044； 2. 現代城市測繪國家測繪地理 信息局重點實驗室，北京 100044)

浮動車地圖匹配算法能夠實現浮動車離散點與路段的快速準確匹配,是浮動車路況信息生成技術中的核心環節。本文針對現有方法的不足，實現了建立定位點的有效閾值緩沖區，并依據空間關系檢索候選匹配路段，研究實現了一種利用行駛速度、行駛方向、投影距離、行駛距離4個參數進行行車軌跡判別的邏輯匹配算法。試驗表明，該方法無需對路網數據進行大量的前期處理工作,簡化了候選匹配路段的檢索過程，在保證匹配正確率的同時也表現出了更高的效率。

路網匹配；浮動車數據；路況信息；路段

路況信息是反映城市道路交通通行狀況的綜合信息，其主要表現為城市交通道路的擁堵或暢通情況。隨著高新信息技術在交通中的廣泛應用，交通信息采集、處理和發布技術日趨成熟和多樣化，而浮動車系統是近些年發展起來的交通路況信息采集技術。一般使用具備一定樣本量的出租車或公交車作為浮動車，通過已安裝的GPS車載裝置和無線通信設備，將車輛信息(如時間、速度、坐標、方向等參數)實時地傳送到浮動車信息中心，經過與路網數據匹配處理后形成實時動態路況信息，為交通管理部門提供調度依據,為公眾提供出行參考,還可作為道路建設規劃、擁堵緩解等各項工作中定量數據分析的基礎[1]。

浮動車數據反映在地圖上是一個個具有空間坐標的離散點要素，但受到定位系統、數據傳輸、地圖矢量化，以及不同空間坐標參考系的選取和轉換過程中多種因素的共同作用，使其絕大多數游離于路網線要素之外，無法與道路直接匹配形成路況信息。因此，將浮動車定位點真實地歸屬到城市路網中的某路段，并確定其在路網線上匹配點的處理過程，是路網匹配算法及路況信息生成的核心。傳統的導航地圖匹配算法不適用于浮動車數據，原因包括:①浮動車數據量較大，且對系統的實時處理計算速度要求較高；②數據采樣間隔較大，導致定位點之間的空間相關性較差；③城市路網密集且結構復雜，對數據的匹配容錯率要求較高。因此，近年來國內外學者對此展開了大量研究，并主要引入邏輯條件和數學模型參與算法判別，成果顯著，對于大規模浮動車數據的匹配效率也有較大提升[2-12]。但仍存在優化和改進空間，一方面算法匹配精確度高但前期需對路網數據進行大量處理工作；另一方面許多算法將GPS定位點視為獨立對象進行匹配，較少考慮路況信息更新周期內同名定位點的邏輯關系，往往導致效率提高而準確率降低。針對這兩方面的不足，本文提出并實現閾值緩沖區確定候選匹配路段，利用4個參數進行行車軌跡判別的邏輯匹配算法，在考慮匹配正確率的同時也表現出較高的效率，而且無需對路網數據進行大量前期處理工作，擁有更好的算法實用性。

1 候選匹配路段

候選匹配路段是指位于浮動車定位點周圍的可能與之匹配的路段集合。從全路網線要素中快速檢索出每個定位點的候選匹配路段是一個高效路網匹配算法的前提。文獻[2]的算法在總結了以往算法的基礎上開展了以下研究：基于網格的候選路段確定，基于距離、航向、可達性權重的定位點匹配，以及基于最短路徑的行駛軌跡選擇的算法研究，算法能夠滿足浮動車地圖匹配準確性與實時性的要求。雖然基于網格劃分法的定位點周邊路段查找具有索引方法靈活、提取目標要素快速等特點，但在實際應用中也存在著一些不足。

1.1 基于網格法的不足

1.1.1 大量零碎路段

由于地圖格網的網格大小相同，而城市路網疏密程度不同，因而不易控制由格網斷開后的路段長度，在實現過程中往往會出現大量被截斷且長度較小的零碎路段，給匹配處理額外增加了一定程度的性能負擔。如對北京市區全路網進行200 m×200 m的網格劃分，路段總長小于10 m的占到了一定比例，其中部分路段信息及其局部放大圖如圖1所示。

圖1 過多的零碎路段

1.1.2 格網確定過程較為復雜

基于網格劃分的檢索方法通常是利用GPS定位點距離網格4條邊的距離，并對比GPS定位點精度的閾值范圍來判斷是否獲取當前網格或周邊鄰域網格中的路段。但由于鄰域網格數量隨定位點位置有3、5、8個，隨方向有上、下、左、右、左上、左下、右上、右下多種情況(如圖2(a)所示，黑色為定位點網格，陰影為鄰域網格)，因而一方面查找過程較為復雜，另一方面容易將本身不符合條件的路段也作為候選對象(如圖2(b)所示路段1、2、3、4)，需要進一步判斷才能排除。

圖2 網格查找法的幾點問題

1.2 閾值緩沖區法

針對上述不足，本文提出閾值緩沖區法檢索候選匹配路段，利用功能性節點層劃分路網形成路段單元，在定義索引編碼的前提下，對每個浮動車定位點動態生成其最大閾值緩沖區，進而利用空間面線關系來判別和獲取候選匹配路段集合。該方法能一次性確定各個點的候選匹配路段，即只要是該集合中的元素，都是需要進行后續判別的候選路段對象。具體如圖3所示，P1、P2、P3、P4分別是定位點生成的緩沖區，其半徑設定為浮動車數據的最大有效閾值(允許半徑不同)；seg1、seg2、…、seg11分別為各功能性節點形成的路段單元。綜合考慮二者的空間面線關系，得到關于P1的相交路段seg2、P2的相切路段seg5、P3的相交路段seg7和seg9。其中，P1、P2、P3與路段相切或相交，對應定位點與路段距離小于或等于最大有效閾值，屬于有效漂移點；P4與路段seg3和seg11相離，屬于漂移嚴重的無效點。seg2是對應P1、seg5是對應P2、seg7和seg9是對應P3定位點的候選匹配路段。

圖3 閾值緩沖區法查找候選匹配路段

2 行車軌跡判別

對于浮動車數據，其在城市路網中的整體表現是一個時間段上的點集。在理想情況下不同車輛在一段時間內擁有相同的點數，但實際上每輛車的一個時間序列很可能會因漂移嚴重或建筑物遮擋造成部分定位點丟失。因此，可以綜合考慮各車輛自身屬性及同名車輛在時間序列中的邏輯規則，進行行車軌跡的推測和判別，并最終確定匹配路段和匹配點。具體判別過程主要包含以下4個參數：

2.1 行駛速度

圖4 行駛速度參數判別分析

2.2 行駛方向

行駛方向判別方法是根據GPS記錄中車輛行駛方向與路段方向的相似度進行判別的方法。一方面浮動車數據中記錄有車輛某時刻的方位角，另一方面候選匹配路段由于已經過了各類功能性節點的打斷處理，各路段單元近似為一條直線，因而該路段方向完全可以由其矢量起終點的連線方向表示。研究發現，雖然行駛方向是一個瞬時概念，在實際行車過程中會隨著當時的駕駛情況(直行、左轉、右轉等)發生較大的偏差，其取值不總是與道路或路段方向保持一致。但是，在正常行駛狀態(即不發生逆行、倒車等突發狀況)的前提下，車輛行駛方向與所屬路段方向的夾角總能保持在一定的變化區間內，即夾角差的絕對值不超過90°。圖5分別是在直線道路和曲線道路條件下根據行駛方向來取舍候選匹配路段的處理方法。如圖5(a)所示，已知nodei和nodej是某道路的兩個相鄰節點，浮動車P行駛在它們生成的路段segi,j內，其正常行駛狀態下的眾多方向dir1、dir2、dir3始終與道路方向Dirroad保持著一定范圍內的一致性；如圖5(b)所示，浮動車定位點P位于曲線道路road的路段segi,j中，匹配點P′的方向記為dirp′，根據幾何關系容易得出dirp′即是過匹配點P′并與路段segi,j相切的切線方向，而此時由于road方向不能代表某個區間的走向，因此通過連接匹配點所在路段始末節點nodei和nodej形成的有向線段，并以它的方向作為道路方向參與方向夾角判斷。

2.3 投影距離

圖5 行駛方向參數判別分析

圖6 投影距離參數判別分析

2.4 行車距離

2.5 匹配流程

基于上述方法設計完整的路徑匹配算法，其主要步驟和具體流程如圖8所示。

2.6 路況生成

路段上車輛的平均速度是表征路況的主要信息，因此在進行浮動車數據的路網匹配之后，還需要按順序計算各路段上同名車輛匹配點的平均速度，以及整條路段上所有車輛的平均速度，從而最終完成由“車的信息”向“路況信息”的轉換過程。此外，還可以根據路段與各道路路鏈、興趣線路或區間的從屬關系，對相應道路平均行車速度值進行符號化和地圖渲染，生成能夠直觀表達出道路擁堵狀態的路況專題圖，以及計算區域的交通擁堵指數等。

圖7 行駛距離參數判別分析

3 實例研究

目前參與北京市浮動車系統的車輛約35 000輛，每輛車如果每分鐘上傳一個GPS數據，那么數據處理中心每天接收到的數據量就有5000余萬條，為了研究算法的實用性，選取北京市市區道路網和2008年某日1000輛出租車GPS數據(采集頻率30 s一次)作為試驗對象，將本文算法運行于2.53 GHz、2 GB內存的計算機上進行驗證，結果見表1，分別是以5 min為路況更新周期下的連續1個、2個和5個周期的10次匹配結果均值。

表1 不同數量下匹配算法耗時結果

結果表明，算法的平均正確匹配率為97.4%，單點的平均匹配時間為0.882 ms。相對于現有實時運轉的浮動車地圖匹配算法，正確匹配率平均在95%左右，單點匹配時間在幾毫秒至幾十毫秒之間。本文算法在保證較高準確率的基礎上，極大地提高了匹配效率，能夠滿足目前北京市浮動車系統地圖匹配的準確性要求及每分鐘35 000點的計算速度要求，同時對比文獻[2]的方法，本文的方法解決了網格法的不足，同時匹配正確率和匹配效率也有提高。

圖8 路網匹配算法流程

4 結束語

本文提出并實現了一種基于閾值緩沖區確定候選匹配路段，并利用行駛速度、行駛方向、投影距離和行車距離4個參數進行行車軌跡邏輯判別的匹配算法。試驗表明，該方法能夠高效且準確地篩選和判斷出浮動車定位點的匹配路段，對浮動車路況信息的生成具有很好的實用價值。本文研究的路況信息匹配生成算法所考慮的因素較多，對于一些非常復雜的路段區域，隨著待定方案的增多會導致部分性能的降低。后續研究工作將針對這些特殊區域路段的特點，對算法性能的穩定性進行改進和優化。

[1] 邵春福,熊志華,姚智勝.道路網短時交通需求預測理論、方法及應用[M].北京:清華大學出版社,2011.

[2] 王美玲，程林.浮動車地圖匹配算法研究[J].測繪學報,2012,1(41),133-138.

[3] 劉培.基于浮動車數據的地圖匹配算法研究[D].北京:北京交通大學,2007.

[4] 尹相勇,賈順平. 基于MapObjects的浮動車中心地圖匹配綜合算法開發[J]. 計算機工程與應用, 2008, 44(36): 881-884.

[5] 諸彤宇,郭勝敏. 浮動車信息處理技術研究[J]. 中國圖象圖形學報, 2009, 14(7):1230-1237.

[6] 章威, 徐建閩, 林綿峰. 基于大規模浮動車數據的地圖匹配算法[J]. 交通運輸系統工程與信息, 2007, 7(2):40-45.

[7] QUDDUS M A,NOLAND R B,OCHIENG W Y.A High Accuracy Fuzzy Logic Based Map Matching Algorithm for Road Transport[J]. Journal of Intelligent Transportation Systems, 2006, 10(3): 103-115.

[8] NAJJAR M E E,BONNIFAIT P.A Road-matching Method for Precise Vehicle Localization Using Belief Theory and Kalman Filtering[J]. Autonomous Robots, 2005,19(2):173-191.

[9] JABBOUR M, BONNIFAIT P, CHERFAOUI V. Map-matching Integrity Using Multihy Pothesis Road-tracking[J]. Journal of Intelligent Transportation Systems, 2008, 12(4): 189-201.

[10] 呂衛鋒,吳東東,諸彤宇. 基于向量識別的啟發式路徑推測算法[J]. 計算機學報,2009,32(7):1443-1450.

[11] 李宇光,李清泉. 利用地圖柵格化的海量浮動車數據道路匹配快速算法[J]. 武漢大學學報(信息科學版),2014,39(6):724-728，733.

[12] RAHMANI M,KOUTSOPOULOS H N.Path Inference from Sparse Floating Car Data for Urban Networks[J]. Transportation Research Part C:Emerging Technologies, 2013(30):41-54.

[14] CHERITON D R, BECHTOLSHEIM A V. Method for Traffic Management,Traffic Prioritization,Access Control,and Packet Forwarding in a Datagram Computer Network: U.S. Patent 6,091,725[P]. 2000-07-18.

[15] MCCLOGHRIE K,GAI S,MOHABAN S. Method and Apparatus for Identifying Network Data Traffic Flows and for Applying Quality of Service Treatments to the Flows: U.S. Patent 6,286,052[P]. 2001-09-04.

[16] DE FABRITIIS C,RAGONA R, VALENTI G. Traffic Estimation and Prediction Based on Real Time Floating Car Data[C]∥Proceedings of the 11th International IEEE Conference on Intelligent Transportation Systems. Beijing：IEEE, 2008: 197-203.

[17] LEDUC G. Road Traffic Data: Collection Methods and Applications[J]. Working Papers on Energy, Transport and Climate Change,2008(1): 55.

[18] FUSHIKI T, YAMANE K, INOUE T, et al. Method of Presuming Traffic Conditions by Using Floating Car Data and System for Presuming and Presenting Traffic Conditions by Using Floating Data: U.S. Patent 6,721,650[P]. 2004-04-13.

[19] EHMKE J F, MEISEL S, MATTFELD D C. Floating Car Data Based Analysis of Urban Travel Times for the Provision of Traffic Quality[M].New York：Springer, 2010: 129-149.

[21] YOSHIDA M. Traffic Information System: U.S. Patent 5,699,056[P]. 1997-12-16.

AnImprovedAlgorithmforFastMap-matchingofFloatingCar

ZHANG Jianqin1,2,LI Mingxuan1,2, DUAN Yingchao1,2,DU Mingyi1,2

(1. School of Surveying and Urban Spatial Information, Beijing University of Civil Engineering and Architecture,Beijing 100044,China; 2. Key Laboratory for Urban Geomatics of National Administration of Surveying, Mapping and Geoinformation，Beijing 100044, China)

Floating car map-matching algorithm enables fast and accurate matching between the discrete points of floating car and the road segments. It is the core part of floating car traffic information generation technology. For the deficiencies of the prior method, an efficient logical matching method is proposed and implemented. Firstly it establishes buffer zones with effective threshold for the anchor points, and then searches the road segments that intersect with the buffer zones. After that, it discriminates the driving track by four parameters(driving speed, driving direction, projection distance and driving distance). The experiments show that this method does not require extensive work to deal with road network data. It simplifies the process of searching candidate matching road segments and ensures matching accuracy while also shows a higher efficiency.

road network matching; floating car data; traffic information; road segments

P283

A

0494-0911(2017)01-0087-06

張健欽，李明軒，段穎超,等.一種改進的快速浮動車地圖匹配方法[J].測繪通報，2017(1)：87-92.

10.13474/j.cnki.11-2246.2017.0019.

2016-02-27

張健欽(1977—)，男，博士，副教授，研究方向為交通GIS、三維GIS及智能交通系統。E-mail：yc.duan@qq.com