1 引 言

浮动车系统是伴随着ITS新技术应用而在近几年发展起来的新型交通流信息采集技术。一般使用大量的出租车或公交车作为浮动车，通过已安装的GPS车载装置和无线通信设备，将车辆信息(如时间、速度、坐标、方向等参数)实时地传送到浮动车信息中心。浮动车输出的动态实时交通信息不仅能为相关部门提供道路交通实况，而且可作为道路建设规划、拥堵缓解等各项工作中定量数据分析的基础^{[1, 2, 3, 4]}。

地图匹配技术是浮动车数据处理的关键技术之一，只有判断出车辆在哪条道路上行驶，才能将GPS数据转化为道路的交通状态^{[5, 6, 7]}。

浮动车系统具有数据量大，实时性要求高和采样点间隔比较大等特点。浮动车地图匹配在应用于现代城市复杂路网时主要面对3大关键技术难点^{[8, 9]}：① 数据需要实时处理，数据量较大，因此对系统的计算速度要求较高；② 数据间隔一般较大，导致定位点信息之间的相关性比较差；③ 现代城市路网密集且结构复杂，因此对系统的匹配容错率要求较高。

文献[10, 11]所述的传统导航地图匹配算法，由于GPS采样点的间隔仅为1 s，因此比较容易获得准确的轨迹曲线作为匹配样本，能够实现基于轨迹曲线的线到线的地图匹配。然而，以北京市为例，每辆浮动车每分钟上传一个GPS点数据，前后两点间的相关性差决定了浮动车系统无法采用线到线的地图匹配方法；此外，浮动车系统的数据量大，反映在单个GPS定位点上，其匹配时间远少于1 s。可见，传统的导航地图匹配算法不能直接应用于浮动车系统。

浮动车实时路况处理技术在我国各大城市还处于示范阶段，目前参与北京市浮动车系统的车辆约35 000辆，每辆车如果每分钟上传一个GPS数据，那么数据处理中心每天接收到的数据量就有5000余万条。随着浮动车数量的日益增多，文献[1, 2, 3, 4, 5, 6, 7, 8, 9]所述的浮动车地图匹配算法已难以满足当前应用环境下准确性与实时性的要求。可见，提高浮动车地图匹配的准确性与实时性，是需要进一步研究的课题。

道路网络的精度和属性结构直接关系到地图匹配算法的性能。为此，本文首先给出SuperMap GIS平台下的路网构建方法。

以经过配准后的栅格地图为背景，通过以直线代替曲线的方式创建道路中心线，将曲线道路分解为若干直线段；对于异面道路，合理设置非打断线参数，以真实再现立体交通；完成拓扑处理^[12]。

将路网中的假节点称为形状点，图 1给出拓扑处理后的部分道路网络。

图 1 部分道路网络 Fig. 1 Part of road network

图选项

地图匹配算法将利用道路网络的如下属性：

(1) 路段编号SmID;

(2) 路段起点SmFNode;

(3) 路段终点SmTNode;

(5) 路段反向阻力SmResistanceB;

(6) 路段长度SmLength;

(7) 路段方向类别Head。

其中，(4)、(5)、(7)为需要编辑与创建的字段。在SuperMap Deskpro中道路网络的部分属性如图 2所示。

图 2 SuperMap Deskpro中路网属性 Fig. 2 Attribute of road network in SuperMap Deskpro

图选项

其中，Head为新建字段，字段值“1”表示双向道路，将SmResistanceA与SmResistanceB均设置为0；字段值“2”表示单向道路，且方向为起点F→终点T，将SmResistanceA与SmResistanceB分别设置为0和∞(由10 000表示)；字段值“3”表示单向道路，且方向为终点T→起点F，将SmResistanceA与SmResistanceB分别设置为∞(由10 000表示)和0。

基于浮动车数据的地图匹配算法流程如图 3所示。

图 3 地图匹配算法流程 Fig. 3 Process of map matching algorithm

图选项

在地图匹配前，首先进行浮动车GPS数据的预处理，剔除存在漂移错误以及记录为空载、驻车及停运的数据，以求真实反映当前路况；然后进行坐标变换，与电子路网地图采用的坐标系一致。

按照一定的步长l(本文取70 m)，将导航电子地图道路网络从上到下、从左到右网格化分块，将道路网络分为M×N个相同的网格，记为Grid(i)，(i=0,1,…,MN－1)，记道路网络左下角的坐标为O(X₀,Y₀)，如图 4所示。

