考慮時(shí)空特性的動(dòng)態(tài)權(quán)重實(shí)時(shí)地圖匹配算法

鄭林江，劉 旭，易 兵

(1.重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400044； 2.重慶城市綜合交通樞紐開(kāi)發(fā)投資有限公司，重慶 401121)

(*通信作者電子郵箱lx1848@126.com)

考慮時(shí)空特性的動(dòng)態(tài)權(quán)重實(shí)時(shí)地圖匹配算法

鄭林江1，劉 旭1*，易 兵2

(1.重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400044； 2.重慶城市綜合交通樞紐開(kāi)發(fā)投資有限公司，重慶 401121)

(*通信作者電子郵箱lx1848@126.com)

針對(duì)當(dāng)前實(shí)時(shí)地圖匹配算法難以同時(shí)保證匹配高準(zhǔn)確性和高實(shí)時(shí)性的問(wèn)題，提出一種基于動(dòng)態(tài)權(quán)重的實(shí)時(shí)地圖匹配改進(jìn)算法。首先，算法考慮了相鄰全球定位系統(tǒng)(GPS)軌跡點(diǎn)在時(shí)間、速度和方向上的約束關(guān)系，以及道路網(wǎng)拓?fù)浣Y(jié)構(gòu)，并基于時(shí)空特性分析，建立了距離權(quán)重、方位權(quán)重、方向權(quán)重和連通性權(quán)重組成的權(quán)重模型；然后，根據(jù)GPS軌跡點(diǎn)自身屬性信息，建立了動(dòng)態(tài)權(quán)重系數(shù)模型；最后，根據(jù)置信度水平選擇最佳匹配路段。用三條總長(zhǎng)36 km的重慶城市公交車(chē)行駛軌跡進(jìn)行測(cè)試，結(jié)果顯示：所提算法平均匹配正確率達(dá)到97.31%，單個(gè)軌跡點(diǎn)匹配平均延遲為17.9 ms。新算法匹配正確率和實(shí)時(shí)性較高，在Y形路口和平行路段的匹配效果上優(yōu)于對(duì)比算法。

地圖匹配；動(dòng)態(tài)權(quán)重；全球定位系統(tǒng)軌跡；時(shí)空特性；智能交通系統(tǒng)

0 引言

目前，許多智能交通系統(tǒng)(Intelligent Transportation System， ITS)應(yīng)用服務(wù)，如車(chē)輛導(dǎo)航、出行路線(xiàn)規(guī)劃、交通流量管理、交通事故預(yù)警與處置、公交到站時(shí)間預(yù)測(cè)等都需要位置信息。近年來(lái)，隨著智能終端技術(shù)發(fā)展與普及，各種車(chē)輛和移動(dòng)終端已將全球定位系統(tǒng)(Global Positioning System, GPS)模塊作為標(biāo)配，GPS已成為ITS應(yīng)用服務(wù)提供位置信息的主流定位技術(shù)。

盡管GPS技術(shù)已很成熟，但由于城市道路密集且形狀復(fù)雜，在車(chē)輛經(jīng)過(guò)多層立交橋、隧道或高層建筑時(shí)，GPS信號(hào)會(huì)丟失或變差。此外，電子地圖中的道路也存在誤差，定位數(shù)據(jù)并不能直接正確顯示到電子地圖中的道路上。地圖匹配作為一種位置修正技術(shù)可以解決這個(gè)問(wèn)題。

