基于大规模浮动车数据的地图匹配算法

第７卷第２期２００７年４月

交通运输系统工程与信息

ＪｏＩｌｍａｌｏｆ１ｈｎ８ｐｏｎ“ｏｎ印８把ｍｓＥⅡ画Ⅱｅ商“ｇａｎｄｈｄｉ珊ａｔｉｏｎＴｅｃｈｎｏｌ。ｇｙ

Ｖ０１．７Ｎｏ２

ＡＤ州２００７

文章编号：１００９—６７“（２００７）０２—００３９一０７

，…………………………’’、

ｉ智能交通系统与信息技术ｌ～。。。。。。。。。。。。。。。。．．。。。…。。。。。．。。一

基于大规模浮动车数据的地图匹配算法

章威１，徐建闽１，林绵峰２

（１．华南理工大学交通学院，广州５１０６４０；２广州交通信息化建设投资运营有限公司，广州５１００３３）

摘要：地图匹配问题是浮动车技术中必须解决的关键问题．由于浮动车数据自身的特

点，传统的导航地图匹配算法难以直接适用于大规模的浮动车数据匹配．在分析基于浮

动车数据的地图匹配与传统的导航地图匹配的异同点的基础上，提出了浮动车地图匹配

模型族的解决方案和相应的道路网格拓扑结构，设计了包括道路初次匹配模型、平行方向

道路识别模型、节点匹配模型、延时匹配模型在内的浮动车数据地图匹配算法体系，并对

算法进行了评估和验证．提出的浮动车数据地图匹配算法模型已经在广州市Ｉ鸭示范工

程中得到了实际应用，应用结果表明该算法具有准确、高效和实用的特点．

关键词：智能交通系统；浮动车数据；地图匹配

中图分类号：ｕ１２文献标志码：Ａ

ＭａｐＭａｔｃｈｉｎｇ舢ｇｏｒｉｔｈｍｏｆＬ盯ｇｅ＿ｓｃａｌｅＰｒｏｂｅｖｅｍｃｌｅＤａｔａ

ｚＨＡⅣＧｗｅｉｌ，ｘｕＪｉｉｌＩｌ—ｍｉｎｌ，ｕＮＭｉａｎ．ｆｅｎｆ

（１．ｃｏＩｋｇｅｏｆｌｈｍｃａⅡｄｃ㈣砒ｉｏｎｓ，Ｓ‘，ｕｔｌｌｃｈｉｎａｕⅢｖｅｒｓｉｌｙ。ｆＴｅｃｈｎｏｋｇｙ，ＧｕＢ“ｇｚ｜Ｉｏｕ５１０６４０，ｃｈｉｎａ；

２Ｇｕ８Ｉｌ铲ｈｏｕＴｒａｍｃＩｎｆｏｎｎａｔｉｏｎＩｎｖｅ咖ｌｅｎｔＢｕ８ｉｎｅ８ｓａ１１ｄＭａｎａｇｅｍｅｎｔｕｍｈｅｄｃｏｍｐａｎｙ，Ｇ岫“ｇｚｈｏｕ５１００３３，ｃｈｉｎａ）

Ａ埘ｒａｎ：Ｍ８ｐｍａｔｃｈｉ“ｇｉ８ｔｌｌｅｋｃｙｐｒｏｂｌｅｍ０ｆＰ工０ｂｅｖｅｈｉｃｌｅｔｅｃｌｌ｜ｌｎｌｏｇｙ．Ｆ０ｒｔｌｌｅｃｈａｒａｃｔｅ血ｔｌｃｓ０ｆｐｍｂｅｖｅｈｉｃｌｅ

ｄＨｔａ，州而ｏｒｌａｌ洲ｇｕｔｉｏｎｍ印ｒｌｌａｔｃｈｉＩｌｇｃａｌｌｎｏｔｓｅⅣｅｔｈｅ陀ｑＩｌｉ慨ｎｅｎｔｓｏｆｐ工ＤｂｅｖｅｈｉｃｋｄａｔＨ．Ｂ蛐ｅｄ岫ｔｈｅｃｏｍ—

Ｈ帕ｎａｎｄｄｉｆｆｅｒｅｎｔｐｏｉ心ｂｅｔｗｅｅｎｔ｝ｌｅｍ印ｍ咖ｂｉ”ｇ０ｆ廿ａｄｉ由ｎｄｎａｖｊ９８ｄ衄ａｎｄ啡ｂｅｖｅｈｊｃｌｅ，ｔｈｅｓｏｌｕｔｉｏｎ０ｆｐｍｂｅ

ｖｅｈｉｃｌｅｍ８ｐｍａｔｃｈｉｌｌｇｍｏｄｅｓａｎｄｃｏｒｒｅｓｐｏｎｄｉＩｌｇｍａｄｎｅｔｗｏｒｋｓ呲ｔｌｌｒｅ｝咀ｖｅ１）ｅｅ“ｐｍｐｏｓｅｄａｎｄｔｈｅｍａｐｍａ把ｈｉ“ｇ

ｄｇｏｄ山ｍ８ｙｓｔｅｍｈ衄ｄｓ０ｋ把“ｐｍｍｏｔｅｄ，ｉＩ＂１１１ｄｉ“ｇｒＤＢｄｆ＿璐ｔｍａｐⅢ砒ｃｈｉｎｇｍｏ乱，ｐａｒａＵｅｌ㈣ｅｍａｄｍ印

咖ｔｃｈｉ“ｇⅡｌｏｄｅ，ｎｏｄｅｍ印ｍａｔｃｈｉｎｇｍｏｄｅ粕ｄｄｅｌａｙｍ８ｐｍａｋｈｉ“ｇｍｏｄｅＩｎａｄ血ｉｏｎ，ｔｋａｌ印五ｔｈⅢｈｓｂｅ眦ｖｅｒ—

ｉｎｅｄａｎｄｅｖａｌｕａ忙ｄ．１１ｌｅ

ｍ８ｐＨｍｔｃｈｉｎｇａｌｇｏｎｔｌｌｍｐｒｏｍｏｔｅｄ

