基于向量识别的启发式路径推测算法

《基于向量识别的启发式路径推测算法》由会员分享，可在线阅读，更多相关《基于向量识别的启发式路径推测算法（15页珍藏版）》请在装配图网上搜索。

1、基于向量识别的启发式路径推测算法* 吕卫锋1+，吴东东2，诸彤宇3（北京航空航天大学软件开发环境国家重点实验室 北京 100083）A Heuristic Path-Estimating Algorithm by Using Vector-Based RecognitionLv Wei-Feng 1+, Wu Dong-Dong 2, Zhu Tong-Yu 3(National Lab of Software Development Environment, Beihang University, Beijing 100083, China) + Corresponding author:

2、Phn: +86-10-8233-8667, Fax: +86-10-8233-8582, E-mail: lwfnlsde.buaa.edu Abstract:Floating Car Data (FCD) is an important material for a broad range of application such as traffic management and control, traffic conditions computation and so on. However, the original data exists error, and the data m

3、ust be handled by path-estimating and be related to the road. The traditional path-estimating algorithms mainly use two methods: the incremental method and the global method. Both of them have advantages and disadvantages of themselves: while the global map-matching algorithm produces better matchin

4、g results, the incremental algorithm produces results of lower quality faster. All things considering the two traditional algorithms, this paper proposes a heuristic path-estimating algorithm by using vector-based recognition. Firstly, the algorithm uses the heuristic search method, and it makes use

5、 of geometric operation to form the restriction, and make the comparison between the vector formed with the vehicular GPS points and the special road network model to search and select the vehicular possible traveling routes. Secondly, it globally compares all the vehicular possible traveling routes

6、, and then chooses the optimal one. The result of testing demonstrates the efficiency of the algorithm both at accuracy and computational speed when handling the large-scale data of GPS tracking data even under the complex road network conditions.Key words:Path-Estimating; Floating Car Data (FCD) ;

7、GPS; Heuristic search摘 要:浮动车数据主要是由车辆的轨迹点数据组成，是一种重要的原始数据，可以广泛的用于各种交通应用，如交通管理和控制，路况计算等. 但是原始的车辆GPS数据存在定位误差，必须经过路径推测的修正处理才可以应用.传统的路径推测算法主要采用两种方法：渐增式和全局式.两种方法各有优缺点，渐增式方法计算速度快但准确性差，全局式方法准确性好但计算速度慢.通过综合考虑两种传统算法，本文提出了一种基于向量识别的启发式路径推测算法，该算法采用了启发式图搜索方式，导入几何运算的约束条件，根据车辆轨迹点所形成的向量与路网模型比较来进行启发式搜索，并选择车辆所有可能行驶的候选路

8、径.根据全局择优的方式从整体进行比较，确定车辆最有可能的行驶路径.实验结果表明，这种算法能够在复杂路网下，比较准确地推测距离间隔较大的车辆轨迹点，并且能够实时高效地处理大规模数据.关键词:路径推测; 浮动车数据; GPS; 启发式搜索中图法分类号: TP301文献标识码: A 在智能交通领域，实时和动态的交通信息能为车辆出行，交通运输等提供有效的交通诱导和出行规划信息，从而达到节省出行时间、减少尾气排放等目的.为了实现上述目标，一个重要研究课题是高效处理实时、动态的交通信息.浮动车（Float Car Data）技术，也被称作“探测车（Probe car）”，是近年来国际智能交通系统（ITS）

9、中所采用的获取道路交通信息的先进技术手段之一.其基本原理是：根据装备车载全球定位系统（GPS）的浮动车在车辆行驶过程中定期记录的车辆位置，方向和速度信息，应用包括路径推测和道路交通拥堵信息计算等相关的计算模型和算法进行处理，从而使浮动车位置数据和城市道路在时间和空间上关联起来，最终得到浮动车所经过道路的车辆行驶速度以及道路的行车旅行时间等交通拥堵信息4.如果在城市中部署足够数量的浮动车，并将这些浮动车的位置数据通过无线通讯系统定期、实时地传输到信息处理中心，经过综合处理，就可以获得整个城市动态、实时的交通拥堵信息.浮动车数据处理主要存在两个方面的问题，一方面，在定位数据的准确性上，由于浮动车所

