1背景如下图，1、2、3这三个点就是小车的GPS定位结果。虽然汽车在路上，但定位结果却偏离了道路。地图匹配是指将行驶轨迹的经纬度采样序列与数字地图路网进行匹配的过程，本质上是平面线段序列的模式匹配问题(Altetal.,2003)。在实际应用中，GPS采样信号的好坏会严重影响地图匹配结果：采样频率的降低、定位误差的增加、信号的丢失都会增加匹配的不准确性。这些情况在实际应用中经常出现。在这种情况下如何保持较高的路径匹配精度是一个值得研究的问题。2012年由ACMSIGSPATIAL创办的竞赛，内容为地图匹配。三年前，我有幸与国防科技大学杨安然博士一起参加比赛，收获颇丰。2地图匹配算法概述2.1按所用信息划分现有算法可分为几何、拓扑、概率和高级四类。a)基于几何的算法考虑GPS点和道路的几何信息，如距离、角度等；b)基于拓扑的算法使用道路拓扑信息进行控制；c)概率法考虑GPS点的概率；d)AdvancedalgorithmsComprehensiveconsideration通常对综合信息的使用给予综合考虑，包括卡尔曼滤波、模糊逻辑模型、隐马尔可夫模型等。2.2按采样点范围划分按采样点范围划分，可分为局部/增量算法和全局算法。a)局部/增量算法是贪心算法，每次确定一个匹配点，下一个点从已经确定的匹配点开始。这些方法根据距离和方向相似性找到局部最优值或边缘。(在线匹配)b)全局算法是从路网中寻找最接近采样轨迹的匹配轨迹。为了衡量采样轨迹和匹配轨迹之间的相似性，大多数算法使用“Frechet距离”或“弱Frechet距离”。还有时空匹配算法、投票算法等。（离线匹配）2.3按采样点频率划分现有的地图匹配算法根据轨迹数据的采样频率可分为：a)高频b)低频采样算法（ST匹配算法和IVVM算法一般认为30s及以上为低频采样，1s为低频采样10s进行高频采样。3我们的训练数据a)路网数据：美国华盛顿州（有128万条边）b)GPS数据：采样频率为1-30s，4使用的算法使用ST-Matching算法（Louetal.,2009），该算法是一种全局算法，可以综合几何信息（GPS点与道路的距离）、道路拓扑信息（最短路径）、道路属性信息（每条道路的限速）。具有精度高、稳定性好等优点。4.1准备候选集4.2确定权重a)空间因素权重(Fs)b)时间因素权重(Ft)5实验结果6技术实现要点6.1地图投影问题轨迹点的坐标不在同一个坐标系中，无法直接计算！解决方法：使用PRJ4地图投影库，将两个数据投影成统一坐标。6.2大路网信息数据量读取问题：路网有128万条边。我们使用C++。如果我们读取每条边并进行new和delete操作，将执行128万次，效率极低！解决方案：使用内存池技术。6.3最短路径算法的选择：最短路径必须在候选集的不同层级的候选点之间计算，而最常用的Dijkstra最短路径算法效率极低！解决方案：使用启发式最短路径算法：A星算法。6.4索引问题：由于比赛的真实测试会用到很多不同的路网数据，所以没有必要建立索引，但是在计算某个GPS点的候选集时，路网的所有数据都会参与计算，效率很低；解决方案：计算某一个GPS点对于一个GPS点的候选集，先进行切片过滤，例如以该GPS点为中心生成一个200m的正方形框，然后在框内建立新的路网.路网数据计算。
