劉　張，王心迪，閆小勇

(1. 電子科技大學(xué)能源科學(xué)與工程學(xué)院　成都　611731；2. 成都師范學(xué)院物理與工程技術(shù)學(xué)院　成都　611130；3. 電子科技大學(xué)大數(shù)據(jù)研究中心　成都　611731；4. 電子科技大學(xué)英才實(shí)驗(yàn)學(xué)院　成都　611731；5. 北京交通大學(xué)交通運(yùn)輸學(xué)院　北京 海淀區(qū)　100044)

·復(fù)雜性科學(xué)·

面向復(fù)雜城市道路網(wǎng)絡(luò)的GPS軌跡匹配算法

劉張1,2,3，王心迪3,4，閆小勇3,5

(1. 電子科技大學(xué)能源科學(xué)與工程學(xué)院成都611731；2. 成都師范學(xué)院物理與工程技術(shù)學(xué)院成都611130；3. 電子科技大學(xué)大數(shù)據(jù)研究中心成都611731；4. 電子科技大學(xué)英才實(shí)驗(yàn)學(xué)院成都611731；5. 北京交通大學(xué)交通運(yùn)輸學(xué)院北京 海淀區(qū)100044)

車輛GPS軌跡的地圖匹配是交通大數(shù)據(jù)挖掘中的一項(xiàng)重要的基礎(chǔ)性工作，可靠的軌跡匹配結(jié)果對于道路交通運(yùn)行狀態(tài)監(jiān)測、實(shí)時(shí)交通信息發(fā)布、車輛定位與智能調(diào)度、出行路徑選擇行為分析等具有重要意義。由于城市道路網(wǎng)絡(luò)中大量存在高架路、主輔路和立體交叉等復(fù)雜的道路場景，傳統(tǒng)的地圖匹配算法在這些場景下難以對車輛軌跡進(jìn)行準(zhǔn)確匹配。針對這一問題，該文提出一種基于道路網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的軌跡匹配算法，將軌跡匹配問題轉(zhuǎn)換為在加權(quán)道路網(wǎng)絡(luò)中尋找最優(yōu)路徑的問題。利用成都市道路網(wǎng)絡(luò)中上萬輛出租車的實(shí)際運(yùn)行軌跡數(shù)據(jù)對本文算法進(jìn)行了驗(yàn)證，結(jié)果表明在復(fù)雜的城市道路網(wǎng)絡(luò)中應(yīng)用該算法能夠獲得較高的匹配成功率和準(zhǔn)確率。

GPS軌跡;地圖匹配;道路網(wǎng)絡(luò);出租車

車輛GPS軌跡匹配是利用GPS軌跡點(diǎn)數(shù)據(jù)和數(shù)字地圖信息，確定車輛在數(shù)字地圖上準(zhǔn)確位置的一種定位技術(shù)。實(shí)際中由于各種因素的影響，車載GPS設(shè)備得到的軌跡點(diǎn)和車輛真實(shí)位置之間總是存在誤差，這就需要利用軌跡匹配技術(shù)將獲取的軌跡點(diǎn)數(shù)據(jù)準(zhǔn)確匹配到數(shù)字地圖上[1]。GPS軌跡匹配技術(shù)被廣泛應(yīng)用于車輛定位[2]、城市計(jì)算[3-4]、人類移動(dòng)行為研究[5]、交通預(yù)測及引導(dǎo)[6-8]、搭乘服務(wù)[9-10]、交通異常事件檢測[11-13]等領(lǐng)域，準(zhǔn)確的軌跡匹配結(jié)果對于為這些領(lǐng)域提供可靠的基礎(chǔ)數(shù)據(jù)具有重要意義。

