基于车辆GPS轨迹数据的农村公路地图匹配算法

毛海臻 毛华

摘 要：为了提升农村地区车辆轨迹与县乡路网的匹配精度，解决车辆行驶轨迹飘移、点位跳跃等问题，本研究基于隐形马尔可夫理论，通过划分农村公路网格，计算观测概率与转移概率乘积的最大值，然后通过编程建模筛选出最佳候选路线，实现车辆轨迹与农村路网的在线匹配。笔者选取平顶山市宝丰县某农村公路为研究对象，现场验证了该算法的可行性和有效性。试验结果表明：该算法能够提升农村公路车辆轨迹的匹配精度，在路线十字、T形交叉及平曲线中点等区域的轨迹匹配精度提升效果明显。

关键词：农村公路;GPS轨迹数据;地图匹配

中图分类号：U418.6      文献标志码：A     文章编号：1003-5168（2022）11-0022-04

DOI：10.19968/j.cnki.hnkj.1003-5168.2022.11.004

Rural Road Map Matching Algorithm Based on Vehicle GPS Trajectory Data

MAO Haizhen1    MAO Hua2

（1.Henan Communications Planning & Design Institute Co.，Ltd，Zhengzhou 450000，China;

2.Hebi Qibin District Transportation Bureau，Hebi 458030，China ）

Abstract：In order to improve the matching accuracy between vehicle trajectory and county and township road network in rural areas，and solve the problems of vehicle trajectory drift，point jumping and so on.With the help of hidden Markov theory，this paper divides the rural road grid，calculates the maximum product of observation probability and transfer probability，selects the best candidate route through programming modeling，and realizes the online matching between vehicle trajectory and rural road network.A rural highway in Baofeng County，Pingdingshan City is selected as the experimental object to verify the feasibility and effectiveness of the algorithm.The results show that the algorithm can improve the track matching accuracy of rural road vehicles.In the areas of route cross，T-shaped cross and the midpoint of horizontal curve，the track matching accuracy is obviously improved.

Keywords：rural highway;GPS track data;map matching

0 引言

近年来，我国乡村公路发展迅速，截至2021年10月，全国农村公路通车里程达到438.2万 km。但部分乡村地区受通信基站数量少、地形地貌复杂等因素的影响，导致车辆GPS轨迹点位与实际路线存在偏差大、匹配度低等问题，如何有效提升乡村公路车辆轨迹匹配精度已成为研究的重点问题。

地图匹配（map-matching）技术是在车辆处于行驶状态下，实时收集、分析车辆的地理空间信息，借助算法模型来实现车辆经纬度与路线位置的动态关联[1]。针对路网轨迹算法模型，国内外学者已相继提出几何模型、权重模型、网络拓扑模型等，但在路网匹配精度和轨迹匹配时间方面仍存在诸多问题[2]。乡村公路具有线多面广、路网复杂的特点，传统的轨迹匹配模型已无法满足农村公路车辆轨迹匹配的精度要求。对此，本研究基于隐马尔可夫模型，建立基于车辆GPS轨迹数据的农村公路地图匹配模型，通过划分路线网格，计算观测概率、转移概率，寻找最大的似然路径，从而实现车辆行驶轨迹与农村路网的动态匹配。本研究选取平顶山市宝丰县某农村公路为研究对象，现场验证算法模型的可行性、准确性，从而有效提升农村路网车辆轨迹的匹配程度。

1 农村公路车辆轨迹匹配模型

1.1 划分农村公路网格

随着采集频率和行驶时间的增加，车辆GPS轨迹点位与路网经纬度的数据集合会成倍数关系增长，从而造成算法模型遍历计算任务重，导致匹配耗时长。依据农村公路路线长度远大于宽度的特征，近似将农村公路看作一条曲线，将路线的集合作为路网。在电子地图基础上，预先将路网进行网格化划分（网格间距约为100 m）[3]，并将网格单元进行分类排序、编码存储，进而提升数据库的计算运行效率。

1.2 车辆轨迹匹配模型

为了进一步提升轨迹点位匹配的效率及精度，通过设定圆形误差检索区域，缩小候选路线范围。检索区域的路线数量Φ分为以下3种情况：①当路线数量Φ为0时，说明受地形环境或数据精度的影响，该GPS点位发生跳跃，无法与路网进行关联匹配，在路网匹配过程中需要将此类无效数据进行剔除;②当路线数量Φ为1时，说明检索区域范围仅存在1条候选路线，车辆轨迹能够真实有效地反映出路网空间线形，该候选路线可作为最终结果进行直接匹配;③当路线数量Φ为2时，表明检索区域内存在2条候选路线，此情况多出現在路线交叉的区域，无法明确与GPS点位相匹配的具体路线，需借助计算模型比较轨迹点位与各路线间的最小距离ε。B4580923-1B7C-4064-8555-C506F1A371D8

依据数据点位匹配特征，发现最小距离ε与匹配概率成反比，即最小距离ε越小，匹配概率越高。选取高斯分布公式建立正态分布，计算轨迹点位于某候选路线的观测概率，见式（1）[4]。

[Pd（Trn︱Φi）=12πσze?12D（Φi，Trn）2σ2z]  （1）

式中：[Trn]为轨迹点位;[σz]为GPS点位的标准差，取20 m[5];[D（Φi，Trn）]表示点到候选路线的垂直距离。

候选路线的选取受相邻轨迹点的路线连续性的影响。同时，考虑到农村公路路线交叉多等特征，车辆行驶轨迹可能存在频繁转弯、点位跳跃等情况。对此，依据上个轨迹点所在的候选路线计算下个轨迹点所在候选路段的概率时，选用Manhattan公式来计算点间距[D1]，依次遍历最小距离[ε]与[D1]的差值，可得出车辆轨迹中连续点位的转移概率，见式（2）（3）[4]。

