基于低采樣率浮動車數據的全局投票地圖匹配算法

楊旭華，汪向飛

(浙江工業(yè)大學 計算機科學與技術學院，浙江 杭州 310023)

基于低采樣率浮動車數據的全局投票地圖匹配算法

楊旭華，汪向飛

(浙江工業(yè)大學 計算機科學與技術學院，浙江 杭州 310023)

摘要：針對現有地圖匹配算法在低采樣率時錯誤率較高的問題，提出一種全局投票地圖匹配算法.算法在浮動車GPS軌跡數據的基礎上，充分考慮道路網絡的拓撲結構和不同距離的GPS軌跡點對匹配過程的影響.算法考慮道路網絡的幾何特性和拓撲結構，首先得出作為初始結果的靜態(tài)匹配矩陣，定義距離加權函數對靜態(tài)匹配矩陣進行修正，得到動態(tài)匹配矩陣，在此基礎上進行全局投票，找出最優(yōu)軌跡作為地圖匹配的結果.最后采用杭州出租車數據對算法進行驗證，結果顯示：在采樣率低情況下，算法能夠充分利用已有信息，得到較好的地圖匹配效果.

關鍵詞：浮動車；低采樣率；拓撲信息；距離加權；全局投票；地圖匹配

A global-voting map matching algorithm for low-sampling-rate

floating car data

YANG Xuhua, WANG Xiangfei

(College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310023, China)

Abstract:Since the existing floating car map-matching algorithms lead to high error rate when GPS data sampling rate is low, a global-voting map matching algorithm is proposed. Based on floating car GPS track data, the algorithm takes a full consideration on the impact of the topology of the road network and the GPS track points at different distances on the matching process Firstly, considering the influence of geometric and topological information of road network, a static matching matrix as initial results are gotten. Then, a distance weighting function is defined to revise the static matching matrix and built a dynamic matching matrix.Then an efficient global voting algorithm is used to identify the optimal trajectory as map matching result. Finally, the algorithm is verified on Hangzhou taxi data. Results show that this algorithm can make full use of existing information and has a good perform on map matching.

Keywords:floating car; low-sampling-rate; topological information; distance weighting; global-voting; map matching

浮動車一般是指安裝了GPS軌跡定位裝置并行駛在城市主干道上的公交汽車和出租車.浮動車技術是近年來興起的一種動態(tài)交通信息檢測的技術，是近年來智能交通系統中所采用的獲取道路交通信息的先進技術手段之一[1].浮動車可以定期將車輛編號、時刻、方向、經緯度坐標等數據傳送到調度中心,經過信息處理，可以方便地獲得整個城市路網的實時交通信息.但是由于GPS軌跡設備自身會存在定位誤差和采樣誤差，GPS軌跡點偏離道路的情況在所難免[2].地圖匹配算法是浮動車數據處理的關鍵技術之一，它可以最大程度地校正GPS軌跡衛(wèi)星定位所產生的誤差，從而矯正車輛軌跡偏離道路的現象，將GPS軌跡數據轉化為道路的交通信息.

傳統地圖匹配算法[3-5]采用很高的GPS軌跡采樣間隔數據，匹配的正確率才得以保證.但在實際應用中,由于節(jié)約能源以及浮動車本身特性等原因，返回給調度中心的數據往往是低采樣率的.在低采樣率的情況下(2 min)，車輛的速度僅為30 km/h，兩個GPS軌跡點之間的距離為1 000 m，尤其是在復雜的城市道路網絡中，GPS軌跡點之間的關聯信息會大部分丟失，給現有的地圖匹配算法帶來極大的挑戰(zhàn)[6].另外一方面，考慮幾何特性的地圖匹配算法[7-9]，在匹配過程中，這些算法又可以分為點對點的匹配、點對曲線的匹配、曲線對曲線的匹配.在現代復雜的道路網絡中，存在大量多車道，高架橋，分岔路情況，這些只考慮道路的幾何特性的算法很容易出錯.因此，傳統的地圖匹配算法不能很好解決低采樣率的浮動車數據的匹配過程，針對上述問題，設計一種適應度更高、魯棒性更強的全局投票地圖匹配算法.

1全局投票地圖匹配算法