常見的GPS軌跡匹配算法主要有位置點(diǎn)匹配、軌跡相關(guān)算法、D-S證據(jù)理論算法、基于隱馬爾科夫模型的算法等。位置點(diǎn)匹配算法[14-15]是在多條候選路段中，選擇具有最小罰函數(shù)的路段作為匹配路段。其算法簡單，反應(yīng)速度快，但罰函數(shù)魯棒性差，對城市道路中的并行路段(一條道路同時(shí)包含主路和輔路，或高架道路和橋下道路水平位置重疊)容易造成誤判。軌跡相關(guān)算法[16]通過對比候選路段的航向增量，選擇具有最優(yōu)值的路段作為合理的匹配路段。該算法能夠矯正定位信息中的縱向誤差分量，但在GPS數(shù)據(jù)誤差增加、道路狀況變得復(fù)雜時(shí)，地圖匹配效果較差，無法對城市道路中復(fù)雜立交等場景進(jìn)行有效的處理。D-S證據(jù)理論算法[17]以距離和航向?yàn)樽C據(jù)，用信任函數(shù)計(jì)算某個(gè)證據(jù)對某條候選路段的支持程度，選擇支持度最大的候選路段作為當(dāng)前路段。該算法能夠處理不完備信息，但當(dāng)證據(jù)發(fā)生沖突時(shí)，容易出錯(cuò)?；陔[馬爾可夫模型(HMM)的地圖匹配算法[18-21]將車輛GPS軌跡點(diǎn)位置作為HMM中的觀察變量，將車輛實(shí)際所在位置作為HMM中的隱藏狀態(tài)變量，通過實(shí)際數(shù)據(jù)訓(xùn)練模型再進(jìn)行真實(shí)位置的預(yù)測。盡管在相對簡單的道路網(wǎng)絡(luò)場景下HMM方法已經(jīng)可以獲得很高的精確度，但對于復(fù)雜城市道路中大量存在并行路段、復(fù)雜立交等場景下該算法的適用性尚缺乏評估。

針對前述傳統(tǒng)GPS軌跡地圖匹配算法不能很好地處理復(fù)雜城市道路網(wǎng)絡(luò)中并行路段、復(fù)雜立交等場景下的軌跡匹配這一問題，本文提出了一種基于道路網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的GPS軌跡匹配算法，將軌跡匹配問題轉(zhuǎn)換為在加權(quán)的城市道路網(wǎng)絡(luò)中尋找最優(yōu)路徑的問題，并利用成都市道路網(wǎng)絡(luò)中上萬輛出租車的實(shí)際運(yùn)行軌跡數(shù)據(jù)對算法進(jìn)行了驗(yàn)證。

1　軌跡匹配算法

1.1算法基本思路

在復(fù)雜的城市道路網(wǎng)絡(luò)中，對車輛的GPS軌跡進(jìn)行地圖匹配的難點(diǎn)在于并行路段和復(fù)雜立交場景的處理，如圖1所示。由于在這些場景下某些軌跡點(diǎn)距離多條路段的距離都非常接近，單純根據(jù)一個(gè)軌跡點(diǎn)的信息很難判定該軌跡點(diǎn)真正處于哪條路段上。但如果從一串軌跡點(diǎn)的角度觀察，則很容易發(fā)現(xiàn)車輛能夠運(yùn)行的路徑是非常有限的。如在圖1中，從該圖左下角的道路經(jīng)過立交駛?cè)胱笊辖堑牡缆罚仨氁ㄟ^立交右上方的左轉(zhuǎn)匝道才可能完成左轉(zhuǎn)過程。因此，處理并行路段和復(fù)雜立交場景下軌跡匹配的關(guān)鍵在于利用道路網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息，找出軌跡首末點(diǎn)之間的可行路徑。在有多條可行路徑的前提下，則可以通過判斷軌跡點(diǎn)到不同路徑的距離，找到軌跡點(diǎn)最可能通過的路徑。

以上過程可以通過在加權(quán)道路網(wǎng)絡(luò)中搜索軌跡首末點(diǎn)之間的加權(quán)最短路徑來實(shí)現(xiàn)?；舅悸肥牵?/p>

1)將路段長度作為道路網(wǎng)絡(luò)上連邊的基本權(quán)值；2)將每個(gè)軌跡點(diǎn)投影給周邊路段，用軌跡點(diǎn)到路段的距離來更新路段權(quán)值，使得投影軌跡點(diǎn)越多，距離軌跡點(diǎn)越近的路段獲得更低的權(quán)值；3)以權(quán)值最小為目標(biāo)在軌跡首末點(diǎn)之間搜索一條路徑。該方法可以保證得到的路徑在拓?fù)渖鲜钦_的，同時(shí)由于用軌跡點(diǎn)到路段的距離更新路段權(quán)值，可以使所得路徑距離軌跡的整體距離最小，因此最終得到的路徑最有可能是軌跡點(diǎn)實(shí)際所處的路徑。