ｉｎｔｈ。ｐ印８“ａｓｂｅｅｎａｐｐｌｉｅｄｉｎ吐”ⅡＳｄｅｍｏｎｓｔｍｔｉｏｎｐｍｊｅｃｔｏｆＧｕ８ｎｇｚ｜ｍｕａｎｄｔ｜Ｉ。ｐｒａｃ６ｃｅｈａ８ｐｍｖｅｄｔ１１ａｔｉｔ抽ｑ１１ｉｔｅｅⅡ＆ｔ押ｅａｌｌｄｐｒａｃｔｉｃａｌ

Ｋｅｙｗｏｒｄｓ：璐；ｐｒｏｂｅｖｅｃｌｌｉｃｋｄａｔａ；ｍ印ｍ且ｔｃｈｉＩｌｇ

ＣＬＣｌ加ｍｋｒ：Ｕ１２

Ｄ州舢脚ｎｃｏｄｅ：Ａ

０引言

交通拥堵现在已经逐渐成为我国大中城市的首要难题，如何及时地反映这些道路上路况，为出行者提供准确的导向，成为智能交通领域亟待解决的问题“。３３．传统的道路运行信息采集方式已经不能够适应快速增长的道路数量和车辆保有量．

收稿日期：２００６一佗一０６

基金项目：“卜五”国家科技攻关重点项目资助和国家自然科学基金资助（５０５７８０６４）．

作者简介：章威（１９６１一）Ｉ男，广东梅州人，华南理工大学博士研究生，主要研究方向为智能交通系统Ｅ—ｍ止ｌ弘｜Ｉａｎｇｗｅｉ＠ｔｏｍｃｏｍ

　万方数据

交通运输系统工程与信息２００７年４月

浮动车技术作为一种崭新的城市路况信息获取、道路建设和出行规划方式，已经逐步成为研究热占［４—７１

大规模浮动车数据地图匹配是浮动车技术中必须解决的关键技术问题．所谓地图匹配，指的是依据ＧＰｓ车载终端车辆在行驶过程中采集到的车辆位置ＧＰｓ信息，通过特定模型和算法，将车辆的当前位置与电子地图上的道路相关联的行为最终输出结果为车辆在道路上的具体位置“。９１．由于浮动车数据的自身的特点，传统的导航地图匹配算法往往精度不够，或者过于复杂，很难应用在大规模数据处理．本文针对大规模浮动车数据地图匹配的特点，提出ｒ一系列相辅相成的地图匹配算法，达到浮动车数据地图匹配的目的，并对算法的有效性进行验证和评估．

１地图匹配模型方案概述

浮动车地图匹配模型是将浮动车的ＧＰｓ数据与电子地图结合，通过一定的算法，得出浮动车所在道路的数学模型．

本文提出的浮动车地图匹配模型是一个模型族．它建立在一个道路网格拓扑结构之上，并且针对道路的实际情况设计了不同的道路匹配算法，如图ｌ所示．

图１浮动车数据地图匹配的模型方案示意图

ｎＢ１Ｍｏ出ｌｓｏｈｉｏｎ０ｆｍａｐｍａ此ｈｉ“ｇｈａ８ｅｄｏｎＦＣＤ

这些算法模型并不是并列的，而是相辅相成、互为补充的．道路初次匹配算法是整个地图匹配模型的第一个步骤；在初步对浮动车的位置进行判断之后，通过反向道路识别和节点匹配，进行更深层次的匹配识别；如果仍未找到满足要求的匹配道路，则进入延时匹配模型，通过后续浮动车ＧＰｓ数据结合这一次的匹配结果，给出最后准确的匹配道路．２道路网格拓扑结构

由于浮动车采集系统的采集对象足上万辆浮动车，采集问隔在５秒到３０秒之间，因此，同时进入模型的ＧＰｓ数据量巨大，综上所述，建立一个高效的道路拓扑结构是非常必要的．

本文将城市路网按某种特殊的拓扑结构组织起来，该拓扑结构适合于存储，并有效改善算法的运行效率．该拓扑结构包括４层对象：城市、区域、道路、道路形状线段，如图２所示．

图２遭路拓扑结构模型罔

Ｆｉｇ２Ｍ０ｄｅｌｏｆｍａｄｎｅｔ

具体的方案是：按照经纬度的方向，以一定的间隔￡，将道路网络从上到下、由左至右网格化均匀分块，假设将其分为．】ｌｆ×Ⅳ个网格，简记为翻ｄ（Ｍ×Ⅳ），其中Ｍ和Ⅳ分别为分块行列数，网格的行编号从０到村一１，列编号从０到Ⅳ一１为了与实际的道路更加符合，引入道路形状线段，即将一条实际的道路用若干条线段首尾相连米近似，并且对这些形状线段进行编号存储，将每条道路的形状线段与道路相关联，这样可以提高匹配精度．在每个网格内，记录网格包含或与之相交的所有形状线段编号．为了提高搜索效率，将所有网格按照编号顺序存储．在给定待匹配的车辆定位点ＧＰｓ坐标之后，用折半查找法快速找到ＧＰｓ点所在的网格．以广州为例，找到一点所在网格，最多不超过１７次比较运算，时间复杂度极低，基本上不受道路网络规模变化的影响．

３浮动车地图匹配模型算法

３．１概念

在进人模型算法之前，为了便于分析、处理以及表达，对需要用到的概念进行说明．

（１）匹配度”】．

首先为了对地图匹配进行定量的分析，匹配模

　万方数据

第２期基于大规模浮动车数据的地图匹配算法

型引入了匹配度概念．匹配度是描述ｃＰｓ点与一

条道路的匹配程度，用（０，１）区间的浮点数进行量

化，匹配度越接近１，就认为发出这个ＧＰＳ数据的

浮动车越有可能位于这条道路．

匹配度公式如下：

占＝，（ｄ，口）＝∞。ｄ＋叫猡（１）

其中８——道路的匹配度，ｄ是ｄ和日的函数；

ｊ——ＧＰＳ点到道路距离的归一化值，设ｄ为

ＧＰＳ点到道路的距离，△。是ＧＰｓ的平均误差（一

般为１０～１５米）．则

ｄ＝１，（１＋ｄ，△ｃ腭）（２）

日——ｃＰｓ方向与道路方向夹角的归一化值，

设日为ｃＰｓ方向与道路方向夹角，则

日：Ｉ，（Ｉ＋口２）

ｍ。和ｍ。——分别为距离和夹角在匹配度中

的权重，且满足

Ⅲｄ＋甜。＝１（３）

