浮動車地圖匹配算法研究

王美玲，程 林

北京理工大學自動化學院，北京100081

1 引 言

浮動車系統是伴隨著ITS新技術應用而在近幾年發展起來的新型交通流信息采集技術。一般使用大量的出租車或公交車作為浮動車，通過已安裝的GPS車載裝置和無線通信設備，將車輛信息（如時間、速度、坐標、方向等參數）實時地傳送到浮動車信息中心。浮動車輸出的動態實時交通信息不僅能為相關部門提供道路交通實況，而且可作為道路建設規劃、擁堵緩解等各項工作中定量數據分析的基礎［1－4］。

地圖匹配技術是浮動車數據處理的關鍵技術之一，只有判斷出車輛在哪條道路上行駛，才能將GPS數據轉化為道路的交通狀態［5－7］。

浮動車系統具有數據量大，實時性要求高和采樣點間隔比較大等特點。浮動車地圖匹配在應用于現代城市復雜路網時主要面對3大關鍵技術難點［8－9］：① 數據需要實時處理，數據量較大，因此對系統的計算速度要求較高；② 數據間隔一般較大，導致定位點信息之間的相關性比較差；③ 現代城市路網密集且結構復雜，因此對系統的匹配容錯率要求較高。

文獻［10—11］所述的傳統導航地圖匹配算法，由于GPS采樣點的間隔僅為1s，因此比較容易獲得準確的軌跡曲線作為匹配樣本，能夠實現基于軌跡曲線的線到線的地圖匹配。然而，以北京市為例，每輛浮動車每分鐘上傳一個GPS點數據，前后兩點間的相關性差決定了浮動車系統無法采用線到線的地圖匹配方法；此外，浮動車系統的數據量大，反映在單個GPS定位點上，其匹配時間遠少于1s。可見，傳統的導航地圖匹配算法不能直接應用于浮動車系統。

浮動車實時路況處理技術在我國各大城市還處于示范階段，目前參與北京市浮動車系統的車輛約35 000輛，每輛車如果每分鐘上傳一個GPS數據，那么數據處理中心每天接收到的數據量就有5000余萬條。隨著浮動車數量的日益增多，文獻［1—9］所述的浮動車地圖匹配算法已難以滿足當前應用環境下準確性與實時性的要求。可見，提高浮動車地圖匹配的準確性與實時性，是需要進一步研究的課題。

2 路網構建

道路網絡的精度和屬性結構直接關系到地圖匹配算法的性能。為此，本文首先給出Super－Map GIS平臺下的路網構建方法。

2.1 拓撲處理

以經過配準后的柵格地圖為背景，通過以直線代替曲線的方式創建道路中心線，將曲線道路分解為若干直線段；對于異面道路，合理設置非打斷線參數，以真實再現立體交通；完成拓撲處理［12］。

將路網中的假節點稱為形狀點，圖1給出拓撲處理后的部分道路網絡。

圖1 部分道路網絡Fig.1 Part of road network

2.2 屬性編輯

地圖匹配算法將利用道路網絡的如下屬性：

（1）路段編號SmID；

（2）路段起點SmFNode；

（3）路段終點SmTNode；

（4）路段正向阻力SmResistanceA；

（5）路段反向阻力SmResistanceB；

（6）路段長度SmLength；

（7）路段方向類別Head。

其中，（4）、（5）、（7）為需要編輯與創建的字段。在SuperMap Deskpro中道路網絡的部分屬性如圖2所示。

圖2 SuperMap Deskpro中路網屬性Fig.2 Attribute of road network in SuperMap Deskpro

其中，Head為新建字段，字段值“1”表示雙向道路，將SmResistanceA與SmResistanceB均設置為0；字段值“2”表示單向道路，且方向為起點F→終點T，將SmResistanceA與SmResistanceB分別設置為0和∞（由10 000表示）；字段值“3”表示單向道路，且方向為終點T→起點F，將SmResistanceA與SmResistanceB分別設置為∞（由10 000表示）和0。

3 地圖匹配算法

基于浮動車數據的地圖匹配算法流程如圖3所示。

圖3 地圖匹配算法流程Fig.3 Process of map matching algorithm

在地圖匹配前，首先進行浮動車GPS數據的預處理，剔除存在漂移錯誤以及記錄為空載、駐車及停運的數據，以求真實反映當前路況；然后進行坐標變換，與電子路網地圖采用的坐標系一致。

3.1 基于網格的候選路段確定

按照一定的步長l（本文取70m），將導航電子地圖道路網絡從上到下、從左到右網格化分塊，將道路網絡分為M×N個相同的網格，記為Grid （i），（i＝0，1，…，MN－1），記道路網絡左下角的坐標為O （X0，Y0），如圖4所示。

圖4 道路網絡的網格分塊Fig.4 Grid block of road network