圖1 并行路段和復(fù)雜立交場景下的GPS軌跡

1.2算法步驟描述

下面給出該方法的具體實(shí)現(xiàn)步驟，算法流程如圖2所示。

初始化：根據(jù)道路地圖建立有向含權(quán)網(wǎng)絡(luò)模型，將道路路段作為網(wǎng)絡(luò)中的有向邊，路段長度作為邊的初始權(quán)值，路段相交處作為網(wǎng)絡(luò)節(jié)點(diǎn)。

1)從車輛運(yùn)行軌跡中截取時(shí)長為T的軌跡片段，將軌跡片段中的第一個(gè)點(diǎn)(記為s)連接到以s點(diǎn)為圓心、D為半徑的圓形所覆蓋的所有路段的起點(diǎn)上，并將s點(diǎn)到這些路段起點(diǎn)的權(quán)值設(shè)為0；同時(shí)將軌跡片段中的最后一個(gè)點(diǎn)(記為t)連接到以t點(diǎn)為圓心、D為半徑的圓形所覆蓋的所有路段的終點(diǎn)上，并將t點(diǎn)到這些路段終點(diǎn)的權(quán)值設(shè)為0。

2)對于軌跡片段中除s、t點(diǎn)之外的每個(gè)軌跡點(diǎn)o，找出以o為圓心、D為半徑的圓形范圍內(nèi)所覆蓋的路段l，將o到l的垂直距離Dol除以D作為權(quán)值更新系數(shù)，乘在l的權(quán)值上，得到新的路段權(quán)值，同時(shí)將點(diǎn)o的時(shí)間戳以及點(diǎn)o到路段l的距離Dol記錄在路段l上。

3)用最短路徑算法搜索s和t點(diǎn)之間權(quán)值最小的路徑。

4)從路徑起點(diǎn)到終點(diǎn)依次檢查路徑中包含的每條路段，以軌跡點(diǎn)到路段的距離為標(biāo)準(zhǔn)去除重復(fù)的軌跡點(diǎn)(即對于同一個(gè)軌跡點(diǎn)判斷它到哪條路段的距離更小就將它歸屬到哪條路段上)，得到軌跡點(diǎn)和路段的一一對應(yīng)關(guān)系，該段軌跡匹配工作完成。

5)返回步驟1)，進(jìn)行下一個(gè)軌跡片段的匹配。

圖2 算法流程示意圖

1.3算法實(shí)現(xiàn)要點(diǎn)

1)具體參數(shù)的選取

算法中包含兩個(gè)待定參數(shù)，一是軌跡片段的截取時(shí)長T，二是空間距離閾值D。對于軌跡片段的截取時(shí)長T，過長和過短都會(huì)影響軌跡匹配的成功率和準(zhǔn)確率，后續(xù)算法應(yīng)用實(shí)例部分會(huì)結(jié)合具體的應(yīng)用場景給出建議的T取值范圍。

對于空間距離閾值D，根據(jù)我國《城市道路交通規(guī)劃設(shè)計(jì)規(guī)范》[22]規(guī)定，城市道路中等級最高的快速路寬度為40～45 m，因此本文取道路的最大寬度為45 m，再考慮到車載GPS的定位誤差為± 15 m[23]，本文取D=60 m。這樣取值能夠保證如果某時(shí)刻車輛在某條道路上行駛，那么這條道路一定處在以該時(shí)刻車輛GPS軌跡點(diǎn)為圓心、60 m為半徑的圓形范圍內(nèi)。如果D取值小于60 m，可能有部分軌跡點(diǎn)無法找到匹配道路；而D取值大于60 m也不會(huì)增加算法精確度，只會(huì)增加空間查詢操作的工作量。

2)空間查詢的效率問題

前述算法中涉及到大量空間查詢操作(查找距離軌跡點(diǎn)D范圍內(nèi)的路段)，如果直接在全圖中進(jìn)行搜索，效率無疑是非常低的。因此，必須通過建立空間索引的方式，將全網(wǎng)中的路段按照一定的空間層次進(jìn)行預(yù)排列，以提高空間查詢的效率。本文采取了經(jīng)典的R樹索引結(jié)構(gòu)[24]為路段建立空間索引，可以有效提高路段空間查詢的效率。