（２）可能匹配的道路集合月Ｑ．

这是本文新提出的概念，在匹配度的基础上定

义匹配度之差的阈值８。和匹配度可接受的最小值

ｄ…当在已排序的匹配度队列中，匹配度ｄ。和

８。满足条件瓯一ａ。＞瓯，且丸＞８～时，就认

为足（ｉ＝ｍ，ｍ＋１，…，Ⅳ）是ＧＰｓ有可能匹配的道

路，记作尺ｃ一另外，对于道路复杂的情况，往往无

法找到满足ｄ。一８。＞ｄ。的匹配度，因为不同道路

匹配度差距不大，在这种情况下，如果存在一系列

ｍ（ｍ＝ｌ，２，…，』ｖ）满足ｄ。＞８。一８，且ｄ。＞ｄ一

，那么就认为这个集合是Ｒｃ。．月ｃ。定义了可能匹

配成功的道路范围，对于后续的匹配道路识别非常

重要．

（３）匹配结果类型．

匹配结果类型就是对于浮动车的一个位置信息

的地图匹配结果进行分类，具体包括：匹配到道路、

匹配到节点和延时匹配．其中匹配到道路是通常意

义上的浮动车数据匹配结果．本文新提出了另外两

种匹配结果

①匹配到节点．

针对浮动车地图匹配的特殊性，本文提出了全

新概念——匹配到节点．由于浮动车地图匹酣的最

终日的是为城市路况模型得到路段通行时问提供起４１

点、终点以及时间信息．而当车辆距离路口（包括普

通交叉路口、主辅路的出入口等）比较近时，由于减

速、并线导致ＧＰｓ数据中的方向信息变化较大、准确

性不高，使得系统很难确定车辆的确切位置．但是

考虑到浮动车地图匹配的最终目的是得到路况信

息，因此如果无论车辆目前在哪条道路ｒ，只要能确

定车辆必定通过或者离开某个路口，就可以根据车

辆的下一个定位数据确定其行驶轨迹．因此当车辆

处于路口节点附近，且必将或者已经经过路口节点

时，认为属于匹配到节点类型．

②延时匹配．

对于不满足以￡两种匹配类型的匹配条什的情

况，统一归人延时匹配的范围．也就是根据各个道

路的匹配度情况，确定一个粗略的匹配范围，然后根

据相同车辆随后的一组ＧＰＳ定位数据，最终确定车

辆的行驶轨迹．

３．２道路初次匹配模型

道路的初次匹配模型是整个地图匹配模型的人

口．此模型通过匹配度算法提取输入的待匹配道路

的匹配度，并对其进行排序，检查是否有道路符合道

路匹配的条件，如果有，则匹配成功；否则进入下一

个匹配模型．流程如图３所示．

输入处理输出

图３道路初次匹配模型

Ｆ１９３Ｏｉ画ＩｍｌｍａｐⅢａ把ｈｉ。蝎Ｉｎｏｄｄ

模型的输人是道路的集合，有两种不同的情况：

第１种，当本次匹配是某浮动车的第１次匹配．

这种情况需要根据当前车辆位置，通过道路网格拓

扑结构搜索车辆所在的分区，记为凸谢（ｉ，ｊ）．由于

ｅＰｓ误差，当车辆位置位于分区边缘时，车辆在实际

中有可能位于邻接的分区．解决办法如图４所示．

图４中，有一ｃＰｓ点（ｘ，ｙ）定位于网格

Ｇ“ｄ（ｉ，ｊ）中，但由于ＧＰｓ靠近网格的边缘和ＧＰｓ

的误差，它有可能落在临近的网格内．于是本文采

用一个边长为２Ｌ、以ＧＰｓ点为中心的正方形与网

格做交集，与正方形交集不为空的网格中的道路都

需要作为道路初次匹配的输入集合．Ｌ为是各种　万方数据

４２交通运输系统工程与信息２００７年４月

，ｌ』ｐ１ｌ：。一—一ｌ型力

罔４网格分区中的道路集台确定

Ｆｉｇ．４ＲｏＨｄｏｂｔａｉ舢ｅｎ【ｉⅡｇ胡ｚ㈣ｓ

因素引起的ＧＰｓ点与道路距离误差总和的最大值，这些因素包括ＧＰｓ本身的误差和电子地图的误差等．

第２种，当本车辆上一次位置匹配的结果是“匹配到道路”时，则可以根据当前ＧＰｓ和前一个ＧＰｓ之间的时间差以及前一个ＧＰｓ所处道路的历史车速，确定车辆可能行驶到的道路的集合．将此集合作为道路初次匹配模型的输人集合．

道路初次匹配模型采用匹配度为判据来判断ＧＰｓ是否满足匹配到道路的条件．

根据匹配度公式，得到输入的道路集合中每一条道路的匹配度．这里把距离权重设置的大于夹角权重，即这里分别设置ｃｕ。和ｍ。为０．６和Ｏ．４．图５是算法流程图．

图５道路初次匹配模型流程图

Ｆ１９５ｎ㈣ｃＩｌ枷ｏｆ嘶ｇｉ蹦ｍａｐｍａｋｈｊ“ｇｍｏｄｅｌ３．３平行反向道路识别模型

由于ＧＰｓ数据本身误差或者电子地图的测绘

误差，可能出现这种情况：车辆沿着一条中间具有隔离带的双向道路行驶，采集到的ＧＰＳ数据反映在电子地图上时，落在了与车辆行驶方向相反的道路上．在这种情况下，初次道路匹配模型得到的道路可能包含反方向的道路．这样会给后续的延时匹配造成干扰．平行反向道路识别模型就是解决以上问题的匹配模型．

模型输入信息为道路初次匹配模型输出的可能的道路匹配集合尺ｃ一流程图如图６所示．

反向道路

讽别模型

——］ｒ

ｌ否

／＼

台丽∞』

个数为】

０是

ＧＰｓ匹配到集

合中的最后一

个道路Ｒ。

可能的道路

匹配集台

从匹配度队列中＿选择与

匹配度最大和歌大相对

应的道路：凰和ＲＭ』

≮

Ｒ西赢焉

０是

使片ｊ新的救重ｍａ、∞。

计算道路集合的匹配

度８；（ｉ＝ｌ，２，．，～）

查拽新的匹配度队列

