在复杂的城市道路网络中，对车辆的GPS轨迹进行地图匹配的难点在于并行路段和复杂立交场景的处理，如图 1所示。由于在这些场景下某些轨迹点距离多条路段的距离都非常接近，单纯根据一个轨迹点的信息很难判定该轨迹点真正处于哪条路段上。但如果从一串轨迹点的角度观察，则很容易发现车辆能够运行的路径是非常有限的。如在图 1中，从该图左下角的道路经过立交驶入左上角的道路，必须要通过立交右上方的左转匝道才可能完成左转过程。因此，处理并行路段和复杂立交场景下轨迹匹配的关键在于利用道路网络的拓扑结构信息，找出轨迹首末点之间的可行路径。在有多条可行路径的前提下，则可以通过判断轨迹点到不同路径的距离，找到轨迹点最可能通过的路径。

图  1  并行路段和复杂立交场景下的GPS轨迹

以上过程可以通过在加权道路网络中搜索轨迹首末点之间的加权最短路径来实现。基本思路是：

1) 将路段长度作为道路网络上连边的基本权值；2) 将每个轨迹点投影给周边路段，用轨迹点到路段的距离来更新路段权值，使得投影轨迹点越多，距离轨迹点越近的路段获得更低的权值；3) 以权值最小为目标在轨迹首末点之间搜索一条路径。该方法可以保证得到的路径在拓扑上是正确的，同时由于用轨迹点到路段的距离更新路段权值，可以使所得路径距离轨迹的整体距离最小，因此最终得到的路径最有可能是轨迹点实际所处的路径。

下面给出该方法的具体实现步骤，算法流程如图 2所示。

图  2  算法流程示意图

初始化：根据道路地图建立有向含权网络模型，将道路路段作为网络中的有向边，路段长度作为边的初始权值，路段相交处作为网络节点。

1) 从车辆运行轨迹中截取时长为T的轨迹片段，将轨迹片段中的第一个点(记为s)连接到以s点为圆心、D为半径的圆形所覆盖的所有路段的起点上，并将s点到这些路段起点的权值设为0；同时将轨迹片段中的最后一个点(记为t)连接到以t点为圆心、D为半径的圆形所覆盖的所有路段的终点上，并将t点到这些路段终点的权值设为0。

2) 对于轨迹片段中除s、t点之外的每个轨迹点o，找出以o为圆心、D为半径的圆形范围内所覆盖的路段l，将o到l的垂直距离D_ol除以D作为权值更新系数，乘在l的权值上，得到新的路段权值，同时将点o的时间戳以及点o到路段l的距离D_ol记录在路段l上。

3) 用最短路径算法搜索s和t点之间权值最小的路径。

4) 从路径起点到终点依次检查路径中包含的每条路段，以轨迹点到路段的距离为标准去除重复的轨迹点(即对于同一个轨迹点判断它到哪条路段的距离更小就将它归属到哪条路段上)，得到轨迹点和路段的一一对应关系，该段轨迹匹配工作完成。

5) 返回步骤1)，进行下一个轨迹片段的匹配。

1) 具体参数的选取

算法中包含两个待定参数，一是轨迹片段的截取时长T，二是空间距离阈值D。对于轨迹片段的截取时长T，过长和过短都会影响轨迹匹配的成功率和准确率，后续算法应用实例部分会结合具体的应用场景给出建议的T取值范围。

对于空间距离阈值D，根据我国《城市道路交通规划设计规范》^[22]规定，城市道路中等级最高的快速路宽度为40~45 m，因此本文取道路的最大宽度为45 m，再考虑到车载GPS的定位误差为±15 m^[23]，本文取D=60 m。这样取值能够保证如果某时刻车辆在某条道路上行驶，那么这条道路一定处在以该时刻车辆GPS轨迹点为圆心、60 m为半径的圆形范围内。如果D取值小于60 m，可能有部分轨迹点无法找到匹配道路；而D取值大于60 m也不会增加算法精确度，只会增加空间查询操作的工作量。

2) 空间查询的效率问题

前述算法中涉及到大量空间查询操作(查找距离轨迹点D范围内的路段)，如果直接在全图中进行搜索，效率无疑是非常低的。因此，必须通过建立空间索引的方式，将全网中的路段按照一定的空间层次进行预排列，以提高空间查询的效率。本文采取了经典的R树索引结构^[24]为路段建立空间索引，可以有效提高路段空间查询的效率。

3) 路径搜索的效率问题

常用的网络最短路径算法(如Dijkstra算法、Floyd算法等)的复杂度是O(n³)^[25]，其中n是道路网络中节点的个数。一般大城市的道路网络所包含的节点往往多达数万个，在如此大规模的路网中反复进行最短路径搜索是非常耗时的。为提高路径搜索效率，本文采用缩减网络规模的办法，即只在轨迹片段周边一定范围内的路段所构成的子网中搜索路径。具体方法是：首先在轨迹片段中相邻的两个轨迹点之间连线，然后建立以连线为中心、半径为D的缓冲区，最后将此缓冲区与整个路网进行空间交集运算，抽取一个路网子集，如图 3所示。在此子网上进行最短路径搜索，可以有效缩短搜索时间，提高整个算法的运行效率。