地圖匹配算法是以定位系統(tǒng)(GPS或GPS/DR等)產(chǎn)生的軌跡數(shù)據(jù)以及高精度路網(wǎng)數(shù)據(jù)作為輸入，以此來(lái)識(shí)別車(chē)輛正在行駛的正確路段并確定車(chē)輛在路段上的位置[1]。目前，實(shí)時(shí)地圖匹配算法可以分為簡(jiǎn)單匹配算法、基于權(quán)重匹配算法和高級(jí)匹配算法三類(lèi)[2]。簡(jiǎn)單匹配算法僅考慮了道路網(wǎng)的幾何形狀，算法簡(jiǎn)單但是在交叉路和平行路段匹配精度不高[3]；基于權(quán)重匹配算法除了考慮道路網(wǎng)的幾何形狀外，還綜合考慮了道路間的連接或連通關(guān)系，?；趲讉€(gè)度量指標(biāo)如距離、方向等給每條候選路段打分，然后選擇得分最高路段作為匹配路段[4-6]；高級(jí)匹配算法會(huì)利用數(shù)學(xué)模型如隱馬爾可夫模型(Hidden Markov Model，HMM)[7-9]、模糊邏輯[10-11]、D-S(Dempster-Shafer)證據(jù)理論[12]、卡爾曼濾波等來(lái)給候選路段計(jì)算分?jǐn)?shù)，并選擇得分最高路段作為匹配路段。盡管高級(jí)匹配算法匹配正確率一般比基于權(quán)重算法高，但是高級(jí)算法具有更高的復(fù)雜度，可能會(huì)產(chǎn)生較大的匹配延遲[2]。

目前基于權(quán)重匹配算法的準(zhǔn)確率介于簡(jiǎn)單匹配算法和高級(jí)匹配算法之間，但其算法復(fù)雜性低，比較適合實(shí)時(shí)地圖匹配。文獻(xiàn)[4]就該類(lèi)算法的權(quán)重系數(shù)為經(jīng)驗(yàn)常數(shù)，不能適應(yīng)匹配場(chǎng)景變化[2]的問(wèn)題進(jìn)行了改進(jìn)：根據(jù)每個(gè)GPS軌跡點(diǎn)自身的水平精度、速度、與上一個(gè)GPS軌跡點(diǎn)的行駛距離，建立了三個(gè)權(quán)重系數(shù)函數(shù)，權(quán)重系數(shù)將隨著GPS軌跡點(diǎn)動(dòng)態(tài)變化，算法平均匹配正確率可達(dá)到92.19%。但是，該算法權(quán)重僅考慮了當(dāng)前GPS軌跡點(diǎn)及候選路段的拓?fù)湫畔?，沒(méi)有考慮與歷史匹配路段的時(shí)空關(guān)系，因此在GPS信號(hào)質(zhì)量差時(shí)，可能會(huì)在平行路段及道路夾角很小路段出現(xiàn)誤匹配。本文針對(duì)該類(lèi)問(wèn)題，考慮GPS軌跡的時(shí)空特性，提出了一種改進(jìn)的基于動(dòng)態(tài)權(quán)重的實(shí)時(shí)地圖匹配算法。該算法主要特點(diǎn)表現(xiàn)在以下幾方面：

1)增加道路連通性權(quán)重，這可以解決跳段問(wèn)題[2]和平行道路匹配問(wèn)題；

2)除距離權(quán)重外的其他三個(gè)權(quán)重都考慮了與歷史匹配點(diǎn)和匹配路段的時(shí)空關(guān)系，可以解決包括Y形道路在內(nèi)的多支路道路的匹配；

3)權(quán)重系數(shù)隨著GPS軌跡點(diǎn)動(dòng)態(tài)變化，可以解決由于候選路段得分很相近導(dǎo)致的“過(guò)度擬合”型匹配錯(cuò)誤。

1 地圖匹配基本概念

GPS軌跡T是由裝有GPS模塊的設(shè)備采集的，由一系列按時(shí)間先后順序記錄的GPS軌跡點(diǎn)組成的集合，表示為T(mén)={p1,p2,…,pn}。每個(gè)GPS軌跡點(diǎn)具有6個(gè)屬性，表示為向量：

pi=[lon,lat,t,v,comp,hdop]

其中:pi.lon是經(jīng)度，pi.lat是緯度，pi.t是記錄時(shí)間戳，pi.v是瞬時(shí)速度，pi.comp是瞬時(shí)方向，pi.hdop是水平精度。

本文將路網(wǎng)當(dāng)作一個(gè)有向圖G，G中的頂點(diǎn)是路網(wǎng)的道路節(jié)點(diǎn)，具有經(jīng)度、緯度屬性。如圖1，路段r1是連接N1、N2兩個(gè)道路節(jié)點(diǎn)的有向邊，表示G中道路的中心線(xiàn)。路段r有5個(gè)屬性，表示為向量：

