张 贺 孙婉莹 宋国平

（1.吉林开放大学，吉林 长春 130000；2.长春市公安局，吉林 长春 130000）

0 引言

随着信息技术的不断发展，GPS 卫星定位技术和地理信息系统（GIS）日渐成熟，基于GIS/GPS 的车辆导航系统已经广泛应用于车载监控及定位领域。在车辆导航系统中，GPS 定位数据误差和电子地图精度误差成为影响地图匹配精度的关键因素，GPS 定位点在电子地图上的匹配位置与车辆实际运行道路时常出现偏差。针对这个实际问题，现提出以下解决方案：1）提高GPS 定位数据及电子地图数据精度。2）采用地图匹配方法。比较以上2 个方案可以得出，前者实现成本较高，无法通过有效手段消除车辆行驶轨迹的显示误差。后者是基于软件技术的一种定位修正方法，它将GIS中道路层数据和GPS 定位数据进行有效匹配，以缓解各种误差导致的消极影响，使车辆实际定位点精准匹配到GIS 中道路层，精确的地图匹配结果可为监测交通流量、实时导航等提供可靠的基础数据。

1 技术简介

1.1 ArcGIS 平台

地理信息系统（GIS）是具备多种功能的一种综合性质的信息管理系统，它广泛应用于各大领域。Arc GIS 10.4.1 作为Arc GIS 10 系列里的一个完整GIS 软件集合，包括类似Arc GIS for Desktop、服务端GIS 等功能框架。其中，Arc GIS for Desktop 主要作为GIS 桌面端的一款软件，包括创建、编辑地理信息以及对地理信息进行分析处理等内容，它不仅能够提供1 套Windows 桌面应用（这里主要指Arc Map 10.4.1），而且能够提供采集和管理数据、构建空间模型等功能。

1.2 ArcPy

ArcPy 包是在arcgisscripting 模块功能基础上继承和丰富Python 站点包的，ArcGIS 平台依靠它来访问包内部所提供的各种地理信息方面的处理方法和模块类，进而进一步访问和处理GIS 平台上的数据，具体可实现的功能包括高效创建和使用各个应用程序、快速在各类业务方面形成逻辑以及完成几何操作、地图代数、地图操作和编辑处理等功能。ArcPy为用户提供了强大的功能，不仅可以通过调取相关的类及函数来实现将代码补充完整的功能（这里主要讲的是自动创建地图和执行交互操作的相关接口函数实现了补充完整功能），而且提供了利用Python 语言调用全部地理处理工具的操作（这里主要指Toolbox），主要负责实现地理数据转换、数据分析以及数据管理等内容。

1.3 GPS

目前，全球定位系统不仅可以应用到大气观测、地理勘测等领域，而且还可以应用到车辆导航系统中，为驾驶员提供路线导航，以便驾驶员可以安全、准确地按照选定路线行驶。

GPS 具备以下4 个特点：1）覆盖范围很广。GPS 导航定位系统是由很多卫星构建而成的一个强大的分布网络，这些卫星可以循环且按照合理的运行周期往地球GPS 接收站传送观测的信号，以便为地球上的驾驶员提供实时导航。2）实现路线实时导航。GPS 车辆导航系统通过语音及线路导航2 种方式为驾驶员提供多个可能行驶路线，并能够根据驾驶员当前行驶路线实时更新后续行驶线路。3）定位准确。GPS车辆导航系统可以全方位且实时地发送精确的车辆位置、方向及车辆行驶速度等定位信息，定位准确度很高。4）成本相对较低。只要对相关软件、硬件设备进行合理配置，就可以免费使用GPS 车辆导航系统。

1.4 WGS-84坐标系

车辆导航系统采用WGS-84 大地坐标系作为表示GPS车辆定位数据经常使用的坐标系，这种坐标系的具体原理简述如下：坐标系的原点主要是地球质心，选取的X轴坐标方向主要是BIH1984.0 的零度子午面和CTP 赤道的交点，Z轴坐标的方向与CTP 的方向一致，X轴、Y轴及Z轴构成直角三维的右手坐标系。

WGS-84椭圆体选择地心坐标系作为主要坐标系。WGS-84椭球上地表实体经纬度（L、B）、实体所在位置高度（H）分别对应空间的直角坐标（X、Y和Z）。

在进行地图匹配前，需要将空间坐标系转换为直角坐标系，具体转换公式如公式（1）～公式（4）所示。

式中：N为卯酉圈曲率半径；e为地球偏心率；a为地球椭球的长半径。

2 原始数据及其误差

该算法采用的原始数据主要来自某市出租车实际行驶数据（GPS 定位数据）和GIS 路网数据，定位数据采集时间间隔较长且松散稀疏，每隔20 s 传输1 次，从道路特征上来看，大部分路况以交叉口或平行路段居多。影响出租车行驶轨迹匹配准确性的因素主要包括GPS 数据及其误差、坐标转换误差和GIS 数据及其误差。

