1 引 言

地图匹配^[1]是将定位装置获得的定位轨迹通过一定的算法，与电子地图的道路信息进行匹配，由此确定车辆在地图上的实际位置。它借助GIS电子地图库中的高精度道路信息作为模板来进行模式识别，根据识别的结果来纠正GPS接收数据的定位误差^[2]。现有的地图匹配算法的基本思想都是按照一定条件筛选候选道路，再通过具体判断规则得到最佳的匹配道路^{[3, 4]}。文献^[5]采用基于模糊理论的地图匹配算法，利用车辆行驶信息不同方面权重的设计，对模糊性作出合理的评判，从而得出匹配道路。文献^[6]结合卡尔曼滤波及其相关技术，利用其在误差处理方面的优势来改善地图匹配结果的可靠性。文献^[7]提出一种基于地图识别和图形识别的方法来研究路径匹配，通过比较车辆行驶时旋转变化度量与地图路径的几何区别实现地图匹配的目的。文献^[8]提出一种基于预测的不确定性推理组合地图匹配算法，利用云模型对车辆行驶信息的不确定性进行推理，并利用隐马尔科夫模型预测驾驶员出行路径，结合二者的信息实现地图匹配。这些算法都有一定的匹配精度，但对于道路网较为密集的城市而言，误差率高，匹配精度无法满足车联网的需求。

利用D-S证据理论^[9]决策者可以根据不完备、不精确或不完全可靠的证据，通过对一些事件的概率加以约束以建立信任函数，并通过证据融合，挑选出问题的正确答案。文献^[10]根据D-S证据理论的基本原理，给出车辆行驶位置和方向信息的基本概率分配函数的设计方法，通过D-S合成公式对二者进行融合，得出融合结果选择匹配道路。相比其他算法，由于增加了逻辑复杂度而具有较高的匹配精度，但仍无法满足城市汽车导航的需求。为获得更高的匹配精度，适应当今复杂的交通网，本文设计了一种改进的D-S证据理论地图匹配算法，对车辆的可达性证据加以考察，并根据城市中不同道路拓扑结构使用最优的可靠性参数值，综合考虑城市路网的复杂性和车辆行驶特性进行地图匹配。

2 基于D-S证据理论的地图匹配算法介绍^[11]

根据D-S证据理论^{[12, 13, 14]}，识别框Θ描述所有候选道路的集合：Θ=A₁,A₂,…,A_n，设i=1,2,…,n，A_i表示车辆在第i号道路上行驶。设j=1,2,…,n表示第j号证据，用车辆GPS定位点P的位置信息和行驶方向信息作为D-S证据理论中的两个证据，设证据函数为c_j,i。当j=1时，c_1,i为位置信息证据函数，令

式中，d_i表示定位点P到第i号道路的投影距离，投影距离越小，位置信息证据越可信。当j=2时，令
式中，α_i表示正北方向顺时针旋转与第i号道路的夹角；α表示正北方向顺时针旋转与车辆在P点的行驶方向的夹角；β_i表示车辆行驶角度的变化值，车辆行驶角度与道路角度差值越小，方向信息证据越可信。考虑到在实际系统中的易实现性，基本概率分配函数构造如下

式中，m_j(A_i)表示证据j对命题“道路A_i是匹配道路”的精确信任程度，即m₁(A_i)是位置信息证据的基本概率分配函数，m₂(A_i)是方向信息证据的基本概率分配函数；m_j(Θ)表示当前时刻由于证据的不可靠和不准确而不能确定车辆在哪条道路上；k_j表示证据j的可靠性参数，即k₁为位置信息证据的可靠性参数，k₂为方向信息证据的可靠性参数。

再得出信任函数Bel(A_i)=m(A_i)和似然函数Pl(A_i)=m(A_i)+m(Θ)。其中，信任函数表示该证据下有理由相信A_i为候匹配道路的程度，似然函数表示不反对A_i为匹配道路的程度。