r=[dir,len,type,start,end]

其中:r.dir是路段通行方向，r.len是路段長(zhǎng)度，r.type是路段類(lèi)型(國(guó)道、高速路等)，r.start是路段點(diǎn)，r.end是路段終點(diǎn)。彎道由多條路段表示。

圖1 路段

Fig. 1 Road segment

2 一種動(dòng)態(tài)權(quán)重實(shí)時(shí)匹配算法

算法的總體邏輯如圖2。

圖2 算法總體邏輯框圖Fig. 2 Overview of algorithm framework

2.1 選取候選路段

地圖匹配算法實(shí)質(zhì)是從整個(gè)路網(wǎng)(解空間)尋找最優(yōu)路徑的一種搜索算法。尋找候選路段過(guò)程就是對(duì)解空間剪枝，簡(jiǎn)單快速的候選路段選取方法能大大提高算法的匹配效率。目前已有的方案有誤差橢圓法和網(wǎng)格搜索法：誤差橢圓法[10，13]數(shù)學(xué)理論復(fù)雜，而且實(shí)現(xiàn)比較復(fù)雜，對(duì)算法效率可能影響較大；網(wǎng)格搜索法[14-15]的搜索效率非常高，但是對(duì)地圖數(shù)據(jù)建立網(wǎng)格索引是一個(gè)較復(fù)雜的過(guò)程。

圖3 基于誤差圓選取候選路段Fig. 3 Candidate road segments selection based on error circle

為了簡(jiǎn)單但又不失效率和準(zhǔn)確性，本文采用誤差圓法。如圖3，以GPS軌跡點(diǎn)pi為圓心，其精度R為半徑得到誤差圓，任何被誤差圓包含的路段和與誤差圓所在區(qū)域相交或相切的路段都將被選作pi的候選路段：

這解決了基于道路節(jié)點(diǎn)的誤差圓法可能找不到候選路段的問(wèn)題。

2.2 計(jì)算各候選路段的總得分

本文基于四個(gè)指標(biāo)，即距離權(quán)重、方位權(quán)重、方向權(quán)重和連通性權(quán)重，對(duì)每條候選路段打分。具體細(xì)節(jié)將在稍后各小節(jié)詳述。

2.2.1 距離權(quán)重

圖4 GPS軌跡點(diǎn)到候選路段距離Fig. 4 Perpendicular projection distance to candidate road segment of GPS points

(1)

將其值歸一化到[0，1],得到距離權(quán)重計(jì)算公式：

(2)

(3)

利用5 700個(gè)GPS軌跡點(diǎn)計(jì)算出σg=17.15。

2.2.2 方位權(quán)重

(4)

(5)

圖5 計(jì)算方位權(quán)重的兩種情況Fig. 5 Two cases of heading weight calculation

當(dāng)車(chē)輛轉(zhuǎn)彎時(shí)，GPS軌跡點(diǎn)瞬時(shí)方向隨著道路方向變化而變化，因此當(dāng)pi有歷史匹配信息時(shí)，如圖5(b)，結(jié)合歷史軌跡點(diǎn)和歷史匹配路段的方向信息描述該變化趨勢(shì)，用式(6)計(jì)算方位權(quán)重，降低方位權(quán)重對(duì)方向誤差的敏感度：

(6)

2.2.3 方向權(quán)重

圖6 方向權(quán)重Fig. 6 Direction weight

(7)

(8)

2.2.4 連通性權(quán)重

全局匹配算法的正確率一般比實(shí)時(shí)匹配算法高，原因是全局算法考慮了歷史GPS軌跡點(diǎn)及路匹配段的信息。而實(shí)時(shí)匹配算法很多都只考慮了當(dāng)前GPS軌跡點(diǎn)及其候選路段的信息，沒(méi)有考慮歷史因素。本文提出連通性權(quán)重來(lái)描述當(dāng)前GPS軌跡點(diǎn)與歷史GPS軌跡點(diǎn)及匹配路段的時(shí)空關(guān)系。

圖7 連通性權(quán)重Fig. 7 Connectivity weight

(9)