3)路徑搜索的效率問題

常用的網(wǎng)絡(luò)最短路徑算法(如Dijkstra算法、Floyd算法等)的復(fù)雜度是O(n3)[25]，其中n是道路網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù)。一般大城市的道路網(wǎng)絡(luò)所包含的節(jié)點(diǎn)往往多達(dá)數(shù)萬個(gè)，在如此大規(guī)模的路網(wǎng)中反復(fù)進(jìn)行最短路徑搜索是非常耗時(shí)的。為提高路徑搜索效率，本文采用縮減網(wǎng)絡(luò)規(guī)模的辦法，即只在軌跡片段周邊一定范圍內(nèi)的路段所構(gòu)成的子網(wǎng)中搜索路徑。具體方法是：首先在軌跡片段中相鄰的兩個(gè)軌跡點(diǎn)之間連線，然后建立以連線為中心、半徑為D的緩沖區(qū)，最后將此緩沖區(qū)與整個(gè)路網(wǎng)進(jìn)行空間交集運(yùn)算，抽取一個(gè)路網(wǎng)子集，如圖3所示。在此子網(wǎng)上進(jìn)行最短路徑搜索，可以有效縮短搜索時(shí)間，提高整個(gè)算法的運(yùn)行效率。

圖3 根據(jù)軌跡點(diǎn)抽取子網(wǎng)示意圖

2　算法應(yīng)用實(shí)例

2.1數(shù)據(jù)集描述

本文用成都市出租車車載GPS所記錄的軌跡數(shù)據(jù)對算法進(jìn)行測試。該數(shù)據(jù)集中包含成都市13 933輛出租車在一天之內(nèi)的行駛記錄，每輛出租車的車載GPS設(shè)備以每10 s為間隔記載該車當(dāng)前所處的時(shí)間、經(jīng)緯度以及空重載狀態(tài)，共有數(shù)據(jù)76 071 067條。同時(shí)，本文還使用了圖4所示的成都市道路網(wǎng)絡(luò)數(shù)據(jù)，該數(shù)據(jù)集中記錄了成都市繞城高速以內(nèi)全部道路的拓?fù)浣Y(jié)構(gòu)和長度等信息，網(wǎng)絡(luò)中共包含路段30 658條，節(jié)點(diǎn)21 921個(gè)。

圖4 成都市道路網(wǎng)絡(luò)地圖

2.2算法匹配結(jié)果分析

圖5是本文算法的一個(gè)典型匹配結(jié)果。從圖中可以看到，不論車輛運(yùn)行軌跡是通過兩座復(fù)雜立交的轉(zhuǎn)向匝道，還是在兩座立交之間的主輔路上進(jìn)行切換，本文算法都給出了準(zhǔn)確的匹配結(jié)果。這一結(jié)果在某種程度上驗(yàn)證了本文算法能夠很好地處理復(fù)雜道路網(wǎng)絡(luò)條件下的車輛軌跡匹配問題。

圖5 算法匹配結(jié)果示意圖

圖6 軌跡長度T對匹配結(jié)果的影響

為對本文算法進(jìn)行更全面的測試，本文分析了在軌跡片段長度T取值不同的情況下，算法匹配成功率和準(zhǔn)確率的變化規(guī)律，結(jié)果如圖6所示。這里的成功率定義為：在所有被匹配的軌跡片段中，成功找到一條有效路徑的軌跡片段所占的比例。找不到一條有效路徑的情況主要是由于在T過小時(shí)，有較大比例的車輛可能停駛不動(dòng)或只移動(dòng)了很短的距離，使得算法無法搜索到一條權(quán)值大于0的路徑。因此，單純從提高算法匹配成功率的角度來看，T取值越大，出現(xiàn)車輛停駛的可能性就越低，匹配成功率就越高。但過大的T會(huì)降低算法匹配的準(zhǔn)確率。本文采用以下方法定義準(zhǔn)確率：對于成功匹配的軌跡片段，如果其中存在一個(gè)軌跡點(diǎn)距離所匹配路段的最大距離超過了60 m，本文認(rèn)為匹配結(jié)果是不可信的。這是由于在1.3節(jié)中已經(jīng)提到，綜合考慮GPS定位的誤差和城市道路最大寬度，一個(gè)軌跡點(diǎn)和它所匹配的道路距離超過60 m是不可能的。因此如果算法結(jié)果中出現(xiàn)了超過60 m的匹配距離則判定結(jié)果是錯(cuò)誤的，反之就認(rèn)為結(jié)果是準(zhǔn)確的。當(dāng)然這種準(zhǔn)確性也是相對的，因?yàn)槌钦嬲儡囕v的實(shí)際運(yùn)行路段，否則無法客觀地判定匹配結(jié)果的準(zhǔn)確性。根據(jù)準(zhǔn)確匹配軌跡片段在全部成功匹配軌跡片段中所占的比例，可以計(jì)算出算法匹配結(jié)果的準(zhǔn)確率。

