考虑时空特性的动态权重实时地图匹配算法

郑林江，刘 旭，易 兵

(1.重庆大学 计算机学院，重庆 400044； 2.重庆城市综合交通枢纽开发投资有限公司，重庆 401121)

(*通信作者电子邮箱lx1848@126.com)

考虑时空特性的动态权重实时地图匹配算法

郑林江1，刘 旭1*，易 兵2

(1.重庆大学 计算机学院，重庆 400044； 2.重庆城市综合交通枢纽开发投资有限公司，重庆 401121)

(*通信作者电子邮箱lx1848@126.com)

针对当前实时地图匹配算法难以同时保证匹配高准确性和高实时性的问题，提出一种基于动态权重的实时地图匹配改进算法。首先，算法考虑了相邻全球定位系统(GPS)轨迹点在时间、速度和方向上的约束关系，以及道路网拓扑结构，并基于时空特性分析，建立了距离权重、方位权重、方向权重和连通性权重组成的权重模型；然后，根据GPS轨迹点自身属性信息，建立了动态权重系数模型；最后，根据置信度水平选择最佳匹配路段。用三条总长36 km的重庆城市公交车行驶轨迹进行测试，结果显示：所提算法平均匹配正确率达到97.31%，单个轨迹点匹配平均延迟为17.9 ms。新算法匹配正确率和实时性较高，在Y形路口和平行路段的匹配效果上优于对比算法。

地图匹配；动态权重；全球定位系统轨迹；时空特性；智能交通系统

0 引言

目前，许多智能交通系统(Intelligent Transportation System， ITS)应用服务，如车辆导航、出行路线规划、交通流量管理、交通事故预警与处置、公交到站时间预测等都需要位置信息。近年来，随着智能终端技术发展与普及，各种车辆和移动终端已将全球定位系统(Global Positioning System, GPS)模块作为标配，GPS已成为ITS应用服务提供位置信息的主流定位技术。

尽管GPS技术已很成熟，但由于城市道路密集且形状复杂，在车辆经过多层立交桥、隧道或高层建筑时，GPS信号会丢失或变差。此外，电子地图中的道路也存在误差，定位数据并不能直接正确显示到电子地图中的道路上。地图匹配作为一种位置修正技术可以解决这个问题。

地图匹配算法是以定位系统(GPS或GPS/DR等)产生的轨迹数据以及高精度路网数据作为输入，以此来识别车辆正在行驶的正确路段并确定车辆在路段上的位置[1]。目前，实时地图匹配算法可以分为简单匹配算法、基于权重匹配算法和高级匹配算法三类[2]。简单匹配算法仅考虑了道路网的几何形状，算法简单但是在交叉路和平行路段匹配精度不高[3]；基于权重匹配算法除了考虑道路网的几何形状外，还综合考虑了道路间的连接或连通关系，常基于几个度量指标如距离、方向等给每条候选路段打分，然后选择得分最高路段作为匹配路段[4-6]；高级匹配算法会利用数学模型如隐马尔可夫模型(Hidden Markov Model，HMM)[7-9]、模糊逻辑[10-11]、D-S(Dempster-Shafer)证据理论[12]、卡尔曼滤波等来给候选路段计算分数，并选择得分最高路段作为匹配路段。尽管高级匹配算法匹配正确率一般比基于权重算法高，但是高级算法具有更高的复杂度，可能会产生较大的匹配延迟[2]。

目前基于权重匹配算法的准确率介于简单匹配算法和高级匹配算法之间，但其算法复杂性低，比较适合实时地图匹配。文献[4]就该类算法的权重系数为经验常数，不能适应匹配场景变化[2]的问题进行了改进：根据每个GPS轨迹点自身的水平精度、速度、与上一个GPS轨迹点的行驶距离，建立了三个权重系数函数，权重系数将随着GPS轨迹点动态变化，算法平均匹配正确率可达到92.19%。但是，该算法权重仅考虑了当前GPS轨迹点及候选路段的拓扑信息，没有考虑与历史匹配路段的时空关系，因此在GPS信号质量差时，可能会在平行路段及道路夹角很小路段出现误匹配。本文针对该类问题，考虑GPS轨迹的时空特性，提出了一种改进的基于动态权重的实时地图匹配算法。该算法主要特点表现在以下几方面：

1)增加道路连通性权重，这可以解决跳段问题[2]和平行道路匹配问题；

