-
车辆GPS轨迹匹配是利用GPS轨迹点数据和数字地图信息,确定车辆在数字地图上准确位置的一种定位技术。实际中由于各种因素的影响,车载GPS设备得到的轨迹点和车辆真实位置之间总是存在误差,这就需要利用轨迹匹配技术将获取的轨迹点数据准确匹配到数字地图上[1]。GPS轨迹匹配技术被广泛应用于车辆定位[2]、城市计算[3-4]、人类移动行为研究[5]、交通预测及引导[6-8]、搭乘服务[9-10]、交通异常事件检测[11-13]等领域,准确的轨迹匹配结果对于为这些领域提供可靠的基础数据具有重要意义。
常见的GPS轨迹匹配算法主要有位置点匹配、轨迹相关算法、D-S证据理论算法、基于隐马尔科夫模型的算法等。位置点匹配算法[14-15]是在多条候选路段中,选择具有最小罚函数的路段作为匹配路段。其算法简单,反应速度快,但罚函数鲁棒性差,对城市道路中的并行路段(一条道路同时包含主路和辅路,或高架道路和桥下道路水平位置重叠)容易造成误判。轨迹相关算法[16]通过对比候选路段的航向增量,选择具有最优值的路段作为合理的匹配路段。该算法能够矫正定位信息中的纵向误差分量,但在GPS数据误差增加、道路状况变得复杂时,地图匹配效果较差,无法对城市道路中复杂立交等场景进行有效的处理。D-S证据理论算法[17]以距离和航向为证据,用信任函数计算某个证据对某条候选路段的支持程度,选择支持度最大的候选路段作为当前路段。该算法能够处理不完备信息,但当证据发生冲突时,容易出错。基于隐马尔可夫模型(HMM)的地图匹配算法[18-21]将车辆GPS轨迹点位置作为HMM中的观察变量,将车辆实际所在位置作为HMM中的隐藏状态变量,通过实际数据训练模型再进行真实位置的预测。尽管在相对简单的道路网络场景下HMM方法已经可以获得很高的精确度,但对于复杂城市道路中大量存在并行路段、复杂立交等场景下该算法的适用性尚缺乏评估。
针对前述传统GPS轨迹地图匹配算法不能很好地处理复杂城市道路网络中并行路段、复杂立交等场景下的轨迹匹配这一问题,本文提出了一种基于道路网络拓扑结构的GPS轨迹匹配算法,将轨迹匹配问题转换为在加权的城市道路网络中寻找最优路径的问题,并利用成都市道路网络中上万辆出租车的实际运行轨迹数据对算法进行了验证。
Map-Matching Algorithm for GPS Trajectories in Complex Urban Road Networks
doi: 10.3969/j.issn.1001-0548.2016.06.023
- Received Date: 2015-07-21
- Rev Recd Date: 2016-03-15
- Publish Date: 2016-11-01
-
Key words:
- GPS trajectories /
- map-matching algorithm /
- road networks /
- taxi
Abstract: Map-matching for GPS trajectories is a key groundwork in mining transportation data. Reliable matching results are significant for monitoring traffic situation, publishing real-time transportation information, vehicle tracking, smart vehicle dispatching, and routing behavior analysis. In real urban road networks, there are numerous complicated road structures such as elevated roads, frontage roads, and interchange bridges. Traditional map-matching algorithms could not match trajectories on these structures accurately. In this paper, we propose a map-matching algorithm based on the topological structure of the road networks and transform the problem of matching GPS trajectories in road map into the problem of finding the shortest path in a weighted road network. We test the algorithm with the real data of GPS trajectories of tens of thousands of taxis in Chengdu. The results show that the presented algorithm can acquire a high success ratio and accuracy ratio in complicated urban road networks.
Citation: | LIU Zhang, WANG Xin-di, YAN Xiao-yong. Map-Matching Algorithm for GPS Trajectories in Complex Urban Road Networks[J]. Journal of University of Electronic Science and Technology of China, 2016, 45(6): 1008-1013. doi: 10.3969/j.issn.1001-0548.2016.06.023 |