設某定位點坐標為（x，y） ，則其所在的網格為Grid （［（Y0＋Ml －y）／l ］N＋［（x－X0）／l］）。

對于每一個網格 Grid （i），將其擴展為邊長為2l的網格 Grid′（i），如圖5中虛線所示，記錄在網格 Grid′（i）之內（如路段AB、BC、AE、BD、DF、DE）及與網格 Grid′（i）相交（如路段AH、EG）的路段編號，將各路段作為落入網格G rid （i）內的GPS定位點的候選路段。

圖5 候選路段的確定Fig.5 Candidate road determination

3.2 基于權重的定位點匹配

算法為每條候選路段計算權重，包括距離權重WD、航向權重WH及可達性權重WR，并計算每條候選路段的權重總和W，以此確定匹配路段和匹配點。

3.2.1 距離權重

距離權重表示為［13］

式中，DW表示距離權重系數D表示定位點到候選路段的距離，當定位點到候選路段的垂足不在候選路段上時，分別計算定位點到候選路段起點F和終點T的距離，并選擇較小值，如圖6所示，定位點P到候選路段BD和EF的距離分別為PH和PE的長；DTH為距離閾值，本文將DTH設置為25m。

圖6 定位點到候選路段的距離Fig.6 Distance between the GPS point and the candidate road

因此，當0≤D≤2DH時，f（D ）取值在1到－1間，并隨D的增加而線性減小。當D＞2DH時，將f（D ）設置為－1。

3.2.2 航向權重

航向權重表示為

式中，HW表示航向權重系數；f（Δθ ）＝cos（Δθ），Δθ表示車輛航向與路段方向的夾角。設θ表示GPS接收機輸出的車輛航向，范圍是［0，2π），正北方向為0；θ0表示道路傾角，范圍是［0，π），正北方向為0；（xf，yf）和（xt，yt）分別表示候選路段起點F與終點T的坐標。則當xf＝xt時，θ0＝0；否則，θ0＝π／2－arctan ［（yt－yf）／（xt－xf）］。Δθ的取值如表1所示。

表1 Δθ的取值Tab.1 The value ofΔθ

續表1

3.2.3 可達性權重

可達性權重表示為

式中，RW表示可達性權重系數；將候選路段上距當前定位點最近的點（垂直投影點、起點或終點）稱為該候選路段的虛擬匹配點，如果上一匹配點到該候選路段虛擬匹配點的最短距離不大于浮動車在該時間間隔內能夠行駛的最大距離（取1200m），X取1，否則取－1。

最短路徑的求解采用Dijkstra算法［12，14－16］，以上一匹配點和當前虛擬匹配點所在網格為對角網格，并將兩對角網格構成的矩形區域作為Dijkstra算法的搜索區域。在解算過程中，各路段權值為路段長度與阻力之和［12，14］，即

正向權值為

反向權值為

如圖7所示，定位點P1已經匹配到路段AB上的P點，對于當前定位點P2，點E和F分別為其候選路段AD和CD的虛擬匹配點，其中路段CD為單向道路。點P到E和F的最短路徑分別為P－A－E和P－B－C－F，而路徑P－B－C－F的距離大于浮動車在該時間間隔內能夠行駛的最大距離，因此，候選路段AD較CD具有更高的可達性權重。

圖7 可達性權重Fig.7 Reachability weight

3.2.4 權重總和

權重總和表示為

算法為每條候選路段計算權重總和W，選出具有最高和次高權重和的兩候選路段，比較兩權重，如果相差大于1%，則將具有最高權重和的候選路段作為匹配路段，將該候選路段的虛擬匹配點作為匹配點。

反之，如果兩權重和相差在1%之內，視為模糊情況，將當前定位點匹配到兩候選路段的上游節點，即上一匹配點到兩候選路段虛擬匹配點的最短路徑所經過的最后一個相同節點。如圖8所示，點P是已經匹配到路段AB上的匹配點，對當前定位點Q，候選路段EF與DG分別具有最高和次高的權重和，點M與N分別為其虛擬匹配點。點P到M與N的最短路徑分別為P－B－C－D－E－M和P－BC－D－N，由于兩權重和相差在1%內，因此將定位點Q匹配到路段EF和DG的上游節點，即D點。

圖8 上游節點匹配Fig.8 Upstream node matching

3.3 基于最短路徑的行駛軌跡選擇

由于浮動車系統上傳數據的時間間隔較大，同一輛車前后兩點很可能相距幾個路段。因此，算法對某一定位點結束匹配之后，在充分考慮路網拓撲關系的前提下，選擇當前匹配點與上一匹配點間的最短路徑作為車輛的行駛軌跡，這與大多數熟悉路網的司機在一般情況下會選擇最近的道路到達目的地的實際情況相符。最短路徑的求解同3.2.3節所述方法，路段權值設置同式（4）和式（5）。