2)除距离权重外的其他三个权重都考虑了与历史匹配点和匹配路段的时空关系，可以解决包括Y形道路在内的多支路道路的匹配；

3)权重系数随着GPS轨迹点动态变化，可以解决由于候选路段得分很相近导致的“过度拟合”型匹配错误。

1 地图匹配基本概念

GPS轨迹T是由装有GPS模块的设备采集的，由一系列按时间先后顺序记录的GPS轨迹点组成的集合，表示为T={p1,p2,…,pn}。每个GPS轨迹点具有6个属性，表示为向量：

pi=[lon,lat,t,v,comp,hdop]

其中:pi.lon是经度，pi.lat是纬度，pi.t是记录时间戳，pi.v是瞬时速度，pi.comp是瞬时方向，pi.hdop是水平精度。

本文将路网当作一个有向图G，G中的顶点是路网的道路节点，具有经度、纬度属性。如图1，路段r1是连接N1、N2两个道路节点的有向边，表示G中道路的中心线。路段r有5个属性，表示为向量：

r=[dir,len,type,start,end]

其中:r.dir是路段通行方向，r.len是路段长度，r.type是路段类型(国道、高速路等)，r.start是路段点，r.end是路段终点。弯道由多条路段表示。

图1 路段

Fig. 1 Road segment

2 一种动态权重实时匹配算法

算法的总体逻辑如图2。

图2 算法总体逻辑框图Fig. 2 Overview of algorithm framework

2.1 选取候选路段

地图匹配算法实质是从整个路网(解空间)寻找最优路径的一种搜索算法。寻找候选路段过程就是对解空间剪枝，简单快速的候选路段选取方法能大大提高算法的匹配效率。目前已有的方案有误差椭圆法和网格搜索法：误差椭圆法[10，13]数学理论复杂，而且实现比较复杂，对算法效率可能影响较大；网格搜索法[14-15]的搜索效率非常高，但是对地图数据建立网格索引是一个较复杂的过程。

图3 基于误差圆选取候选路段Fig. 3 Candidate road segments selection based on error circle

为了简单但又不失效率和准确性，本文采用误差圆法。如图3，以GPS轨迹点pi为圆心，其精度R为半径得到误差圆，任何被误差圆包含的路段和与误差圆所在区域相交或相切的路段都将被选作pi的候选路段：

这解决了基于道路节点的误差圆法可能找不到候选路段的问题。

2.2 计算各候选路段的总得分

本文基于四个指标，即距离权重、方位权重、方向权重和连通性权重，对每条候选路段打分。具体细节将在稍后各小节详述。

2.2.1 距离权重

图4 GPS轨迹点到候选路段距离Fig. 4 Perpendicular projection distance to candidate road segment of GPS points

(1)

将其值归一化到[0，1],得到距离权重计算公式：

(2)

(3)

利用5 700个GPS轨迹点计算出σg=17.15。

2.2.2 方位权重

(4)

(5)

图5 计算方位权重的两种情况Fig. 5 Two cases of heading weight calculation

当车辆转弯时，GPS轨迹点瞬时方向随着道路方向变化而变化，因此当pi有历史匹配信息时，如图5(b)，结合历史轨迹点和历史匹配路段的方向信息描述该变化趋势，用式(6)计算方位权重，降低方位权重对方向误差的敏感度：

(6)

2.2.3 方向权重

图6 方向权重Fig. 6 Direction weight

(7)

(8)

2.2.4 连通性权重

全局匹配算法的正确率一般比实时匹配算法高，原因是全局算法考虑了历史GPS轨迹点及路匹配段的信息。而实时匹配算法很多都只考虑了当前GPS轨迹点及其候选路段的信息，没有考虑历史因素。本文提出连通性权重来描述当前GPS轨迹点与历史GPS轨迹点及匹配路段的时空关系。

图7 连通性权重Fig. 7 Connectivity weight

(9)

2)GPS轨迹点采样间隔大于5 s。这时用第一种方式计算平均速度就不合适了，此时ltravel近似等于相邻GPS轨迹点间的欧拉距离，即ltravel=lpi-1→pi。

3)当车辆在经过隧道或立交桥时， GPS信号丢失导致采样时间间隔变大，可能长达数分钟。这期间车辆的速度变化可能会很大，这时ltravel=lpi-1→pi。