2)GPS軌跡點(diǎn)采樣間隔大于5 s。這時(shí)用第一種方式計(jì)算平均速度就不合適了，此時(shí)ltravel近似等于相鄰GPS軌跡點(diǎn)間的歐拉距離，即ltravel=lpi-1→pi。

3)當(dāng)車(chē)輛在經(jīng)過(guò)隧道或立交橋時(shí)， GPS信號(hào)丟失導(dǎo)致采樣時(shí)間間隔變大，可能長(zhǎng)達(dá)數(shù)分鐘。這期間車(chē)輛的速度變化可能會(huì)很大，這時(shí)ltravel=lpi-1→pi。

圖8 連通性權(quán)重對(duì)平行道路匹配的影響Fig. 8 Influence of connectivity weight on parallel road’s matching

2.3 權(quán)重系數(shù)的確定

[4]，本文選擇以下函數(shù)來(lái)計(jì)算各個(gè)權(quán)重的權(quán)重系數(shù)，對(duì)于不同的GPS軌跡點(diǎn)進(jìn)行匹配時(shí)將采用不同權(quán)重系數(shù)。

Wdisti=

(10)

Wheadi=

(11)

(12)

(13)

2.4 獲取最佳匹配路段

以往實(shí)時(shí)匹配算法一般分三個(gè)階段[2]：初始位置匹配、跟蹤匹配、路口路段匹配。路口路段匹配階段需要進(jìn)行路口檢測(cè)，這無(wú)疑增加了算法的復(fù)雜性。本文算法將跟蹤匹配和路口路段匹配合并為一個(gè)階段，不再進(jìn)行路口檢測(cè)以算法簡(jiǎn)化模型，即分為兩個(gè)階段：初始位置匹配、后續(xù)位置匹配。

(14)

(15)

2.4.1 初始位置匹配

(16)

2.4.2 后續(xù)位置匹配

(17)

其中Ki為匹配置信度水平，該值越大匹配正確的信心越高。如果pi僅有一條候選路段，則直接將點(diǎn)匹配到該路段。參考文獻(xiàn)[4]，本文用式(18)計(jì)算置信度Ki,匹配不同GPS軌跡點(diǎn)采用不同的置信度。

在計(jì)算出pi的匹配路段ri后，將pi垂直投影到ri,投影點(diǎn)就是車(chē)輛當(dāng)前的位置。如果投影點(diǎn)在ri的延長(zhǎng)線(xiàn)上，則將ri更靠近pi的端點(diǎn)作為車(chē)輛當(dāng)前的位置。

(18)

3 算法評(píng)估與結(jié)果

3.1 實(shí)驗(yàn)環(huán)境準(zhǔn)備

地圖數(shù)據(jù)為開(kāi)源地圖OpenStreetMap；GPS軌跡為三條重慶市區(qū)公交車(chē)軌跡，包含道路類(lèi)型有立交橋、隧道等特殊路段，軌跡點(diǎn)采集時(shí)間間隔為1～3 s；地理信息系統(tǒng)(Geographic Information System， GIS)引擎為github開(kāi)源項(xiàng)目GraphHopper, 用于計(jì)算候選路段方向、最短路徑等。實(shí)驗(yàn)平臺(tái)基于Java實(shí)現(xiàn)，平臺(tái)硬件配置為：內(nèi)存4 GB，CPU型號(hào)為Intel Core i3- 2310M 2.1 GHz。

由于OpenStreetMap地圖數(shù)據(jù)并不完備，一些非主干道數(shù)據(jù)存在缺失，導(dǎo)致GPS軌跡中部分軌跡點(diǎn)無(wú)法找到正確的匹配路段，因此將這部分GPS軌跡點(diǎn)提前去除。表1中列舉了實(shí)驗(yàn)軌跡的一些特征信息。 根據(jù)三條軌跡中所有GPS軌跡點(diǎn)的pi.v和pi.hdop確定距離權(quán)重系數(shù)函數(shù)和方位權(quán)重系數(shù)函數(shù)中的常數(shù)，利用MAD公式計(jì)算得到：V1=2.35 m/s,V2=3.35 m/s,HDOP1=4,HDOP2=7。

3.2 實(shí)驗(yàn)結(jié)果