近年來，低采樣率浮動車數據地圖匹配問題引起了很大關注.BRAKASTSOULS等提出一種針對相對低采樣率(30 s)數據的地圖匹配算法[10]，算法采用一種look-ahead技術來減少路段被遺漏的情況，從而提高準確率.CHEN Biyu等提出一種針對在線浮動車數據的多目標動態(tài)規(guī)劃地圖匹配算法[11],該算法考慮了GPS軌跡點之間的最短路徑，減少待匹配軌跡點的候選路段來降低復雜度.WENK C等提出一種根據Frechet距離確定誤差橢圓和匹配路徑的匹配算法[12]，找出最有可能的軌跡點序列作為匹配結果，并運用在離線的地圖匹配情況中.上述這些匹配算法不考慮全局GPS軌跡點之間的相互影響，在某個GPS軌跡點的匹配過程中，只利用該點本身的信息，或者僅僅考慮相鄰GPS軌跡點對其匹配過程的影響[13].由于缺乏對整體道路網絡拓撲結構的考慮，在復雜的道路環(huán)境和低采樣率的浮動車數據情況下，GPS軌跡點之間的關聯信息大量丟失，很難得到正確的匹配結果.尤其是當道路情況復雜時，例如多車道的情況下，很容易出現跨車道的情況.

實際上，浮動車數據不僅僅反映了車輛的位置信息，在某種程度上也反映了道路的拓撲結構信息以及GPS軌跡點之間的時間序列信息[14].因此這種針對低采樣率GPS軌跡數據的全局投票地圖匹配算法，在采樣率低的情況下，充分考慮道路網絡的拓撲結構，以及全局GPS軌跡點之間的關聯信息，且根據GPS軌跡點之間的距離，對它們之間的影響程度進行加權處理，從而提高匹配的正確率.

1.1算法基本策略

這種全局投票地圖匹配算法，有以下三個基本策略：

1) 考慮道路的拓撲結構

圖1　考慮道路網絡拓撲結構Fig.1　Consider the topological structure of road network

全局投票地圖匹配算法從最短路徑的角度考慮道路的拓撲結構.算法定義一個全新的匹配函數作為指標，不僅考慮GPS軌跡點之間的歐氏距離，還考慮候選點之間在道路網絡中的最短路徑，定義近距概率和連通概率計算得出靜態(tài)匹配矩陣.在實際的城市交通網絡中，考慮GPS軌跡點之間的最短路徑，十分必要而且實用.

2) 考慮GPS軌跡點之間的相互影響

圖2　不同距離空間位置相鄰GPS軌跡點的相互影響Fig.2　Mutual influence of different distance adjacent GPS track point

全局投票地圖匹配算法從全局投票的角度考慮GPS軌跡點之間的相關性.根據GPS軌跡點之間的歐氏距離和投影過程，產生每個GPS軌跡點的候選點集合，所有的GPS軌跡點相互之間進行投票過程，并且算法過程完全并行，只需要從候選點集合中投票產生正確匹配結果，而不需要計算大量的可能匹配結果，大大減小算法復雜度.

3) 考慮不同空間距離GPS軌跡點之間的加權影響

GPS軌跡點之間的相互影響的強弱程度是與它們之間的距離相關的.如圖2所示，p1,p2,p4,p5在p3的地圖匹配過程中，影響程度會因為它們距離p3的距離不同而不同.很明顯，p2,p4對p3匹配過程的影響程度會大于p1,p5的影響程度.

全局投票地圖匹配算法從加權的角度考慮GPS軌跡點之間的相關性.算法定義距離加權函數來代表GPS軌跡點之間距離越遠，相互之間的影響程度越弱這一現象.并且在實驗的基礎上，得出加權函數不是簡單的線性相關函數，而是更為有效的指數相關的距離加權函數.

1.2算法的具體步驟

這種全局投票算法在道路網絡的模型下，首先計算當前GPS軌跡點可能匹配的候選集合.考慮集合中候選點的近距概率和連通概率，得出靜態(tài)匹配矩陣.再考慮GPS軌跡點之間距離的不同導致影響程度的不同，定義距離加權函數，得出加權匹配矩陣，在此基礎上，各個GPS軌跡點之間相互進行單點投票過程，完成匹配算法.具體可以分為5個步驟,如圖3所示.

圖3　算法流程圖Fig.3　The algorithm flow chart

1) 數據預處理，完成道路網絡G的構建以及GPS數據T整理.

2) 選取候選節(jié)點，根據路段投影過程，得出每個GPS軌跡點的候選集合.

3) 靜態(tài)分析過程，定義匹配函數F，對每個GPS軌跡點的候選集合進行計算，得出靜態(tài)匹配矩陣.

4) 加權分析過程，對每一個GPS軌跡點，定義距離加權函數，以此來反映GPS軌跡之間距離和影響程度之間的關系.經過全局計算，得出動態(tài)匹配矩陣.

5) 全局投票，在每個GPS軌跡點對應的動態(tài)匹配矩陣中，進行單點投票過程.同時，所有單點投票過程并行運算，最后進行匯總，得出全局投票結果.

