[0022] 本发明体系结构如图1所示。它由以下几部分组成：候选点准备、位置环境分析、加权分析和交互式投票。
[0023] 1.候选点准备
[0024] 针对GPS轨迹P＝(pi|i＝1,2,3…N)，选取在路网中以GPS点为圆心，半径r范围内的所有路段作为候选路段 k表示GPS点pi的第k个候选路段，选取在路段上与GPS点最近的点作为候选点。如图2所示，GPS点p1拥有一条候选路段r3，对应有一个候选点 GPS点p2拥有四条候选路段，路段r2和r3对应的候选点 和 落在路段范围内，而路段r1和r4对应的候选点 和 落在路段对应的起始节点。
[0025] 2.位置环境分析
[0026] 位置环境分析包括两部分：(1)约束分析；(2)时空分析。
[0027] (1)约束分析
[0028] 约束一：定义方向差阈值，如果车辆实时运动方向与对应路段方向之间的方向差值 保留对应的候选点，并使用方向分析函数对候选路段分配权重，否则，当时，直接将对应的候选节点滤除，后续的处理过程将不再考虑此候选点。阈值的设置可根据经验或统计数据进行设置。
[0029] 约束二：现实中车辆在路网中的运动速度都是在一个合理的范围内的。根据这一事实，我们可考虑通过分析车辆平均速度与最短路径的权重限速的关系，将速度超过合理范围的对应候选路段过滤。定义参数α(1＜α＜2)，当 时(1<α<2)，将 视为错误的匹配路径，其中 为两个连续候选点之间的
车辆平均速度， 为他们之间的最短路径的权重限速。如果采样点i-1的所有候选点到pi的候选点 全为错误匹配路径，则将GPS点i的候选点 所对应的候选路段作为噪声路段过滤。
[0030] 约束三：现实中，车辆一般被允许超速15％左右，根据这一事实我们还可以设置一个超速极限值将部分不符合条件的候选路段过滤。定义参数，设vi为GPS点pi的实时速度，vj是对应候选路段的限速，当vi＞(1+γ)·vj时，我们将对应的候选路段rj作为噪声路段滤除。
[0031] (2)时空分析
[0032] 时空分析是考虑几何拓扑和道路限速信息，通过数学函数式来确定候选点的权重的分析过程。观测概率是由GPS与候选路段的距离和GPS实时方向与候选路段的夹角决定，状态转移概率是由道路的拓扑结构决定。此外，算法还加入了速度分析函数，通过道路限速信息寻找与GPS速度相似的道路。
[0033] 一般而言，测量误差(距离误差和方向误差)的分布满足高斯分布N(μ，σ2)，所以计算观测概率 其中 是GPS点pi的候选点， 是与pi的欧几里得距离， 是GPS实时方向和对应候选路段之间的角度差。
[0034] 状态转移概率是评估两个连续候选点之间的最短路径和直线路径的相似性，算法中计算状态转移概率为 其中d(i-1,i)是两个相邻GPS采样点pi-1，pi之间的欧几里得距离，w(i-1,s),(i,t)是两个GPS点对应的两个候选之间的最短路径距离。
[0035] 我们定义一个时间分析函数，考虑结合采样速度与路段的限速来计算权重，反映车辆的平均行驶速度与路段限速的相似性，倾向于帮助我们选择行驶速度与限速最为相似的路段。算法中将时间分析函数定义为其中 是候选点 到候选点 的平均速度， 是最短路径的权重
限速。
[0036] 这一部分最后输出一个结合空间分析和时间分析后的权重候选图。节点是候选点集，边是两个相邻候选点之间最短路径的集合，节点和边所有的权重值都是基于位置和道路分析的结果。
[0037] 3.加权分析
[0038] 加权分析分析通过考虑全局GPS轨迹点之间的相互影响关系，在位置环境分析的基础上进行权重影响建模，即对静态矩阵的加权，它由两部分组成：(1)建立静态得分矩阵；(2)加权影响建模。
[0039] (1)建立静态得分矩阵
[0040] 位置环境分析产生的静态矩阵表示为M＝diag{M2,M3,M4,…,Mn}，其中ai和ai-1分别代表第个和
[0041] i-1个GPS点的候选点个数权重影响建模。
[0042] (2)加权影响建模
[0043] 考虑到两个GPS点之间距离影响成反比的关系，我们定义了一个反比权重函数对各个GPS点之间的影响进行分析。最后，每一个GPS点都有一个对应的距离加权矩阵：
[0044]
[0045] 4.交互式投票
[0046] 交互式投票是通过加权分析得到的权重候选图构建全局最优路径的过程，它由两部分组成：(1)寻找局部路径；(2)全局投票。
[0047] (1)寻找局部最优路径
[0048] 每一个候选点 必定有一条经过它的路径，并称之为 的局部最优路径。通过枚举，整个候选图中共有 条局部最优路径，其中ai表示GPS点pi候选点的个数。例如：图3所示的一条轨迹的候选图中，我们假设 和 的权重为-∞，这也就意味着整条路径必须经过 每个候选点的累计权重计算为
对于每个候选点，计算其累计权重后，记录得到该候选点累计权重的前一个候选点 最后，计算完所有采样点对应的候选点的累计权重之后，由最后一个采样点的候选节点的累计权重得到一个最大累计权重值，即 图3
中，最大累计权重值 它来自于p4的三个候选点。最终，可通过
全局最大权重值，以及每个最大权重值记录的其前一采样点对应的候选点的位置，得到权重最大的局部最优路径，即路径：
[0049] (2)全局投票
[0050] 每找到一条局部最优路径，我们会对路径中出现的候选点进行计数。完成所有的局部路径查找后，我们拥有了一组拥有计数值的候选点。全局投票就是将每个GPS点中计数值最大的候选点取出来组成全局最优路径。