表2是本文提出算法的性能評(píng)估結(jié)果?？梢钥吹狡骄?5.6%的GPS軌跡點(diǎn)被匹配到了道路上，表明計(jì)算出的平均延遲比較可靠，不會(huì)因?yàn)樘嘬壽E點(diǎn)未被匹配到道路而導(dǎo)致算法長(zhǎng)時(shí)間不更新車(chē)輛位置。

如圖9(a)，從軌跡點(diǎn)的候選路段可以看出車(chē)輛經(jīng)過(guò)了一個(gè)Y形路口，盡管GPS軌跡點(diǎn)距離誤差很大，但算法仍匹配正確，而以往實(shí)時(shí)匹配算法在Y形路口很容易發(fā)生誤匹配[1]。如圖9(b)，從立交橋處軌跡點(diǎn)的候選路段平行且方向一樣可以看出這是平行路段，最終算法將軌跡點(diǎn)匹配到了正確路段。如圖9(c)，車(chē)輛經(jīng)過(guò)U形路口(圓圈處)時(shí)，由于連續(xù)多個(gè)GPS軌跡點(diǎn)速度為0，導(dǎo)致匹配錯(cuò)誤軌跡點(diǎn)的方向權(quán)重和方位權(quán)重都為0。而且在U形路口，兩條候選路段與歷史匹配路段都能連通，導(dǎo)致連通權(quán)重也失效。最終起作用的只有距離權(quán)重，但是GPS軌跡點(diǎn)距離誤差很大，因而導(dǎo)致了匹配錯(cuò)誤。

表3將本文算法與其他幾種實(shí)時(shí)地圖匹配算法進(jìn)行了對(duì)比。本文算法匹配正確率比以往基于權(quán)重匹配算法都高，甚至超過(guò)了高級(jí)匹配算法[7]基于HMM的匹配準(zhǔn)確率。

表1 GPS軌跡數(shù)據(jù)特征Tab. 1 Characteristics of GPS trajectories

表2 本文提出算法的性能評(píng)估結(jié)果Tab. 2 Performance evaluation results by proposed map matching algorithm

圖9 實(shí)驗(yàn)匹配情況Fig. 9 Experimental results of map matching表3 本文提出算法與已有算法性能比較Tab. 3 Comparison of the proposed algorithm with other exsiting algorithms

算法路段匹配基準(zhǔn)測(cè)試環(huán)境導(dǎo)航傳感器類(lèi)型地圖匹配模型文獻(xiàn)中給出的匹配準(zhǔn)確率/%本文算法距離、方位變化、方向變化、連通性重慶市區(qū)GPS基于權(quán)重97.31文獻(xiàn)[4]方法距離、方位變化、方向變化、連通性芝加哥市區(qū)GPS基于權(quán)重92.19文獻(xiàn)[6]方法距離、方位變化、方向變化倫敦市區(qū)GPS/DR基于權(quán)重88.60文獻(xiàn)[7]方法距離、連通性新加坡市區(qū)GPSHMM92.10文獻(xiàn)[11]方法距離、方位變化、方向變化、連通性倫敦市區(qū)GPS/DR模糊邏輯98.50

4 結(jié)語(yǔ)

在總結(jié)以往全局地圖匹配算法和實(shí)時(shí)匹配算法的優(yōu)缺點(diǎn)后，本文提出了一種改進(jìn)的基于動(dòng)態(tài)權(quán)重的實(shí)時(shí)地圖匹配算法。基于對(duì)道路網(wǎng)和GPS軌跡時(shí)空信息的分析，該算法建立了由四個(gè)權(quán)重組成的權(quán)重模型：1)距離權(quán)重，即GPS軌跡點(diǎn)到候選路段距離；2)方位權(quán)重，即相鄰GPS軌跡點(diǎn)瞬時(shí)方向的變化程度與候選路段相對(duì)上一條匹配路段方向的變化程度間的相似性；3)方向權(quán)重，即相鄰GPS軌跡點(diǎn)間連線(xiàn)的方向與候選路段方向間的相似性；4)連通性權(quán)重，即連通性候選路段和上一條匹配路段間的連通性。然后利用GPS軌跡點(diǎn)的速度、水平精度衰減因子hdop等信息建立各權(quán)重對(duì)應(yīng)的動(dòng)態(tài)權(quán)重系數(shù)函數(shù)，進(jìn)而得到每條候選路段的總得分。最后，算法根據(jù)每個(gè)軌跡點(diǎn)的匹配置信度水平得到最佳匹配路段。