５．“＝１．２，，Ⅳ）

的匹配线Ｒ“

ｌ器§寄瀚ｉ≤‰嚣

面，并排序

幽６平行反向道路识别模型算法流程图

Ｆｉｇ６ｎｏｗｃｈ州ｏｆ㈣ｇｎｉ叫ｔｌｏｎｍｏｄｅｌｏｆｐａｒａｌｌｅｌ

ａｎｄＭＴ∞ｄｒｏａｄ

乎行反向道路识别模型将产生干扰信息的反向平行道路剔除，识别出ＧＰｓ真正匹配的道路，并将其作为匹配结果输出．

３．４节点匹配模型

当车辆靠近道路路Ｌｉ（路段与路段的联结点，包括普通交叉路ｒ｜、主辅路的出入口等）时，由于减速、并线、转向等行驶行为导致ＧＰＳ数据中的方向信息变化较大而且准确性不高．此时，将ＧＰｓ匹配到道路往往会产生较大的误差．

　万方数据

第２期基于大规模浮动车数据的地网匹配算法４３

道路匹配模型最终的目的是为城市路况模型

提供车辆行驶轨迹．如果将ｃＰＳ数据匹配到节点，

即认为车辆一定经过该节点，节点就成为轨迹的一

个点这样就避免了路口的匹配误差，这就是节

点匹配模型的出发点．

匹配到节点的识别不能仅仅使用到节点的距离

远近作为判断因素，因为距离车辆近的节点，车辆并不ｕ一定通过．本模型结合可能匹配道路集合的概念，判断集合中的道路是否经过同一个节点．如果经过同一个节点，并且距离小于节点距离阈值，则认为ＧＰｓ匹配到节点，算法流程如图７所示．

绎过平行匣向道路

识别模型过滤的可

能道路匹配集合

瓣器竞

得到菇同的节点与

ＧＰｓ点的距离Ｄ。

礤彩叫翌

忱为ＧＰｓ与竹点距＞卜＿叫世芸茹ｍ

＼竺吵Ｌ兰

０是

＾研藁碧ｒ＿７

黼／

十道路Ｒ。／

图７节点匹配模型算法流程匿

Ｆｉ９７Ｍ０ｄｅｌｎｏｗｃｈｍｏｆｎｏｅｄｍｍｈ吨

３．５延时匹配模型

对于大型城市的复杂道路，如主辅路、立交桥等，道路与道路之间的距离近，角度差小，有时投影到平面上几乎是重合的．在这样的路网环境下，通过单一ＧＰＳ数据往往无法确定车辆的确切位置．这时就需要通过相同车辆的多个ＧＰｓ数据来联合判断车辆的行驶轨迹延时模型是一个迭代模型．图８是延时匹配模型的输人输出．

（１）模型输入．

对于单凭一个ＧＰｓ数据无法识别匹配类型的情况，把ｃＰＳ数据缓冲起来等待相同车辆发送更多的ＧＰＳ数据．

假设某车连续的Ｋ个ＧＰＳ数据组成的序列

罔８延时匹配模型

Ｆｉ９８ＭｏｄｃＪ０ｉ

ｄｃｆｃｍｄ

ｍ叶ｃｈｉ“ｇ

Ｇ。（＆＝１，…，Ｋ），满足以下条件之一：

①Ｋ小于延时匹配输入量的预设最大值Ｍ，其中肘根据ｃＰＳ采集间隔和道路复杂程度确定．本文根据广州的实际情况设置为１０．

②Ｇ，是已经确定匹配类型的ＧＰＳ，则ＧＰＳ数据序列Ｇ；（＾＝１，…，Ｋ）可作为延时匹配模型的输人量．

（２）模型算法．

模型的目的足为输入量中未匹配的ＧＰＳ确定匹配类型．算法总体思想是，在获得ＧＰｓ序列中满足各个ＧＰｓ数据匹配线要求的路段集合的基础卜，搜索并确定若干条可以从起点ｅＰｓ位置到终点ＧＰｓ位置的路线，然后对这些路线进行匹配度和长度的综合判别，最后确定一条最合适的匹配路线，作为最终的车辆行驶轨迹，同时也就确定了队列中所有ＧＰＳ的匹配结果．

算法首先提取Ｇ（％＝１，…，Ｋ）相对应的可能匹配道路集合矗ｃ，（女＝ｌ，…，Ｋ）．如果Ｇ。的匹配类型已经确定，则对应的路段集合Ｒｃ。只有一条道路或者一个节点．

之后，寻找路径ＲＴ．该路径由Ｊ条依次相连的路段Ｒ，（，＝１，…，，）组成，且满足以下条件：

①路径中路段的数量，一定大于或者等于ｃＰｓ队列的个数Ｋ；

②对于每一个与ＧＰｓ队列对应的路段集合面五（☆＝１，…，Ｋ），一定存在一条路段尺；∈Ｒｃ。，满足兄∈Ｒｒ；

③对于路径ＲＴ中，仟意两个满足条件２的路段Ｒ。，尺。（１≤ｎ＜６≤Ｊ），且Ｒ。∈尺Ｃ。一，Ｒｓ∈丽。，则ｎ７、６７一定满足１≤口’＜６７≤厍．可能存在多条满足条件的路径组成路径集合冗啊，即Ｒｒ（ｉ＝１，…，Ⅳ）．

　万方数据

交通运输系统工程与信息

如果Ａｒ＝ｌ表示只有一条通路可以满足以上３个条件．那么这条通路就是车辆经过的轨迹，也就是说，当Ｒ。∈面ｃ＾且Ｒ。∈月ｒ．，则Ｒ。就是第ｉ个ＧＰｓ匹配的道路．

如果路径集合Ｒ阳中的元素多于一个，即Ⅳ

＞ｌ时，进入路径识别过程．首先计算通路集合中每一条路径中的匹配度总和，即将路径Ｒ置中每一条包含于Ｒｃ。（＾＝１，…，臣）的道路的匹配度相加求和；之后计算所有通路长度．对以上两个结果进行归一化处理，之后按照一定的权重做求和，得到

柬匹配ｏＰｓ对列的匹配结果

２０（）７年４月

一个路径的可信度．采用与道路初次匹配模型中