根据D-S合成公式^{[12, 13, 14]}，将得到的位置信息和方向信息在识别框Θ上的基本概率分配函数m₁和m₂融合为一个m函数，表示命题“道路A_i是匹配道路”的精确信任程度

根据以上条件，可以得出命题“道路A_i是匹配道路”的类概率函数

对于不同的道路A_i，式中的m(Θ)/n值是不变的，考察f(A_i)的值就相当于考察m(A_i)的值，即{maxm(A₁),m(A₂),…,m(A_n)}，得对应的道路即可判定为车辆当前行驶的道路。

3 算法的改进策略 3.1 城市环境不同路段的可靠性参数取值研究

车辆在城市环境行驶的过程中会遇到平行路段、交叉路口以及立交桥等特殊路段^[15]，对于这些路段的处理是目前匹配算法面对的难点。文献^{[16, 17]}考虑车辆轨迹曲线与路网路径的曲线相似性等约束条件，通过一系列规则以实现地图匹配。基于D-S证据理论的地图匹配算法则是通过改变证据的可靠性参数值以适应不同的路段，文献^{[10, 11, 12, 13, 14]}等对可靠性参数k₁和k₂的取值固定为0.8，虽都提及两参数对结果影响较大，但并未就此展开研究。

因此，本文遵循可靠性参数选择中适用性和针对性原则，根据实际道路拓扑结构的特点，选取相应的可靠性参数值。由式(3)可知，证据的可靠性参数值越大，表示其证据参考的价值越可靠。首先定义算法的可靠性参数默认值为0.8；取值时考虑车辆定位点所处路网，当某种道路环境下位置或方向信息证据更为可靠时参数值取0.9。分为“位置信息证据较可靠”(k₁=0.9，k₂=0.8)、“方向信息证据较可靠”(k₁=0.8，k₂=0.9)和默认取值(k₁=0.8，k₂=0.8)3种情况。以此思路，本文针对平行路段、交叉路口和立交桥等分口较多的路段进行仿真分析，考察位置信息和方向信息证据的可靠性程度，得出可靠性参数的最优取值。

平行路段是指两条或以上路段平行的道路，车辆的定位数据有可能连续落在n条道路之间。此时n条道路的方向角是相等的，方向信息证据的可靠性相对较弱，应当选取“位置信息证据较可靠”的取值方案。模拟实际环境中平行路段的情况，进行仿真试验，并对结果分析，得出的结果对方案的验证完全统一。选取一仿真实例，如图 1所示，车辆的初始位置为A，定位系统获得的位置为B，而车辆的真实行驶位置为C，将仿真得出的结果绘制成m(A_i)与k₁和k₂大小关系的曲线图。可以直观地看出：当k₁>k₂时，m(A₁)和m(A₂)的值相差最大，此时匹配结果的误差范围最大，完成了平行路段时采用“位置信息证据较可靠”的取值方案的验证，即k₁=0.9，k₂=0.8。

当车辆驶入交叉路口时，定位点有可能在各条道路之间，由于道路之间的方向角相差较大，因此相对位置证据而言，方向信息证据的可靠性较强，应当选取“方向信息证据较可靠”的取值方案。通过Java编程模拟实际环境，考察城市不同类型的交叉路口，进行仿真试验，并对结果分析，得出的仿真结果对方案的验证完全统一。选取仿真过程中的一则代表性实例，如图 2所示，车辆的初始位置为A，定位系统获得的位置为B，而车辆的真实行驶位置为C，将仿真得出的结果绘制成m(A_i)与k₁和k₂大小关系的曲线图。可以看出：当k₁＜k₂时，m(A₁)和m(A₂)的值相差最大，此时匹配结果的误差范围最大，错误率最小；而当k₁≥k₂时，支持正确结果的证据函数值逐渐下降而支持错误结果的证据逐渐上升，误差范围最小，仿真完成了对交叉路口路段使用“方向信息证据较可靠”的取值方案的验证，即k₁=0.8，k₂=0.9。

