基于GPS车辆轨迹数据的地图匹配算法研究

陈芳芳

（阿里巴巴集团 北京市 100102）

在我国，车辆的管理是一个很重要的问题，目前国内很多城市都出现了停车难、车位贵等现象。由于人们出行越来越多导致交通压力增大，交通拥堵问题也越来越突出，车辆管理的智能化成为人们关注和解决的热点。基于GPS车辆轨迹数据技术能够实现对道路路段信息采集并进行实时更新与控制，通过卫星定位系统获取到最新路况情况和周边环境状况以及用户需求变化等相关路况资料，利用地图数据库存储在服务器中以便调用地理信息系统，提高运输效率及准确性的同时也能节省人力资源成本、增强竞争力。由于这些原因，基于GPS车辆轨迹数据的路径匹配算法在交通领域得到了广泛研究和应用。

1 地图匹配算法研究

1.1 地图匹配的概念

车辆的轨迹匹配是基于地图数据集进行路径规划，以满足用户需求，实现对路段、道路和时间点等信息在计算机中显示，并根据实际情况选择合适路线。定位技术结合地图匹配算法，实现车辆的三维地形图和交路GPS数据。该方法能够有效地减少人工操作过程中存在着错误率高、计算量大等问题，同时还能避免算法在实际应用中路由过采样点处的布设误差以及由于天气原因产生局部精度差值造成定位失败，提高了系统运行速度并降低成本。

地图匹配算法主要包含两个重要的过程：一是要先定位到该物体当前正在形式的道路，并根据路线图确定目的地，从而得到地图匹配方测量点。二是将当前的定位点投影到道路上，计算出匹配方的位置。车辆轨迹数据是基于GPS实时导航系统而产生，该算法可以根据道路信息生成路线图，并能获取当前时间段内的车流量、车道数和方向等基础参数。

1.2 常用的地图匹配算法

（1）直接投影法。直接投影方法的应用是基于在车辆运动方向上，通过计算车轮与轨道间距离，从而得到地面点坐标。该算法的基本思想是根据实际的车辆运动轨迹，在计算机上计算车轮与轨道间距离，从而得到地面点坐标，该算法采用的是轮轨测距和轨道数据匹配，可以在计算机上通过GPS轨迹数据计算出车辆运动速度和加速度，该算法的实现需要硬件、软件以及数据库。直接投影方法如图1所示。

图1：直接投影方法

图1中P点可以看做为一个定位点，而道路A和道路B是离该定位点最近的两条道路，该车辆轨迹上有一条起始点，且相邻两条道路之间距离较近，根据交通流分析的方法计算出两条车道数和A、B路段间平均坐标。通过公式（1）可以分别计算道路的距离度量值：

式中ri表示点P到各条道路的隐射聚力，θi是物体行驶方向与道路之间的夹角，分别为距离和方向的权重系数。

（2）基于几何关系的算法。基于几何关系的路径匹配算法是一种常见且实用性较高的车辆轨迹匹配方法，它把GPS导航和无人机航拍相结合，根据地理位置、周边环境等信息对车辆位置进行定位。通常基于几何关系的地图匹配算法具体分为三种：点到点的匹配、点到线的匹配及线到线的匹配。

点到点的匹配，指的是将GPS定位点匹配到附近道路网络中的节点或形状点上，以一定的比例、位置计算出所匹配到点处的坐标，并按照某种规则进行组合，从而得到车辆轨迹。此算法匹配速度快，但计算量大，且在车辆运动轨迹数据中，该算法可以有效的处理大量道路数据。点到点匹配的具体数学计算模型如图2所示。

图2：点到点匹配

点到线的匹配是指车辆从起点到终点间的所有路段上的数据信息匹配，是基于GPS定位技术实现，其原理是通过GPS定位点做所有待匹配路段的投影距离，并将其与已匹配路段的实际距离进行对比，从而得出车辆在起点到终点间所有道路上运行轨迹信息。具体做法是当道路为直线道路时，通过GPS地图数据计算出车辆的坐标，再将其平分成不同路段，分别匹配到直线路和交叉口，再做垂线段。点到线的匹配的数学模型如图3所示。

由图3中可知，P点到直线AB的距离为的计算如公式（2）所示：

图3：点到线的匹配

P点到直线AB的投影点C即为候选匹配点，k为直线AB的斜率，则C点的坐标计算如公式（3）所示：

线到线的匹配算法是交通领域中的一个重要内容，也是解决数据匹配问题最常用且有效、最快速和最有效率途径之一，在车辆运动控制和智能导航等方面得到了广泛研究。该算法不仅利用了当前GPS定位数据，还利用了历史轨迹数据，可以在地图数据中添加导航信息，使车辆轨迹的匹配更加准确。与前面两种算法相比，该算法是一种更先进的算法，具有很强的实时性，可以在地图数据中添加导航信息。线到线的匹配算法的具体数学计算模型如图4所示。