從圖6的結(jié)果可以看到，隨著T的增大，算法匹配的準(zhǔn)確率逐漸下降。通過分析未能準(zhǔn)確匹配的軌跡片段特征，發(fā)現(xiàn)造成匹配錯(cuò)誤的原因主要有兩方面：一是真實(shí)路網(wǎng)中存在某些路段，但在地圖數(shù)據(jù)中這些路段卻是缺失的，如圖7a所示。在這種情況下，軌跡只能匹配到相對更近的道路上去，造成結(jié)果的偏差。二是車輛存在繞行的情況，即在一個(gè)軌跡片段中車輛兩次或多次經(jīng)過了同一個(gè)節(jié)點(diǎn)，導(dǎo)致路徑搜索算法忽略了繞行部分的路段(因?yàn)檫@樣總權(quán)值更小)，如圖7b所示。繞行的原因可能是出租車司機(jī)在繞行路段部分的某個(gè)地點(diǎn)放下乘客后又搭載了其他乘客，或者空車返回到其他地點(diǎn)載客等。

圖7 軌跡匹配不成功的兩種典型情況

在以上兩種情況中，第一種情況的改善依賴于道路網(wǎng)絡(luò)地圖完整度與準(zhǔn)確度的提高，與算法本身無關(guān)。理論上如果有一個(gè)完全準(zhǔn)確的路網(wǎng)地圖，這種情況不可能發(fā)生。但第二種情況則與軌跡片段長度T的取值有關(guān)，因?yàn)門越長，出租車將以更大的可能性返回之前走過的一條路段。綜合圖6中成功率和準(zhǔn)確率兩方面的結(jié)果，本文建議T取值在5～10 min之間是一個(gè)比較合理的范圍，這也與一般在線交通狀態(tài)發(fā)布的時(shí)間間隔要求相符合。

3　結(jié) 束 語

本文針對傳統(tǒng)的地圖匹配算法不能有效處理復(fù)雜城市道路網(wǎng)絡(luò)中并行路段和復(fù)雜立交場景下的車輛軌跡匹配的問題，提出了一種基于道路網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的軌跡匹配算法。該算法充分利用了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息，可確保找到的路徑一定是拓?fù)渖峡尚械穆窂健Ｍ瑫r(shí)，也充分考慮了軌跡點(diǎn)到路段的投影距離信息，使得最終匹配的路徑以很大的可能性是車輛真實(shí)運(yùn)行的路徑。通過在成都市大規(guī)模路網(wǎng)中上萬輛出租車的運(yùn)行軌跡數(shù)據(jù)對本文算法進(jìn)行了實(shí)際驗(yàn)證，結(jié)果表明在對軌跡片段長度進(jìn)行合理取值的情況下，本文算法能獲得較高的匹配成功率和準(zhǔn)確率，能夠滿足實(shí)際應(yīng)用的需求。這一研究結(jié)果為道路交通運(yùn)行狀態(tài)識(shí)別、在線交通信息發(fā)布、車輛定位與智能調(diào)度、出行路徑選擇行為分析等應(yīng)用領(lǐng)域中的車輛GPS軌跡匹配提供了一種全新的方法。

