基于多路徑的交通網(wǎng)絡(luò)離線地圖匹配算法

湯文蘊(yùn) 馬健霄 楊震

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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é)果進(jìn)行比較得到結(jié)果如圖6所示。其中算法準(zhǔn)確率通過算法所得到路徑的路段與實(shí)際使用路段的重合率來體現(xiàn)，其計(jì)算公式：

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

4 結(jié)束語

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

【參 考 文 獻(xiàn)】

[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車輛導(dǎo)航中的實(shí)時地圖匹配算法[J].測繪學(xué)報(bào)，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]唐進(jìn)君，曹凱.一種自適應(yīng)軌跡曲線地圖匹配算法[J].測繪學(xué)報(bào)，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].計(jì)算機(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ò)拓?fù)潢P(guān)系的地圖匹配算法[J].測繪科學(xué)技術(shù)學(xué)報(bào).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]王敏，魏衡華，鮑遠(yuǎn)律.GPS導(dǎo)航系統(tǒng)中的地圖匹配算法[J].計(jì)算機(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].重慶：重慶大學(xué)，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.