图8 连通性权重对平行道路匹配的影响Fig. 8 Influence of connectivity weight on parallel road’s matching

2.3 权重系数的确定

[4]，本文选择以下函数来计算各个权重的权重系数，对于不同的GPS轨迹点进行匹配时将采用不同权重系数。

Wdisti=

(10)

Wheadi=

(11)

(12)

(13)

2.4 获取最佳匹配路段

以往实时匹配算法一般分三个阶段[2]：初始位置匹配、跟踪匹配、路口路段匹配。路口路段匹配阶段需要进行路口检测，这无疑增加了算法的复杂性。本文算法将跟踪匹配和路口路段匹配合并为一个阶段，不再进行路口检测以算法简化模型，即分为两个阶段：初始位置匹配、后续位置匹配。

(14)

(15)

2.4.1 初始位置匹配

(16)

2.4.2 后续位置匹配

(17)

其中Ki为匹配置信度水平，该值越大匹配正确的信心越高。如果pi仅有一条候选路段，则直接将点匹配到该路段。参考文献[4]，本文用式(18)计算置信度Ki,匹配不同GPS轨迹点采用不同的置信度。

在计算出pi的匹配路段ri后，将pi垂直投影到ri,投影点就是车辆当前的位置。如果投影点在ri的延长线上，则将ri更靠近pi的端点作为车辆当前的位置。

(18)

3 算法评估与结果

3.1 实验环境准备

地图数据为开源地图OpenStreetMap；GPS轨迹为三条重庆市区公交车轨迹，包含道路类型有立交桥、隧道等特殊路段，轨迹点采集时间间隔为1～3 s；地理信息系统(Geographic Information System， GIS)引擎为github开源项目GraphHopper, 用于计算候选路段方向、最短路径等。实验平台基于Java实现，平台硬件配置为：内存4 GB，CPU型号为Intel Core i3- 2310M 2.1 GHz。

由于OpenStreetMap地图数据并不完备，一些非主干道数据存在缺失，导致GPS轨迹中部分轨迹点无法找到正确的匹配路段，因此将这部分GPS轨迹点提前去除。表1中列举了实验轨迹的一些特征信息。 根据三条轨迹中所有GPS轨迹点的pi.v和pi.hdop确定距离权重系数函数和方位权重系数函数中的常数，利用MAD公式计算得到：V1=2.35 m/s,V2=3.35 m/s,HDOP1=4,HDOP2=7。

3.2 实验结果

表2是本文提出算法的性能评估结果。可以看到平均95.6%的GPS轨迹点被匹配到了道路上，表明计算出的平均延迟比较可靠，不会因为太多轨迹点未被匹配到道路而导致算法长时间不更新车辆位置。

如图9(a)，从轨迹点的候选路段可以看出车辆经过了一个Y形路口，尽管GPS轨迹点距离误差很大，但算法仍匹配正确，而以往实时匹配算法在Y形路口很容易发生误匹配[1]。如图9(b)，从立交桥处轨迹点的候选路段平行且方向一样可以看出这是平行路段，最终算法将轨迹点匹配到了正确路段。如图9(c)，车辆经过U形路口(圆圈处)时，由于连续多个GPS轨迹点速度为0，导致匹配错误轨迹点的方向权重和方位权重都为0。而且在U形路口，两条候选路段与历史匹配路段都能连通，导致连通权重也失效。最终起作用的只有距离权重，但是GPS轨迹点距离误差很大，因而导致了匹配错误。

表3将本文算法与其他几种实时地图匹配算法进行了对比。本文算法匹配正确率比以往基于权重匹配算法都高，甚至超过了高级匹配算法[7]基于HMM的匹配准确率。

表1 GPS轨迹数据特征Tab. 1 Characteristics of GPS trajectories

表2 本文提出算法的性能评估结果Tab. 2 Performance evaluation results by proposed map matching algorithm

图9 实验匹配情况Fig. 9 Experimental results of map matching表3 本文提出算法与已有算法性能比较Tab. 3 Comparison of the proposed algorithm with other exsiting algorithms