相對于傳統(tǒng)的地圖匹配算法，本文算法的主要缺點(diǎn)是計(jì)算效率較低，主要原因是本文算法需要反復(fù)進(jìn)行網(wǎng)絡(luò)路徑搜索和空間對象查詢等耗時(shí)較高的運(yùn)算。在實(shí)際應(yīng)用中，可以從以下3方面著手提高該算法的計(jì)算效率：1)采用更為高效的最短路徑搜索算法，例如基于堆結(jié)構(gòu)和桶結(jié)構(gòu)優(yōu)先級隊(duì)列的最短路徑搜索算法[25]；2)采用更為高級的空間索引結(jié)構(gòu)對路段進(jìn)行索引，進(jìn)一步提高空間查詢效率；3)由于本文算法對不同軌跡片段的匹配是完全分開處理的，因此非常適合采用并行計(jì)算的方法，可從根本上提升算法的計(jì)算效率。

本文的研究工作得到成都師范學(xué)院科研項(xiàng)目(CS142B02)以及成都市委政研室提供的基礎(chǔ)數(shù)據(jù)的資助，在此表示感謝。

[1]王建輝,李愛光. 顧及多要素影響的路網(wǎng)匹配改進(jìn)算法[J]. 測繪與空間地理信息,2015,38(3): 109-113. WANG Jian-hui,LI Ai-guang. Improved algorithm of network matching base on multi factors influence[J]. Geomatics & Spatial Information Technology,2015,38(3): 109-113.

[2]YUAN J,ZHENG Y,ZHANG L,et al. Where to find my next passenger[C]//Proceedings of the 13th International Conference on Ubiquitous Computing. New York: ACM,2011: 109-118.

[3]ZHENG Y,LIU Y,YUAN J,et al. Urban computing with taxicabs[C]//Proceedings of the 13th International Conference on Ubiquitous Computing. [S.l.]: ACM,2011: 89-98.