1.2.1數據預處理

表1　GPS軌跡點數據

圖4　GPS軌跡數據Fig.4　GPS track data

道路網絡定義為一個有向圖G(V,E)，其中V為道路的交叉點、起點或終點，E為被兩個相鄰交叉口分隔出的路段，每個路段包含起始點、結束點、路段長度.根據道路網絡，從而定義一條路徑P為：在道路網絡中，選取兩個節(jié)點Vi,Vj，找到一條互相連接的路段集合E1→E2→E3→…→En，并且路段E1的起點為Vi，路段En的終點為Vj.

根據上述定義，將已有的GPS軌跡數據和道路數據進行預處理，分別得到GPS軌跡T和道路網絡G.同時可以得出：地圖匹配算法的目的在于，輸入一個GPS軌跡T和道路網絡G(V,E)，找出一條路徑P去匹配軌跡T.

1.2.2選取候選節(jié)點

圖5　候選節(jié)點選取Fig.5　Candidate points selection

1.2.3靜態(tài)分析過程

(1)

得到每個候選節(jié)點的近距概率后，為了避免錯誤，考慮道路網絡的拓撲結構，根據GPS軌跡點之間的最短路徑長度，定義兩個候選節(jié)點之間的連通概率CP為

(2)

綜上所述，近距概率考慮了道路網絡的幾何性質，連通概率考慮了道路網絡的拓撲結構.在這兩者的基礎上，定義一個匹配函數F，其表達式為

(3)

圖6　候選節(jié)集合Fig.6　Candidate points sets

(4)

(5)

其中：1≤j≤m,1≤k≤n,m,n分別為ci-1,ci的候選節(jié)點總個數.比如針對p1→p2→p3→p4，為了方便說明，假設有

依次得出M3,M4，最終的靜態(tài)匹配矩陣為

1.2.4加權分析過程

在步驟3得到的靜態(tài)匹配矩陣的基礎上，考慮GPS軌跡之間的距離越遠，它們之間互相的影響越弱.因此，針對每個軌跡點pi，定義一個n-1維距離影響矩陣Wi為

(6)

1)f(0)=1.

2)f(∞)=0.

3) 0

為了方便說明，選取f=2-|i-j|說明算法過程，i,j為軌跡點pi,pj的下標.定義動態(tài)匹配矩陣Gi(1≤i≤n)為

(7)

1.2.5全局投票過程

表2　投票結果

2實驗結果與分析

2.1實驗數據來源

實驗中，如圖7(a)所示，在杭州道路網絡上進行實驗，道路網絡數據通過開源網站OpenStreetMap以及高德地圖API獲取.另外，如圖7(b)所示，待匹配軌跡數據選用杭州真實的出租車GPS軌跡數據，數據格式如表3所示.

圖7　實驗數據Fig.7　Experimentation data

ID車牌號經度緯度速度/(km·h-1)方向記錄時刻3879981103浙AT1239120.11283330.31798330.24180.0007:34:523879981104浙AT6105114.49003633.8530730.37350.0007:34:53

2.2對比過程

為了評價算法的匹配效率，選取一種點對點地圖匹配算法[8]和一種多目標動態(tài)規(guī)劃地圖匹配算法[12]作為比較對象.這種基于點對點距離的地圖匹配算法(P2PMM)，先找到候選點和候選路段，計算軌跡點和候選點之間的距離，選取距離最短的候選點作為匹配結果.另外，這種多目標動態(tài)規(guī)劃地圖匹配算法(MDPMM)會考慮節(jié)點之間的最短路徑，但是只考慮相鄰鄰居節(jié)點對匹配過程的影響.定義正確匹配率，即正確匹配GPS軌跡點數量與待匹配GPS軌跡點總數的比例，以此來對比不同算法的匹配準確率.

實驗過程中，每次選取一輛出租車時間間隔為2 min的20個點作為待匹配GPS軌跡點，每次實驗在GPS軌跡點經緯度坐標加上一個與時間戳有關的隨機數，進行2 000次實驗.將每次匹配結果與剛開始設定的正確匹配結果(人為標識)進行對比，誤差不超過1M認定問匹配正確.

2.3結果

首先給出在道路網絡中，杭州出租車數據經過全局地圖匹配算法計算以后的可視化結果(共匹配3 000輛出租車數據，每輛出租車選取20個GPS軌跡點).實驗結果表明：杭州出租車數據很好的匹配到道路上，正確率達到90%左右.如圖8(b)所示，在道路情況相對復雜的情況下，比如多車道，MDPMM很難得到正確的匹配結果，會出現復雜的跨車道情況，然而全局投票匹配后的結果如圖8(a)所示，很好的避免了跨車道情況.其中不帶標記的線為GPS軌跡數據，帶星形標記的線為地圖匹配結果.