4 算法驗證

將本文算法應用于北京市道路網絡，距離、航向與可達性權重系數DW、HW與RW均設置為1／3。圖9給出同一輛浮動車連續3個定位點的正確匹配結果；圖10和表2分別給出了其中第2個定位點的匹配情況，在表2中，ID表示候選路段編號，R表示上一匹配點到當前定位點候選路段虛擬匹配點的距離；圖11給出傳統算法直接將具有最高權重的候選路段作為匹配路段時的錯誤匹配結果。

圖9 正確地圖匹配結果Fig.9 The correct map matching result

圖10 第2個定位點的匹配結果Fig.10 Matching result of the second GPS point

表2 第2個定位點的候選路段Tab.2 Candidate roads of the second GPS point

由此可見，本文設計的算法能夠正確計算候選路段的各項權重，有效排除不可能的候選路段；同時，候選路段11和176分別具有最高與次高的權重，且相差1%之內，176為車輛實際經過的路段，算法將定位點匹配到兩路段的上游節點，而如圖11所示，如果直接選擇最高權重的候選路段作為匹配路段，將造成連續的匹配錯誤。浮動車地圖匹配的最終目的是為城市路況模型提供車輛行駛軌跡，模糊情況下的上游節點匹配雖然帶來較大的單點匹配誤差，但卻避免由于單點匹配錯誤而造成的連續匹配失敗。

圖11 錯誤地圖匹配結果Fig.11 The wrong map matching result

此外，采用NovAtel FlexPak－G2GPS接收機接收同一輛浮動車在不同時間段內行駛于多條路線時的定位數據。利用此數據，將本文算法運行于2.53GHz CPU、2G內存的計算機上進行驗證。經統計，算法的平均正確匹配率為96.55%，單點的平均匹配時間為0.931ms。

對于現有實時運轉的浮動車地圖匹配算法，正確匹配率平均在95%左右，單點匹配時間在幾毫秒至幾十毫秒之間。可見，本文算法在保證較高準確率的基礎上，極大地提高匹配效率，能夠滿足目前北京市浮動車系統地圖匹配的準確性要求及每分鐘35 000點的計算速度要求。

5 結 論

針對現有浮動車地圖匹配算法應用于城市復雜路網時面臨的關鍵技術難點，對浮動車地圖匹配展開研究，主要包括以下方面：

（1）給出道路網絡的構建方法，充分考慮道路網絡的空間分布特性，使構建的網絡區別于普通平面網絡。合理編輯屬性表結構，有效降低了地圖匹配算法的計算復雜度。

（2）基于網格的候選路段確定，根據GPS定位點所在網格，直接得到其候選路段，極大地提高了算法的運行效率。將各網格擴展為原來邊長的2倍，將新網格所包含的路段作為候選路段，能夠保證正確路段在候選路段之中，克服潛在的匹配錯誤。

（3）基于距離、航向和可達性權重的定位點匹配，距離的計算，考慮投影點與候選路段的位置關系，準確得到虛擬匹配點。根據道路屬性，給出車輛航向與路段方向夾角的各種可能。可達性權重的引入使車輛處于單向道路、立體交通道路時保證地圖匹配的精度。模糊情況下的節點匹配，適于城市路網結構復雜、主輔路并行和交叉口繁多的特點，避免連續匹配失敗。

（4）基于最短路徑的行駛軌跡選擇，適于浮動車數據采樣間隔大的特點，對Dijkstra算法搜索區域的合理限制，有效保證路徑選擇的實時性。

由于不同的權重系數會給匹配結果帶來一定的影響，車輛在兩匹配點間的行駛軌跡并不是在任何情況下都是兩點間的最短路徑，因此，為進一步提高算法的準確性，根據車輛的行駛狀態和所處的路網環境合理調整權重系數，以及考慮更多的因素確定車輛在兩匹配點間的行駛軌跡，是下一步的研究方向。

［1］ LIU Pei.Study on Map－matching Algorithm Based on Probe Car［D］.Beijing：Beijing Jiaotong University，2007.（劉培.基于浮動車數據的地圖匹配算法研究 ［D］.北京：北京交通大學，2007.）

［2］ YIN Xiangyong，JIA Shunping.Synthesized Map Matching Algorithm for Floating Cars Processing Center［J］.Computer Engineering and Applications，2008，44（36）：881－884.（尹相勇，賈順平.基于MapObjects的浮動車中心地圖匹配綜合算法開發［J］.計算機工程與應用，2008，44（36）：881－884.）

［3］ ZHU Tongyu，GUO Shengmin.A Study on Floating Car Based Information Processing Technology［J］.Journal of Image and Graphics，2009，14（7）：1230－1237.（諸彤宇，郭勝敏.浮動車信息處理技術研究 ［J］.中國圖象圖形學報，2009，14（7）：1230－1237.）