10、采用的GPS设备一般会有15米以上的圆周误差9，在推测过程中存在将轨迹点匹配到多条道路上的可能性.另一方面，在计算效率上，浮动车采集GPS轨迹点数据的采样率较低，一般在5300秒之间（实际应用中多为30120秒），造成两个连续轨迹点跨越了较长距离，两个轨迹点间有可能存在多条可行驶的路径.因此，应用于浮动车信息系统的路径推测算法既要有高效的计算速度，又要有较高的准确性.传统的方法无法很好适用于这种应用.基于此，本文设计了采用启发式搜索路径的路径推测算法.首先在算法的计算速度上，为了满足实时性的要求，采用了渐增式方法，一方面，重新设计了路网模型和路网拓扑，将其与算法进行整合3.另一方面，利用启发式

11、搜索方式，算法在特殊的路网模型支持下，利用车辆轨迹点所形成的向量与路网相比较，导入三角形的几何理论作为约束，采用启发式的图搜索方式快速的搜索浮动车可能行驶的候选道路.两方面相结合有效的提高了算法的计算速度.其次，在算法的准确性上，采用全局择优的方法，通过树结构保存与车辆轨迹相符合的所有候选路径，然后比较每条路径上轨迹点的匹配权值，从整体上选择最接近车辆轨迹的一条路径作为推测结果.本文第1节给出了相关研究，第2节介绍了算法使用的路网模型和路网拓扑，第3节对问题进行了描述与分析，第4节描述了算法的设计，第5节分析了实验测试的结果，最后对本文进行了总结，并给出了下一步研究工作.1 相关研究路径推测是

12、浮动车信息系统的关键技术，是正确计算道路交通状况的基础.路径推测是通过匹配车辆较大间隔的行驶轨迹点数据，搜索车辆正确行驶路径的技术，是地图匹配的一种处理方法.传统的路径推测算法主要采用两种方式：渐增式3和全局式1.渐增式方法分别对每个轨迹点进行路网搜索，计算轨迹点与其附近的道路的距离，选择与轨迹点距离最小的道路作为匹配结果.全局式方法则使用曲线匹配的方式，连接连续的多个轨迹点形成轨迹曲线，与路网中的路径做几何曲线匹配，通过计算Frchet距离的方法选择相似的道路作为匹配结果.渐增式方法计算简单，因此处理速度快，但是准确性差；全局式方法从整体上进行考虑，因此准确性好，但是由于计算复杂，处理速度慢

13、1.两种方法均不能很好的支持对大规模浮动车数据的实时处理.2 路网模型和路网拓扑路网数据是路径推测的基础，同时高效的路径推测算法应该整合相适应的路网模型和拓扑.但是，常见的电子地图路网模型一般是由基于桌面GIS (地理信息系统) 的路网模型改进得来.这种模型的缺陷在于难以表达复杂道路的拓扑关系，对路网的描述比较单一，无法满足针对大规模浮动车数据处理的需求.因此，必须对原有路网模型进行改进，以适应高效路径推测的要求.基于此，本文通过对数据的分层处理和抽象，建立了新型的路网模型构和路网拓扑.2.1 路网模型路网模型用于描述区域内的道路网，是由车辆轨迹点进行路径推测的基础.图1显示了路网模型的基本元

14、素，包括节点和路段.整个路网模型可以表述为 （1）（1）式中代表道路网络.代表节点集，表示路网中构成道路的坐标点集合，其元素为经纬度值对；代表路网的路段集合，其元素是有序对，表示存在一条有向直线道路s，其起始节点，终止节点，且s上不存在其他节点，如图1中，节点1和节点2之间存在着路段1;若在路网中，存在一个路段的序列，其中每条路段的终止节点是下一个路段的起始节点，则此序列代表路网上的一条有向通路，如图1中，路段1、2、3和4构成一条通路.图1 路网模型中的基本元素2.2 路网拓扑结构假设是路网中的一个节点.出度表示以为起始节点的路段的个数；入度表示以为终止节点的路段的个数，如图1中节点1的入度

15、为1，出度为2.路网中的节点，当或时，称为连通性节点.在路网中，存在一条通路，若的起始节点和的终止节点均为连通性节点，且其他路段的节点的入度和出度均为1，则此路段的序列称为一条路链，路链的集合为.在路网模型的基础上，根据道路网络的连通性和路链结构，建立路链间的拓扑结构图，其中，表示在路网上的路链集合，E则是根据道路的连通性建立的路链之间的连通关系.按照路链之间的连接性，路链的驶入路链称为此路链的前继路链，路链的驶出路链称为此路链的后继路链，表示link是link的前继路链，而link是link的后继路链.如图2中所示，.图2 十字交叉路口拓扑结构示意图2.3 向量在地图上取一坐标点（为点的经度