圖8　多車道情況下匹配結果Fig.8　Multi-Lane matching result

圖9　不同地圖匹配算法Fig.9　Different map matching algorithm

圖10　不同距離加權函數Fig.10　Different distance weighted function

3結論

這種全局投票地圖匹配算法針對低采樣率的浮動車數據，在分析已有地圖匹配算法的基礎上，結合道路的拓撲結構，綜合考慮了GPS軌跡點之間的相互作用，并且定義了距離加權函數來體現節(jié)點之間距離和相互影響權重之間的關系，提出一種全局投票地圖匹配算法.該算法運用于杭州真實的出租車GPS軌跡數據，獲得了良好的地圖匹配效果.

參考文獻：

[1]趙敬洋，郭明飛，郭海峰，等.基于典型行車路線理論的城市交通中誘導屏選址優(yōu)化方法研究[J].浙江工業(yè)大學學報，2010，38(5):586-590.

[2]陳曉瞇，孟志青，徐杰．基于混合禁忌搜索算法的動態(tài)車輛路徑研究[J].浙江工業(yè)大學學報,2009,37(5):580-581.

[3]SU Jie, ZHOU Dongfang, YUE Chunsheng. Real-time map-matching algorithm in GPS navigation system for vehicle[J].Acta Geodaetica et Cartographica Sinca,2001,30(3):252-256.

[4]TANG Jinjun, CAO Kai. An adaptive trajectory curves map-matching algorithm[J]. Acta Geodaetica et Cartographica Sinca,2008,37(3):308-315

[5]XU H, LIU H C, TAN C W,BAO Y L. Development and application of an enhanced kalman filter and global positioning system error-correction approach for improved map-matching[J]. Journal of Intelligent Transportation Systems,2010,14(1):27-36.

[6]TOMIO M, DAISUKE K, TOSHIYUKI Y. Development of map matching algorithm for low frequency probe data[J]. Transportation Research,2012,22:132-145.

[7]WHITE C, BERNSTEIN D, KORNHAUSER A L. Some map matching algorithms for personal navigation assistants[J]. Transportation Research Part C,2000,8:91-108.

[8]YIN H B, WOLFSON O A weight-based map matching method in moving objects databases[C]//In Proceedings of the International Conference on Scientific and Statistical Database Management. Chicago: Scientific and Statistical Database Management Press,2004:437-410.

[9]HONG W B, CHEN C Y, PENG J W. Improvements of driver fatigue detection system based on eye tracking and dynamic template matching[J]. WSEAS Transactions on Information Science and Application,2012,9(1):14-23.

[10]BRAKATSOULS D P, SALAS R, WENK C. On map-matching vehicle tracking data[C]//In 31st International Conference on Very Large Databases. San Antonio：University of Texas Press，2005:853-864.

[11]CHEN Biyu , YUAN Hui, LI Qingquan, et al. Map-matching algorithm for large-scale low-frequency floating car data[J]. International Journal of Geographical Information Science,2014,28(1):22-38.

[12]WENK C, SALAS R, PFOSER D. Addressing the need for map-matching speed: localizing global curve-matching algorithm[C]//In 18th International Conference on Scientific and Statistical Database Management. San Antonio：University of Texas Press，2006:379-388.

[13]GREENFELD J S. Matching GPS observations to locations on a digital map[J]. Transportation Research Board,2002,27(1):13-16.

[14]GUO L M, LUO D Y. Study on map matching technology in wireless position[J]. Computer Engineering and Applications,2009,45(18):25-27.

[15]QUDDUS M A, WASH INGTON Y O, ROBERT B N. Current map-matching algorithms for transport applications: state-of-the art and future research directions [J].Transportation Research Part C,2007(15):312-328.

[16]楊旭華,李傳告,陳光.基于K-最短路徑的交通網絡傳輸性能分析[J].浙江工業(yè)大學學報，2014,42(3):249-256.

(責任編輯：劉巖)

中圖分類號：TP13

文獻標志碼：A

文章編號：1006-4303(2015)03-0318-08

作者簡介：楊旭華(1971—),男，浙江余姚人，教授，研究方向為復雜網絡和智能效能，E-mail:xhyang@zjut.edu.cn.

基金項目：國家自然科學基金資助項目(61374152)；浙江省公益性技術應用研究計劃項目(2012C23126)

收稿日期：2015-01-22