本文基于總長(zhǎng)36 km的3條真實(shí)軌跡對(duì)算法進(jìn)行評(píng)估，結(jié)果表明：1)本文算法能正確匹配Y形道路、平行道路，甚至能對(duì)立交橋的彎道有比較好的匹配效果，然而在U形路口處匹配錯(cuò)誤表明算法在對(duì)低速下行駛車(chē)輛的匹配仍有待提高；2)本文算法的平均匹配正確率為97.31%，優(yōu)于現(xiàn)有的基于權(quán)重匹配算法，單個(gè)軌跡點(diǎn)匹配平均延遲為17.9 ms，滿(mǎn)足ITS應(yīng)用對(duì)準(zhǔn)確性和實(shí)時(shí)性的要求。研究也說(shuō)明充分利用路網(wǎng)和GPS軌跡點(diǎn)信息，權(quán)重匹配算法也可以達(dá)到高級(jí)算法的匹配正確率，但由于它不像高級(jí)算法那樣復(fù)雜，實(shí)時(shí)性能更高。但本文算法的性能也可能受到了實(shí)驗(yàn)平臺(tái)和電子地圖精度的限制，以及低速下的匹配精度仍有進(jìn)一步提升的空間，這將成為未來(lái)的研究方向。

參考文獻(xiàn)(References)

[1] QUDDUS M A, OCHIENG W Y, NOLAND R B. Current map-matching algorithms for transport applications: State-of-the art and future research directions [J]. Transportation Research Part C: Emerging Technologies, 2007, 15(5): 312-328.

[2] HASHEMI M, KARIMI H A. A critical review of real-time map-matching algorithms: Current issues and future directions [J]. Computers, Environment and Urban Systems, 2014, 48: 153-165.

[3] KIM J-S. Node based map matching algorithm for car navigation system [C]// Proceedings of the 29th International Symposium on Automotive Technology & Automation. Croydon, England: Automotive Automation Ltd., 1996.

[4] HASHEMI M, KARIMI H A. A weight-based map-matching algorithm for vehicle navigation in complex urban networks [J]. Journal of Intelligent Transportation Systems, 2016, 20(6): 573-590.

[5] 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, 17(6): 672-683.

[6] QUDDUS M A, OCHIENG W Y, ZHAO L, et al. A general map matching algorithm for transport telematics applications [J]. GPS Solutions, 2003, 7(3): 157-167.

[7] GOH C Y, DAUWELS J, MITROVIC N, et al. Online map-matching based on hidden Markov model for real-time traffic sensing applications [C]// ITSC 2015: Proceedings of the 2012 15th International IEEE Conference on Intelligent Transportation Systems. Piscataway, NJ: IEEE, 2012: 776-781.

[8] LOU Y, ZHANG C, ZHENG Y, et al. Map-matching for low-sampling-rate GPS trajectories [C]// Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2009: 352-361.

[9] NEWSON P, KRUMM J. Hidden Markov map matching through noise and sparseness [C]// GIS ’09: Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems. New York: ACM, 2009: 336-343.

[10] 鄭學(xué)遠(yuǎn).基于模糊邏輯的綜合地圖匹配方法研究與實(shí)現(xiàn)[D].北京：北京交通大學(xué),2014:29-53. (ZHENG X Y. The research and realization of integrated map matching method based on fuzzy logic [D]. Beijing: Beijing Jiaotong University, 2014: 29-53.)

[11] 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.

[12] 肖維麗,岳春生,奚玲.基于高程的改進(jìn)D-S證據(jù)理論地圖匹配算法[J].計(jì)算機(jī)應(yīng)用與軟件,2015,32(7):262-265. (XIAO W L, YUE C S, XI L. Improved D-S evidence theory map maching algorithm based on elevation information [J]. Computer Applications and Software, 2015, 32(7): 262-265.)