[4]YUAN J,ZHENG Y,XIE X. Discovering regions of different functions in a city using human mobility and POIs[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. [S.l.]: ACM,2012: 186-194.

[5]周濤,韓筱璞,閆小勇,等. 人類行為時(shí)空特性的統(tǒng)計(jì)力學(xué)[J]. 電子科技大學(xué)學(xué)報(bào),2013,42(4): 481-540.ZHOU Tao,HAN Xiao-pu,YAN Xiao-yong,et al. Statistical mechanics on temporal and spatial activities of human[J]. Journal of University of Electronic Science and Technology of China,2013,42(4): 481-540.

[6]YUAN J,ZHENG Y,ZHANG C,et al. T-drive: Driving directions based on taxi trajectories[C]//Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM,2010: 99-108.

[7]JENELIUS E,KOUTSOPOULOS H N. Travel time estimation for urban road networks using low frequency probe vehicle data[J]. Transportation Research Part B: Methodological,2013,53: 64-81.

[8]YUAN J,ZHENG Y,XIE X,et al. Driving with knowledge from the physical world[C]//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. California: ACM,2011: 316-324.

[9]MA S,ZHENG Y,WOLFSON O. T-share: a large-scale dynamic taxi ridesharing service[C]//2013 IEEE 29th International Conference on Data Engineering (ICDE). [S.l.]: IEEE,2013: 410-421.

[10]HE W,LI D,ZHANG T,et al. Mining regular routes from GPS data for ridesharing recommendations[C]// Proceedings of the ACM SIGKDD International Workshop on Urban Computing. New York: ACM,2012: 79-86.

[11]CHAWLA S,ZHENG Y,HU J. Inferring the root cause in road traffic anomalies[C]//12th IEEE International Conference on Data Mining. Brussels: ICDM,2012: 141-150.

[12]ZHANG J T. Smarter outlier detection and deeper understanding of large-scale taxi trip records: a case study of NYC[C]//Proceedings of the ACM SIGKDD International Workshop on Urban Computing. New York: ACM,2012: 157-162.

[13]CHEN C,ZHANG D,CASTRO P S,et al. iBOAT: Isolation-based online anomalous trajectory detection[J]. IEEE Transaction on Intelligent Transportation Systems,2013,14(2): 806-818.

[14]ERIC C A. Land-vehicle navigation system: an examination of the influence of individual navigation aids on system performance[D]. California: Stanford University,1997.

[15]SINN K,JONG H K. Adaptive fuzzy-network-based c-measure map-matching algorithm for car navigation system[J]. IEEE Transaction on Industrial Electronics,2001,48(2): 432-441.

[16]BISHNU P P. Adaptive trajectory segmentation method and its application in in-car navigation system[D]. Columbus,Ohio: The Ohio State University,2001.

[17]CHEN Z W,SUN Y R,YUAN X. Development of an algorithm for car navigation system based on dempstershafer evidence reasoning[C]//5th International IEEE Conference on Intelligent Transportation Systems. Singapore: IEEE,2002: 534-537.

[18]LOU Y,ZHANG C Y,ZHENG Y,et al. Map-matching for low-sampling-rate GPS trajectories[C]//Proceedings of the 17th ACM SIGSPATIAL. Seattle,WA: ACM,2009: 352-361.

[19]NEWSON P,KRUMM J. Hidden Markov map matching through noise and sparseness[C]//Proceedings of the 17th ACM SIGSPATIAL. Redmond,WA: ACM,2009: 336-343. [20]RAYMOND R,MORIMURA T,OSOGAMI T,et al. Map matching with hidden Markov model on sampled road network[C]//21st International Conference on Pattern Recognition. Tsukuba: [s.n.],2012: 2242-2245.

[21]GOH C Y,DAUWELS J,MITROVIC N,et al. Online map-matching based on hidden markov model for real-time traffic sensing applications[C]//15th International IEEE Conference on ITSC. Anchorage. Alaska: [s.n.],2012: 776-781.

[22]中華人民共和國住房和城鄉(xiāng)建設(shè)部. 城市道路交通規(guī)劃設(shè)計(jì)規(guī)范: GB50220-1995[S]. 北京: 建設(shè)部標(biāo)準(zhǔn)定額研究所,1995. MOHURD. Code for transport planning and design on urban road: GB50220-1995[S]: Beijing: Research Institute of Standard Quota of Ministry of Construction,1995.

[23]ZAIDI A S,SUDDLE M R. Global navigation satellite systems: a survey[C]//International Conference on Advances in Space Technologies. [S.l.]: IEEE,2006: 84-87.

[24]GUTTMAN A. R-Trees: a dynamic index structure for spatial searching[C]//Proceedings of the 1984 ACM SIGMOD. Boston: ACM,1984: 47-57.

[25]ZHAN F B. Three fastest shortest path algorithms on real road networks[J]. Journal of Geographic Information and Decision Analysis,1997,1(1): 70-82.

編輯蔣曉

Map-Matching Algorithm for GPS Trajectories in Complex Urban Road Networks

LIU Zhang1,2,3,WANG Xin-di3,4,and YAN Xiao-yong3,5
(1. School of Energy Science and Engineering,University of Electronic Science and Technology of ChinaChengdu611731; 2. College of Physics and Engineering,Chengdu Normal UniversityChengdu611130; 3. Big Data Research Center,University of Electronic Science and Technology of ChinaChengdu611731; 4. Yingcai Honors College,University of Electronic Science and Technology of ChinaChengdu611731; 5. School of Traffic and Transportation,Beijing Jiaotong UniversityHaidian Beijing100044)

Map-matching for GPS trajectories is a key groundwork in mining transportation data. Reliable matching results are significant for monitoring traffic situation,publishing real-time transportation information,vehicle tracking,smart vehicle dispatching,and routing behavior analysis. In real urban road networks,there are numerous complicated road structures such as elevated roads,frontage roads,and interchange bridges. Traditional map-matching algorithms could not match trajectories on these structures accurately. In this paper,we propose a map-matching algorithm based on the topological structure of the road networks and transform the problem of matching GPS trajectories in road map into the problem of finding the shortest path in a weighted road network. We test the algorithm with the real data of GPS trajectories of tens of thousands of taxis in Chengdu. The results show that the presented algorithm can acquire a high success ratio and accuracy ratio in complicated urban road networks.

GPS trajectories;map-matching algorithm;road networks;taxi

TP301.6

A

10.3969/j.issn.1001-0548.2016.06.023

2015 ? 07 ? 21；

2016 ? 03 ? 15

國家自然科學(xué)基金(61304177,71671015)；四川省教育廳科研項(xiàng)目(15ZB0345)

劉張(1979 ? )，男，博士生，主要從事交通大數(shù)據(jù)挖掘方向的研究.