16、，为点的纬度），从出发向某点（为点的经度，为点的纬度）引一条线段，有方向且有长度，这种有向线段称为向量，记做，它的长度记作，表示与之间的距离，它的方向记作，表示为与正北方向的夹角（顺时针方向，方向值取值0360）.对于中的任一路链，其向量长度记为表示路链起点与路链终点所构成有向线段的距离，其向量方向记作，表示路链起点与路链终点所构成有向线段的方向.3 问题描述和问题分析3.1 问题描述在路网中，假设由其形成的路网拓扑为G，运动车辆在一个时间段T内的连续GPS轨迹点集合表示为，(为车辆定位坐标点 ，为车行方向)， .假设车辆在T内所行驶过的通路为，如何将轨迹点集合映射为，就是路径推测所要解决的最

17、主要问题，即 （2）通过构建匹配函数，完成与的推测计算得到车辆的正确行驶路径.3.2 车辆行驶规律分析3.2.1 车辆GPS轨迹点的匹配在对车辆的行驶位置进行定位时，车载GPS设备一般会有15米以上的圆周误差，车辆的GPS轨迹点需要投影到实际描述道路的路段上，才可以确定车辆的真实位置.因此，路链作为道路的抽象，不能完成对车辆实际位置的匹配支持.车辆轨迹点到道路的投影计算必须通过路段来完成.图3 车辆轨迹点的匹配示意3.2.2 车辆行驶状态分析 车辆在短时间内的行驶轨迹具有一定的相似性，通过对车辆的行驶状态分析归纳，可以掌握车辆的行驶规律，再与路网模型相结合，进一步得到了路径搜索的启发式条件.下

18、面通过实例的方式对车辆在路网上的行驶状态进行分析，并归纳路径推测算法的启发式搜索条件.1) 车辆在单一路链行驶车辆的连续轨迹点位于同一路链上.如图4中，p1在link1上的匹配点m1与p2构成的向量其长度小于m1与link1的终点构成的向量长度，即（e1=end（link1）且.图4 车辆在单一路链上行驶2) 车辆跨路链行驶车辆的连续轨迹点跨越了两条或两条以上路链，车辆基本存在了两种行车状态：一种是保持直行，如图5所示；另一种是转弯行驶，如图6a和图6b分别所示.图5 车辆跨路链直行在示意车辆跨路链直行的图5中 + + + + .另外，在方向上，车辆行驶路链的方向与向量的方向值必定会小于90.

19、因此，车辆行驶时满足的约束条件可以归纳如下：1. 路链的方向与匹配点和车辆轨迹点形成向量的方向值之差小于90，即 （3）2. 车辆行驶经过路链的累计向量长度之和小于匹配点与车辆轨迹点形成向量的长度的2倍，即2 * + + + + （4）4 算法设计4.1 路径搜索树为了提高搜索效率，采用启发式搜索思想，其中路径搜索树定义为，其中U是路网拓扑中V的非空子集，A为U集合中边的关系.依据GPS定位的车辆轨迹，车辆在一段时间内的所有可能行驶路径都保存在路径搜索树中.当依据路网拓扑和车辆的定位数据，对车辆的行驶路径进行搜索时，这颗树的深度和广度就会不断的增加，树节点里保存着车辆可能行驶过的路链.从路径搜

20、索树中得到算法的输出，是车辆记录的GPS定位数据的时间范围内所行驶的路径，表现为若干条相连的路链.4.2 车辆行驶路径搜索4.2.1 初始化对于给定的任一GPS轨迹点p，它在路链l上的匹配点被定义为与路链上的路段投影距离最小的点，且其到点p的距离小于最大匹配误差值，记作且，其中z为p在上的匹配点.每个GPS轨迹点均可以通过点匹配得到其在路网上的匹配路链集合，表述如下 （5）路径搜索树将根据匹配路链集合的不同，进行不同的初始化：1. 如果候选匹配路链集合的元素只有一个，则以匹配路链建立根节点，即；2. 如果候选匹配路链集合的元素大于1，则建立一个空节点作为根节点，以每条候选匹配点路链分别建立根节