当车辆驶入立交桥等分口较多的路段时，是地图匹配中最为复杂的情况，此时GPS定位点有可能在n条较为密集的道路间，可靠性参数细微的变化将直接影响匹配结果。此种情况与交叉路口类似，因此相对位置证据而言，方向信息证据的可靠性较强，应当选取“方向信息证据较可靠”的取值方案。通过Java编程模拟实际环境对立交桥复杂路口进行匹配模拟，仿真结果通过一则实例来说明。如图 3所示，车辆的初始位置为A，定位系统获得的位置为B，而车辆的真实行驶位置为C，将仿真得出的结果绘制成m(A_i)与k₁和k₂大小关系的曲线图。可以看出：当k₁<k₂时，m(A₁)和m(A₂)的值相差最大，此时匹配结果的误差范围最大，错误率最小；随着k₁的增大和k₂的减小，支持正确结果的证据逐渐下降而支持错误结果的证据逐渐上升，最终出现错误的匹配结果，论证了立交桥等分口较多的路段应采用“方向信息证据较可靠”的取值方案，即k₁=0.8，k₂=0.9。

3.2 可达性信息证据的考察

将从GPS等定位设备获取到的车辆定位点分别投影到候选道路上，视做假如车辆行驶在该道路上的位置点，称此投影点为该候选路段的虚拟匹配点。可达性信息是指匹配过程中车辆从上一匹配点到虚拟匹配点的连通性、行驶距离、行驶时间等信息^[18]。改进算法考察可达性信息证据，通过计算行驶至各候选道路虚拟匹配点需要的速度，即虚拟速度，与从定位设备获取的车辆实际行驶速度信息比较，以考察虚拟匹配点的可达性信息证据。

在传统D-S证据理论的地图匹配算法的基础上，对于式(3)，当j=3时，m₃(A_i)是可达性信息证据的基本概率分配函数，令可达性信息证据函数

式中，D_i表示车辆从上匹配点到第i号道路的虚拟匹配点的行驶距离；t表示定位设备的定位周期；v表示车辆的瞬时速度；v_i表示车辆行驶到第i号道路虚拟速度与实际速度的差值。由于城市路网中的车辆行驶有一定规律性，且在交通规则的约束下行驶速度近似均匀，瞬时刹车的可能性较低，因此本算法中车辆虚拟行驶速度按照匀速计算。在此前提下，此式考察车辆在位置点P到第i号道路的虚拟匹配点的可达性信息的证据强度，车辆虚拟行驶到第i号道路所需的速度与实际行驶速度的差值越小，证据越可信。这样，就得到了位置、方向和连通性3个基本概率分配函数供D-S证据融合以得出最为精确的结果。

接下来探讨D-S证据融合^[19,20]的问题。由文献^{[19, 20]}所述，目前D-S证据理论在多证据融合中所需面临的主要两大问题，一是如何将采集到的证据信息转换为基本概率分配函数；二是如何将这些基本概率分配函数按照同一识别框架进行证据融合。文献[19]将多证据融合大致分为集中式证据融合模型和分布式证据融合模型。其中分布式证据融合模型采用递归式D-S证据融合的方式，证据1与证据2融合的结果作为新的证据与证据3进行二次融合，以此类推直至融合所有证据。这种模型适用于事先对各证据的可信程度有所倾向的情况，可以弱化人为证据的可信程度，增强客观证据的可信程度，并且当证据量较少时计算过程更为简便。由于地图匹配算法实际运用中，实际弯曲的道路在电子地图中要用一系列直线段来逼近，并且每个司机的驾车习惯导致经过相同拐角的车行轨迹不同，所以方向信息证据受到人为证据的影响；而从定位设备中获取的可达性信息证据和位置信息证据较为客观，因此改进算法中采用分布式证据融合模型，如图 4所示。

