湯文蘊 馬健霄 楊震

摘 要：為了提高交通網(wǎng)絡(luò)中離線地圖匹配算法的準確率，避免在離線地圖匹配過程中出現(xiàn)路段匹配錯誤的情況，本文基于多路徑的原則，提出在路徑節(jié)點進行迭代的基本思路，通過數(shù)據(jù)預(yù)處理、構(gòu)建子網(wǎng)絡(luò)、構(gòu)建初始使用路徑、建立節(jié)點與路段的關(guān)聯(lián)矩陣、構(gòu)建潛在路徑集以及確定最終選擇路徑等6個步驟來實現(xiàn)。本文詳細介紹所提離線地圖匹配算法的詳細流程，本算法思路清晰易實現(xiàn)。通過將算法應(yīng)用于美國明尼阿波利斯-圣保羅都市圈的GPS數(shù)據(jù)處理中，發(fā)現(xiàn)本算法的準確率整體較高，隨著出行距離的增加，算法的準確率會逐步降低。與基于最短路徑的算法相比，本文算法的準確性更高，尤其是在遠距離出行中，本算法更具有優(yōu)越性。

關(guān)鍵詞：交通網(wǎng)絡(luò);GPS 軌跡;地圖匹配;多路徑

中圖分類號：U491 ? ?文獻標識碼：A ? 文章編號：1006-8023（2019）05-0106-07

Abstract：In order to increase the accuracy of off-line map matching algorithm in transport networks， and avoid matching a wrong link， the idea of iteration at the route node is proposed based on the principle of multi-route. The algorithm includes six steps： data pre-process， subnetwork generation， initial chosen route generation， associative matrix between nodes and links generation， generation of consideration set of routes and final chosen route. The detailed process of the proposed algorithm is referred in this paper， which is simple and easy to implement. The algorithm is used to process GPS data in Minneapolis-St. Paul Metropolitan area. From the application of the algorithm， it can be found that the accuracy is on a high level in total and decrease as the distance getting longer. And compared with the matching algorithm based on the shortest path， it is found that the accuracy of the algorithm in this paper is much better， especially when the distance is long.

Keywords：Transport network; GPS trajectory; map matching; multi route

0 引言

隨著GPS技術(shù)的廣泛應(yīng)用，大量車行、人行軌跡通過GPS設(shè)備收集、存儲并進行分析。在交通研究領(lǐng)域，GPS數(shù)據(jù)通過必要的處理，轉(zhuǎn)換為可用于模型估計的格式后，被用于分析出行目的、出行方式和出行路徑等[1-3]。在利用GPS數(shù)據(jù)進行出行路徑選擇行為分析之前，需要進行兩個重要步驟：地圖匹配和選擇集生成，其中地圖匹配過程是將GPS點的軌跡流匹配到相應(yīng)道路上，進而識別出行者所選擇的路徑。在車輛GPS定位過程中，雖然依靠差分技術(shù)、無線電信標和載波相位技術(shù)等方法，可以提高其定位精度，但是一方面這些方法成本高，另一方面精度提高后依然存在少許偏離，并且最終依然需要將軌跡點與拓撲網(wǎng)絡(luò)相對應(yīng)。因而地圖匹配算法作為一種直接可執(zhí)行、價廉的基于軟件技術(shù)的定位修正方法，在GIS領(lǐng)域成為一個經(jīng)典命題，已有一系列研究成果[4-5]。

目前已有的地圖匹配算法可分為在線地圖匹配算法和離線地圖匹配算法，其中在線地圖匹配算法的目標是將車輛的實時位置定位到地圖上，因此，在線地圖匹配算法的基本要求是將每個GPS點均匹配到路段上，相應(yīng)需要更高效快速的算法。而離線地圖匹配算法的研究對象是一條已給定的GPS軌跡路徑，它主要用于路徑選擇行為研究中，除了不需要對GPS點進行實時定位外，也不需要將每個GPS點進行匹配[6]。本文所提及的地圖匹配算法均為離線地圖匹配算法。在現(xiàn)有研究中，離線地圖匹配算法主要包括兩種類型：基于最短路徑[7-9]與基于多重假設(shè)技術(shù)[10-13]。本文在多重假設(shè)技術(shù)的基礎(chǔ)上，提出一種基于多路徑的交通網(wǎng)絡(luò)地圖匹配算法，所提出的方法，思路清晰便于實現(xiàn)，能有效的將GPS點準確的匹配到正確的路段上。此外，在已有基于多路徑的匹配算法[12]中，將每個GPS軌跡點進行迭代，并找到相應(yīng)的路徑，但是對于一次通勤出行，GPS軌跡點個數(shù)一般都在幾千個以上，因此，本文引入路徑節(jié)點概念，以此減少迭代次數(shù)，加快算法完成速率。通過比較發(fā)現(xiàn)，本文所提方法在準確性上明顯優(yōu)于基于最短路徑方法，而準確性是離線地圖匹配最重要的一項評價指標。