21、点的子节点，即.4.2.2 的生成初始化路径搜索树后，就要根据后续GPS轨迹点搜索车辆可能行驶过的路链，生成路径推测树.算法根据车辆的后续GPS轨迹点，将前一个轨迹点在路链上的匹配点作为起点，下一个GPS轨迹点作为终点建立一条向量，计算这条向量的方向和长度.向量的方向就是车辆行驶路线的主要方向，向量的长度就是浮动车行驶路线的最小可能距离，在上文分析的约束条件下搜索车辆行驶路径.为实现这个算法需要附设一个辅助队列Matchedlinkqueue，用于记录轨迹点匹配到的路链和在路链上的匹配点.生成的算法：输入：路网拓扑、车辆轨迹点集合输出：车辆的若干条最有可能行驶路径(1) 通过点匹配得到的匹配路

22、链集合，完成路径搜索树和Matchedlinkqueue的初始化；(2) 对从开始的每两个连续车辆轨迹点进行路径搜索，置迭代次数=1，取车辆轨迹点；(3) 置迭代次数i = sizeof( Matchedlinkqueue )，计数器j=i；(4) 获取Matchedlinkqueue队头元素h同时出队列，j=j-1，h中记录的前一车辆轨迹点的匹配点m作为起点与建立一条向量；(5) 遍历m中记录的路链的后续路链集合L=，进行约束条件1的比较，若，则进行与的匹配计算，若且，则说明搜索到一条车辆可能行驶路链，加入中的U，与之间的边加入A，同时和z入队列Matchedlinkqueue；(6) 若没

23、有计算到匹配点，则进行约束条件2的比较，若2* + ，加入，根据对的后续路链进行深度遍历，将满足约束条件1并计算得到匹配点的路链加入和Matchedlinkqueue，将同时满足约束条件1和2的路链加入，直到没有路链可以同时满足约束条件1和2；(7) 重复步骤(4)至(6)，直到j=0；(8) 取下一个车辆轨迹点和Matchedlinkqueue，置l = l + 1，重复步骤(3)至(8)，直到l = n.完成扩展后，车辆在所形成的轨迹之间的所有可能路径均保存在中.4.3 车辆行驶路径选择在轨迹点匹配中，如果有多条道路满足匹配的条件，则可以使用计算匹配点权值的方法挑选出最有可能的一个.GPS

24、 轨迹点向附近所有道路做投影后，计算GPS 点与各道路间的投影距离 ，及车辆行驶方向与路段方向间的夹角 .计算各候选匹配点对应路链的权值 : = + ，其中和分别是投影距离和方向夹角的权值计算参数，且 =1.保存每个候选匹配点权值.生成最终的后，如果有多个叶节点保存是中最后一个轨迹点的匹配路链，则表明车辆可能存在多条行驶路径，每个包含匹配路链的叶节点向上回溯到根节点对应一条可能行驶的路径.累计每条路径上的候选匹配点的权值，选择累计权值最小的一条路径作为最终的路径推测结果.此外，由于在中保存了车辆的多条候选行驶路径，可以根据实际需要通过不同的权值计算方法对候选路径进行评估，选择车辆的最佳行驶路径

25、.4.4 算法时间复杂度分析在路径推测中，算法的性能主要体现在对路网的搜索效率上，通过对算法的路径搜索效率进行分析得到算法的计算性能.设车辆在一个时间段T内共采集到n个GPS轨迹点，每2个轨迹点之间进行一轮路径搜索.假设前一匹配点和后续的轨迹点所建立的向量平均长度为d，路链的平均长度为l，路链的后续路链数平均为3，满足约束条件（1）的路链数平均为2.假设路径搜索的候选路径数平均为t，每两点之间的路径搜索所花费的时间为，因此，算法的时间复杂度为.其中向量平均长度d，路链的平均长度l，路径搜索的候选路径数t均可考虑为常数值.4.5 生成示例图7示出了车辆在一段时间内的5条GPS定位数据记录的轨迹点

26、在路网地图上的分布情况，轨迹点按照时间顺序记为g1、g2、g3、g4、g5，路网上的道路被分成了路链并被编号，图中的黑色正方形代表了车辆位置点，红色圆点代表了车辆位置点在路链上的匹配点，红色有向线段代表了匹配点和下一个车辆轨迹点构成的向量，绿色路线代表车辆的行驶路径.图8示出了使用基于向量识别的启发式路径推测算法对图7中的车辆轨迹点进行处理而生成路径搜索树的过程.图8中的a，b，c，d，e，子图分别示出了浮动车轨迹点g1、g2、g3、g4、g5处理后所生成的路径搜索树.图8e为生成的最终路径搜索树，从中可以提取出两条路径作为车辆的候选行驶路径，通过比较匹配权值可以确定唯一的一条路径作为匹配结果