匹配度的处理方式，路径可信度最大与次大之差如果大于设定阈值，那么可信度最大的路径就是最后的匹配路径．如果不满足以上条件，等待下一个ＧＰｓ，并日将新的ＧＰｓ一起作为输入条件输入延时模型，这也使得延时匹配模型成为一个迭代模型．

如果迭代次数大于一个阔值Ｍ或者新的ＧＰＳ在前面的模型已经确定了匹配结果，则不再继续进行迭代，将可信度最大的路径作为匹配结果．

图９为延时匹配模型算法流程图．

未匹配的ｏＰｓ对列

篇篇篙名箍ｆ

噤！登警Ｉ厂磊五丽孬

＾ｃ?ｎ＝１．．Ｅ）

，

’…………————ｆ——一／

列的匹配结果

病足条件的路＆目ｍ

鲨蛉篱嚣嚣Ｉ苎《贿专配的道略

ｌ≥、／

ｌ镒篙裴

计算路径吼的路

经长度玎

找出￡ｒ和６，进行归一化处理

二二工二二

将Ｌｚ和５，按腻不同的权重得卅通路屿

可信度

积窀

ｌ等特下

驾§

髫揣巷法

图９延时匹配模型算法流程图

ｎｇ９

Ｍｏｄｅｌ日ｏｗｅｈａｎｏｆｄｅｆｅｔ”ｄ

ｍａｔｃｈｉ噌

ＧＰＳ采集系统巾的采集频率是可以配置的．在采样周期较大、车速较快的情况下，两次ＧＰｓ数据之间的距离较大，通常会位于不同路段，甚至中间间隔数条路段．

对于两个连续的ｃＰｓ位于两条不相连的路段时，需要通过算法找出从起点ＧＰＳ位置到终点ＧＰＳ位置之间车辆的行驶轨迹，这种情况和在整个城市中搜索任意两个点之间的最短路径有所不同．城市中任意两点之问可能距离较远，经过的路径也比较复杂，而两个ＧＰＳ之间的距离不会太远，经过的路段也不会太多．路网中任意两个节点之间最

短路径算法通常使用删ｉｋｓｃｒａ算法，算法的时间复杂度为Ｏ（ｎ２），即使两点之间的距离很近，算法也需要进行多次计算量为ｎ的操作．而且需要大量的附加存储空问．凼此Ｄｉｉｋｓｔｍ算法并不适合距离较近的最短路径求解．

本文提出了一种针对短距离最短路径的基于深度优先搜索算法．思路如下：

根据车辆ＧＰｓ数据发送和车辆行驶的特点，同一辆车相邻两个ＧＰＳ之间的距离不会太远．一般情况下，在相邻路段或者相隔一个路段，只有少数会相隔多个路段．因此，算法分为两部分：先判断两个

万方数据

第２期基于大规模浮动车数据的地图匹配算法

ＧＰＳ是否相隔一个路段；如果不是，则进入下面算法．通过深度优先搜索遍历道路，结束条件有两个：第一，距离起点长度超过预先设定的最太长度；第二，找到终点节点．在这个过程中记录符合终点条件的路径，并且比较出最短路径．搜索算法采用递归方式，道路节点存储在先进先出队列中．

４算法评估及模型验证结果

算法的主要的计算量集巾在从道路网格拓扑结构中搜索道路集合以及两条道路之间的最短路径搜索．对于前者，由于网格分区已经排序，通过折半搜索法町以将复杂度控制在与道路数量级无关，不会随着道路复杂程度的增加而增加．对于后者，由于通过两个ＧＰｓ之间的最大行驶距离来控制，使得搜索的深度不会增加，同样与道路的复杂程度无关．

从实时性Ｅ考虑，主要时间延迟会发生在延时匹配，但通过延时匹配的个数控制，可以有效地避免大规模的延时．延时的时间也可以控制在满足浮动车地图匹配要求的范围之内．对于算法匹配的准确性，笔者通过跟车测试方式收集了大量的实际浮动车数据跑车路线覆盖ｒ大型城市的各种复杂道路情况，包括立交桥、高架桥、主辅路出入ｕ、环岛等．跟车测试中，不但记录浮动车数据，还实地考察跟车测试轨迹，避免电子地图不准确对验证结果产生影响．验证结果表明，此匹配模型的方案的准确率达到９５％以上．

本文所提出的浮动车地图匹配算法已经应用于广州市Ⅱｓ示范工程中，实现了对全市范围内１００００多辆装备有ＧＰＳ设备的出租车（浮动车）的数据有效匹配采集．系统运行情况表明该算法具有高效、准确和实用的特点．

５结束语

浮动车数据地图匹配是浮动车技术中的关键问题．ＧＰＳ数据误差、电子地图误差以及车辆行驶的不规则性，加重ｒ浮动车的地图匹配模型的复杂性和匹配难度．本文提出了一套完整的浮动车地图匹配算法．模型设计时，采取多模型相对独立的方式来构成地图匹配模型链，保证模型具有良好的

模型性．该算法已经被实际工程应用证明是有效的．为了有效采集浮动车数据，进一步的研究应着眼于路况信息的获取，浮动车规模系数等问题．

参考文献：

［１］谢振东智能交通系统的发展与思考［Ｊ］广州交通，２唧（２）：３２—３６［ｘＴＥＺｌｌｅｎ＿ｄｏｒ培．１＇Ｉｉ出ＩｌｇａⅡｄｄｅｖｄｏｐⅡ蜘ｔ

ｄⅡ研Ｊ］．‰卸ｇ小叫ｃ㈣耐ｃ蚯嘶，２０叭（２）：３２—３６］［２］谢振东，徐建闽丌ｓ与广州ｒ｜丁中心城市建设［Ｊ］．电子技术工程，２００２（Ｉ）：柏一４５［ｘＩＥｚｈｅｎ—ｄｏｎＥ，ｘｕ

量ａｎ＿ｍ｛ｎ兀弓ａｎｄａｍｌｕｌｅｃｔｕｒｅ。ｆｃｅｎｔｅｒｃｌｔＹｏｆＧｕａｆ懈ｈ删

［Ｊ］．Ｅｌｅｃｈ帅ｉｃＴｅｃｈｎｏｌｏ盯Ｅ峭Ⅱ。ｅｒ，２００２（１）：４０—４５．ｊ［３］章威，徐建闽．广州市Ⅱｓ共用信息平台软件体系结构研究［Ｊ］交通运输系统工程与信息，２００６，６（４）：

