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

基于向量识别的启发式路径推测算法*Supported by the National High-Tech Research and Development Plan of China Under Grant No.2006AA12Z315 (国家高技术研究开展方案(863) and the Next Generation Internet Demonstrated Project of China Under Grant No GI-04-15-5A(3-8-002)(中国下一代互联网工程(CNGI).作者简介: 吕卫锋, 男,山东日照人,博士,副教授,主要研究领域为智能交通系统,网络管理;吴东东,男,硕士,主要研究领域为智能交通系统;诸彤宇,男,博士,副教授,主要研究领域为智能交通系统. 吕卫锋1+，吴东东2，诸彤宇3北京航空航天大学软件开发环境国家重点实验室 北京 100083A 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: 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 must 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 matching 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 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, 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) ; GPS; Heuristic search摘 要:浮动车数据主要是由车辆的轨迹点数据组成，是一种重要的原始数据，可以广泛的用于各种交通应用，如交通管理和控制，路况计算等. 但是原始的车辆GPS数据存在定位误差，必须经过路径推测的修正处理才可以应用.传统的路径推测算法主要采用两种方法：渐增式和全局式.两种方法各有优缺点，渐增式方法计算速度快但准确性差，全局式方法准确性好但计算速度慢.通过综合考虑两种传统算法，本文提出了一种基于向量识别的启发式路径推测算法，该算法采用了启发式图搜索方式，导入几何运算的约束条件，根据车辆轨迹点所形成的向量与路网模型比拟来进行启发式搜索，并选择车辆所有可能行驶的候选路径.根据全局择优的方式从整体进行比拟，确定车辆最有可能的行驶路径.实验结果说明，这种算法能够在复杂路网下，比拟准确地推测距离间隔较大的车辆轨迹点，并且能够实时高效地处理大规模数据.关键词:路径推测; 浮动车数据; GPS; 启发式搜索中图法分类号: TP301文献标识码: A 在智能交通领域，实时和动态的交通信息能为车辆出行，交通运输等提供有效的交通诱导和出行规划信息，从而到达节省出行时间、减少尾气排放等目的.为了实现上述目标，一个重要研究课题是高效处理实时、动态的交通信息.浮动车Float Car Data技术，也被称作“探测车Probe car，是近年来国际智能交通系统ITS中所采用的获取道路交通信息的先进技术手段之一.其根本原理是：根据装备车载全球定位系统GPS的浮动车在车辆行驶过程中定期记录的车辆位置，方向和速度信息，应用包括路径推测和道路交通拥堵信息计算等相关的计算模型和算法进行处理，从而使浮动车位置数据和城市道路在时间和空间上关联起来，最终得到浮动车所经过道路的车辆行驶速度以及道路的行车旅行时间等交通拥堵信息1.如果在城市中部署足够数量的浮动车，并将这些浮动车的位置数据通过无线通讯系统定期、实时地传输到信息处理中心，经过综合处理，就可以获得整个城市动态、实时的交通拥堵信息2.浮动车数据处理主要存在两个方面的问题，一方面，在定位数据的准确性上，由于浮动车所采用的GPS设备一般会有15米以上的圆周误差9，在搜索路径的过程中存在将轨迹点匹配到多条道路上的可能性.另一方面，在计算效率上，浮动车采集GPS轨迹点数据的采样率较低，一般在20300秒，造成两个连续轨迹点跨越了较长距离，两个轨迹点间有可能存在多条可行驶的路径. 传统的路径搜索算法主要采用两种方式：渐增式4和全局式3。渐增式方法分别对每个轨迹点进行路网搜索，计算轨迹点与其附近的道路的距离，选择与轨迹点距离最小的道路作为搜索结果。全局式方法那么使用曲线匹配的方式，连接连续的多个轨迹点形成轨迹曲线，与路网中的路径做几何曲线匹配，通过计算Frchet距离的方法选择相似的道路作为匹配结果。渐增式方法计算简单，因此处理速度快，但是准确性差；全局式方法从整体上进行考虑，因此准确性好，但是由于计算复杂，处理速度慢3。应用于浮动车信息系统的路径推测算法既要有高效的计算速度，又要有较高的准确性.传统的方法无法很好适用于这种应用.基于此，本文设计了采用启发式搜索路径的路径推测算法.首先在算法的计算速度上，为了满足实时性的要求，采用了渐增式方法，一方面，重新设计了路网模型和路网拓扑，将其与算法进行整合2.另一方面，利用启发式搜索方式，算法在特殊的路网模型支持下，利用车辆轨迹点所形成的向量与路网道路相比拟，导入三角形的几何理论作为约束，采用启发式的图搜索方式快速的搜索浮动车可能行驶的候选道路.两方面相结合有效的提高了算法的计算速度.其次，在算法的准确性上，采用全局择优的方法，通过树结构保存与车辆轨迹相符合的所有候选路径，然后比拟每条路径上轨迹点的匹配权值，从整体上选择最接近车辆轨迹的一条路径作为推测结果.本文第1节给出了相关研究，第2节介绍了算法使用的路网模型和路网拓扑，第3节对问题进行了描述与分析，第4节描述了算法的设计，第5节分析了实验测试的结果，最后对本文进行了总结，并给出了下一步研究工作.1 相关研究路径推测是浮动车信息系统的关键技术，是正确计算道路交通状况的根底.路径推测是通过匹配车辆较大间隔的行驶轨迹点数据，搜索车辆正确行驶路径的技术，是地图匹配的一种处理方法.传统的方法中，渐增式方法基于已完成点匹配的两点进行搜索，需要进行两次独立的地图匹配运算，然后基于路网拓扑进行道路的广度搜索找出车辆可能的行驶路径，搜索范围大，效率较低，准确性偏低；全局式方法那么使用曲线匹配的方式，将整体轨迹点形成轨迹曲线，通过与路网道路之间计算Frchet距离或弱Frchet距离的方法选择候选道路作为匹配结果，计算量大，效率低.2 路网模型和路网拓扑路网数据是路径推测的根底，同时高效的路径推测算法应该整合相适应的路网模型和拓扑.常见的电子地图路网模型一般是由基于桌面GIS (地理信息系统) 的路网模型改良得来.这种模型的缺陷在于难以表达复杂道路的拓扑关系，对路网的描述比拟单一，无法满足针对大规模浮动车数据处理的需求.因此，必须对原有路网模型进行改良，以适应高效路径推测的要求.基于此，本文通过对数据的分层处理和抽象，建立了新型的路网模型和路网拓扑.2.1 路网模型路网模型用于描述区域内的道路网，是由车辆轨迹点进行路径推测的根底.图1显示了路网模型的根本元素，包括节点和路段.整个路网模型可以表述为： 11式中Rn代表道路网络.N代表节点集，表示路网中构成道路的坐标点集合，其元素为经纬度值对x,y；S代表路网的路段集合，其元素是有序对，表示存在一条有向直线道路s，其起始节点，终止节点，且s上不存在其他节点，如图1中，节点1和节点2之间存在着路段1.假设在路网Rn中，存在一个路段的序列，其中每条路段的终止节点是下一个路段的起始节点，那么此序列代表路网上的一条有向通路，如图1中，路链3和路链4分别是由3条路段构成的通路.图1 路网模型中的根本元素2.2 路网拓扑结构假设n是路网Rn中的一个节点.出度表示以n为起始节点的路段的个数；入度表示以n为终止节点的路段的个数，如图1中节点1的入度为1，出度为2.路网Rn中的节点，当或时，n称为连通性节点.在路网Rn中，存在一条通路，假设S1的起始节点和Sn的终止节点均为连通性节点，且其他路段的节点的入度和出度均为1，那么此路段的序列L称为一条路链，路链的集合为 (2).在路网模型的根底上，根据道路网络的连通性和路链结构，建立路链间的拓扑结构图，其中，表示在路网上的路链集合，E那么是根据道路的连通性建立的路链之间的连通关系.按照路链之间的连接性，路链的驶入路链称为此路链的前继路链，路链的驶出路链称为此路链的后继路链，表示link是link的前继路链，而link是link的后继路链.如图2中所示，. 图2 十字交叉路口拓扑结构示意图2.3 向量在地图上取一坐标点为点的经度，为点的纬度，从出发向某点为点的经度，为点的纬度引一条线段，有方向且有长度，这种有向线段称为向量，记做，它的长度记作，表示与之间的距离，它的方向记作，表示为与正北方向的夹角顺时针方向，方向值取值0360.对于中的任一路链，其向量长度记为表示路链起点与路链终点所构成有向线段的距离，其向量方向记作，表示路链起点与路链终点所构成有向线段的方向.3 问题描述和问题分析3.1 问题描述在路网中，假设由其形成的路网拓扑为G，运动车辆在一个时间段T内的连续GPS轨迹点集合表示为，(为车辆定位坐标点 ，为车行方向)， .假设车辆在T内所行驶过的通路为，如何将轨迹点集合映射为，就是路径推测所要解决的最主要问题，即 3通过构建匹配函数，完成与的推测计算得到车辆的正确行驶路径.3.2 车辆行驶规律分析3.2.1 车辆行驶状态分析 车辆在短时间内的行驶轨迹具有一定的相似性，通过对车辆的行驶状态分析归纳，可以掌握车辆的行驶规律，再与路网模型相结合，进一步得到了路径搜索的启发式条件.下面通过实例的方式对车辆在路网上的行驶状态进行分析，并归纳路径推测算法的启发式搜索条件.(1) 车辆在单一路链行驶车辆的连续轨迹点位于同一路链上.如图3中，p1在link1上的匹配点m1与p2构成的轨迹向量其长度小于m1与link1的终点构成的向量长度，即e1=endlink1且.图3 车辆在单一路链上行驶(2) 车辆跨路链行驶车辆的连续轨迹点跨越了两条或两条以上路链，车辆根本存在了两种行车状态：一种是保持直行，如图4所示；另一种是转弯行驶，如图5a和图5b分别所示.图4 车辆跨路链直行在示意车辆跨路链直行的图5中 + + + + .另外，在方向上，车辆行驶路链的方向与向量的方向值必定会小于90.因此，车辆行驶时满足的约束条件可以归纳如下：(1). 路链的方向与匹配点和车辆轨迹点形成向量的方向值之差小于90，即 5(2). 车辆行驶经过路链的累计向量长度之和小于匹配点与车辆轨迹点形成向量的长度的2倍，即2 * + + + + 64 算法设计4.1 路径搜索树为了提高搜索效率，采用启发式搜索思想，其中路径搜索树定义为Ps-T，Ps-T=U，A，其中U是路网拓扑中V的非空子集，A为U集合中边的关系.从路径搜索树中得到算法的输出，是车辆记录的GPS定位数据的时间范围内所行驶的路径，表现为假设干条相连的路链.4.2 车辆行驶路径搜索4.2.1 候选匹配点为了提高地图匹配的准确性，本文提取了点匹配过程中两个特征：定义为GPS 轨迹点到路段的距离，dirDiff为行车方向与路链的角度差，帮助判断定位点M的所在。两个特征对应的后验概率为和，然后用SVM分类器进行分类。SVM的分类结果表示为： 7利用GPS匹配点的两个特征值定义匹配概率如下： 8对于给定的任一GPS轨迹点p，它在路链l上的候选匹配点被定义为匹配概率大于匹配阀值的点，记作且 ，其中z为p在上的匹配点.每个GPS轨迹点均可以通过点匹配得到其在路网上的匹配路链集合，表述如下 94.2.2 的生成路径搜索树将根据匹配路链集合的不同，进行不同的初始化：1. 如果候选匹配路链集合的元素只有一个，那么以匹配路链建立根节点，即；2. 如果候选匹配路链集合的元素大于1，那么建立一个空节点作为根节点，以每条候选匹配点路链分别建立根节点的子节点，即. 依据GPS定位的车辆轨迹，车辆在一段时间内的所有可能行驶路径都保存在路径搜索树中. 利用路网拓扑和车辆的定位数据，按照车辆行驶时满足的约束条件(5)和(6)，对车辆的行驶路径进行搜索时，这颗树的深度和广度就会不断的增加，树节点里保存着车辆可能行驶过的路链. 4.3 车辆行驶路径选择生成最终的后，如果有多个叶节点保存是中最后一个轨迹点的匹配路链，那么说明车辆可能存在多条行驶路径，每个包含匹配路链的叶节点向上回溯到根节点对应一条车辆的候选行驶路径.累计每条路径上的候选匹配点的匹配概率，选择累计值最小的一条路径作为最终的路径推测结果.4.4 算法时间复杂度分析基于路网拓扑G进行浮动车行驶路径的搜索通常是一个NP问题，每2个轨迹点之间进行图遍历搜索. 在本文介绍的方法中，设车辆在一个时间段T内共采集到n个GPS轨迹点，2个轨迹点之间进行一轮路径搜索. 假设前一匹配点和后续的轨迹点所建立的向量平均长度为d，路链的平均长度为l，路链的后续路链数平均为3，通过约束条件(4)的限制，参加的路链数平均为2. 两点之间的深度可到达2*d/l，起始两点完成搜索后，路径搜索树的叶节点为，假设叶节点中有1/2保存了匹配到的路链，因此，算法的时间复杂度为，为指数时间算法. 实际上，经过约束条件(5)和(6)的限制，其搜索空间范围非常有限，远远小于. 5 实验分析为了验证本文提出的算法，作者使用了北京市的导航电子地图包括86000条路链和13000辆出租车发回的以60120秒为间隔的GPS数据作为浮动车数据进行了实验.5.1 提高地图匹配精度在利用样本数据对匹配距离和角度差两个匹配特征值使用SVM分类器进行分类后，得到匹配距离和角度差dirDiff的后验概率线性拟合情况，如图6：图 6 匹配特征参数的后验概率线性拟合SVM分类得：= 0.64， = 0.36，阈值= 0.592。5.2 准确性为了验证算法推测车辆行驶路线的准确性，在实验中作者抽取了四辆作为浮动车的出租车，在正常运营时间范围内选取了北京市的主要道路作为规定的行车路线，分四组进行了11次路侧.通过算法计算出的车辆行驶旅程与实际路线比照的正确率作为评测的标准. 在推测结果的效果图7上，绿色代表推测正确的道路，红虚色的路线代表车辆实际行驶而算法没有进行正确推测的道路.通过图8对测试结果的统计，可发现算法的准确率到达93以上.图 7 测试路线的路径推测结果图 8 不同测试路线的匹配准确率统计5.3 计算速度由于浮动车系统是对最近一段时间范围内一般采用515分钟采集的全部数据进行批量处理，因此本文选取早8：00至晚8：00的不同时间段，采用缓存的5-15分钟时间范围内的浮动车数据对算法的计算速度进行测试，并对不同处理周期下的平均计算时间做了统计，如图9所示.测试环境为：Pentium(R) 4 CPU 3.20GHz，2GB 内存.(a) 不同采样周期下CPU处理时间统计 (b) 不同采样周期下处理速度统计图 9 算法的计算效率测试统计对算法的运行效率上的测试可以看出算法具有很高的运行效率，但是随着采样周期的延长，计算速度有所下降。从系统发布路况的要求来看，处理的时间应该控制在30s-40s以内，因此，算法可以充分满足浮动车系统的实时性要求.5.4 比照测试使用同样的测试数据，本文对渐进式和全局式的匹配算法进行了测试，并在准确性和计算效率上与本文介绍的启发式算法进行了比照. 从表1对不同算法的比拟可以看出，启发式算法在准确性和计算效率比渐进式和全局式算法具有明显优势，满足了实际ITS系统信息的需求，快速准确地提供了道路交通实时信息. 表 1 算法的比照测试结果渐进式全局式启发式准确性86%93%93. 75计算效率GPS记录数/秒45473235 8885 6 结论综上所述， 本文提供了一种适用于实时处理大规模浮动车GPS数据的路径推测算法.它具有启发式搜索的特征，算法的效率不受路网的复杂性影响，将路径搜索的效率进行了有效的提高.通过实际数据的测试可以看出，其特点是实时性好， 效率高， 并且具有较好的准确性.下一步，我们将在候选路径的选择方法上进行深入的研究和实验，进一步提高算法的准确性.References:1 Xiaowen Dai; Ferman, M.A. A simulation evaluation of a real-time traffic information system using probe vehicles. IEEE ITSC, Shanghai, China, 2003. 2003: 12-152 R. Kuehne, R.-P. Schaefer, J. Mikat, K.-U. Thiessenhusen, U. Boettger, and S. Lorkowski. New approaches for traffic management in metropolitan areas. IFAC CTS Symposiun, 2003, Tokyo, Japan. 2003: 42-453 Stoiris Brakatsouls,Dleter Pfoser,Randall Salas and Carola Wenk. On Map-Matching Vehicle Tracking Data. The International Conference on Very Large Data Bases, Trondheim, Norway, 2005.VLDB Journal, 2005, Vol.14: 853 - 864.4 Marchal, F., J.K. Hackney and K.W. Axhausen. Efficient map-matching of large GPS data sets - Test on a speed monitoring experiment in Zurich, Transport. Res. Rec., 2004, Monte Verit. 2004:23-255 Lv WF, Zhu TY, Wu DD.A heuristic path-estimating algorithm for large-scale real-time traffic information calculating. Science in China Series E:Technological Sciences, 2021 Vol. 51(zkI):165-1746 D.Pfoser and C.S Jensen. Capturing the uncertainty of moving-object representations. The 6th SSD conf. , Hong Kong, China, 1999. Springer Verlag LNCS , 1999:111-1327 Wu Dongdong, Zhu Tongyu and Lv Weifeng. A Heuristic Map-Matching Algorithm by Using Vector-Based Recognition. IEEE ICCGI, Guadeloupe, French Caribbean, 2007. IEEE Computer Society Washington, DC, USA,2007:18 188 J.-S. Pyo, D.-H. Shin, and T.-K. Sung. Development of a map matching method using the multiple hypothesis technique. IEEE Intelligent Transportation Systems Conference, Oakland , USA, 2001. 2001: 23 27.9 S.Brakatsoulas, D.Pfoser, and N.Tryfona. Practical data management techniques for vehicle tracking data. In Proc.21st ICNE conf, 2005:324-325.附中文参考文献: 10张其善,吴今培,杨东凯.智能车辆定位导航系统及应用.北京: 科学出版社,2002.Zhang Shanqi, Wu Jinpei, Yang Dongkai. Intelligent vehicle positioning navigation system and application. Beijing : Science Press, 200211丁胜昔.基于数字道路地图的车辆导航系统研究 博士学位论文. 北京: 北京航空航天大学,2004Ding Shengxi. Research of the vehicle navigation system based on the digital road network mapPhD thesis. Beijing : Beihang University, 2004BackgroudHow to acquire real-time and dynamic transportation information is becoming prevailing research focus in the community of Intelligent Transport Systems (ITS) nowadays. This information can be applied in the transportation area like vehicle navigation, traffic control and so on. Floating car data(FCD) refers to assess the overall traffic conditions. Using technologies like orientation, wireless communication and information processing to achieve the collection and disposal of the raw data like instantaneous speed, position and travel time of the floating cars. A pre-processing step that matches FCD to the road network is needed. This technique is commonly referred to as path-estimating. Large-scale, real-time and discrete distribution is the main characteristics of FCD, and the core processing algorithms must provide good performance of high efficiency and accuracy in order to meet the needs of real traffic information system. The traditional path-estimating algorithm adopts two mechanisms: incremental and global. The incremental method is simple and fast, while the accuracy of the results is poor; the global method is complicated and the accuracy of the result is pretty good, while the processing speed is slow. For this reason, the paper studies and designs a heuristic route-estimating algorithm by using vector-based recognition. The proposed algorithm is efficiency both at accuracy and computational speed when handling the large-scale data of GPS tracking data even under the complex road network conditions. This subject belongs to the Next Generation Internet Demonstrated Project-Beijing Internet ITS Demonstration and Application Project and the National High-Tech Research and Development Plan of China The research to key technologies of high-quality dynamic traffic information services for vehicles navigation. With the result of the projects, it provides real-time picture of traffic conditions of the whole road network of Beijing through handling large volume of GPS data recorded by 13000 taxis. The results of this paper provide the core computations which make the raw FCD to be related which the city road. 作者简介: 吕卫锋1, 男,出生于1972,博士,副教授,主要研究领域为智能交通系统,网络管理;Lv Weifeng, Male, born in 1972, Ph.D, Professor. His research interests focus on ITS, Network Managememt.吴东东2,男, 出生于1982,硕士,工程师,主要研究领域为智能交通系统;Wu Dongdong, Male, born in 1982, Master, Engineer, His research interests focus on ITS.诸彤宇3,男, 出生于1969,博士,副教授,主要研究领域为智能交通系统.Zhu Tongyu, Male, born in 1969, Ph.D, Professor, His research interests focus on ITS.