27、.图7 浮动车的轨迹点在路网上的分布示意图图8 的生成示意图5 实验分析为了验证本文提出的算法，作者使用了北京市的导航电子地图（包括57000条路链）和3500辆出租车发回的以60120秒为间隔的GPS数据作为浮动车数据进行了实验.5.1 准确性为了验证算法推测车辆行驶路线的准确性，在实验中作者抽取了三辆出租车，在正常运营时间范围内选取了北京市的主要道路作为规定的行车路线，然后提取出它们回传的GPS数据（包括车号，时间，经纬度，方向）输入算法中进行处理.通过推测出的车辆行驶旅程的正确率作为评测的标准.正确率的定义如下： (5)在推测结果的效果图9上，绿色代表推测正确的道路，红虚色的路线代表车辆

28、正确行驶而算法没有进行正确推测的道路.通过表1对测试结果的统计，可发现算法的准确率达到90以上.图9 测试路线2的路径推测结果表1 不同测试路线的匹配准确率统计路线路线长度测试次数推测正确的路径长度准确率 12235032064192.35%2035591.07%2043691.43%21516031442495.14%1435294.67%1425694.03%33276023008091.81%3010591.89%5.2 计算速度由于浮动车系统是对最近一段时间范围内（一般采用515分钟）采集的全部数据进行批量处理，因此本文选取早8：00至晚8：00的不同时间段，分别采用5分钟，10分钟，

29、15分钟的处理周期对算法的计算速度进行测试，并对不同处理周期下的平均计算时间做了统计，如表2所示.测试环境为：Pentium(R) 4 CPU 3.20GHz，1GB 内存.表 2 不同处理周期的计算时间统计浮动车数量平均GPS记录数处理周期平均CPU运行时间平均每秒种处理的GPS记录数3410134005min2520ms532034102620010min5850ms448034103962015min10930ms3625从对算法的运行效率上的测试可以看出算法具有很高的运行效率，可以充分满足浮动车系统的实时性要求.6 结论综上所述， 本文提供了一种适用于实时处理大规模浮动车GPS数据的路

30、径推测算法.它具有启发式搜索的特征，算法的效率不受路网的复杂性影响，将路径搜索的效率进行了有效的提高.通过实际数据的测试可以看出，其特点是实时性好， 效率高， 并且具有较好的准确性.下一步，我们将在候选路径的选择方法上进行深入的研究和实验，进一步提高算法的准确性.References:1 Stoiris Brakatsouls,Dleter Pfoser,Randall Salas and Carola Wenk. On Map-Matching Vehicle Tracking Data. Proceeding of the 31st VLDB Conference Trondheim, N

31、orway, 2005.2 J.-S. Pyo, D.-H. Shin, and T.-K. Sung. Development of a map matching methodusing the multiple hypothesis technique. IEEE Intelligent Transportation Systems Conference Proceedings, pages 23 27, 2001.3 Marchal, F., J.K. Hackney and K.W. Axhausen (2005) Efficient map-matching of large GPS

32、 data sets - Test on a speed monitoring experiment in Zurich, Conference Paper, STRC,Monte Verit.4 S.Brakatsoulas, D.Pfoser, and N.Tryfona. Practical data management techniques for vehicle tracking data. In Proc.21st ICNE conf, pages 324-325, 2005.5 J. Hackney, F. Marchal, and K.W. Axhausen. Monitor

33、ing a road systems levelof service: The canton of Zurich floating car study 2003. Presented at the 84th Annual Meeting of the Transportation Research Board, 2005.6 R. Kuehne, R.-P. Schaefer, J. Mikat, K.-U. Thiessenhusen, U. Boettger, and S. Lorkowski. New approaches for traffic management in metrop

34、olitan areas. In Proc. IFAC CTS Symposiun, 20037 M.A. Quddus, W.Y. Ochieng, L. Zhao, and R.B. Noland. A general map matching algorithm for transport telematics applications. GPS Solutions, 7:157167, 2003.8 J. Hackney, F. Marchal, and K.W. Axhausen. Monitoring a road systems level of service: The can

35、ton of Zurich floating car study 2003. Presented at the 84thAnnual Meeting of the Transportation Research Board, 2005.9 D.Pfoser and C.S Jensen. Capturing the uncertainty of moving-object representations. In Proc. 6th SSD conf. , pages 111-132, 199附中文参考文献: 9张其善,吴今培,杨东凯.智能车辆定位导航系统及应用.北京: 科学出版社,2002.Page.110.10丁胜昔.基于数字道路地图的车辆导航系统研究 博士学位论文. 北京: 北京航空航天大学,2004.