运用分布式证据融合模型，将式(4)中位置信息和方向信息融合得到的m(A_i)函数作为一个新的基本概率分配函数，再次运用D-S合成公式，与可达性信息证据的基本概率函数m₃(A_i)融合为一个新的m函数m′(A_i)

最后，max{m′(A₁),m′(A₂),…,m′(A_n)}，所对应的道路即为车辆当前行驶的道路。

3.3 改进的D-S证据理论地图匹配算法流程

综合以上讨论，总结得到图 5所示的改进的D-S证据理论地图匹配算法流程。

4 算法的仿真与结论

为了验证上述改进算法的可行性，将该算法用Java编程实现，集成到一套地图匹配算法测试系统中。该系统可以调用嵌入的地图匹配算法，获取电子地图中的定位数据进行匹配并在地图中显示匹配结果。仿真所用的数据为MapInfo格式北京市2011年电子地图“北四环-安慧桥”路段的数据(1∶50000，50m)，车辆的行驶路段包含直行、平行路段、交叉路口和立交桥等城市复杂道路，可以有效地检验算法的可行性，考察算法的匹配精度与稳定性。通过对基于D-S证据理论的地图匹配算法和改进算法依次进行仿真分析，并将改进算法与其他地图匹配算法的结果数据进行比较，验证算法改进后匹配精度和稳定性的提高。

4.1 算法的仿真实例说明

仿真模拟车辆行驶路线(图 6箭头表示)，全长约8.7km，车辆行驶路线包括直行路段、平行路段、交叉路口和立交桥等，其中复杂路口41个，平行路段12个。仿真默认车辆匀速行驶，设定行驶速度为30km/h，GPS数据采样周期为5s，对获取到的226个GPS定位点使用传统的基于D-S证据理论的地图匹配算法进行地图匹配，如图 6所示。匹配后，车辆行驶226个定位点中有211个点匹配正确，匹配准确率为93.36%。

使用改进的算法对GPS定位点进行匹配，如图 7所示。其中，在地图匹配算法测试系统中设定可达性信息证据k₃=0.8，车辆在定位点的瞬时行驶速度v=30km/h。匹配后，226个定位点中有221个点匹配正确，匹配准确率为97.79%，比传统算法有较大的提高。

4.2 仿真结果分析

为了更好地验证本文提出的改进算法的匹配效果，又在地图匹配算法测试系统中分别使用文献^[18]提出的基于浮动车数据的地图匹配算法和文献^[16]提出的基于GPS轨迹数据的地图匹配算法，对上例进行匹配，并对各算法匹配结果进行分析，如表 1所示。

可以看出，4种匹配算法错误的匹配点都出现在城市的复杂道路段中。仿真过程中的226个GPS定位点，有116个定位点在上述道路网络中。在这116个点中，基于D-S证据理论的地图匹配算法有15个错误匹配点匹配到了错误路线上，错误率为12.93%；而改进后的算法有5个错误匹配点，其余的错误点在第二次D-S证据融合后都得以正确匹配，使错误率降低到了4.31%，并且在整个仿真过程中考虑了实际情况中GPS数据漂移、无效等情况，算法仍然能准确、有效地定位车辆的实际行驶路段。在与基于浮动车数据的地图匹配算法和基于GPS轨迹数据的地图匹配算法比较中，平均匹配率和复杂区域匹配率也都有了一定的提高，可以很好地适用于城市中日益复杂的道路网络环境。

5 结 论

本文针对基于D-S证据理论的地图匹配算法存在的问题，提出了一种适用于城市复杂网络环境的改进算法。改进算法使用研究得出的可靠性参数将第一次证据融合结果精度提高，再与车辆的可达性信息证据进行D-S证据的二次融合，进一步确保了匹配结果的准确性和稳定性。通过仿真实例与其他匹配算法的横向比较，证实了改进算法进一步提高了匹配精度，更好地适用于复杂的城市路网。但算法增加了逻辑复杂度，所以实时性方面有所降低，因此，研究出一种实时性较好且适用各种路网环境的匹配算法将是下一步的完善方向。