基于模糊神经网络的地图匹配算法

D0I:10.13374.issn1001-053x.2012.01.021 第34卷第1期 北京科技大学学报 Vol.34 No.1 2012年1月 Journal of University of Science and Technology Beijing Jan.2012 基于模糊神经网络的地图匹配算法 苏海滨四王光政王继东 华北水利水电学院电力学院，郑州450011 区通信作者，E-mail:suhaibin2.000@yahoo.com.cm 摘要提出了基于模糊神经网络的新的地图匹配算法.该算法综合了数字道路信总和GPS/DR定位信息，提取两个重要参 数作为输入变量，即定位点到候选路段的投影距离及定位航向与候选路段方位角差.设计出了四层模糊神经网络及改进的收 敛学习规则.实验结果表明所提出的算法能很好地匹配车辆行驶路段位置， 关键词车辆：导航系统：全球定位系统：地图匹配：模糊神经网络 分类号V249.3 Map matching algorithm based on fuzzy neural networks SU Hai-bin☒，WANG Guang--heng,WANG Ji--dong Electric Power School,North China University of Water Conservancy and Electric Power,Zhengzhou 450011,China Corresponding author,E-mail:suhaibin2000@yahoo.com.cn ABSTRACT A novel map matching method based on fuzzy neural networks was proposed.This method integrates digital road map information and GPS/DR position data,and two important variables,the projection distance from the positioning point to the candidate link and the angle difference between GPS/DR heading and the link bearing of the candidate link,are selected as input signals for fuzzy neural networks.A four-ayer fuzzy neural network was designed and the improved learning rule was acquired for the fuzzy neural net- work.Experimental results show that the proposed algorithm has very good performance for matching the position of car running to the correct link under normal traffic conditions. KEY WORDS vehicles:navigation systems;global positioning system;map matching:fuzzy neural networks 目前使用的定位传感器大都是廉价的GPS/差分地图匹配算法和卡尔曼滤波的地图匹配算法， DR,定位精度不高，受各种随机误差的影响，传感器 不同程度地修正了噪声干扰，提高了定位传感器的 所得到的定位位置往往偏离车辆运行的道路。由于 定位精度：文献2]利用隐马尔可夫模型，提出了 数字电子地图精度不断提高，用高精度数字电子地 隐马尔可夫模型地图匹配算法.这些方法都不同程 图来修正传感器的定位位置是可能的，但前提条件 度地提高了地图匹配的可信度，但匹配精度和计算 是车辆必须在道路上运行，这一方法称为地图匹 效率仍未达到满意结果.模糊神经网络融合了模糊 配皿.地图匹配算法是借助于高精度的导航电子地 逻辑和神经网络的优点，使得模糊神经网络方法具 图，用软件技术手段来改进定位精度，通常包含两个 有较强的学习能力、逼近能力和预测能力.既能表 主要过程，即挑选被匹配的路段和投影定位点到该 示定性知识，又具有自学习和处理定量数据的能力， 路段上.由于GPS/DR定位数据具有高度随机性和 推理速度快，泛化能力和容错能力强，且具有网络学 非线性，很难建立精确的数学模型回，文献D,3]提 习时间较短等特点.本文采用基于模糊神经网络建 出了基于GPS定位点和轨迹曲线拟合的地图匹配 立了一种新型的地图匹配算法模型.以GPS/DR定 算法；文献49]分别提出了不同形式的基于模糊 位数据为基础，结合道路电子地图获得车辆运行方 和神经网络的地图匹配算法：文献0-11]提出了 向与路段夹角以及定位点到路段的投影距离两个参 收稿日期：201105-10 基金项目：华北水利水电学院高层次人才科研启动金资助项目(20101285)