图  3  根据轨迹点抽取子网示意图

本文用成都市出租车车载GPS所记录的轨迹数据对算法进行测试。该数据集中包含成都市13 933辆出租车在一天之内的行驶记录，每辆出租车的车载GPS设备以每10 s为间隔记载该车当前所处的时间、经纬度以及空重载状态，共有数据76 071 067条。同时，本文还使用了图 4所示的成都市道路网络数据，该数据集中记录了成都市绕城高速以内全部道路的拓扑结构和长度等信息，网络中共包含路段30 658条，节点21 921个。

图  4  成都市道路网络地图

图 5是本文算法的一个典型匹配结果。从图中可以看到，不论车辆运行轨迹是通过两座复杂立交的转向匝道，还是在两座立交之间的主辅路上进行切换，本文算法都给出了准确的匹配结果。这一结果在某种程度上验证了本文算法能够很好地处理复杂道路网络条件下的车辆轨迹匹配问题。

图  5  算法匹配结果示意图

为对本文算法进行更全面的测试，本文分析了在轨迹片段长度T取值不同的情况下，算法匹配成功率和准确率的变化规律，结果如图 6所示。这里的成功率定义为：在所有被匹配的轨迹片段中，成功找到一条有效路径的轨迹片段所占的比例。找不到一条有效路径的情况主要是由于在T过小时，有较大比例的车辆可能停驶不动或只移动了很短的距离，使得算法无法搜索到一条权值大于0的路径。因此，单纯从提高算法匹配成功率的角度来看，T取值越大，出现车辆停驶的可能性就越低，匹配成功率就越高。但过大的T会降低算法匹配的准确率。本文采用以下方法定义准确率：对于成功匹配的轨迹片段，如果其中存在一个轨迹点距离所匹配路段的最大距离超过了60 m，本文认为匹配结果是不可信的。这是由于在1.3节中已经提到，综合考虑GPS定位的误差和城市道路最大宽度，一个轨迹点和它所匹配的道路距离超过60 m是不可能的。因此如果算法结果中出现了超过60 m的匹配距离则判定结果是错误的，反之就认为结果是准确的。当然这种准确性也是相对的，因为除非真正知道车辆的实际运行路段，否则无法客观地判定匹配结果的准确性。根据准确匹配轨迹片段在全部成功匹配轨迹片段中所占的比例，可以计算出算法匹配结果的准确率。

图  6  轨迹长度T对匹配结果的影响

从图 6的结果可以看到，随着T的增大，算法匹配的准确率逐渐下降。通过分析未能准确匹配的轨迹片段特征，发现造成匹配错误的原因主要有两方面：一是真实路网中存在某些路段，但在地图数据中这些路段却是缺失的，如图 7a所示。在这种情况下，轨迹只能匹配到相对更近的道路上去，造成结果的偏差。二是车辆存在绕行的情况，即在一个轨迹片段中车辆两次或多次经过了同一个节点，导致路径搜索算法忽略了绕行部分的路段(因为这样总权值更小)，如图 7b所示。绕行的原因可能是出租车司机在绕行路段部分的某个地点放下乘客后又搭载了其他乘客，或者空车返回到其他地点载客等。

图  7  轨迹匹配不成功的两种典型情况

在以上两种情况中，第一种情况的改善依赖于道路网络地图完整度与准确度的提高，与算法本身无关。理论上如果有一个完全准确的路网地图，这种情况不可能发生。但第二种情况则与轨迹片段长度T的取值有关，因为T越长，出租车将以更大的可能性返回之前走过的一条路段。综合图 6中成功率和准确率两方面的结果，本文建议T取值在5~10 min之间是一个比较合理的范围，这也与一般在线交通状态发布的时间间隔要求相符合。

本文针对传统的地图匹配算法不能有效处理复杂城市道路网络中并行路段和复杂立交场景下的车辆轨迹匹配的问题，提出了一种基于道路网络拓扑结构的轨迹匹配算法。该算法充分利用了网络拓扑结构信息，可确保找到的路径一定是拓扑上可行的路径。同时，也充分考虑了轨迹点到路段的投影距离信息，使得最终匹配的路径以很大的可能性是车辆真实运行的路径。通过在成都市大规模路网中上万辆出租车的运行轨迹数据对本文算法进行了实际验证，结果表明在对轨迹片段长度进行合理取值的情况下，本文算法能获得较高的匹配成功率和准确率，能够满足实际应用的需求。这一研究结果为道路交通运行状态识别、在线交通信息发布、车辆定位与智能调度、出行路径选择行为分析等应用领域中的车辆GPS轨迹匹配提供了一种全新的方法。

相对于传统的地图匹配算法，本文算法的主要缺点是计算效率较低，主要原因是本文算法需要反复进行网络路径搜索和空间对象查询等耗时较高的运算。在实际应用中，可以从以下3方面着手提高该算法的计算效率：1) 采用更为高效的最短路径搜索算法，例如基于堆结构和桶结构优先级队列的最短路径搜索算法^[25]；2) 采用更为高级的空间索引结构对路段进行索引，进一步提高空间查询效率；3) 由于本文算法对不同轨迹片段的匹配是完全分开处理的，因此非常适合采用并行计算的方法，可从根本上提升算法的计算效率。