在關(guān)聯(lián)矩陣構(gòu)建過程中，分別以節(jié)點或路段為基礎(chǔ)構(gòu)建緩沖區(qū)，然后判斷路段或節(jié)點是否在緩沖區(qū)內(nèi)，其基本原理如ArcGIS[18]的原理類似，可避免出現(xiàn)反向搜索問題。

步驟 5：構(gòu)建潛在路徑集。

本算法從第一個路徑節(jié)點開始構(gòu)建潛在路徑集，即最靠近起點的那個路徑節(jié)點，然后依次考慮所有的路徑節(jié)點。在第一個路徑節(jié)點處，依據(jù)步驟4中所提的節(jié)點-路段關(guān)聯(lián)矩陣，找到與此路徑節(jié)點相關(guān)聯(lián)的路段，認為他是一條可選路段，同時，依據(jù)路段-節(jié)點關(guān)聯(lián)矩陣，可以獲得此路段另外一個端點，并判斷此端點是否是路徑節(jié)點，若是則將其標記為“正確節(jié)點”。若第一條可選路段是斷頭路，則將其標為無效路段，將起點附近的其他路段作為第一條可選路段，若不是則加入潛在路徑集。

在對某個路徑節(jié)點進行標記為“正確節(jié)點”之后，依據(jù)節(jié)點-路段關(guān)聯(lián)矩陣，除已記入在潛在路徑集中的路段之外，找到其他關(guān)聯(lián)路段，將這些路段標記為可選路段，并繼續(xù)分別“向前”對這些路段進行判斷。一旦某條路段為斷頭路，這條可選路段則被標記是無效路段，并將無效路段上的路徑節(jié)點標記為“錯誤節(jié)點”，然后對其他可選路段進行判斷分析，若不是斷頭路則加入潛在路徑集。

依照上述的方法，本算法繼續(xù)對子網(wǎng)絡(luò)里的其他路段進行判斷，直到路徑節(jié)點上所連接的所有路段均被分析考慮。直到所有的路徑節(jié)點均被檢查完，且滿足條件的可選路段均被加入潛在路徑集為止。如果被分析的路徑的端點是一個局部節(jié)點，其迭代方法與路徑節(jié)點的方法相同。

構(gòu)建潛在路徑集的具體步驟如圖2所示。

步驟 6：確定最終使用路徑。

當所有標記為“正確節(jié)點”的路徑節(jié)點被分析判斷過后，本算法將囊括所有的潛在路徑。最終，在潛在路徑集里，判斷某一條路徑上，所投影的GPS點數(shù)量最多，即是所選路徑。

2 實例應(yīng)用

本文所采用的數(shù)據(jù)取自美國明尼蘇達州明尼阿波利斯-圣保羅大都市圈于2011年做的居民出行行為調(diào)查，GPS設(shè)備被攜帶在調(diào)查者身上，通過GPS設(shè)備提供的信號，得到每秒鐘出行者所處的位置，以文獻[19-20]中小汽車通勤出行的GPS軌跡作為本文的研究對象。以某一束GPS軌跡為例，說明本算法的應(yīng)用。基礎(chǔ)地圖采用TLG（The Lawrence Group）地圖，其包含290 231條路段和113 864個節(jié)點，是研究區(qū)域內(nèi)最詳細的路網(wǎng)地圖之一。圖3所展示的是算法中步驟2的子網(wǎng)絡(luò)構(gòu)建過程，圖3（a）是某出行者的一次出行GPS軌跡點與電子地圖以及某區(qū)域的放大詳細圖，可以發(fā)現(xiàn)每個GPS點并沒有直接覆蓋在相應(yīng)的道路上，存在一定的偏差。接著以每個GPS點為中心，建立半徑為200 m的緩沖區(qū)，如圖3（b）所示，所建立的緩沖區(qū)與道路電子地圖的部分路段產(chǎn)生交集，將這些路段單獨提取出來建立新的道路網(wǎng)絡(luò)，即本算法中所需的子網(wǎng)絡(luò)，如圖3（c）所示。

對于基于最短路徑的地圖匹配算法，接下來就以此子網(wǎng)絡(luò)為基礎(chǔ)，從起點到終點尋找一條最短路徑即可，容易出現(xiàn)部分路段匹配錯誤的情況。而在本算法中提出“初始使用路徑”、“路徑節(jié)點”和“局部節(jié)點”，通過不停的路徑迭代，找到最后可選路徑集。圖4（a）展示了根據(jù)空間連接和最短路徑得到的初始使用路徑，從圖4（a）中可以看到，初始使用路徑包含了大部分出行者確實使用的路段，也包含部分未使用路段，同時還有部分使用路段未被包括在內(nèi)，主要體現(xiàn)為“斷頭路”和“環(huán)路”現(xiàn)象。以初始路徑為基礎(chǔ)，采用步驟3的方法創(chuàng)建路徑節(jié)點集和局部節(jié)點集，如圖4（b）所示，接著對每個節(jié)點和路段分別構(gòu)建路段-節(jié)點和節(jié)點-路段關(guān)聯(lián)矩陣。