2.1 GPS 数据及其误差

GPS 定位存在一定的误差，GPS 定位误差主要包括GPS系统及其他因素导致的误差。出租车导航系统中的GPS 定位误差主要是由GPS 定位系统造成的误差[1]；其他误差主要由卫星测量导致误差、传播途径影响的误差以及接收机本身造成的误差组成[1]。

2.2 坐标转换误差

在与电子地图中的GIS 路网数据完成匹配测试前，需要完成坐标转换，即需要将车辆的多维定位数据进行高斯一克吕格正形投影处理变成二维数据，但是在坐标转换过程中，无法达到精准无误的坐标转换。

2.3 GIS 数据及其误差

在获得道路网数据并构建拓扑关系时，必须保证电子地图的路网地图数据具有规范有序的网络拓扑结构信息和高质量坐标数据，这样才可以真实展现道路状况，才能为后续的地图匹配试验提供准确的基础数据。因此，对匹配精度来说，路网地图数据的质量至关重要。

3 基于投影的地图匹配算法

3.1 基本思想

基于投影的地图匹配算法的基本思想如下：选择待匹配GPS 定位点附近所有道路作为候选投影路段，并分别向全部候选路段进行投影操作，计算待匹配点与全部候选路段间的投影距离di以及车辆行驶方向与各路段间的夹角α，如公式（5）所示。

式中：i为各个投影路段；λd、λα分别为距离、方向的权值；Wi为各候选路段的度量值，从全部候选路段的度量值Wi中选择最小度量值作为最终匹配路段，即判定车辆行驶在该路段上。

现将λd、λα分别赋值为0.5，通过公式（1）计算得出最小度量值为W1，确定其对应的候选路段L1作为车辆的最佳匹配路段，选择p1点在匹配路段L1上的投影点p1作为车辆的最终匹配位置。

3.2 投影算法的局限性

基于投影的地图匹配算法目前被认定为逻辑相对简单且在简单路段具有较好的匹配效果，但是在复杂道路网（交叉路口或平行路段）匹配效果不理想，极易出现错误匹配情况。当在交叉口路段或2 条距离相近的平行路段行驶时，按照车辆实际行驶轨迹判断得出，车辆行驶点p1的正确匹配路段为L1且匹配位置点为p'1，但是通过算法匹配到了路段L2且匹配位置点为p'2。经过反复试验验证得出，该算法需要在原有匹配因素的基础上，新增定位点与待匹配路段的相对位置、待匹配道路和历史匹配路段的连通性这2 个匹配因素才能提高匹配精度。

4 改进的基于特征权重的地图匹配算法

4.1 设置“缓冲区域”

该算法采用的电子地图内包括大量路网数据，假如针对整个路网道路执行匹配试验时，特别影响匹配效率。为了改善这种情况，就需要根据当前车辆位置信息筛选满足算法匹配规则的待匹配道路范围。因此，该文提出的算法设计了“缓冲区域”概念，基本原理是以车辆当前GPS 定位点为圆心来划定缓冲区域，并确定圆形区域内所有的候选路段作为地图匹配测试的路段。设置“缓冲区域”主要通过调用ArcGIS 中内嵌的ArcPy 包中函数来计算实现。

4.2 算法描述

基于特征权重的地图匹配算法基本原理如下：1）设置“缓冲区域”，筛选车辆当前GPS 定位点在缓冲区域内所有的候选道路，并判断历史GPS 定位点已匹配成功位置点行驶至当前GPS 定位点匹配位置点是否符合驾驶行为，是否存在道路，经过这一系列判断后，存储具备合理性、可达性的路段。2）判断已确定的历史匹配成功路段与当前待匹配路段是否符合合理的拓扑关系，并存储具备拓扑关系的候选路段，舍弃不具备拓扑关系的候选路段。

4.3 确定最佳匹配路段

通过以上步骤的精确筛选后，如果GPS 定位点还存在多个候选路段，通过该文提出的算法对当前GPS 定位点和其缓冲区域划定范围内候选路段之间夹角与距离相似程度、定位点和候选道路相对位置、候选道路和历史匹配路段的连通性等3 个因素执行加权计算操作，选择权重值最小的候选路段作为最佳匹配路段。

4.3.1 相似程度权重

利用当前GPS 定位点和其缓冲区域划定范围内路段之间夹角与距离关系去计算相似程度权重值。GPS 定位点将向缓冲区域内的待匹配路段进行垂直投影操作，然后计算道路通行方向和车辆瞬时行驶方向的夹角、当前GPS 定位点到全部待匹配路段的垂直距离，并通过公式（6）计算每个待匹配道路对应的相似程度数值。

式中：λα为cosαi相应的权重系数；λd为di相应的权重系数；W1为相似程度权重相应的特征值。

4.3.2 定位点和候选道路的相对位置权重