图4：线到线的匹配

用积分来计算两条曲线之间的距离，则曲线的平均距离计算如公式（4）所示：

（3）概率统计算法。概率统计算法是根据实测值或历史测得的数据，对所有可能出现的情形，按一定规则进行统计运算分析。该算法的基本思想是依据GPS 接收到的定位数据设置一个误差区域，根据实际数据和已知的车辆轨迹分析出两者之间的关系，计算出相应误差区域，再将得到结果与真实轨道差值进行比较以验证匹配算法正确性。概率统计算法利用误差椭圆确定了置信区域，然后从数字地图数中提取候选路段，然后根据已提取的路段信息计算出车辆行驶方向、运行距离等行车状态，最后将结果与真实轨道差值进行比较，得到匹配情况。按照统计理论，定位误差椭圆的推导如公式（5）所示：

（4）模糊逻辑算法。模糊逻辑算法是利用计算机对输入信息进行判断，并根据相应的规则来处理输出。它通过模拟人脑中多角度和空间经验而得出一个较为理想化结果，其优点在于能够在一定范围内实现最优控制。该方法主要有两种形式：一种情况是将所有信息按不同方式划分成许多集合，然后再进行划分，这种方法在计算过程中能够实现快速准确的运算，并且能将时间分割为若干个小区间。另一种则为根据集合确定出一个规则函数来实现模糊逻辑推理，通过GPS车辆轨迹数据的特点来确定出离散点在同一地点下所对应的位置。

1.3 改进的基于权重的地图匹配算法

基于权重的地图匹配算法是在车辆轨迹数据中引入了一些权重，这些指标和层次分析法可以有效地对采集到的交通信息进行处理。它能够将各种不同类型道路之间存在着一定差异性，但是由于其本身具有主观因素导致计算过程复杂、运算量大等问题限制了其应用范围与实际价值不相符甚至出现偏差，同时也无法准确获得所需匹配路段的具体位置以及车辆在整个路网中所处地理位置，因此不能很好地利用这些数据对路径优化算法进行设计和实现。

基于权重的地图匹配算法是局部修正算法，它的计算量比较大，但在实际应用中，由于车辆运动轨迹具有不确定性，所以需要进行大量数据处理。本文进行GPS车辆轨迹研究时，主要是将基于权重的地图匹配算法和道路拓扑结构相结合，通过GPS车辆轨迹数据进行匹配，同时，将车辆轨迹数据和道路信息相结合，从而获得更加精确的匹配结果。

2 影响地图匹配质量的因素

2.1 GPS定位误差

在车辆路径规划中，定位误差是不可避免的，GPS数据采集到的是行驶距离、车道位置信息以及方向偏差等多种因素引起的车迹地别的偏移而产生，从而影响到车辆行驶的准确性。由于这些信息存在于不同载体上且具有不确定性和非连续性特征，因此对卫星导航系统造成了一定程度上损失。基于车辆轨迹匹配算法可以实现道路资源合理分配并提高道路运输效率：通过使用GIS地图定位软件，可有效避免交通拥堵情况，GPS轨迹数据中蕴含着大量的车辆位置和行程信息，可以在地图上显示停车位、路径等相关参数，利用GIS地理信息系统（如卫星定位系统）获取道路资源时，可实现对地面交通流进行实时监控。

GPS定位误差包括内部误差和外部误差。内部误差是指由卫星接收引起的固定误差，主要原因是卫星运行速度太慢，并且在经过若干年后，GPS车辆轨迹数据精度已经很难满足用户的需求。外部误差则有环境因素和天气原因等方面引起，主要包括GPS系统自身存在的一些缺陷,例如气象条件、地形地貌以及道路状况等，这些都会对定位精度造成影响。基于GPS车辆轨迹数据的定位方法，通过对已有算法原理进行分析归纳，提出了利用多传感器网络相结合来提高车位计算精度、增强地图匹配速度和满足用户需求等优化方案。

2.2 电子地图误差

由于通过GPS轨迹数据中的车辆位置、速度、方向等信息来匹配到当前车主所处地点，并在这些内容记录下行驶时间，根据地图上显示出来的路线图和对应路段进行坐标计算。因此在交通系统中占有重要地位，其性能优劣直接影响到车辆运行速度、道路数据传输质量和处理效率等。基于GPS轨迹数据采集与分析技术是一种新型地理信息系统，该数据库采用了GIS地图管理系统来管理平台上所有存储空间位置分布图谱，并根据道路信息数据建立了基于地图数据库的车辆轨迹库。电子地图的精度误差对地图匹配效果的影响很小，但出现道路变更、道路情况复杂以及电子地图精度较低的情况时，将会加大电子地图的误差，导致地图匹配失效。

