面向復雜城市道路網絡的GPS軌跡匹配算法

劉　張，王心迪，閆小勇

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

·復雜性科學·

面向復雜城市道路網絡的GPS軌跡匹配算法

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

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

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

GPS軌跡;地圖匹配;道路網絡;出租車

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

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

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

1　軌跡匹配算法

1.1算法基本思路

在復雜的城市道路網絡中，對車輛的GPS軌跡進行地圖匹配的難點在于并行路段和復雜立交場景的處理，如圖1所示。由于在這些場景下某些軌跡點距離多條路段的距離都非常接近，單純根據一個軌跡點的信息很難判定該軌跡點真正處于哪條路段上。但如果從一串軌跡點的角度觀察，則很容易發(fā)現(xiàn)車輛能夠運行的路徑是非常有限的。如在圖1中，從該圖左下角的道路經過立交駛入左上角的道路，必須要通過立交右上方的左轉匝道才可能完成左轉過程。因此，處理并行路段和復雜立交場景下軌跡匹配的關鍵在于利用道路網絡的拓撲結構信息，找出軌跡首末點之間的可行路徑。在有多條可行路徑的前提下，則可以通過判斷軌跡點到不同路徑的距離，找到軌跡點最可能通過的路徑。

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

1)將路段長度作為道路網絡上連邊的基本權值；2)將每個軌跡點投影給周邊路段，用軌跡點到路段的距離來更新路段權值，使得投影軌跡點越多，距離軌跡點越近的路段獲得更低的權值；3)以權值最小為目標在軌跡首末點之間搜索一條路徑。該方法可以保證得到的路徑在拓撲上是正確的，同時由于用軌跡點到路段的距離更新路段權值，可以使所得路徑距離軌跡的整體距離最小，因此最終得到的路徑最有可能是軌跡點實際所處的路徑。

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

1.2算法步驟描述

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

初始化：根據道路地圖建立有向含權網絡模型，將道路路段作為網絡中的有向邊，路段長度作為邊的初始權值，路段相交處作為網絡節(jié)點。

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

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

3)用最短路徑算法搜索s和t點之間權值最小的路徑。

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

5)返回步驟1)，進行下一個軌跡片段的匹配。

圖2 算法流程示意圖

1.3算法實現(xiàn)要點

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

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

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

2)空間查詢的效率問題

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

3)路徑搜索的效率問題

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

圖3 根據軌跡點抽取子網示意圖

2　算法應用實例

2.1數(shù)據集描述

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

圖4 成都市道路網絡地圖

2.2算法匹配結果分析

圖5是本文算法的一個典型匹配結果。從圖中可以看到，不論車輛運行軌跡是通過兩座復雜立交的轉向匝道，還是在兩座立交之間的主輔路上進行切換，本文算法都給出了準確的匹配結果。這一結果在某種程度上驗證了本文算法能夠很好地處理復雜道路網絡條件下的車輛軌跡匹配問題。

圖5 算法匹配結果示意圖

圖6 軌跡長度T對匹配結果的影響

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

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

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

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

3　結 束 語

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

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

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

[1]王建輝,李愛光. 顧及多要素影響的路網匹配改進算法[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]周濤,韓筱璞,閆小勇,等. 人類行為時空特性的統(tǒng)計力學[J]. 電子科技大學學報,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)建設部. 城市道路交通規(guī)劃設計規(guī)范: GB50220-1995[S]. 北京: 建設部標準定額研究所,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

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

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