基于多路径的交通网络离线地图匹配算法

汤文蕴 马健霄 杨震

摘 要：为了提高交通网络中离线地图匹配算法的准确率，避免在离线地图匹配过程中出现路段匹配错误的情况，本文基于多路径的原则，提出在路径节点进行迭代的基本思路，通过数据预处理、构建子网络、构建初始使用路径、建立节点与路段的关联矩阵、构建潜在路径集以及确定最终选择路径等6个步骤来实现。本文详细介绍所提离线地图匹配算法的详细流程，本算法思路清晰易实现。通过将算法应用于美国明尼阿波利斯-圣保罗都市圈的GPS数据处理中，发现本算法的准确率整体较高，随着出行距离的增加，算法的准确率会逐步降低。与基于最短路径的算法相比，本文算法的准确性更高，尤其是在远距离出行中，本算法更具有优越性。

关键词：交通网络;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技术的广泛应用，大量车行、人行轨迹通过GPS设备收集、存储并进行分析。在交通研究领域，GPS数据通过必要的处理，转换为可用于模型估计的格式后，被用于分析出行目的、出行方式和出行路径等[1-3]。在利用GPS数据进行出行路径选择行为分析之前，需要进行两个重要步骤：地图匹配和选择集生成，其中地图匹配过程是将GPS点的轨迹流匹配到相应道路上，进而识别出行者所选择的路径。在车辆GPS定位过程中，虽然依靠差分技术、无线电信标和载波相位技术等方法，可以提高其定位精度，但是一方面这些方法成本高，另一方面精度提高后依然存在少许偏离，并且最终依然需要将轨迹点与拓扑网络相对应。因而地图匹配算法作为一种直接可执行、价廉的基于软件技术的定位修正方法，在GIS领域成为一个经典命题，已有一系列研究成果[4-5]。

目前已有的地图匹配算法可分为在线地图匹配算法和离线地图匹配算法，其中在线地图匹配算法的目标是将车辆的实时位置定位到地图上，因此，在线地图匹配算法的基本要求是将每个GPS点均匹配到路段上，相应需要更高效快速的算法。而离线地图匹配算法的研究对象是一条已给定的GPS轨迹路径，它主要用于路径选择行为研究中，除了不需要对GPS点进行实时定位外，也不需要将每个GPS点进行匹配[6]。本文所提及的地图匹配算法均为离线地图匹配算法。在现有研究中，离线地图匹配算法主要包括两种类型：基于最短路径[7-9]与基于多重假设技术[10-13]。本文在多重假设技术的基础上，提出一种基于多路径的交通网络地图匹配算法，所提出的方法，思路清晰便于实现，能有效的将GPS点准确的匹配到正确的路段上。此外，在已有基于多路径的匹配算法[12]中，将每个GPS轨迹点进行迭代，并找到相应的路径，但是对于一次通勤出行，GPS轨迹点个数一般都在几千个以上，因此，本文引入路径节点概念，以此减少迭代次数，加快算法完成速率。通过比较发现，本文所提方法在准确性上明显优于基于最短路径方法，而准确性是离线地图匹配最重要的一项评价指标。

在关联矩阵构建过程中，分别以节点或路段为基础构建缓冲区，然后判断路段或节点是否在缓冲区内，其基本原理如ArcGIS[18]的原理类似，可避免出现反向搜索问题。

步骤 5：构建潜在路径集。

本算法从第一个路径节点开始构建潜在路径集，即最靠近起点的那个路径节点，然后依次考虑所有的路径节点。在第一个路径节点处，依据步骤4中所提的节点-路段关联矩阵，找到与此路径节点相关联的路段，认为他是一条可选路段，同时，依据路段-节点关联矩阵，可以获得此路段另外一个端点，并判断此端点是否是路径节点，若是则将其标记为“正确节点”。若第一条可选路段是断头路，则将其标为无效路段，将起点附近的其他路段作为第一条可选路段，若不是则加入潜在路径集。

在对某个路径节点进行标记为“正确节点”之后，依据节点-路段关联矩阵，除已记入在潜在路径集中的路段之外，找到其他关联路段，将这些路段标记为可选路段，并继续分别“向前”对这些路段进行判断。一旦某条路段为断头路，这条可选路段则被标记是无效路段，并将无效路段上的路径节点标记为“错误节点”，然后对其他可选路段进行判断分析，若不是断头路则加入潜在路径集。

依照上述的方法，本算法继续对子网络里的其他路段进行判断，直到路径节点上所连接的所有路段均被分析考虑。直到所有的路径节点均被检查完，且满足条件的可选路段均被加入潜在路径集为止。如果被分析的路径的端点是一个局部节点，其迭代方法与路径节点的方法相同。

构建潜在路径集的具体步骤如图2所示。

步骤 6：确定最终使用路径。

当所有标记为“正确节点”的路径节点被分析判断过后，本算法将囊括所有的潜在路径。最终，在潜在路径集里，判断某一条路径上，所投影的GPS点数量最多，即是所选路径。

2 实例应用

