基于动态规划算法的轨迹地图匹配软件设计与实现

姜雪原

摘要：针对智能交通领域中动态轨迹点的地图匹配问题，提出并设计了一种基于动态规划算法的轨迹匹配软件，并在路网拓扑构建、最短路径计算方面进行改进优化，提升了软件工作性能。工程应用表明，该软件具有较好的计算精度和效率。

关键词：地图匹配；GPS轨迹；路网拓扑

中图分类号：P208 文献标识码：A DOI：10.3969/j.issn.1003-6970.2015.05.023

0 引言

智能交通系统（ITS）应用越来越广泛，常见的包括车辆导航、交通流量分析、位置服务（LBS）等。能够提供位置信息的传感器主要是安装在车辆、手机等移动终端上的GPS设备。连续的GPS采样点就形成了运动轨迹，由于GPS的采样精度和频率、建筑物遮挡等原因，使得轨迹无法直接与道路网络（简称“路网”）重合，存在一定误差。通过一定算法使得轨迹与数字地图中的相应道路重合的过程称为“轨迹匹配”。轨迹匹配的实现能够为车辆导航、交通流量实时分析、公交线网分析等应用提供较大支撑能力。

1 相关研究

轨迹地图匹配软件的核心模块就是轨迹匹配算法。在轨迹匹配的相关算法资料中，主要分为局部匹配和全局匹配两类。局部匹配适合于解决在线实时应用问题，全局匹配适合于解决离线应用问题。

局部匹配算法主要是利用当前GPS轨迹点与候选道路几何关系及前后相邻轨迹点的关联信息来进行匹配的。文献[4]采用轨迹点与道路的方向权重、轨迹点到道路的距离权重、历史信息权重的综合来完成轨迹匹配。然而由于局部匹配算法仅采用区域范围内的轨迹点信息，所以仅适合于高采样频率轨迹的实时地图匹配情况。特别是由于没有全面考虑到道路拓扑关系，在复杂路网情况下，容易导致误匹配。

全局匹配算法主要是利用道路拓扑网络来匹配整个GPS轨迹。文献[5]使用Frechet距离作为权重来构建拓扑网络图，采用最短路径算法得到匹配道路。文献[6]使用曲线相似度计算来进行轨迹匹配。然而，全局匹配算法比较明显问题就是算法实现复杂、计算量大，有一定应用的局限性。

使用隐马尔科夫（HMM）等概率统计算法，以及多假设技术（MHT）来解决轨迹匹配问题也是对匹配算法的重要补充。

本文工作主要是基于动态规划的全局匹配算法，设计并实现了一套软件来解决离线轨迹匹配的问题。

2 软件构成与功能

轨迹地图匹配软件主要由路网拓扑软件和地图匹配软件两部分组成。

路网拓扑软件的主要功能是基于导航电子地图数据构建道路拓扑网络，为地图匹配软件提供路网拓扑结构。

主要的工作流程如图l所示，首先读取电子地图数据，并可对数据进行修改和编辑，然后加载全部路网数据，并对路网数据进行预处理（验证数据和格式的有效性），基于预处理后数据构建路网拓扑，最后对拓扑结构进行验证，并发布为路网数据。

地图匹配软件的主要功能是基于路网拓扑数据完成对轨迹数据的地图匹配，支持单轨迹匹配及多轨迹批量匹配，并可对匹配结果进行展示和编辑。

主要工作流程如图2所示，首先加载轨迹数据文件并进行初始化，然后对轨迹数据进行检查和重采样，基于匹配算法进行轨迹匹配，可基于地图实现结果展示及编辑，最后进行匹配结果的发布。

3 关键技术及算法设计

3.1 路网拓扑构建

路网拓扑构建主要是利用电子地图中的节点和线数据构建拓扑结构图，如图3所示。路网拓扑构建是轨迹匹配前的必要工作，路网拓扑的质量也对地图匹配的效率和准确性至关重要。

路网拓扑构建的主要步骤包括：数据预处理、数据校验、拓扑建立、拓扑验证。

数据预处理是根据道路等级、可通行等属性对道路进行过滤，以减少道路数量，提升查询和搜索效率。

数据校验主要进行剔除未与道路连接的节点、边界道路补点、以及图幅拼接问题，从而保证路网数据的完整性和一致性。