１１９—１２４．［ｚＨ＾ＮＧｗｄ，ｘｕＪｉ∽－Ⅲｌｎ．ｓｏｆｌｗａ咒ｓｙｓｔｅⅢ

６咖ｃｔＩ】ｒｅｏｆ丌丐ｃ０唧ｏｎｉｎｆｏ丌ｎ“血“ｐｌａ怕硼讷Ｇｕａ”铲ｈｏｕ

ｃ竹【ＪＪＪ伽阳“ｏｆＴｒａｎｓｐｏｎ“ｏｎｓｙｓｔ吣ＥⅡ画ｎｅｅ五ＩｌｇＨｌＩｄ

Ｉ山ｍ“ｏｎ１ｈｌｌｎｏｌｏ目，２００６，６（４）：１１９—１２４］

［４］Ｔ０ｒｄ８ｙＡｌ髑ａｎｄｒｅｂｋｔＬ吖ｅｌｔｉ“”ｅｓｔｉｍａｎ蚰ｗｊｔｈｐＩｏｂｅｖｅｈｉｃＪｅＢｌｎｓｉｇｎｄ—ｉ８ｅｄｎｅｔＷｏｒｋｓ【ｃｊ，，ｓ耐ｓｓＴｍ“印ｏｎＲｅ—

ｓｅａｒｃｈＣｏ—ｈｅｎｃｅ．Ｍａ唧ｈ１９—２１．２００３．

［５］Ｇ岫Ｇ，ＢｕＨＪ，勖ｍｍｏｎｓＮｃｏｍｍｅｒｃｉａｌ

ａｐｐｌｉｃａｎｎｎｓａｒｉｓｉ“ｇ如ｍａｎｏ““ｇｖｅｌｌｊｃｌｅｄⅡｔａｓｙｎｅｍ［ｃｊ，，丌ｓｕＫ

ｓｕｍｍｅＴＣｏｆ如咖坼ｅ

２００２，ＢｉｎｎｉｎＲｈ机

［６］土力，张海，范耀祖．基于探测车技术的路段平均速度估计模型［Ｊ］．交通运输系统工程与信息，２００６，６

（４）：２９～３３【ｗＡＮＧＴｊ，ｚＨＡＮＧＨｏ，ＦＡＮＹ洲

Ｓｔｕｄｙ０ｆｌｉｎｋａｖｅｒａｇｅ８婶ｅｄｅ出ｍａ“０ⅡⅢｏｄｅｌｂａｓｅｄｏ“ｐＩｏｂｃ

ｖｅｈｉｃｌｃｌ川．Ｊｏｕｍａｌ０ｆ１ｈｎ８ｐｏｎａｂｏｎｓｙｍ㈣Ｅｎ舒ｎｅｅ而“ｇ

ａｎｄＩｎｆ０加ａｂｏｎＲｃｈｎ胡ｑｇｙ，２００６，６（４）：２９—３３］［７］ｚＨＡＮＧＺｉ，ｘｕＪｉ蛐＿ｍｉｎ１）ｙｎ锄记州ｔｅ柙ｉｄ扑ｃｅｕｓ．ｎｇＧＰＳｅｑｕｉｐｐｅｄｔ丽ｄａ诅［ｃ］／，ｃｏｎｆｅ他ｎｃｅＰｒｏｃｅｄｄｊ“ｇｓｏｆｔｋ

ｓｅｖｅｎｔｌｌＩｎｋｍａ６０ｎ丑ｌＣｏⅢｅ㈣ｏｎＥｌｅｃｎｎｆｄｃ

Ｍ㈣ｍｅｎｔ＆Ｉｎ５ｎｍｅⅡｂ，２００５（８）：５４６—５５２

［８］夸德仁，郭阿轩基于ＧＰｓ与ＧＩｓ集成的车辆导航系统设计与实现［Ｊ］武汉测绘科技大学学报，２０００，２５

（３）：２０９—２１】ｌｕＤｅ硼，Ｇｕ０Ｂ１”ｐｘｕａ¨．ｖ“ｌｃ】ｅ¨ａｖｊ－

ｇａｄ帆ｓｙｓｋｍｄｅｓｉ印ａｎｄｉⅡｌｐｌ舢ｔａ６０ｎｂａ８ｅｄｏｎｉｎｔ。Ｆ“加

０ｆＧＰｓ锄ｄＧＴｓ【ＪｊＪ０ｕｒｎ一０ｆ砒ａｒＩ‰ｈｎｌｃａ】ｕｎｉ煳ｉｔｙ

ｏｆｓｍ＂“ｇ且１１ｄＭ＂ｐ１“ｇ，２０００．２５（３）：２０９—２１１］

［９ｊ苏沽，周东方，岳春生ＧＰｓ车辆导航中的实时地图匹配算法［Ｊ］．测绘学报，２００ｌ，３０（３）：２５２—２５６［ｓｕ

Ｊｉｅ，Ｚ１１０ＵＤｏｎｇ＿ｆａＩｌｇ，ＹＵＣｈⅡｎ＿３ｈｅ”ｇＲｅ甜一ｂｍｅｍ８ｐ＿

Ⅲ呲ｋ“ｇ出咿ｉＬｈｍ－ｎＣＰｓＮａｖｌ９３ｂｏｎｓｙｓｔｃｍｈｖｅｈｉｃｋＢ

［Ｊｊ．ＡｃＴＡＧｅｏｄａｅ６ｃａｅｔｃａｒＩｏＧｒａｐｈＩｃＡｓＩＮｌｃＡ２００ｌ，

３０（３）：２５２—２５６．］

　万方数据

基于大规模浮动车数据的地图匹配算法

作者：章威， 徐建闽， 林绵峰， ZHANG Wei， XU Jian-min， LIN Mian-feng

作者单位：章威,徐建闽,ZHANG Wei,XU Jian-min(华南理工大学,交通学院,广州,510640)， 林绵峰,LIN Mian-feng(广州交通信息化建设投资运营有限公司,广州,510033)

刊名：

交通运输系统工程与信息

英文刊名：JOURNAL OF TRANSPORTATION SYSTEMS ENGINEERING AND INFORMATION TECHNOLOGY

年，卷(期)：2007，7(2)

被引用次数：5次