構(gòu)建潛在路徑集是本算法中關(guān)鍵的一步，以如圖5（a）所示區(qū)域說明潛在路徑集的創(chuàng)建過程，根據(jù)GPS軌跡點，確定第一個路徑節(jié)點，然后根據(jù)此節(jié)點的節(jié)點-路段矩陣確認第一條可選路段，并得到它的另外一個端點的節(jié)點符號。在本示例中，這個節(jié)點是路徑節(jié)點，將其標記為“正確節(jié)點”，如圖5（b）所示。從被標記的路徑節(jié)點出發(fā)，有兩條路段，如圖5（c）所示，其中一條是斷頭路，因此將其標記為無效路段，由于其端點是一個局部節(jié)點，固不將其標記為“錯誤節(jié)點”，而在圖5（d）中，無效路段的端點是一個路徑節(jié)點，固將其標記為“錯誤節(jié)點”。在圖5（e）中，從路徑節(jié)點出發(fā)，除了一個無效路段外，還有兩條可選路段，則可根據(jù)這兩條可選路段建立兩條新的路徑加入到路徑集中。按此方法繼續(xù)對子網(wǎng)絡(luò)內(nèi)剩余部分進行迭代，并根據(jù)條件創(chuàng)建新的路徑加入潛在路徑集。最后，在潛在路徑集中，選取GPS點投影最多的路徑作為實際使用路徑。

3 算法應(yīng)用比較

本文獲取了50位出行者的小汽車通勤出行數(shù)據(jù)，經(jīng)過數(shù)據(jù)處理后得到有效軌跡214條，在每個出行者的出行軌跡中選取一條GPS軌跡作為研究對象，其中小于5 km的軌跡5條，5～10 km的軌跡8條，10～15 km的軌跡7條，15～20 km的軌跡6條，20～25 km的軌跡7條，25～30 km的軌跡6條，大于30 km的軌跡11條。根據(jù)本文所提的地圖匹配算法以及基于最短路徑的匹配算法，對其結(jié)果進行比較得到結(jié)果如圖6所示。其中算法準確率通過算法所得到路徑的路段與實際使用路段的重合率來體現(xiàn)，其計算公式：

從圖6的結(jié)果可以發(fā)現(xiàn)，隨著出行距離的增加，算法的準確率會逐步降低，尤其是基于最短路徑的算法，在距離增大后，準確率的下降速度加快，這是因為隨著距離的增加，出行者所使用的路段數(shù)量會隨之增加，且出行軌跡可能更復雜。例如，隨著出行距離的增加，出行者使用快速道路的可能性增加，而快速道路的匝道之間的距離較近，容易造成匹配路段的錯誤。而通過比較基于最短路徑的算法和本文算法的結(jié)果發(fā)現(xiàn)，在每個區(qū)間段，本文算法均比基于最短路徑的算法準確性更高，尤其是在遠距離出行中，本算法更具有優(yōu)越性。

4 結(jié)束語

離線地圖匹配算法作為基于GPS數(shù)據(jù)的路徑選擇行為研究中重要一部分，其輸出結(jié)果的準確性直接影響到最終結(jié)論。本文基于多路徑的原則，提出了在路徑節(jié)點進行迭代的基本思路，詳細介紹了所提離線地圖匹配算法的詳細流程，通過數(shù)據(jù)預(yù)處理、構(gòu)建子網(wǎng)絡(luò)、構(gòu)建初始使用路徑、建立節(jié)點與路段的關(guān)聯(lián)矩陣、構(gòu)建潛在路徑集以及確定最終選擇路徑等6個步驟來實現(xiàn)，本算法思路清晰易實現(xiàn)。通過將算法應(yīng)用于美國明尼阿波利斯-圣保羅都市圈的GPS數(shù)據(jù)處理中，發(fā)現(xiàn)本算法的準確率整體較高，隨著出行距離的增加，算法的準確率會逐步降低。與基于最短路徑的算法相比，本文算法的準確性更高，尤其是在遠距離出行中，本算法更具有優(yōu)越性。當然對于本算法，雖然不需要像其他算法對每個GPS軌跡點進行迭代判斷，但依然需要對每個正確的路徑節(jié)點進行分析，建立新的路徑并儲存，其速率在以后的研究中還有待進一步加強。

【參 考 文 獻】

