基于FMM算法的地图匹配

FMM算法是一种将隐马尔可夫模型与预计算相结合的快速地图匹配（FMM）算法。通过预先计算指定上限的“起点-终点表”，以存储道路网络中特定长度内的所有最短路径对。通过预计算，使用哈希表搜索替代被称为MM性能瓶颈的重复路由的查询。此外，在FMM中识别并解决了几个退化情况和反向运动问题。对大量真实出租车出行轨迹的实验表明，FMM已实现了25000–45000点/秒的相当大的单处理器MM速度，随输出模式而变化。对FMM中不同步骤的运行时间的研究表明，在采用预计算后，新的瓶颈位于候选搜索中，更具体地说，是GPS点到道路边缘折线的投影。通过施加抑制措施，也可以有效地减少结果中的反向移动。下图为FMM算法的执行流程：

本文所获取的数据为深圳市2019年5月20日至26日7天的数据，其中23日的数据文件损坏。每一日的数据由288个以5分钟为时间切片组成的txt文件。文件中的字段值以逗号分隔，其值含义如下表所示：

不同的数据处理工具的适用性如下：

根据数据量的大小，使用python进行数据的处理，并利用数据处理相关的包如pandas、geopandas、transbigdata等。以一天的数据处理为例，为了方便数据的处理，首先需要将所有的小文件合并为一个大文件。使用pandas将读取的文件转为dataframe的格式，数据文件约为三千万行，之后利用transbigdata进行数据的可视化，其结果如下图所示：

经可视化以及数据的探查，发现有些字段的值不符合要求，如日期不对、出租车的瞬时速度异常、经纬度超出研究范围等，需要将这些数据剔除。利用pandas、transbigdata等包的一些方法对原始数据中的异常数据进行剔除，得到的结果可视化如下图：

其中数据的分布基本都在研究区的范围之内，一些异常的数据值也被剔除，相比原始数据，其数据质量有了很大的提升。然后对其进行OD数据和轨迹点数据的获取，轨迹点数据约有一千万个点，轨迹点的数据在QGIS中的可视化如下图所示，将得到的轨迹点保存为.csv文件，为后续的地图匹配做准备。

通过python的osmnx包下载深圳市的路网，osmnx是python拓展包，构建在geopandas，networkx和matplotlib之上，可从openstreetmap的下载地理数据资源，并进行建模，投影，可视化和分析等。通过osmnx下载的深圳市的路网地图如下图所示：

将FMM算法封装为docker镜像，docker 是一个开源的应用容器引擎，基于Go语言并遵从Apache2.0协议开源。docker可以让开发者打包他们的应用以及依赖包到一个轻量级、可移植的容器中，然后发布到任何流行的Linux机器上，也可以实现虚拟化。容器是完全使用沙盒机制，相互之间不会有任何接口（类似于iphone的app）, 更重要的是容器性能开销极低，这意味着一台机器可以运行更多的容器。 在容器中首先通过UBODT的命令，先对路网进行预处理，获取5km以下的所有OD对的最短路径，以加速地图匹配的处理。然后，使用fmm的命令，加载预处理结果，对所有的轨迹点数据与深圳市的路网进行匹配，将其中一条地图匹配的轨迹数据以及相应轨迹点和深圳市的路网在QGIS中的可视化如下图所示。

从可视化的结果来看，其轨迹点与路网匹配的结果符合人认知的常理。一天的轨迹点数据的地图匹配结果中，地图匹配的成功率在96%以上，容器处理的速度为约1500个点每秒，且地图匹配的效果较好。

本文首先对现有的地图匹配算法进行介绍比较，最终选用FMM算法对2019年5月20日至26日的深圳市出租车的GPS数据进行地图匹配。首先对出租车的GPS数据进行去重、异常数据剔除和研究区范围外数据剔除等数据处理操作提升数据质量，之后将数据处理之后的数据提取为轨迹点数据，然后使用docker的容器化技术将FMM算法封装为docker镜像，在容器中运行FMM算法，将轨迹点数据与深圳市路网进行地图匹配，其匹配的成功率在96%以上，且匹配的效果较好。现有的地图匹配算法发展较为成熟，后续可以使用其它不同的采样间隔出租车GPS数据，尤其是采样间隔更大的数据进行路网匹配，也可以使用其它类型的GPS数据，如共享单车GPS数据，公交车GPS数据等。