参考文献(9条)

1.谢振东智能交通系统的发展与思考 2001(02)

2.谢振东.徐建闽ITS与广州市中心城市建设[期刊论文]-电子技术工程 2002(01)

3.章威.徐建闽广州市ITS共用信息平台软件体系结构研究[期刊论文]-交通运输系统工程与信息 2006(04)

4.Torday Alexandre Link travel time estimation with probe vehicles in signal-ised networks 2003

5.Gates G.Burr J.Simmons N Commercial applications arising from a floating vehicle data system

6.王力.张海.范耀祖基于探测车技术的路段平均速度估计模型[期刊论文]-交通运输系统工程与信息 2006(04)

7.ZHANG Zi.XU Jian-min Dynamic route guidance using GPS equipped taxi data[会议论文] 2005

8.李德仁.郭丙轩基于GPS与GIS集成的车辆导航系统设计与实现[期刊论文]-武汉测绘科技大学学报 2000(03)

9.苏洁.周东方.岳春生GPS车辆导航中的实时地图匹配算法[期刊论文]-测绘学报 2001(03)

相似文献(10条)

1.学位论文朱爱华基于浮动车数据的路段旅行时间预测研究2007

路段旅行时间预测是智能交通系统的一项重要内容，预测效果直接关系到ATIS和ATMS等ITS相关子系统功能的有效发挥。以往基于线圈等固定设备采集的数据预测路段旅行时间，采用路段上一个或几个断面的交通状况推断路段的交通状况，存在一定误差。浮动车比较均匀的分布在路段上，通过GPS车载装置和无线通信设备，将车辆信息(如时间、速度、经纬度坐标、方向等参数)实时的传送到浮动车信息中心。因此，浮动车数据对固定设备采集信息是一个良好的补充。

本文对国内外浮动车技术和路段旅行时间预测的研究和应用现状进行了综述，研究了浮动车数据预处理的方法，路段旅行时间的确定方法。在此基础上，研究了适合浮动车数据特点的路段旅行时间预测模式和方法，分别建立了路段旅行时间短时预测的卡尔曼滤波模型和长时预测的BP神经网络模型，并对模型的输入和参数的确定方法与选取范围进行了研究。应用本文研究的方法，基于“国家十五科技攻关课题“《杭州市道路和交通管理应用浮动车技术示范工程》所采集的杭州市浮动车数据，进行了路段旅行时间预测的示例分析，验证了模型的有效性。

2.学位论文龚珊基于浮动车GPS数据的行车速度预测模型研究2009

行车速度是交通状态的重要参数之一，也是智能交通系统需要预测的一项重要指标。由速度可以得到道路交通流量、密度等信息，为预测未来一段时间内的道路交通基本状况提供依据；同时可以分析道路上的交通流运行状态，控制交通流，反馈数据作为交叉口信号协同控制的依据，以便及时疏导过往车辆，缩短出行时间，减少损失，保证交通的安全畅通。以往基于线圈等固定设备采集的数据的短时预测，只是路段的某个断面，分布不够；浮动车比较均匀的分布在路段上，通过GPS车载装置和无线通信设备，将车辆信息（如时间、速度、经纬度坐标、方向等参数）实时传送到浮动车信息中心。因此，浮动车GPS数据对固定设备采集信息是一个较好的补充，为行车速度预测研究提供了良好的基础。

论文在综述国内外浮动车以及道路旅行时间、行车速度预测相关研究的基础上，对基于浮动车数据的路段行车速度短时预测模型进行了研究。基于浮动车数据，结合路网的历史运行和实时交通数据，分别建立了K-近邻预测模型、灰色马尔柯夫预测模型和加权马尔柯夫预测模型。在K-近邻预测模型中，提出了基于聚类分析和Pareto有效解的近邻确定方法；在灰色预测模型中，将灰色GM（1，1）和马尔柯夫理论有机地结合在一起；在加权马尔柯夫预测模型中，将对交通信息状态进行划分，并导入模型中进行预测分析。论文基于杭州市浮动车数据，对论文所建立的模型，进行了路段行车速度预测的示例分析，验证了模型的有效性。

3.期刊论文翁剑成.荣建.于泉.任福田.WENG Jian-cheng.RONG Jian.YU Quan.REN Fu-tian基于浮动车数据的行程速度估计算法及优化-北京工业大学学报2007,33(5)

依托重点实验室构建的浮动车采集处理实验系统,从行程速度的交通工程学定义出发,利用实时上传的浮动车数据,构建了以浮动车的驻留时间和路段长度为基础的行程速度估计算法.通过对比现场跟车实验测得的行程速度与算法计算结果,验证了该算法的行程速度结果精度达到90%以上,从而为交通信息服务系统提供了简单、准确的区间速度计算方法.最后,对算法进行了优化,有效地提高了算法效率,为满足大规模应用奠定了基础.

4.学位论文章春军动态交通信息系统的设计与实现2009

随着ITS（智能交通系统）技术的日益成熟，作为ITS主要内容的交通信息服务系统对实现动态交通诱导、缓解城市交通压力的作用也日趋重要。为此，国内外纷纷开展了依赖WWW基础、将图形化的GIS融合实时GPS浮动车数据的WebGIS在ITS上的应用研究。基于Web GIS的交通信息服务系统凭借其信息可视化、广泛的互操作性等众多优点，越来越得到重视。

本文在总结WebGIS网络化体系结构的演变和相应的关键技术的基础上，分析了交通信息的地图文件与属性数据组织方式，以实时GPS浮动车数据为基础，研究了基于道路附加属性的地图匹配方法、基于最优路径的交通诱导算法与基于存储过程的模糊查询实现等问题。并以浙江省为例，结合交通信息系统中的实际需求，采用基于J2EE技术的MVC多层结构下的Web应用方案，借助功能强大的MapXTreme Java为地图管理服务器，使用

Spring，Struts，Hibernate等优势技术，设计了基于SQL Server关系数据库与JBoss Web服务器的B/S结构方案，实现了适用于城市交通信息发布与诱导的瘦客户机/服务器模式的WebGIS系统。

该系统对城市交通信息资源加以利用，建立了快捷方便的查询机制，来获得路线有效的交通信息，为出行人员及有关部门提供快速准确、图文并茂的道路交通信息服务。本文设计实现的系统，无论在理论上还是在具体应用上都具有一定的价值。