第 34 卷 第 1 期 2012 年 1 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 34 No． 1 Jan． 2012 基于模糊神经网络的地图匹配算法 苏海滨 王光政 王继东 华北水利水电学院电力学院，郑州 450011 通信作者，E-mail: suhaibin2000@ yahoo． com． cn 摘 要 提出了基于模糊神经网络的新的地图匹配算法． 该算法综合了数字道路信息和 GPS /DR 定位信息，提取两个重要参 数作为输入变量，即定位点到候选路段的投影距离及定位航向与候选路段方位角差． 设计出了四层模糊神经网络及改进的收 敛学习规则． 实验结果表明所提出的算法能很好地匹配车辆行驶路段位置． 关键词 车辆; 导航系统; 全球定位系统; 地图匹配; 模糊神经网络 分类号 V249. 3 Map matching algorithm based on fuzzy neural networks SU Hai-bin ，WANG Guang-zheng，WANG Ji-dong Electric Power School，North China University of Water Conservancy and Electric Power，Zhengzhou 450011，China Corresponding author，E-mail: suhaibin2000@ yahoo． com． cn ABSTRACT A novel map matching method based on fuzzy neural networks was proposed． This method integrates digital road map information and GPS /DR position data，and two important variables，the projection distance from the positioning point to the candidate link and the angle difference between GPS /DR heading and the link bearing of the candidate link，are selected as input signals for fuzzy neural networks． A four-layer fuzzy neural network was designed and the improved learning rule was acquired for the fuzzy neural net￾work． Experimental results show that the proposed algorithm has very good performance for matching the position of car running to the correct link under normal traffic conditions． KEY WORDS vehicles; navigation systems; global positioning system; map matching; fuzzy neural networks 收稿日期: 2011--05--10 基金项目: 华北水利水电学院高层次人才科研启动金资助项目( 20101285) 目前使用的定位传感器大都是廉价的 GPS / DR，定位精度不高，受各种随机误差的影响，传感器 所得到的定位位置往往偏离车辆运行的道路． 由于 数字电子地图精度不断提高，用高精度数字电子地 图来修正传感器的定位位置是可能的，但前提条件 是车辆必须在道路上运行，这一方法称为地图匹 配［1］． 地图匹配算法是借助于高精度的导航电子地 图，用软件技术手段来改进定位精度，通常包含两个 主要过程，即挑选被匹配的路段和投影定位点到该 路段上． 由于 GPS /DR 定位数据具有高度随机性和 非线性，很难建立精确的数学模型［2］，文献［1，3］提 出了基于 GPS 定位点和轨迹曲线拟合的地图匹配 算法; 文献［4--9］分别提出了不同形式的基于模糊 和神经网络的地图匹配算法; 文献［10--11］提出了 差分地图匹配算法和卡尔曼滤波的地图匹配算法， 不同程度地修正了噪声干扰，提高了定位传感器的 定位精度; 文献［12］利用隐马尔可夫模型，提出了 隐马尔可夫模型地图匹配算法． 这些方法都不同程 度地提高了地图匹配的可信度，但匹配精度和计算 效率仍未达到满意结果． 模糊神经网络融合了模糊 逻辑和神经网络的优点，使得模糊神经网络方法具 有较强的学习能力、逼近能力和预测能力． 既能表 示定性知识，又具有自学习和处理定量数据的能力， 推理速度快，泛化能力和容错能力强，且具有网络学 习时间较短等特点． 本文采用基于模糊神经网络建 立了一种新型的地图匹配算法模型． 以 GPS /DR 定 位数据为基础，结合道路电子地图获得车辆运行方 向与路段夹角以及定位点到路段的投影距离两个参 DOI:10.13374/j.issn1001-053x.2012.01.021