算法路段匹配基准测试环境导航传感器类型地图匹配模型文献中给出的匹配准确率/%本文算法距离、方位变化、方向变化、连通性重庆市区GPS基于权重97.31文献[4]方法距离、方位变化、方向变化、连通性芝加哥市区GPS基于权重92.19文献[6]方法距离、方位变化、方向变化伦敦市区GPS/DR基于权重88.60文献[7]方法距离、连通性新加坡市区GPSHMM92.10文献[11]方法距离、方位变化、方向变化、连通性伦敦市区GPS/DR模糊逻辑98.50

4 结语

在总结以往全局地图匹配算法和实时匹配算法的优缺点后，本文提出了一种改进的基于动态权重的实时地图匹配算法。基于对道路网和GPS轨迹时空信息的分析，该算法建立了由四个权重组成的权重模型：1)距离权重，即GPS轨迹点到候选路段距离；2)方位权重，即相邻GPS轨迹点瞬时方向的变化程度与候选路段相对上一条匹配路段方向的变化程度间的相似性；3)方向权重，即相邻GPS轨迹点间连线的方向与候选路段方向间的相似性；4)连通性权重，即连通性候选路段和上一条匹配路段间的连通性。然后利用GPS轨迹点的速度、水平精度衰减因子hdop等信息建立各权重对应的动态权重系数函数，进而得到每条候选路段的总得分。最后，算法根据每个轨迹点的匹配置信度水平得到最佳匹配路段。

本文基于总长36 km的3条真实轨迹对算法进行评估，结果表明：1)本文算法能正确匹配Y形道路、平行道路，甚至能对立交桥的弯道有比较好的匹配效果，然而在U形路口处匹配错误表明算法在对低速下行驶车辆的匹配仍有待提高；2)本文算法的平均匹配正确率为97.31%，优于现有的基于权重匹配算法，单个轨迹点匹配平均延迟为17.9 ms，满足ITS应用对准确性和实时性的要求。研究也说明充分利用路网和GPS轨迹点信息，权重匹配算法也可以达到高级算法的匹配正确率，但由于它不像高级算法那样复杂，实时性能更高。但本文算法的性能也可能受到了实验平台和电子地图精度的限制，以及低速下的匹配精度仍有进一步提升的空间，这将成为未来的研究方向。

参考文献(References)

[1] QUDDUS M A, OCHIENG W Y, NOLAND R B. Current map-matching algorithms for transport applications: State-of-the art and future research directions [J]. Transportation Research Part C: Emerging Technologies, 2007, 15(5): 312-328.

[2] HASHEMI M, KARIMI H A. A critical review of real-time map-matching algorithms: Current issues and future directions [J]. Computers, Environment and Urban Systems, 2014, 48: 153-165.

[3] KIM J-S. Node based map matching algorithm for car navigation system [C]// Proceedings of the 29th International Symposium on Automotive Technology & Automation. Croydon, England: Automotive Automation Ltd., 1996.

[4] HASHEMI M, KARIMI H A. A weight-based map-matching algorithm for vehicle navigation in complex urban networks [J]. Journal of Intelligent Transportation Systems, 2016, 20(6): 573-590.

[5] VELAGA N R, QUDDUS M A, BRISTOW A L. Developing an enhanced weight-based topological map-matching algorithm for intelligent transport systems [J]. Transportation Research Part C: Emerging Technologies, 2009, 17(6): 672-683.

[6] QUDDUS M A, OCHIENG W Y, ZHAO L, et al. A general map matching algorithm for transport telematics applications [J]. GPS Solutions, 2003, 7(3): 157-167.

[7] GOH C Y, DAUWELS J, MITROVIC N, et al. Online map-matching based on hidden Markov model for real-time traffic sensing applications [C]// ITSC 2015: Proceedings of the 2012 15th International IEEE Conference on Intelligent Transportation Systems. Piscataway, NJ: IEEE, 2012: 776-781.

[8] LOU Y, ZHANG C, ZHENG Y, et al. Map-matching for low-sampling-rate GPS trajectories [C]// Proceedings of the 17th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. New York: ACM, 2009: 352-361.

[9] NEWSON P, KRUMM J. Hidden Markov map matching through noise and sparseness [C]// GIS ’09: Proceedings of the 17th ACM SIGSPATIAL international conference on advances in geographic information systems. New York: ACM, 2009: 336-343.

[10] 郑学远.基于模糊逻辑的综合地图匹配方法研究与实现[D].北京：北京交通大学,2014:29-53. (ZHENG X Y. The research and realization of integrated map matching method based on fuzzy logic [D]. Beijing: Beijing Jiaotong University, 2014: 29-53.)