5.学位论文张周强浮动车交通数据采集技术研究2008

浮动车(Floating Car)的思想是通过密集分布在路网交通流中连续的浮动车来采集数据，我们把这个数据叫做浮动车数据(Floating Car

Data，FCD)。与传统的采集方法不同的是，FCD可以在花费较少的情况下灵活的采集很多路段的信息，是智能交通系统(ITS)数据的采集的主要方式。

本文的浮动车集成GPS、GIS和高频摄像头，利用这些设备来采集行程时间、行程车速、停车时间、交通流密度和交通流流量等交通参数。

本文介绍了两种采集行程时间和停车时间等重要交通参数的方法，并用半自动的采集数据作为真值，与自动算法的结果进行比较，发现两种算法行程时间差别不大于6s的路段有84.7％，行程车速差别不大于5Km/h的路段有88.5％。我们可以认为本文的自动算法具有很高的精度和可靠度。

分析研究了浮动车采集交通流量的算法。通过理论推导和对间断流和连续流的实证验证，提出了合理的交通流速度算法，并验证了算法的可行性。 结合本文浮动车对图像识别的要求，并通过分析目前图像识别技术的特点，提出了适合本义的图像识别技术。还给出了本义浮动车的设备组成。

最后，就本研究进行了总结和进一步研究方向进行了简要的讨论。

6.期刊论文翁剑成.周翔.翟雅峤.赵晓娟.Weng Jiancheng.Zhou Xiang.Zhai Yaqiao.Zhao Xiaojuan浮动车数据

在城市宏观交通特性研究中的应用-武汉理工大学学报（交通科学与工程版）2008,32(5)

回顾和总结了国内外浮动车数据在交通信息服务和路网评价方面的研究及应用现状,提出浮动车数据的三阶段应用.重点阐述了面向城市宏观交通运行规律分析的第三阶段应用,提出基于历史交通流状态数据的数据分析流程.并以北京市浮动车系统采集的数据分析结果为例,分析了北京市路网运行速度的时空分布特性以及不同等级道路的里程利用情况.

7.期刊论文王嘉文.王吟松.刘好德.吴亦政.朱琛.WANG Jiawen.WANG Yinsong.LIU Haode.WU Yizheng.ZHU Chen

面向实时交通状态参数估计的浮动车车速置信优化算法-交通信息与安全2010,28(3)

针对浮动车数据稳定性问题,在浮动车及其数据特性分析的基础上,设计了考虑车速置信权重的交通状态参数算法.以车速、样本数和时间为衡量基准得到置信权重,据此计算交通状态参数.在出现异常数据时进行去噪处理;在数据量不足或数据连续性不好的情况下融合历史数据及临近时段数据,以反映真实交通状态.通过编程仿真和实地实验,对优化算法进行数值分析和测试,证明该算法可有效消除异常数据波动和数据量不足的影响,对交通状态参数估计具有较高的准确度和平稳性.

8.会议论文扈中伟.于泉.邵长桥.荣建城市出租车运营管理方法研究2007

本文研究基于浮动车数据进行出租车运营管理的方法,结合匹配后浮动车数据、出租车运营信息表等建立起专题数据库,开发了出租车运营状况分析系统,可对城市出租车系统的运营情况进行全面分析。经比较,该方法比基于人工调查和基于计价器IC卡数据的传统方法更为先进和有效。

9.会议论文叶加圣.胡学钢.陈锋FCD道路交通信息采集与应用系统设计与实现2009

FCD是当前智能交通领域的研究热点之一,能够实现城市大规模路网的实时交通信息采集。本文以宁波市FCD动态交通诱导系统为背景,采用出租车为交通信息探测车,研究并实现了一种FCD交通信息采集与应用系统。本文介绍了FCD的基本原理,详细描述了FCD道路交通信息采集系统的结构、功能和特点,并给出了FCD应用实例,说明了该系统的有效性。

10.学位论文段学勇基于小样本浮动车数据的信号灯路段行程时间估计方法研究2008

高效的交通是现代化城市发展不可缺少的部分。自上世纪后半叶，全球许多大城市在发展进程中逐渐遇到拥堵严重、效率低下等交通问题以及由此衍生出的一系列环境和社会问题，这在一定程度上制约了城市的发展。在这一背景下，人们提出了智能交通系统(ITS)的概念。交通检测技术作为智能交通系统的基础部分，对整个系统的运行效率起到重要作用。现代检测技术主要以断面检测器、车牌识别和浮动车为主，其中浮动车数据的获取成本相对较低，测量范围大，目前在采集行程时间数据的方法已获得广泛应用；

本文首先对现有的交通检测技术，尤其是行程时间采集方法进行了综述，在此基础上重点阐述了现有的行程时间的断面数据和浮动车数据估计方法。针对现有技术的不足，提出了一种基于小样本浮动车数据的信号灯路段行程时间估计方法，该方法能够较好的克服在浮动车小样本数据前提下，信号灯延误造成的数据波动带来的估计误差。最后，通过在实际道路上进行交通调查验证本方法的有效性，分别采用断面检测和浮动车检测方式对多个路段交通状态进行调查并估计路段行程时间，结果显示浮动车估计行程时间与断面估计行程时间相似，且采用本算法后行程估计时间误差较采用直接平均法减小。说明本文提出的方法能够有效的提高行程时间估计精度，在工程实践中具有应用价值。

引证文献(4条)

1.李宇光.李清泉基于矢量道路栅格化的海量浮动车数据快速处理[期刊论文]-公路交通科技 2010(3)

2.何鹏.史望聪基于3G技术的浮动车交通信息采集系统研究[期刊论文]-现代电子技术 2009(17)

3.尹相勇.贾顺平基于MapObjects的浮动车中心地图匹配综合算法开发[期刊论文]-计算机工程与应用 2008(36)

4.徐占鹏.伊文君.林凯基于GPS技术的浮动车改进地图匹配算法研究[期刊论文]-科技资讯 2008(20)

本文链接：82c32777f46527d3240ce037/Periodical_jtysxtgcyxx200702007.aspx

授权使用：沈阳自动化所(syzdhs)，授权号：0610d498-23d2-4b9f-9679-9e450093bfb7

下载时间：2010年12月7日

本文来源：https://www.bwwdw.com/article/3djq.html