[13] 夏州.GPS車(chē)輛導(dǎo)航中的數(shù)據(jù)處理與地圖匹配研究[D]. 北京：北京交通大學(xué), 2009: 37-40. (XIA Z. Research of GPS data processing and map matching in vehicle navigation system [D]. Beijing: Beijing Jiaotong University, 2009: 37-40.)

[14] TANG Y, ZHU A D, XIAO X. An efficient algorithm for mapping vehicle trajectories onto road networks [C]// SIGSPATIAL ’12: Proceedings of the 20th International Conference on Advances in Geographic Information Systems. New York: ACM, 2012: 601-604.

[15] TAYLOR G, BLEWITT G, STEUP D, et al. Road reduction filtering for GPS-GIS navigation [J]. Transactions in GIS, 2001, 5(3): 193-207.

[16] OCHIENG W Y, QUDDUS M, NOLAND R B. Map-matching in complex urban road networks [J]. Brazilian Journal of Cartography, 2003, 55(2): 1-14.

This work is partially supported by Project Funded by China Post Doctoral Science Foundation (2014T70852), the Post-Doctoral Research Funds of Chongqing (XM201305), the Fundamental Research Funds for the Central Universities (106112014CDJZR188801), Key Projects of Chongqing Application Development Plan (cstc2014yykfB30003).

ZHENGLinjiang, born in 1983, Ph. D., associate professor. His research interests include intelligent transportation system, big data.

LIUXu, born in 1991, M. S. candidate. His research interests include intelligent transportation system, big data.

YIBing, born in 1971, senior engineer. His research interests include traffic engineering.

Dynamicweightedreal-timemapmatchingalgorithmconsideringspatio-temporalproperty

ZHENG Linjang1, LIU Xu1*, YI Bing2

(1.CollegeofComputerScience,ChongqingUniversity,Chongqing400044,China；2.ChongqingIntegratedTransportHubDevelopmentInvestmentCompanyLimited,Chongqing401121,China)

Focusing on the issue that current real-time map matching algorithms are difficult to keep high efficiency and high accuracy simultaneously, an improved dynamic weighted real-time map matching algorithm was proposed. Firstly, considering the temporal, speed, heading and direction constraints of Global Positioning System (GPS) points and the topological structures of road network, a weighted model was constructed in the algorithm based on spatio-temporal analysis, which consisted of proximity weight, heading weight, direction weight and connectivity weight. Then according to the properties of GPS points, a dynamic weighted coefficient model was created. Lastly, the best matching road segment was selected according to the confidence level of current GPS point. The experiments were conducted on three city bus trajectories with length of 36 km in Chongqing. The average matching accuracy of the algorithm was 97.31% and the average matching delay of each GPS point was 17.9 ms. The experimental results show that compared with the contrast algorithms, the proposed algorithm has higher accuracy and efficiency, and has better performance in matching Y-junctions and parallel roads.

map matching; dynamic weight; Global Positioning System (GPS) trajectory; spatio-temporal property; Intelligent Transportation System (ITS)

TP391.41

A

2017- 02- 20;

2017- 03- 21。

中國(guó)博士后科學(xué)基金特別資助項(xiàng)目(2014T70852)；重慶市博士后科研項(xiàng)目特別資助項(xiàng)目(XM201305)；中央高?；究蒲袠I(yè)務(wù)費(fèi)資助項(xiàng)目(106112014CDJZR188801)；重慶市應(yīng)用開(kāi)發(fā)計(jì)劃重點(diǎn)項(xiàng)目(cstc2014yykfB30003)。

鄭林江(1983—)，男，四川鄰水人，副教授，博士，CCF會(huì)員，主要研究方向：智能交通系統(tǒng)、大數(shù)據(jù)； 劉旭(1991—)，男，四川南充人，碩士研究生，主要研究方向：智能交通系統(tǒng)、大數(shù)據(jù)； 易兵(1971—)，男，湖南邵陽(yáng)人，高級(jí)工程師，主要研究方向：交通工程。

1001- 9081(2017)08- 2381- 06

10.11772/j.issn.1001- 9081.2017.08.2381