2.3 坐标变换误差

坐标变换的精度是指计算出车辆在坐标系中点相对于车轴或线下两点间轨迹角度。它可以消除由轨道误差所引起的数据处理上出现错误。由于GPS定位系统采用的是车载天线，因此其坐标变化对车上车辆位置也有一定影响，因此需要在车辆轨迹匹配过程中对其坐标进行准确的调整以保证数据能够满足实际需求。

3 地图匹配软件的实现

3.1 开发工具及环境

车辆轨迹数据的匹配是一个过程,它需要根据实际情况进行选择和分析。在开发工具上，主要采用Microsoft Visual Studio 2010开发平台和MapInfo公司提供的MapX控件进行地图匹配模块的集成二次开发，利用MATLAB、Java语言和C++编程语言对车辆轨迹进行数据处理，同时结合数据库技术，完成了基于GPS的车辆路径轨迹匹配算法。其中硬件环境使用的是智能手机定位模块和计算机硬件。

3.2 地图匹配的总体设计与实现

地图匹配的应用目的不同，对地图匹配的实时性、效率等的要求不同，导致车辆轨迹匹配的方法也不同。基于GPS数据平台，通过合理安排车道、车速等基本信息，根据道路情况确定路线并实现实时路况显示，利用GPS轨迹信息进行车辆路径匹配，可以大大提高路况数据的实时性，为司机提供一条准确、快速且易于操作控制和保护的道路。根据本文的应用需求，地图匹配软件的总体设计如图5所示。

图5：地图匹配软件的总体设计

4 实验效果分析

本次实验的数据来源为两部分，一部分为校园实测数据，该数据是通过Android智能手机的GPS定位技术，通过数据的拼接与处理，生成位置轨迹，再使用GPS车辆运动控制软件GPRS模块获取到导航信息。另一部分是基于匹配算法中基于对已有地图资料进行调整后得到较为精确地车距、时间等参数。这些结果都能在一定程度上减少人为因素造成不必要损失和提高计算精度降低成本支出，另外该方法可以通过GPS卫星定位系统实现高分辨率的道路数据，还可利用车辆轨迹数据库提供的交通状况实时分析数据支持来满足用户需求，通过车辆轨迹数据的匹配计算可以得到道路行程时间，还能在地图上提供更加精确地导航路径，满足用户对车距、速度等参数的要求。

通过实验，对本文所提出的算法进行分析研究，围绕准确性和实时性2个重要指标，来衡量本文算法的有效性。

4.1 准确性分析

为了验证本文匹配算法的准确性，分别采用三组不同地方的GPS轨迹进行实验，并获取了车辆轨迹数据。通过不同的方法，将所获取到的GPS轨迹与电子地图进行匹配，结果对比如表1所示。

表1：基于权重的匹配算法

4.2 实时性分析

在实验过程中，为了评价该算法的实时性，我们对车辆轨迹数据的获取、处理和匹配过程进行了研究。通过分析得知,使用GPS导航定位模块,基于地图生成算法中最常用到的是曲线拟合。本次实验通过多线程并行化方法优化算法，实验结果如表2所示。

表2：实验结果

实验结果表明:基于GPS的车辆轨迹数据匹配算法在实际应用中具有较好的效果,能够满足用户对实时信息和路面状况准确且及时地提供相应导航服务。同时,该方法还可以用于交通监控领域，如交通拥堵的实时监测、高速公路动态流量采集等方面。

5 总结

综上所述，随着GPS技术的不断成熟，基于交通信息数据领域对车辆轨迹智能化管理已经成为现实，在我国国内许多大城市和综合实力强大、使用方便的公共停车场也越来越多，基于交通信息数据领域的GPS车辆轨迹智能化系统已经在国内被广泛投入使用。本文基于GPS车辆轨迹数据采集与匹配算法研究，对基于个人GPS轨迹数据的地图匹配算法进行了研究，提升位置服务应用的用户体验，实现交通信息实时匹配。根据车辆轨迹数据获取和处理的基本原理，提出基于位置、距离等关键参数，利用GPS车辆运动学模型，结合GIS平台进行车位分配算法研究。通过实验结果表明：基于权重的地图匹配算法具有较高的精确度与高效性，同时也能保证在城市道路拥堵情况下提高运输效率并降低交通事故发生率，其计算速度快且可重复率低是它存在和发展所要求实现的目标之一。