·44 北京科技大学学报 第34卷 数作为算法输入变量，模型采用改进的梯度下降算 D=-）-y(s,-)+(x1-y) 法来确定输出层权值的大小，简化了在线学习，有利 √x-x+1)+(-1)7 于减少模型计算时间. (2) 1特征变量提取 投影距离越小，车辆在该路段上运行的可能性 越大，如果投影距离非常接近该投影路段，则表明车 在决定车辆运行路段时，有两个重要的问题必 辆运行在该路段上 须考虑，所设计的算法与这两个问题关系密切.一 另一种计算接近度的方法是计算两个GPS/DR 是由GPS/DR定位系统获得位置到路段上投影点之 估计点(pg-1(xg-1yg-),P.(xg'y))的连线与候选 间的距离应当较小；二是路段的形状与GPS/DR定 路段的夹角（锐角），夹角越小，表明接近程度越高， 位轨迹应该是相似的.令P。=(xg,y,)为GPS/DR 车辆在该路段运行可能性就越大.本文采用投影距 定位位置，P,=(x,y,)为路段上的投影位置.令0。 离来估计点到候选路段的接近程度. 为GPS/DR系统获得的航向角，O,为由电子地图获 由于△0和D与GPS/DR定位数据密切相关， 得的路段的方向角（也就是北向角）.车辆运动方向 其值具有随机性和不确定性，所以要精确建立数学 与路段方向相似度以车辆运动方向与路段方向的夹 模型是很困难的.然而只要参数特性是己知的，模 角来表示，如图1所示 糊逻辑方法是非常有用工具.基于这一原理提出了 布辆运行方向 模糊神经网络地图匹配算法以获得最佳地图匹配效 北向4 路段方向 果，提高路段选择的正确率. △0 2模糊神经网络地图匹配算法 GPS定位点 所设计的地图匹配系统如图3所示，模糊神经 网络的输入是D和△0'，模糊逻辑知识库来自于 F-THEN规则，这些规则集形成知识库充分体现了 图1航位角及道路方向角表示 完成地图匹配特征方法.本文所设计模糊神经网络 Fig.1 Denotation of vehicle heading and link bearing 有两个输入，每个输入有五个隶属函数，10个顶点 车辆运动方向角与空间道路方向角之差用△0 对称的高斯函数，模糊神经网络输出是节点所有输 表示， 入信号之和. △0=0.-0，- (1) 考虑到车辆全方位运行，实际△0的取值范围 输出层 △0如下： △0'=△9，-180°≤△0≤180°： △0°=360°-△0，△0>180°： 规则层 △0=360°+△0，△0<-180°. 隶属函数层 有两种方法可以表示估计点到候选路段的接近 输入层 程度，一种方法是估计点到路段的正交投影距离，如 TX=△6 X,=D 图2所示. 图3地图匹配模糊神经网络结构 0 Fig.3 Architecture of the fuzzy neural network of map matching D 2.1模糊神经网络结构 Pi.r) r 0 由图3所提出模糊神经网络结构可以看出，有 P(.y) 一个输入层，一个隶属函数层，一个规则层和一个输 图2估计点到路段的正交投影距离 出层组成.信号传播及每一层函数分析如下. Fig.2 Perpendicular distance from the estimation point to the link 2.1.1第1层：输入层 GPS/DR测量点P.=(xgy.)到AB路段的正交 第1层有两个输入节点，起到传输信号到下一 投影距离可用下式计算： 节点的作用，每一个节点相当一个输入变量，也就是

北 京 科 技 大 学 学 报 第 34 卷 数作为算法输入变量，模型采用改进的梯度下降算 法来确定输出层权值的大小，简化了在线学习，有利 于减少模型计算时间． 1 特征变量提取 在决定车辆运行路段时，有两个重要的问题必 须考虑，所设计的算法与这两个问题关系密切． 一 是由 GPS /DR 定位系统获得位置到路段上投影点之 间的距离应当较小; 二是路段的形状与 GPS /DR 定 位轨迹应该是相似的． 令 pg = ( xg，yg ) 为 GPS /DR 定位位置，pr = ( xr，yr ) 为路段上的投影位置． 令 θg 为 GPS /DR 系统获得的航向角，θr 为由电子地图获 得的路段的方向角( 也就是北向角) ． 车辆运动方向 与路段方向相似度以车辆运动方向与路段方向的夹 角来表示，如图 1 所示． 图 1 航位角及道路方向角表示 Fig． 1 Denotation of vehicle heading and link bearing 车辆运动方向角与空间道路方向角之差用 Δθ 表示， Δθ = θg － θr. ( 1) 考虑到车辆全方位运行，实际 Δθ 的取值范围 Δθ'如下: Δθ' = Δθ， － 180°≤Δθ≤180°; Δθ' = 360° － Δθ， Δθ ＞ 180°; Δθ' = 360° + Δθ， Δθ ＜ － 180°． 有两种方法可以表示估计点到候选路段的接近 程度，一种方法是估计点到路段的正交投影距离，如 图 2 所示． 图 2 估计点到路段的正交投影距离 Fig． 2 Perpendicular distance from the estimation point to the link GPS /DR 测量点 pg = ( xg，yg ) 到 AB 路段的正交 投影距离可用下式计算: D = xg ( yi － yi + 1 ) － yg ( xi － xi + 1 ) + ( xiyi + 1 － xi + 1 yi ) ( xi － xi + 1 ) 2 + ( yi － yi + 1 槡 ) 2 ． ( 2) 投影距离越小，车辆在该路段上运行的可能性 越大，如果投影距离非常接近该投影路段，则表明车 辆运行在该路段上． 另一种计算接近度的方法是计算两个 GPS /DR 估计点( pg － 1 ( xg － 1，yg － 1 ) ，pg ( xg，yg ) ) 的连线与候选 路段的夹角( 锐角) ，夹角越小，表明接近程度越高， 车辆在该路段运行可能性就越大． 本文采用投影距 离来估计点到候选路段的接近程度． 由于 Δθ 和 D 与 GPS /DR 定位数据密切相关， 其值具有随机性和不确定性，所以要精确建立数学 模型是很困难的． 然而只要参数特性是已知的，模 糊逻辑方法是非常有用工具． 基于这一原理提出了 模糊神经网络地图匹配算法以获得最佳地图匹配效 果，提高路段选择的正确率． 2 模糊神经网络地图匹配算法 所设计的地图匹配系统如图 3 所示，模糊神经 网络的输入是 D 和 Δθ'，模糊逻辑知识库来自于 IF--THEN规则，这些规则集形成知识库充分体现了 完成地图匹配特征方法． 本文所设计模糊神经网络 有两个输入，每个输入有五个隶属函数，10 个顶点 对称的高斯函数，模糊神经网络输出是节点所有输 入信号之和． 图 3 地图匹配模糊神经网络结构 Fig． 3 Architecture of the fuzzy neural network of map matching 2. 1 模糊神经网络结构 由图 3 所提出模糊神经网络结构可以看出，有 一个输入层，一个隶属函数层，一个规则层和一个输 出层组成． 信号传播及每一层函数分析如下． 2. 1. 1 第 1 层: 输入层 第 1 层有两个输入节点，起到传输信号到下一 节点的作用，每一个节点相当一个输入变量，也就是 ·44·

第1期 苏海滨等：基于模糊神经网络的地图匹配算法 ·45 D和△0'，这一层上每一个节点输入和输出表示 种控制规则，具有两个语言输入变量形成25个规则 如下： 库，每一个规则节点有两个固定的来自于术语节点 net=,Y=f (net)=net:,i=1,2.(3) 输入，第k个节点输入/输出表示为 式中，X=D、X=△0表示第i个节点的输入，1为 net=ΠXw,y2=f元(net)=neti,k=l,2,…,l. 层数. (7) 2.1.2第2层：隶属函数层 式中，X为第j个输入，0为输入权值取1. 在这一层里，每一节点都是术语节点，用以表示 2.1.4第4层：输出层 输入/输出模糊语言变量，隶属函数用高斯函数表 图3中虚线包围部分是第4层输入，链的权值 示，对于第j个节点输入输出表示如下： 代表第k个规则控制作用，第4层节点输出就是解 net=-(X-cg)2/2(og)2, j=1,2,…,n. 模糊，只有一个节点，用符号∑进行标记，表示对 =f (net)=exp(net), 所有输入信号进行求和，以获得最终推理结果 (4) netd=∑wiXt,。=f(netd)=netd,o=l.(8) 式中，c,和σ，分别表示高斯函数平均值和标准方 式中，w。为第k个规则作用强度，X为第k个输入， 差，也就是隶属函数的中心和宽度.输入到隶属函 :为路段估计值（匹配度） 数层的权重设定为1，输入输出变量模糊集为“很 好”（表示D和△θ很小）、“好《表示D和△9小)、 2.2地图匹配学习规则 “中等”（表示D和△0中等、“差《表示D和△0 采用梯度下降法作为模糊神经网络的学习算 大)和“很差”（表示D和△0很大）.在第2层和第 法，能量函数E定义如下： E,=y:-Y(X)]2/2=e/2 (9) 3层上分别布置了10个节点，分别表示输入/输出 式中，Y(X)为候选路段实际匹配度，Y,为期望的 语言变量 模糊神经网络输出匹配度，©，为实际值与估计值之 对于第2层高斯隶属函数中参数c,和σ：采用 “均值聚类算法”确定，这是一种性能良好的无监 间的差值.基于反向传播学习算法描述如下 督学习算法.算法原理步骤如下： 在第4层上，反向传播误差由下式表示： 8=-aE,/anet。=eyr (10) 步骤1选择k个初始化聚类中心点cj=1, 权值增量由下式给出： 2,…,k: (11) 步骤2将所有的数据集合按最近聚类中心分 Awi =-n aE /awi =nosxi. 组，如果‖x-C‖偏差最小，则将x:分配给N,N 其中，)是模糊神经网络连接权重的学习速率参数 输出层连接权重用下述公式进行更新： 表示聚集在聚类中心℃：周围的训练数据集合： (12) 步骤3重新计算聚类中心 wn(N+1）=en(N）+△wo. 式(12)学习规则与输出的误差e,有关，因此为 (5) 了使用式(12)，需要一个参考模型或一个真实输出 式中M为N中元素个数； 值用于计算误差e,然而地图匹配算法中即没有参 步骤4重复步骤2和步骤3直到聚类中心C 考模型也没有真实值，式(12)不能使用，为了满足 不再变化为止 地图匹配算法需要，推出另一学习算法，该学习算法 聚类算法完成后，可以直接确定参数σ，它表 不需要输出精确误差，学习目的是找到车辆最有可 示和每个中心相联系的数据分布的一种测度，可以 能的行驶路段，使用下列评判标准：(1)真实路段 用很多方法确定，本文中取聚类中心和训练数据之 是所有候选路段中最大者：(2)真实路段。要大于 间距离之和的平均值： 真实路段的阈值T。·学习过程连续进行直到上述 (1)和(2)满足.要直接得到T.也是很困难的，但 =7∑x-c)'(-c). (6) 通过计算机仿真就很容易得到，通过不断评估仿真 隶属函数参数确定后，输出层学习可用简单学 中不同阈值，就会得到一个合适的阈值 习算法来完成 2.3改进的地图匹配学习规则 2.1.3第3层：规则层 导航系统中实际地图匹配不需要精确期望值， 这一层上每个节点对输入信号逻辑相乘，乘积 只需要一个可信的范围值，因此期望值定义如下： 作为输出结果，因此每个节点都是规则节点代表一 Y.=Tm+y×rand(1) (13)

第 1 期 苏海滨等: 基于模糊神经网络的地图匹配算法 D 和 Δθ'，这一层上每一个节点输入和输出表示 如下: net 1 i = X1 i ，Y1 i = f 1 i ( net 1 i ) = net 1 i ，i = 1，2． ( 3) 式中，X1 1 = D、X1 2 = Δθ'表示第 i 个节点的输入，1 为 层数． 2. 1. 2 第 2 层: 隶属函数层 在这一层里，每一节点都是术语节点，用以表示 输入/输出模糊语言变量，隶属函数用高斯函数表 示，对于第 j 个节点输入输出表示如下: net 2 j = － ( X2 i － cij ) 2 /2( σij ) 2 ， y 2 j = f 2 j ( net 2 j ) = exp( net 2 j { ) ， j = 1，2，…，n． ( 4) 式中，cij 和 σij 分别表示高斯函数平均值和标准方 差，也就是隶属函数的中心和宽度． 输入到隶属函 数层的权重设定为 1，输入输出变量模糊集为“很 好”( 表示 D 和 Δθ'很小) 、“好“( 表示 D 和 Δθ'小) 、 “中等”( 表示 D 和 Δθ'中等) 、“差“( 表示 D 和 Δθ' 大) 和“很差”( 表示 D 和 Δθ'很大) ． 在第 2 层和第 3 层上分别布置了 10 个节点，分别表示输入/输出 语言变量． 对于第 2 层高斯隶属函数中参数 cij和 σij采用 “k-均值聚类算法”确定，这是一种性能良好的无监 督学习算法． 算法原理步骤如下: 步骤 1 选择 k 个初始化聚类中心点 cj ，j = 1， 2，…，k; 步骤 2 将所有的数据集合按最近聚类中心分 组，如果‖xj － cj‖偏差最小，则将 xi 分配给 Nj ，Nj 表示聚集在聚类中心 cj 周围的训练数据集合; 步骤 3 重新计算聚类中心 cj = 1 Mj ∑ Mj i = 1 xi， ( 5) 式中 Mj 为 Nj 中元素个数; 步骤 4 重复步骤 2 和步骤 3 直到聚类中心 cj 不再变化为止． 聚类算法完成后，可以直接确定参数 σ2 j ，它表 示和每个中心相联系的数据分布的一种测度，可以 用很多方法确定，本文中取聚类中心和训练数据之 间距离之和的平均值: σ2 j = 1 Mj ∑ ( x － cj ) T ( x － cj ) ． ( 6) 隶属函数参数确定后，输出层学习可用简单学 习算法来完成． 2. 1. 3 第 3 层: 规则层 这一层上每个节点对输入信号逻辑相乘，乘积 作为输出结果，因此每个节点都是规则节点代表一 种控制规则，具有两个语言输入变量形成 25 个规则 库，每一个规则节点有两个固定的来自于术语节点 输入，第 k 个节点输入/输出表示为 net 3 k = Πj Xj w3 jk，Y3 k = f 3 k ( net 3 k ) = net 3 k，k = 1，2，…，l． ( 7) 式中，Xj 为第 j 个输入，wjk为输入权值取 1． 2. 1. 4 第 4 层: 输出层 图 3 中虚线包围部分是第 4 层输入，链的权值 代表第 k 个规则控制作用，第 4 层节点输出就是解 模糊，只有一个节点，用符号 ∑ 进行标记，表示对 所有输入信号进行求和，以获得最终推理结果． net 4 o = ∑ w4 koX4 k，Y4 o = f 4 o ( net 4 o ) = net 4 o，o = 1． ( 8) 式中，w4 ko为第 k 个规则作用强度，X4 ko为第 k 个输入， Y4 o 为路段估计值( 匹配度) ． 2. 2 地图匹配学习规则 采用梯度下降法作为模糊神经网络的学习算 法，能量函数 E 定义如下: EJ =［Yi － Y( Xi ) ］2 /2 = e 2 J /2． ( 9) 式中，Y( Xi ) 为候选路段实际匹配度，Yi 为期望的 模糊神经网络输出匹配度，eJ 为实际值与估计值之 间的差值． 基于反向传播学习算法描述如下． 在第 4 层上，反向传播误差由下式表示: δ 4 o = － EJ / net 4 o = eJ ． ( 10) 权值增量由下式给出: Δw4 ko = － η EJ / w4 ko = ηδ4 o x 4 k ． ( 11) 其中，η 是模糊神经网络连接权重的学习速率参数． 输出层连接权重用下述公式进行更新: w4 ko ( N + 1) = w4 ko ( N) + Δw4 ko ． ( 12) 式( 12) 学习规则与输出的误差 eJ 有关，因此为 了使用式( 12) ，需要一个参考模型或一个真实输出 值用于计算误差 eJ，然而地图匹配算法中即没有参 考模型也没有真实值，式( 12) 不能使用，为了满足 地图匹配算法需要，推出另一学习算法，该学习算法 不需要输出精确误差，学习目的是找到车辆最有可 能的行驶路段，使用下列评判标准: ( 1) 真实路段 Y4 o 是所有候选路段中最大者; ( 2) 真实路段 Y4 o 要大于 真实路段的阈值 Tm. 学习过程连续进行直到上述 ( 1) 和( 2) 满足． 要直接得到 Tm 也是很困难的，但 通过计算机仿真就很容易得到，通过不断评估仿真 中不同阈值，就会得到一个合适的阈值． 2. 3 改进的地图匹配学习规则 导航系统中实际地图匹配不需要精确期望值， 只需要一个可信的范围值，因此期望值定义如下: Yo = Tm + γ × rand( 1) ． ( 13) ·45·

·46 北京科技大学学报 第34卷 式中，y是一个常数，rand(1)是0到1随机数 该算法在MAPINFO环境下仿真实现，并在郑 如果模糊神经网络的输出值比T。大，该路段 州城市区域道路网络做了多次实验，所使用数字道 就是车辆运行真实路段，第4层权重不改变.如果 路地图是郑州市区街道图，其规模是1：10000，一个 模糊神经的输出值比T。小，而且车辆运行该路段 单频GPS接收机安装在测试车辆上，样本采样周期 上，则第4层权值按式(8)~(11)进行修改，可得到 为4s,阈值Tm设置为6.5，)设置为0.2，y设置为 下面学习算法： 2,学习样本数为100个GPS/DR定位点，地图匹配 r0, (k)≥Tm; 模糊神经网络的输出结果如图4所示. △wo= (14) n [e(k).net ]Y (k)<T. 10 9 式中，e(k)=Y。-Y(k). 2.4车辆在路段上位置估计算法改进 LMnwbwwy 有两种计算方法可以计算车辆在路段上实际位 T阀值 置，一种是依据车辆运行路段的方向和由GPS/DR 单元获得的车辆运行速度.假设P和P+“点分别 代表车辆在t和t+△t时刻的位置，P点东向和北 1 向经纬度数据是己知的.从己知路段方向角和车辆 102030405060708090100 GPS/DR定位点数 在P+“运行速度，可计算出东向和北向经纬度的增 图4正确的地图匹配输出值 量，车辆在P+“的位置可由下式计算： Fig.4 Correct output values of map matching E:+1=E+△E, (15) 真实路段模糊神经网络输出。(k)值的范围在 N+1=N:+△N 6.6-8.7. 另一种是由定位测量单元GPS/DR获得的东向 在不同类型的道路上完成实际运行实验，算法 和北向经纬度数据直接向车辆运行路段进行投影， 在测试区域匹配结果如图5和图6所示.图5显示 从而获得车辆在路段上的投影位置.上述两种不同 了算法在一级道路上匹配结果(S为起点位置，D为 方法独立计算得到的车辆东向和北向经纬度数据 结束位置)，图中空心圆点为GPS定位点，黑圆点为 P(Es,N)和P+1(E+1,N+),再一次通过加权优 匹配后的车辆位置，一级道路宽阔，车辆速度高，则 化计算最终得到车辆在路段上东向和北向经纬度数 GPS定位精度高，没有错误的匹配点发生，图6显示 据估计位置(E,),计算方法如下： 三级道路上的算法匹配结果，道路宽度小于15m, E= ES -E+1+ PEs 形状复杂，GPS多径效应增加，定位误差在这区域内 TEs+ 会增大，在这样情况下该算法仍能找到正确的匹配 s,E+1+ PNs 路段。 s+σ2 (16) 式中，0p为电子地图的误差方差，σs为定位单元 北向纬度误差方差，σs为定位单元东向经度误差方 oGPS定位点 差，PEs、PNs是由定位获得的东向和北向定位数据. ·地图匹配点 3 实验结果分析 6w888进 机场路 实验使用的模糊神经网络节点设置原则是：第 1层节点的个数为输入变量的个数，这里输入变量 的个数为2，分别对应于D和△0：第2层节点的个 图5一级道路地图匹配结果 数为各个输入变量的模糊集合数之和，本文取k均 Fig.5 Map matching of the first class road 值聚类数为5，故该层的节点数为10；第3层节点的 从实验结果可以看出，所提出的算法在GPS误 个数为各输入变量的模糊集合数之积（即规则数）， 差增大的情况下，仍能取得很好的匹配效果 则求得该层的节点个数为25：第4层节点数等于输 基于模糊神经网络的地图匹配算法，进一步提 出变量的个数即节点数为1，对应于地图匹配度 高了地图匹配精度，使得匹配准确度达到99%以

北 京 科 技 大 学 学 报 第 34 卷 式中，γ 是一个常数，rand( 1) 是 0 到 1 随机数． 如果模糊神经网络的输出值比 Tm 大，该路段 就是车辆运行真实路段，第 4 层权重不改变． 如果 模糊神经的输出值比 Tm 小，而且车辆运行该路段 上，则第 4 层权值按式( 8) ～ ( 11) 进行修改，可得到 下面学习算法: Δw4 ko = 0， Y4 o ( k) ≥Tm ; η［e( k)·net 3 k］， Y4 o ( k) ＜ Tm { ． ( 14) 式中，e( k) = Yo － Yo ( k) ． 2. 4 车辆在路段上位置估计算法改进 有两种计算方法可以计算车辆在路段上实际位 置，一种是依据车辆运行路段的方向和由 GPS /DR 单元获得的车辆运行速度． 假设 Pt 和 Pt + Δt 点分别 代表车辆在 t 和 t + Δt 时刻的位置，Pt 点东向和北 向经纬度数据是已知的． 从已知路段方向角和车辆 在 Pt + Δt 运行速度，可计算出东向和北向经纬度的增 量，车辆在 Pt + Δt 的位置可由下式计算: Ei + 1 = Ei + ΔEi， Ni + 1 = Ni + ΔNi { ． ( 15) 另一种是由定位测量单元 GPS /DR 获得的东向 和北向经纬度数据直接向车辆运行路段进行投影， 从而获得车辆在路段上的投影位置． 上述两种不同 方法独立计算得到的车辆东向和北向经纬度数据 PS ( ES，NS ) 和 Pi + 1 ( Ei + 1，Ni + ! ) ，再一次通过加权优 化计算最终得到车辆在路段上东向和北向经纬度数 据估计位置( ^ E，^ N) ，计算方法如下: ^ E = ( σ2 ES σ2 ES + σ2 ) map Ei + 1 + ( σ2 map σ2 ES + σ2 ) map PES， ^ N = ( σ2 NS σ2 NS + σ2 ) map Ei + 1 + ( σ2 map σ2 NS + σ2 ) map PNS      ． ( 16) 式中，σmap为电子地图的误差方差，σNS为定位单元 北向纬度误差方差，σES为定位单元东向经度误差方 差，PES、PNS 是由定位获得的东向和北向定位数据． 3 实验结果分析 实验使用的模糊神经网络节点设置原则是: 第 1 层节点的个数为输入变量的个数，这里输入变量 的个数为 2，分别对应于 D 和 Δθ'; 第 2 层节点的个 数为各个输入变量的模糊集合数之和，本文取 k 均 值聚类数为 5，故该层的节点数为 10; 第 3 层节点的 个数为各输入变量的模糊集合数之积( 即规则数) ， 则求得该层的节点个数为 25; 第 4 层节点数等于输 出变量的个数即节点数为 1，对应于地图匹配度． 该算法在 MAPINFO 环境下仿真实现，并在郑 州城市区域道路网络做了多次实验，所使用数字道 路地图是郑州市区街道图，其规模是 1∶ 100 00，一个 单频 GPS 接收机安装在测试车辆上，样本采样周期 为 4 s，阈值 Tm 设置为 6. 5，η 设置为 0. 2，γ 设置为 2，学习样本数为 100 个 GPS /DR 定位点，地图匹配 模糊神经网络的输出结果如图 4 所示． 图 4 正确的地图匹配输出值 Fig． 4 Correct output values of map matching 真实路段模糊神经网络输出 Y4 o ( k) 值的范围在 6. 6 ～ 8. 7． 在不同类型的道路上完成实际运行实验，算法 在测试区域匹配结果如图 5 和图 6 所示． 图 5 显示 了算法在一级道路上匹配结果( S 为起点位置，D 为 结束位置) ，图中空心圆点为 GPS 定位点，黑圆点为 匹配后的车辆位置，一级道路宽阔，车辆速度高，则 GPS 定位精度高，没有错误的匹配点发生，图 6 显示 三级道路上的算法匹配结果，道路宽度小于 15 m， 形状复杂，GPS 多径效应增加，定位误差在这区域内 会增大，在这样情况下该算法仍能找到正确的匹配 路段． 图 5 一级道路地图匹配结果 Fig． 5 Map matching of the first class road 从实验结果可以看出，所提出的算法在 GPS 误 差增大的情况下，仍能取得很好的匹配效果． 基于模糊神经网络的地图匹配算法，进一步提 高了地图匹配精度，使得匹配准确度达到 99% 以 ·46·

第1期 苏海滨等：基于模糊神经网络的地图匹配算法 ·47 上，不足之处是算法在学习时计算量少大一些，在计 算机资源允许的情况下仍不失为较好的匹配算法. ·地图匹配，点 表1列出了几种不同匹配算法的匹配性能比较结 ·GPS定位点 4中特44华4件林4电 果，从表1可以看出，基于模糊神经网络的地图匹配 算法准确率和计算时间有所提高. 4结论 (1)提出了基于模糊神经网络地图匹配算法以 图6三级道路地图匹配结果 及相应的学习规则，通过k均值聚类算法得到模糊 Fig.6 Map matching of the third class road 隶属函数中心宽度及方差，设计模糊神经网络结构， 表1儿种不同地图匹配算法性能对比 Table 1 Performance of some different map matching algorithms 算法种类 需要信息 匹配率/% 时间/ms 基于权重地图匹配算法 距离与方向 92.86 52 基于模糊逻辑地图匹配算法 距离、方向及轨迹相似性 98.12 78 基于模糊神经网络地图匹配算法 距离与方向 99.78 65 采用改进有条件的梯度下降学习法获得较好的效 transport systems.Transp Res C,2009,17(6):672 果，采用误差优化算法进一步提高定位精度 6 Su H B,Tang J S,Hou C Z.An integrated map matching algo- (2)在MAPINFO环境下验证所提算法的有效 rithm based on fuzzy theory for navigation system /Proceeding of the International Conference on Computational Intelligence and Se- 性，即使在GPS定位误差增大的情况下，算法仍能 curity.Guangzhou,2006:916 准确找到车辆运行路段. Kim S,Kim J H.Adaptive fuzzy-network-based C-measure map (3)由于该算法有学习能力，能在任何环境下 matching algorithm for car navigation system.IEEE Trans Ind 应用，其计算时间并不随道路网络规模增大而增加， Electron,2001,48(2):432 8] Tang J J,Liu F.A driver route prediction based map-matching al- 适合于实时性要求较高的导航系统 gorithm integrating uncertain reasoning.Acta Geod Cartogr Sin, 2010,39(5):546 参考文献 (唐进君，刘芳.基于路径预测的不确定性推理组合地图匹配 Wang N,Wang F Y,Liu J R.A point based matching algorithm. 算法.测绘学报，2010,39(5)：546) J Northeast Univ Nat Sci,1999,20(4):344 9] Zhang T,Yang D G.Li K Q,et al.Fuzzy map-matching algo- (王楠，王勇蜂，刘积仁.一个基于位置点匹配的地图匹配算 rithm with confidence feedback for vehicle navigation.Tsinghua 法.东北大学学报：自然科学版，1999,20(4)：344) Unig Sci Technol,2009,49(2):277 2]Quddus M A,Ochieng W Y,Noland R B.Current map-matching (张涛，杨殿阁，李克强，等.车辆导航中带匹配度反锁的模糊地 algorithms for transport applications:state-of-the art and future re- 图匹配算法.清华大学学报：自然科学版，2009,49(2)：277) search directions.Transp Res Part C,2007,15(5):312 10 Liu H C,Xu H,Norville H S,et al.A virtual differential map- B]Chen J,Hu J H,Zhang F Z.Research on map-matching algorithm matching algorithm with improved accuracy and computational ef- oriented navigation and monitor.Acta Sci Nat Unig Pekinensis, ficiency.Navig,2008,61(3):421 2009,45(2):299 [11]Xu H,Liu H C,Tan C W,et al.Development and application (陈嘉，胡继华，张飞舟.面向车辆监控导航的地图匹配算法 of an enhanced Kalman filter and global positioning system error- 研究.北京大学学报：自然科学版，2009,45(2)：299) correction approach for improved map-matching.Intell Transp 4]Quddus M A,Noland R B,Ochieng W Y.A high accuracy fuzzy st,2010,14(1):27 logic based map matching algorithm for road transport.J Intell 02] Zelenkov A V.Calculation of the parameters of Hidden Markov Transp Syst,2006,10(3):103 models used in the navigation systems of surface transportation for [5]Velaga N R.Quddus M A,Bristow A L.Developing an enhanced map matching:a review.Autom Control Comput Sci,2010,44 weight-based topological map-matching algorithm for intelligent (6):309