如果当车辆驾驶到复杂道路（例如交叉路段）时，车辆瞬间驾驶方向和各候选道路所形成的夹角有较大偏差，当前GPS 定位点pi和候选道路L1、L2和L3形成夹角分别为β1、β2和β3，其大小的差别较大。当车辆瞬时驾驶方向与各个候选道路通行方向形成的夹角越小，代表定位点和候选道路相对位置这个因素的权重值越小，对应路段是最佳匹配道路的概率就越大[2]。定位点和候选道路的相对位置权重相应的特征值如公式（7）所示。

式中：λ2为cos|βj|相应的权重系数；W2为定位点和候选道路的相对位置权重相应的特征值。

4.3.3 连通性权重

判断当前GPS 定位点缓冲区域内的全部候选路段与以往匹配成功路段之间是否满足合理的拓扑关系，保存满足合理拓扑关系的候选道路，舍弃不满足合理拓扑关系的候选道路，直至后续全部GPS 定位点执行匹配试验成功后，利用Dij kstra 算法去计算历史匹配成功路段和后续定位点对应的匹配道路的最短长度路径，该算法基本原理是利用数组按照权重大小顺序排列存储路径长度，最后选择具有最短路径长度的路段作为最优匹配路段[3]。

当前车辆GPS 定位点pi向路段L1和路段L2分别做垂直投影，投影位置点分别为点A和点B，以往GPS 定位点pi-1在匹配成功路段L3上的位置投影点是点C，Ldistance表示车辆处于持续时间段里的真实行驶距离，其本质就是计算点pi-1到点pi的欧拉距离代表上一个GPS 定位点pi-1在匹配成功路段L3上投影位置点C到点pi在候选路段L1、路段L2上投影点A、点B在道路网上的成功匹配距离（匹配距离如果真实行驶距离与匹配距离相减后的绝对值越小，就代表路段Li为点pi的最佳匹配路段，如公式（8）所示。

4.3.4 计算总权重

利用网格搜索法确定每个权重对应的系数[4]，规则如下：1）连通性的权重系数>相对位置的权重系数>相似程度的权重系数，即λ3>λ2>λd+λα。2）相对位置的权重系数+连通性的权重系数+相似程度的权重系数=1，即λ3+λ2+λd+λα=1，其中λd=λα。3）设定一个阈值（由经验确定），以确定经过加权计算操作后满足要求的匹配路段。利用该文提出的算法对“缓冲区域”内全部候选路段的3 个权重进行加权计算操作，比较在合理阈值范围内的全部候选路段的权重值，选择权重值（W总）最小的路段为最优匹配路段，如公式（9）所示。

4.4 算法匹配步骤

筛选最优匹配路径的过程如下[5]：1）收集车辆经度坐标、纬度坐标以及瞬时运行方向等全部信息。2）对数据进行预处理。舍弃无效或异常数据。3）对预处理后的GPS 数据和路网数据进行坐标转换操作。4）设置缓冲区域。以当前GPS 定位点为圆心画圆，选择圆形区域范围内的全部路段作为候选路段。5）按照合理可达性原则保存具备合理可达性的路段，舍弃不具备合理可达性的道路。6）如果当前车辆的GPS 定位点在缓冲区域内只存在1 条候选路段，则选择基于投影的地图匹配算法来匹配车辆位置点；如果当前GPS 定位点不止存在1 条候选路段，则通过网格搜索法确定权重系数，利用该文提出的算法计算全部侯选路段的3 个特征对应的总权重值，并将具有最小权重值的候选路段确定为最佳匹配路段。7）如果同一辆车所行驶过的道路存在不连续的情况，就需要综合考虑合理可达性、最短路径算法、当下GPS 定位点的候选路段和历史匹配成功路段的连通性等因素来筛选车辆最佳匹配路段。8）匹配结束。

5 试验结果及分析

该文采用某市出租车的GPS 定位数据及道路网数据来完成地图匹配试验，算法匹配试验平台采用ArcGIS 的ArcMap 模块功能完成匹配试验，选用Python 语言实现具体功能，在进行匹配试验前需要将GPS 定位数据的多维坐标转换为二维平面坐标。该算法从上千条出租车GPS 实际运行数据中任意抽取1 条运行轨迹数据，并将其在电子地图里展现图层。在交叉口、平行路段完成2 种地图匹配算法的匹配对比试验后，使用基于投影算法在交叉口路段达到的匹配率为61.5%，平行路段匹配率为80.3%，总匹配率为70.9%；使用该文算法在交叉口路段的匹配率为82.6%，平行路段匹配率为93.7%，总匹配率为88.1%，显然该文算法匹配效果更好。

6 结语

车辆导航系统采用的基于特征权重的地图匹配算法的精确地图匹配结果可以为监测交通流量、判断交通拥堵情况以及实时导航提供可靠的基础数据。它在原有的基于投影的地图匹配算法基础上做出了改进，能够在平行路段、交叉路段取得较理想的匹配效果。在未来工作中，将进一步研究地图匹配算法，使它向更优化、更高效的方向发展，并继续探索算法在其他领域应用的可行性。