图 4 道路网络的网格分块 Fig. 4 Grid block of road network

图选项

设某定位点坐标为(x,y)，则其所在的网格为Grid([(Y₀+Ml－y/l]N+[(x－X₀/l])。

对于每一个网格Grid(i)，将其扩展为边长为2l的网格Grid′(i)，如图 5中虚线所示，记录在网格Grid′(i)之内(如路段AB、BC、AE、BD、DF、DE)及与网格Grid′(i)相交(如路段AH、EG)的路段编号，将各路段作为落入网格Grid(i)内的GPS定位点的候选路段。

图 5 候选路段的确定 Fig. 5 Candidate road determination

图选项

算法为每条候选路段计算权重，包括距离权重W_D、航向权重W_H及可达性权重W_R，并计算每条候选路段的权重总和W，以此确定匹配路段和匹配点。

距离权重表示为^[13]

点击浏览公式

图 6 定位点到候选路段的距离 Fig. 6 Distance between the GPS point and the candidate road

图选项

因此，当0≤D≤2D_H时，f(D)取值在1到-1间，并随D的增加而线性减小。当D>2D_H时，将f(D)设置为-1。

航向权重表示为

点击浏览公式

表 1 Δθ的取值 Tab. 1 The value of Δθ

	θ0	θ	Δθ
双 向 道 路 F T		[0,θ0]	θ0－θ
		(θ0,θ0+π/2]	θ－θ0
		(θ0+ π /2,θ0+ π]	π +θ0－θ
		(θ0+ π ,θ0+3 π /2]	θ－θ0－ π
	[0,π /2]	(θ0+3 π /2,2 π )	2 π －θ+θ0
		[0,θ0－ π /2]	π +θ－θ0
		(θ0－ π /2,θ0]	θ0－θ
		(θ0,θ0+ π /2]	θ－θ0
		(θ0+ π /2,θ0+ π ]	π +θ0－θ
	[π /2,π]	(θ0+ π ,2 π )	θ－θ0－ π
单 向 道 路 F T	xt，xf	θ	Δθ
		[0,θ0]	θ0－θ
		(θ0,θ0+ π]	θ－θ0
	xt≥xf	(θ0+ π ,2 π]	2 π －θ+θ0
		[0,θ0]	π +θ－θ0
		(θ0,θ0+ π]	π +θ0－θ
	xt xf	(θ0+ π ,2 π]	θ－θ0－ π
单 向 道 路 F T	xt，xf	θ	Δθ
		[0,θ0]	π +θ－θ0
		(θ0,θ0+ π]	π +θ0－θ
	xt≥xf	(θ0+ π ,2 π]	θ－θ0－ π
		[0,θ0]	θ0－θ
		(θ0,θ0+ π ]	θ－θ0
	xt xf	(θ0+ π ,2 π]	2 π －θ+θ0

表选项

可达性权重表示为

点击浏览公式

最短路径的求解采用 Dijkstra算法^{[12, 14, 15, 16]}，以上一匹配点和当前虚拟匹配点所在网格为对角网格，并将两对角网格构成的矩形区域作为Dijkstra算法的搜索区域。在解算过程中，各路段权值为路段长度与阻力之和^{[12, 14]}，即

正向权值为

点击浏览公式

反向权值为

点击浏览公式

如图 7所示，定位点P₁已经匹配到路段AB上的P点，对于当前定位点P₂，点E和F分别为其候选路段AD和CD的虚拟匹配点，其中路段CD为单向道路。点P到E和F的最短路径分别为P-A-E和P-B-C-F，而路径P-B-C-F的距离大于浮动车在该时间间隔内能够行驶的最大距离，因此，候选路段AD较CD具有更高的可达性权重。

图 7 可达性权重 Fig. 7 Reachability weight

图选项

权重总和表示为

点击浏览公式

算法为每条候选路段计算权重总和W，选出具有最高和次高权重和的两候选路段，比较两权重，如果相差大于1 % ，则将具有最高权重和的候选路段作为匹配路段，将该候选路段的虚拟匹配点作为匹配点。

反之，如果两权重和相差在1 % 之内，视为模糊情况，将当前定位点匹配到两候选路段的上游节点，即上一匹配点到两候选路段虚拟匹配点的最短路径所经过的最后一个相同节点。如图 8所示，点P是已经匹配到路段AB上的匹配点，对当前定位点Q，候选路段EF与DG分别具有最高和次高的权重和，点M与N分别为其虚拟匹配点。点P到M与N的最短路径分别为P-B-C-D-E-M和P-B-C-D-N，由于两权重和相差在1 % 内，因此将定位点Q匹配到路段EF和DG的上游节点，即D点。

图 8 上游节点匹配 Fig. 8 Upstream node matching

图选项

由于浮动车系统上传数据的时间间隔较大，同一辆车前后两点很可能相距几个路段。因此，算法对某一定位点结束匹配之后，在充分考虑路网拓扑关系的前提下，选择当前匹配点与上一匹配点间的最短路径作为车辆的行驶轨迹，这与大多数熟悉路网的司机在一般情况下会选择最近的道路到达目的地的实际情况相符。最短路径的求解同3.2.3 节所述方法，路段权值设置同式(4)和式(5)。

将本文算法应用于北京市道路网络，距离、航向与可达性权重系数D_W、H_W与R_W均设置为1/3。图 9给出同一辆浮动车连续3个定位点的正确匹配结果；图 10和表 2分别给出了其中第2个定位点的匹配情况，在表 2中，ID表示候选路段编号，R表示上一匹配点到当前定位点候选路段虚拟匹配点的距离；图 11给出传统算法直接将具有最高权重的候选路段作为匹配路段时的错误匹配结果。

图 9 正确地图匹配结果 Fig. 9 The correct map matching result

图选项

图 10 第2个定位点的匹配结果 Fig. 10 Matching result of the second GPS point

图选项

由此可见，本文设计的算法能够正确计算候选路段的各项权重，有效排除不可能的候选路段；同时，候选路段11和176分别具有最高与次高的权重，且相差1%之内，176为车辆实际经过的路段，算法将定位点匹配到两路段的上游节点，而如图 11所示，如果直接选择最高权重的候选路段作为匹配路段，将造成连续的匹配错误。浮动车地图匹配的最终目的是为城市路况模型提供车辆行驶轨迹，模糊情况下的上游节点匹配虽然带来较大的单点匹配误差，但却避免由于单点匹配错误而造成的连续匹配失败。

图 11 错误地图匹配结果 Fig. 11 The wrong map matching result

图选项

此外，采用NovAtel FlexPak-G2 GPS接收机接收同一辆浮动车在不同时间段内行驶于多条路线时的定位数据。利用此数据，将本文算法运行于2.53 GHz CPU、2G内存的计算机上进行验证。经统计，算法的平均正确匹配率为96.55%，单点的平均匹配时间为0.931 ms。

对于现有实时运转的浮动车地图匹配算法，正确匹配率平均在95%左右，单点匹配时间在几毫秒至几十毫秒之间。可见，本文算法在保证较高准确率的基础上，极大地提高匹配效率，能够满足目前北京市浮动车系统地图匹配的准确性要求及每分钟35 000点的计算速度要求。

针对现有浮动车地图匹配算法应用于城市复杂路网时面临的关键技术难点，对浮动车地图匹配展开研究，主要包括以下方面：

(1) 给出道路网络的构建方法，充分考虑道路网络的空间分布特性，使构建的网络区别于普通平面网络。合理编辑属性表结构，有效降低了地图匹配算法的计算复杂度。

(2) 基于网格的候选路段确定，根据GPS定位点所在网格，直接得到其候选路段，极大地提高了算法的运行效率。将各网格扩展为原来边长的2倍，将新网格所包含的路段作为候选路段，能够保证正确路段在候选路段之中，克服潜在的匹配错误。

(3) 基于距离、航向和可达性权重的定位点匹配，距离的计算，考虑投影点与候选路段的位置关系，准确得到虚拟匹配点。根据道路属性，给出车辆航向与路段方向夹角的各种可能。可达性权重的引入使车辆处于单向道路、立体交通道路时保证地图匹配的精度。模糊情况下的节点匹配，适于城市路网结构复杂、主辅路并行和交叉口繁多的特点，避免连续匹配失败。

(4) 基于最短路径的行驶轨迹选择，适于浮动车数据采样间隔大的特点，对Dijkstra算法搜索区域的合理限制，有效保证路径选择的实时性。

由于不同的权重系数会给匹配结果带来一定的影响，车辆在两匹配点间的行驶轨迹并不是在任何情况下都是两点间的最短路径，因此，为进一步提高算法的准确性，根据车辆的行驶状态和所处的路网环境合理调整权重系数，以及考虑更多的因素确定车辆在两匹配点间的行驶轨迹，是下一步的研究方向。