[dij]=[Dsp（Φi，Φj）]-[D1（Trn，Trn+1）]   （2）

[Pd（Φi，Trn，Φj，Trn+1）]=[  1βedijβ0]    （3）

式中：[Dsp（Φi，Φj）]<[THDsp]时，[Pd]取[1βedijβ]，反之则取0;[THDsp]为最短路径阈值，该值取决于车辆行驶速度;[β]为模型参数[2]。

1.3 车辆轨迹匹配

在已知观测概率及转移概率的基础上，采用维特比算法（Viterbi algorithm）来寻找最大似然路线[2]，即通过n个GPS轨迹点的观测概率、转移概率来计算所有情况下两者的乘积结果，乘积最大值的组合方式就是最接近真实路径的车辆轨迹，如图1所示。

1.4 编程建模开发应用

依据车辆轨迹的数据特征，建立涵盖车辆经纬度（lng，lat）、方位角[θ]、速度v、间隔时间t等参数的专题数据库，数据库类型选取目前应用广泛的MySQL。通过编程语言建立轨迹点位与路网数据的动态匹配模型，基于Java语言定制开发Android手机软件（见图2），通過高德地图API将处理前后的车辆行驶轨迹展示出来。由于高德地图采用的是GCJ-02火星坐标系，若直接使用WGS84坐标会造成点位偏差，因此在传递经纬度数据时应将坐标系格式进行统一[6]。

2 车辆轨迹匹配流程

依据数据采集、编程建模、开发验证等环节，总结车辆GPS轨迹数据与农村公路地图匹配算法流程，具体如下。

①采集车辆轨迹GPS点位数据（包括经纬度、间隔时间、瞬时速度等），调用农村公路电子地图，对初始数据进行筛选、清洗，创建数据库、数据表。

②依据农村公路路网密度，设定单元网格尺寸，批量生成单元模块，并进行分类排序、编码存储。

③划定误差检索区域范围，优选圆形误差阈值、采点频率等相关参数及数据标准。

④确定误差检索范围内存在的路线数量Φ，判定是否需要借助模型筛选候选路径。

⑤计算候选点的观测概率、转移概率、最小距离等，确定最大似然路线。

⑥通过编程建模、开发应用模块、现场采集验证，最终得到车辆的优化轨迹。

3 试验结果分析

为验证车辆轨迹与农村路网匹配模型的有效性，以平顶山市宝丰县某农村公路为试验对象，通过现场采集车辆GPS点位信息，对比算法优化前后车辆轨迹匹配结果存在的差异。

车辆行驶点位的采集频率将影响连续两点的距离误差及数据计算效率。随着采集频率的增加，采样点将更为密集，轨迹数据误差减小，但路网的匹配效率降低。为兼顾采集误差及计算效率的合理性，现场试验测试得出车辆连续GPS点位的采集时间间隔为20 s。

在保证车辆行驶速度、采样频率、起始时间等因素相同的前提下，平行采集车辆GPS轨迹点位，分别验证农村公路线形为直线、曲线及交叉口区域的轨迹优化效果，车辆GPS点位的数据处理结果如表1、表2所示。

为了能够更直观地展示路网匹配修正效果，将县乡道路电子地图、原始车辆轨迹、优化后轨迹分别导出为CSV或shp文件，借助ArcGIS及奥维地图软件，生成可视化的放大图片，如图3、图4所示

通过对图3、图4进行分析可以得出：①当农村公路线型为直线时，车辆原始轨迹、模型优化轨迹与路网的偏差较小，均能真实地反映出车辆的行驶轨迹;②当道路线形的平曲线半径较小时，车辆轨迹易在平曲线中点附近发生偏移，相较于原始数据，经模型优化后的轨迹可以更加准确地反映出车辆行驶轨迹;③当位于农村公路交叉口时，存在检索区域的路线数量Φ为2的时刻，叠加GPS精度误差，原始轨迹的部分点位可能跳跃至其他路线，而优化后的车辆轨迹能够有效保持车辆轨迹的准确性、连续性，避免发生点位偏离距离过大等现象。

4 结论

为提升车辆GPS轨迹与农村路网的匹配程度，本研究基于隐马尔科夫模型，通过计算观测概率、转移概率等参数，得出车辆最佳行驶轨迹，并以平顶山市宝丰县某农村公路为例，编程验证匹配模型的可行性、有效性。试验结果表明，经模型优化后的车辆GPS轨迹与路网的匹配程度较好，在曲线、路线交叉等复杂路网条件下，路网匹配精度良好。

参考文献：

[1] 于娟，杨琼，鲁剑锋，等.高级地图匹配算法：研究现状和趋势[J].电子学报，2021（9）：1818-1829.

[2] 高文超，李国良，塔娜.路网匹配算法综述[J].软件学报，2018（2）：225-250.

[3] 吉宏梅.基于隐马尔可夫模型的路网匹配算法研究[D].沈阳：沈阳理工大学，2020.

[4] 陈浩，许长辉，张晓平，等.基于隐马尔科夫模型和动态规划的手机数据移动轨迹匹配[J].地理与地理信息科学，2019（3）：1-8.

[5] 文江辉，霍佳琪，杨玲.一种车辆GPS轨迹数据的改进地图匹配算法[J/OL].武汉理工大学学报（交通科学与工程版），2022：1-11[2022-05-01].http：//kns.cnki.net/kcms/detail/42.1824.U.20220309.2125.093.html

[6] 康路，闫浩文，张黎明.电子地图间的实时坐标转换系统[J].遥感信息，2018（2）：122-126.B4580923-1B7C-4064-8555-C506F1A371D8