本文所采用的数据取自美国明尼苏达州明尼阿波利斯-圣保罗大都市圈于2011年做的居民出行行为调查，GPS设备被携带在调查者身上，通过GPS设备提供的信号，得到每秒钟出行者所处的位置，以文献[19-20]中小汽车通勤出行的GPS轨迹作为本文的研究对象。以某一束GPS轨迹为例，说明本算法的应用。基础地图采用TLG（The Lawrence Group）地图，其包含290 231条路段和113 864个节点，是研究区域内最详细的路网地图之一。图3所展示的是算法中步骤2的子网络构建过程，图3（a）是某出行者的一次出行GPS轨迹点与电子地图以及某区域的放大详细图，可以发现每个GPS点并没有直接覆盖在相应的道路上，存在一定的偏差。接着以每个GPS点为中心，建立半径为200 m的缓冲区，如图3（b）所示，所建立的缓冲区与道路电子地图的部分路段产生交集，将这些路段单独提取出来建立新的道路网络，即本算法中所需的子网络，如图3（c）所示。

对于基于最短路径的地图匹配算法，接下来就以此子网络为基础，从起点到终点寻找一条最短路径即可，容易出现部分路段匹配错误的情况。而在本算法中提出“初始使用路径”、“路径节点”和“局部节点”，通过不停的路径迭代，找到最后可选路径集。图4（a）展示了根据空间连接和最短路径得到的初始使用路径，从图4（a）中可以看到，初始使用路径包含了大部分出行者确实使用的路段，也包含部分未使用路段，同时还有部分使用路段未被包括在内，主要体现为“断头路”和“环路”现象。以初始路径为基础，采用步骤3的方法创建路径节点集和局部节点集，如图4（b）所示，接着对每个节点和路段分别构建路段-节点和节点-路段关联矩阵。

構建潜在路径集是本算法中关键的一步，以如图5（a）所示区域说明潜在路径集的创建过程，根据GPS轨迹点，确定第一个路径节点，然后根据此节点的节点-路段矩阵确认第一条可选路段，并得到它的另外一个端点的节点符号。在本示例中，这个节点是路径节点，将其标记为“正确节点”，如图5（b）所示。从被标记的路径节点出发，有两条路段，如图5（c）所示，其中一条是断头路，因此将其标记为无效路段，由于其端点是一个局部节点，固不将其标记为“错误节点”，而在图5（d）中，无效路段的端点是一个路径节点，固将其标记为“错误节点”。在图5（e）中，从路径节点出发，除了一个无效路段外，还有两条可选路段，则可根据这两条可选路段建立两条新的路径加入到路径集中。按此方法继续对子网络内剩余部分进行迭代，并根据条件创建新的路径加入潜在路径集。最后，在潜在路径集中，选取GPS点投影最多的路径作为实际使用路径。

3 算法应用比较

本文获取了50位出行者的小汽车通勤出行数据，经过数据处理后得到有效轨迹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条。根据本文所提的地图匹配算法以及基于最短路径的匹配算法，对其结果进行比较得到结果如图6所示。其中算法准确率通过算法所得到路径的路段与实际使用路段的重合率来体现，其计算公式：

从图6的结果可以发现，随着出行距离的增加，算法的准确率会逐步降低，尤其是基于最短路径的算法，在距离增大后，准确率的下降速度加快，这是因为随着距离的增加，出行者所使用的路段数量会随之增加，且出行轨迹可能更复杂。例如，随着出行距离的增加，出行者使用快速道路的可能性增加，而快速道路的匝道之间的距离较近，容易造成匹配路段的错误。而通过比较基于最短路径的算法和本文算法的结果发现，在每个区间段，本文算法均比基于最短路径的算法准确性更高，尤其是在远距离出行中，本算法更具有优越性。

4 结束语

离线地图匹配算法作为基于GPS数据的路径选择行为研究中重要一部分，其输出结果的准确性直接影响到最终结论。本文基于多路径的原则，提出了在路径节点进行迭代的基本思路，详细介绍了所提离线地图匹配算法的详细流程，通过数据预处理、构建子网络、构建初始使用路径、建立节点与路段的关联矩阵、构建潜在路径集以及确定最终选择路径等6个步骤来实现，本算法思路清晰易实现。通过将算法应用于美国明尼阿波利斯-圣保罗都市圈的GPS数据处理中，发现本算法的准确率整体较高，随着出行距离的增加，算法的准确率会逐步降低。与基于最短路径的算法相比，本文算法的准确性更高，尤其是在远距离出行中，本算法更具有优越性。当然对于本算法，虽然不需要像其他算法对每个GPS轨迹点进行迭代判断，但依然需要对每个正确的路径节点进行分析，建立新的路径并储存，其速率在以后的研究中还有待进一步加强。

【参 考 文 献】

[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]唐进君，曹凯.一种自适应轨迹曲线地图匹配算法[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].计算机工程与应用.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]陈波，王茂林，王宏，等.一种基于网络拓扑关系的地图匹配算法[J].测绘科学技术学报.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导航系统中的地图匹配算法[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]戴文舟.交通網络中最短路径算法的研究[D].重庆：重庆大学，2004.

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

[17]刘志勇，李瑞敏.北京市公共交通网络系统的鲁棒性研究[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.