第 1 期 苏海滨等: 基于模糊神经网络的地图匹配算法 图 6 三级道路地图匹配结果 Fig． 6 Map matching of the third class road 上，不足之处是算法在学习时计算量少大一些，在计 算机资源允许的情况下仍不失为较好的匹配算法． 表 1 列出了几种不同匹配算法的匹配性能比较结 果，从表 1 可以看出，基于模糊神经网络的地图匹配 算法准确率和计算时间有所提高． 4 结论 ( 1) 提出了基于模糊神经网络地图匹配算法以 及相应的学习规则，通过 k 均值聚类算法得到模糊 隶属函数中心宽度及方差，设计模糊神经网络结构， 表 1 几种不同地图匹配算法性能对比 Table 1 Performance of some different map matching algorithms 算法种类 需要信息 匹配率/% 时间/ms 基于权重地图匹配算法 距离与方向 92. 86 52 基于模糊逻辑地图匹配算法 距离、方向及轨迹相似性 98. 12 78 基于模糊神经网络地图匹配算法 距离与方向 99. 78 65 采用改进有条件的梯度下降学习法获得较好的效 果，采用误差优化算法进一步提高定位精度． ( 2) 在 MAPINFO 环境下验证所提算法的有效 性，即使在 GPS 定位误差增大的情况下，算法仍能 准确找到车辆运行路段． ( 3) 由于该算法有学习能力，能在任何环境下 应用，其计算时间并不随道路网络规模增大而增加， 适合于实时性要求较高的导航系统． 参 考 文 献 ［1］ Wang N，Wang F Y，Liu J R． A point based matching algorithm． J Northeast Univ Nat Sci，1999，20( 4) : 344 ( 王楠，王勇峰，刘积仁． 一个基于位置点匹配的地图匹配算 法． 东北大学学报: 自然科学版，1999，20( 4) : 344) ［2］ Quddus M A，Ochieng W Y，Noland R B． Current map-matching algorithms for transport applications: state-of-the art and future re￾search directions． Transp Res Part C，2007，15( 5) : 312 ［3］ Chen J，Hu J H，Zhang F Z． Research on map-matching algorithm oriented navigation and monitor． Acta Sci Nat Univ Pekinensis， 2009，45( 2) : 299 ( 陈嘉，胡继华，张飞舟． 面向车辆监控导航的地图匹配算法 研究． 北京大学学报: 自然科学版，2009，45( 2) : 299) ［4］ Quddus M A，Noland R B，Ochieng W Y． A high accuracy fuzzy logic based map matching algorithm for road transport． J Intell Transp Syst，2006，10( 3) : 103 ［5］ Velaga N R，Quddus M A，Bristow A L． Developing an enhanced weight-based topological map-matching algorithm for intelligent transport systems． Transp Res C，2009，17( 6) : 672 ［6］ Su H B，Tang J S，Hou C Z． An integrated map matching algo￾rithm based on fuzzy theory for navigation system / / Proceeding of the International Conference on Computational Intelligence and Se￾curity． Guangzhou，2006: 916 ［7］ Kim S，Kim J H． Adaptive fuzzy-network-based C-measure map matching algorithm for car navigation system． IEEE Trans Ind Electron，2001，48( 2) : 432 ［8］ Tang J J，Liu F． A driver route prediction based map-matching al￾gorithm integrating uncertain reasoning． Acta Geod Cartogr Sin， 2010，39( 5) : 546 ( 唐进君，刘芳． 基于路径预测的不确定性推理组合地图匹配 算法． 测绘学报，2010，39( 5) : 546) ［9］ Zhang T，Yang D G，Li K Q，et al． Fuzzy map-matching algo￾rithm with confidence feedback for vehicle navigation． J Tsinghua Univ Sci Technol，2009，49( 2) : 277 ( 张涛，杨殿阁，李克强，等． 车辆导航中带匹配度反馈的模糊地 图匹配算法． 清华大学学报: 自然科学版，2009，49( 2) : 277) ［10］ Liu H C，Xu H，Norville H S，et al． A virtual differential map￾matching algorithm with improved accuracy and computational ef￾ficiency． J Navig，2008，61( 3) : 421 ［11］ Xu H，Liu H C，Tan C W，et al． Development and application of an enhanced Kalman filter and global positioning system error￾correction approach for improved map-matching． J Intell Transp Syst，2010，14( 1) : 27 ［12］ Zelenkov A V． Calculation of the parameters of Hidden Markov models used in the navigation systems of surface transportation for map matching: a review． Autom Control Comput Sci，2010，44 ( 6) : 309 ·47·