[11] QUDDUS M A, NOLAND R B, OCHIENG W Y. A high accuracy fuzzy logic based map matching algorithm for road transport [J]. Journal of Intelligent Transportation Systems, 2006, 10(3): 103-115.

[12] 肖维丽,岳春生,奚玲.基于高程的改进D-S证据理论地图匹配算法[J].计算机应用与软件,2015,32(7):262-265. (XIAO W L, YUE C S, XI L. Improved D-S evidence theory map maching algorithm based on elevation information [J]. Computer Applications and Software, 2015, 32(7): 262-265.)

[13] 夏州.GPS车辆导航中的数据处理与地图匹配研究[D]. 北京：北京交通大学, 2009: 37-40. (XIA Z. Research of GPS data processing and map matching in vehicle navigation system [D]. Beijing: Beijing Jiaotong University, 2009: 37-40.)

[14] TANG Y, ZHU A D, XIAO X. An efficient algorithm for mapping vehicle trajectories onto road networks [C]// SIGSPATIAL ’12: Proceedings of the 20th International Conference on Advances in Geographic Information Systems. New York: ACM, 2012: 601-604.

[15] TAYLOR G, BLEWITT G, STEUP D, et al. Road reduction filtering for GPS-GIS navigation [J]. Transactions in GIS, 2001, 5(3): 193-207.

[16] OCHIENG W Y, QUDDUS M, NOLAND R B. Map-matching in complex urban road networks [J]. Brazilian Journal of Cartography, 2003, 55(2): 1-14.

This work is partially supported by Project Funded by China Post Doctoral Science Foundation (2014T70852), the Post-Doctoral Research Funds of Chongqing (XM201305), the Fundamental Research Funds for the Central Universities (106112014CDJZR188801), Key Projects of Chongqing Application Development Plan (cstc2014yykfB30003).

ZHENGLinjiang, born in 1983, Ph. D., associate professor. His research interests include intelligent transportation system, big data.

LIUXu, born in 1991, M. S. candidate. His research interests include intelligent transportation system, big data.

YIBing, born in 1971, senior engineer. His research interests include traffic engineering.

Dynamicweightedreal-timemapmatchingalgorithmconsideringspatio-temporalproperty

ZHENG Linjang1, LIU Xu1*, YI Bing2

(1.CollegeofComputerScience,ChongqingUniversity,Chongqing400044,China；2.ChongqingIntegratedTransportHubDevelopmentInvestmentCompanyLimited,Chongqing401121,China)

Focusing on the issue that current real-time map matching algorithms are difficult to keep high efficiency and high accuracy simultaneously, an improved dynamic weighted real-time map matching algorithm was proposed. Firstly, considering the temporal, speed, heading and direction constraints of Global Positioning System (GPS) points and the topological structures of road network, a weighted model was constructed in the algorithm based on spatio-temporal analysis, which consisted of proximity weight, heading weight, direction weight and connectivity weight. Then according to the properties of GPS points, a dynamic weighted coefficient model was created. Lastly, the best matching road segment was selected according to the confidence level of current GPS point. The experiments were conducted on three city bus trajectories with length of 36 km in Chongqing. The average matching accuracy of the algorithm was 97.31% and the average matching delay of each GPS point was 17.9 ms. The experimental results show that compared with the contrast algorithms, the proposed algorithm has higher accuracy and efficiency, and has better performance in matching Y-junctions and parallel roads.

map matching; dynamic weight; Global Positioning System (GPS) trajectory; spatio-temporal property; Intelligent Transportation System (ITS)

TP391.41

A

2017- 02- 20;

2017- 03- 21。

中国博士后科学基金特别资助项目(2014T70852)；重庆市博士后科研项目特别资助项目(XM201305)；中央高校基本科研业务费资助项目(106112014CDJZR188801)；重庆市应用开发计划重点项目(cstc2014yykfB30003)。

郑林江(1983—)，男，四川邻水人，副教授，博士，CCF会员，主要研究方向：智能交通系统、大数据； 刘旭(1991—)，男，四川南充人，硕士研究生，主要研究方向：智能交通系统、大数据； 易兵(1971—)，男，湖南邵阳人，高级工程师，主要研究方向：交通工程。

1001- 9081(2017)08- 2381- 06

10.11772/j.issn.1001- 9081.2017.08.2381