楊旭華，汪向飛

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

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

楊旭華，汪向飛

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

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

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

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)交通信息檢測的技術，是近年來智能交通系統(tǒng)中所采用的獲取道路交通信息的先進技術手段之一[1].浮動車可以定期將車輛編號、時刻、方向、經(jīng)緯度坐標等數(shù)據(jù)傳送到調(diào)度中心,經(jīng)過信息處理，可以方便地獲得整個城市路網(wǎng)的實時交通信息.但是由于GPS軌跡設備自身會存在定位誤差和采樣誤差，GPS軌跡點偏離道路的情況在所難免[2].地圖匹配算法是浮動車數(shù)據(jù)處理的關鍵技術之一，它可以最大程度地校正GPS軌跡衛(wèi)星定位所產(chǎn)生的誤差，從而矯正車輛軌跡偏離道路的現(xiàn)象，將GPS軌跡數(shù)據(jù)轉(zhuǎn)化為道路的交通信息.

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

1全局投票地圖匹配算法

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

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

1.1算法基本策略

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

1) 考慮道路的拓撲結(jié)構(gòu)

圖1　考慮道路網(wǎng)絡拓撲結(jié)構(gòu)Fig.1　Consider the topological structure of road network

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

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

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

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

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

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

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

1.2算法的具體步驟

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

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

1) 數(shù)據(jù)預處理，完成道路網(wǎng)絡G的構(gòu)建以及GPS數(shù)據(jù)T整理.

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

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

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

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

1.2.1數(shù)據(jù)預處理

表1　GPS軌跡點數(shù)據(jù)

圖4　GPS軌跡數(shù)據(jù)Fig.4　GPS track data

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

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

1.2.2選取候選節(jié)點

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

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

(1)

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

(2)

綜上所述，近距概率考慮了道路網(wǎng)絡的幾何性質(zhì)，連通概率考慮了道路網(wǎng)絡的拓撲結(jié)構(gòu).在這兩者的基礎上，定義一個匹配函數(shù)F，其表達式為

(3)

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

(4)

(5)

其中：1≤j≤m,1≤k≤n,m,n分別為ci-1,ci的候選節(jié)點總個數(shù).比如針對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　投票結(jié)果

2實驗結(jié)果與分析

2.1實驗數(shù)據(jù)來源

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

圖7　實驗數(shù)據(jù)Fig.7　Experimentation data

ID車牌號經(jīng)度緯度速度/(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)，先找到候選點和候選路段，計算軌跡點和候選點之間的距離，選取距離最短的候選點作為匹配結(jié)果.另外，這種多目標動態(tài)規(guī)劃地圖匹配算法(MDPMM)會考慮節(jié)點之間的最短路徑，但是只考慮相鄰鄰居節(jié)點對匹配過程的影響.定義正確匹配率，即正確匹配GPS軌跡點數(shù)量與待匹配GPS軌跡點總數(shù)的比例，以此來對比不同算法的匹配準確率.

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

2.3結(jié)果

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

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

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

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

3結(jié)論

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

參考文獻：

[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-最短路徑的交通網(wǎng)絡傳輸性能分析[J].浙江工業(yè)大學學報，2014,42(3):249-256.

(責任編輯：劉巖)

中圖分類號：TP13

文獻標志碼：A

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

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

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

收稿日期：2015-01-22