［4］ ZHANG Wei，XU Jianmin，LIN Mianfeng.Map Matching Algorithm of Large Scale Probe Vehicle Data［J］.Journal of Transportation Systems Engineering and Information Technology，2007，7（2）：40－45.（章威，徐建閩，林綿峰.基于大規模浮動車數據的地圖匹配算法 ［J］.交通運輸系統工程與信息，2007，7（2）：40－45.）

［5］ WANG Dongzhu，DONG Jiming，LI Yameng，et al.Mapmatching Method Based on Zero－speed Points in Floating Car Data［J］.Journal of Transport Information and Safety，2009，27（6）：38－42.（王東柱，董繼明，李亞檬，等.浮動車數據中零速度點數據地圖匹配方法 ［J］.交通信息與安全，2009，27（6）：38－42.）

［6］ XUE Ming，LV Weifeng，ZHU Tongyu.Study on Key Technology of Floating Car Information Processing System［J］.Control and Automation，2006，22（11）：244－246.（薛明，呂衛鋒，諸彤宇.浮動車信息處理系統關鍵技術的研究［J］.微計算機信息，2006，22（11）：244－246.）

［7］ LIU Yanting，WU Jianping，ZHANG Ge.A Map Matching Algorithm for Public Traffic Control Center Based on Long Space and Limited GPS Data［J］.Journal of Transportation Engineering and Information，2007，5（2）：69－74.（劉彥廷，吳建平，張鴿.基于長間隔大規模數據的地圖匹配算法研究［J］.交通運輸工程與信息學報，2007，5（2）：69－74.）

［8］ ZHU Liyun，WEN Huimin，SUN Jianping.Floating Car Based Real－time－traffic－info Collection System in Beijing［J］.Urban Transport of China，2008，6（1）：77－80.（朱麗云，溫慧敏，孫建平.北京市浮動車交通狀況信息實時計算系統［J］.城市交通，2008，6（1）：77－80.）

［9］ ZHU Liyun，GUO Jifu，WEN Huimin，et al.A Mapmatching Algorithm of Real－time Floating Car System for Complex City Road Network［J］.Computer and Communications，2007，25（6）：81－84.（朱麗云，郭繼孚，溫慧敏，等.一種適用于復雜城市路網的浮動車實時地圖匹配技術［J］.交通與計算機，2007，25（6）：81－84.）

［10］ SU Jie，ZHOU Dongfang，YUE Chunsheng.Real－time Map－matching Algorithm in GPS Navigation System for Vehicles［J］.Acta Geodaetica et Cartographica Sinica，2001，30（3）：252－256.（蘇潔，周東方，岳春生.GPS車輛導航中的實時地圖匹配算法［J］.測繪學報，2001，30（3）：252－256.）

［11］ TANG Jinjun，CAO Kai.An Adaptive Trajectory Curves Map－matching Algorithm［J］.Acta Geodaetica et Cartographica Sinica，2008，37（3）：308－315.（唐進君，曹凱.一種自適應軌跡曲線地圖匹配算法 ［J］.測繪學報，2008，37（3）：308－315.）

［12］ CHENG Lin，WANG Meiling，ZHANG Yi.An Improved Algorithm Based on SuperMap GIS［J］.Journal of Geoinformation Science，2010，12（5）：649－654.（程林，王美玲，張毅.一種基于SuperMap GIS的改進Dijkstra算法［J］.地球信息科學學報，2010，12（5）：649－654.）

［13］ VELAGA N R，QUDDUS M A，BRISTOW A L.Developing an Enhanced Weight－based Topological Map－matching Algorithm for Intelligent Transport Systems［J］.Transportation Research Part C—Emerging Technologies，2009，7：672－683.

［14］ CHENG Lin，WANG Meiling.A New Path Planning Algorithm Based on Partitioned Urban Transportation Network［C］∥Proceedings of 2010International Conference on Computer Application and System Modeling（ICCASM 2010）.Taiyuan：IEEE，2010：13－17.

［15］ HAN Gang，JIANG Jie，CHEN Jun，et al.An Arc Based Dijkstra Algorithm for Road Turning Penalty in Vehicle Navigation System［J］.Acta Geodaetica et Cartographica Sinica，2002，31（4）：366－368.（韓剛，蔣捷，陳軍，等.車載導航系統中顧及道路轉向限制的弧段Dijkstra算法［J］.測繪學報，2002，31（4）：366－368.）

［16］ LU Feng.Shortest Path Algorithms：Taxonomy and Advance in Research［J］.Acta Geodaetica et Cartographica Sinica，2001，30（3）：269－275.（陸鋒.最短路徑算法：分類體系與研究進展［J］.測繪學報，2001，30（3）：269－275.）