[1]DHAKAR N， SRINIVASAN S. Route choice modeling using GPS-based travel surveys[J]. Transportation Research Record， 2014， 2413： 65-73.

[2]NOUR A， HELLINGA B， CASELLO J M. Classification of automobile and transit trips from smartphone data： enhancing accuracy using spatial statistics and GIS[J]. Journal of Transport Geography， 2016， 51：36-44.

[3]GONG H M， CHEN C， BIALOSTOZKY E， et al. A GPS/GIS method for travel mode detection in New York City[J]. Computers， Environment and Urban Systems， 2012， 36（2）：131-139.

[4]蘇潔，周東方，岳春生.GPS車輛導航中的實時地圖匹配算法[J].測繪學報，2001，30（3）：252-256.

SU J， ZHOU D F， YUE C S. Real-time map-matching algorithm in GPS navigation system for vehicles[J]. Acta Geodaetica et Cartographica Sinica， 2001， 30（3）：252-256.

[5]唐進君，曹凱.一種自適應(yīng)軌跡曲線地圖匹配算法[J].測繪學報，2008，37（3）：308-315.

TANG J J， CAO K. An adaptive trajectory curves map-matching algorithm[J]. Acta Geodaetica et Cartographica Sinica， 2008， 37（3）：308-315.

[6]YIN H B， WOLFSON O. A weight-based map matching method in moving objects databases[C]. Scientific and Statistical Database Management， Proceedings of 16th International Conference， 2004， 437-438.

[7]ZHOU J， GOLLEDGE R. A three-step general map matching method in the GIS environment： Travel/transportation study perspective[J]. International Journal of Geographical Information System， 2006， 8（3）：243-60.

[8]GRIFFIN T， HUANG Y， SEALS S. Routing-based map matching for extracting routes from GPS trajectories[C]. In Proceedings of the 2nd International Conference on Computing for Geospatial Research & Applications， 2011：24.

[9]SPISSU E， MELONI I， SANJUST B. Behavioral analysis of choice of daily route with data from global positioning system[J]. Transportation Research Record， 2011， 2230（1）：96-103.

[10]MARCHAL F， HACKNEY J， AXHAUSEN K. Efficient map matching of large global positioning system data sets： tests on speed-monitoring experiment in Zürich[J]. Transportation Research Record， 2005， 1935（1）：93-100.

[11]PYO J S， SHIN D H， SUNG T K. Development of a map matching method using the multiple hypothesis technique[C]. IEEE Intelligent Transportation Systems， 2001：23-27.

[12]MENGHINI G， CARRASCO N， SCHUSSLER N， et al. Route choice of cyclists in Zurich[J]. Transportation Research Part A： Policy and Practice， 2010， 44（9）：754-765.

[13]劉智，王番，李潤生，等.基于偽Zenike矩的離線地圖匹配算法[J].計算機工程與應(yīng)用.2014，50（10）：23-26.

LIU Z， WANG P， LI R S， et al. Off-line map matching algorithm based on Pseudo-Zernike moments[J]. Computer Engineering and Applications， 2014， 50（10）：23-26

[14]陳波，王茂林，王宏，等.一種基于網(wǎng)絡(luò)拓撲關(guān)系的地圖匹配算法[J].測繪科學技術(shù)學報.2006，23（5）：331-334.

CHEN B， WANG M L， WANG H， et al. A map-matching algorithm based on network topology[J]. Journal of Geomatics Science and Technology， 2006， 23（5）：331-334.

[15]王敏，魏衡華，鮑遠律.GPS導航系統(tǒng)中的地圖匹配算法[J].計算機工程，2012，38（14）：259-261.

WANG M， WEI H H， BAO Y L. Map-matching algorithm in GPS navigation system[J]. Computer Engineering， 2012， 38（14）：259-261.

[16]戴文舟.交通網(wǎng)絡(luò)中最短路徑算法的研究[D].重慶：重慶大學，2004.

DAI W Z. Study on shortest path algorithm on GIS-T[D]. Chongqing： Chongqing University， 2004.

[17]劉志勇，李瑞敏.北京市公共交通網(wǎng)絡(luò)系統(tǒng)的魯棒性研究[J].公路工程，2017，42（6）：17-23.

LIU Z Y， LI R M. The robustness research of Beijing public traffic network system[J]. Highway Engineering， 2017， 42（6）：17-23.

[18]ArcGIS Help[EB/OL]. http：//resources.arcgis.com/en/help/main/10.2/index.html.

[19]TANG W Y， LEVINSON D M. Deviation between actual and shortest travel time paths for commuters[J]. Journal of Transportation Engineering， Part A： Systems， 2018， 144（8）： 04018042.

[20]TANG W Y， CHENG L. Analyzing multiday route choice behavior of commuters using GPS data[J]. Advances in Mechanical Engineering， 2016， 8（2）：1687814016633030.