基于偏好的个性化路网匹配算法-高需 , 武延军 , 郭黎敏 , 丁治明 , 陈军成.pdf
免费下载
软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2018,29(11):3500−3516 [doi: 10.13 328/j.cnki.jos.005297] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563
基于偏好的个性化路网匹配算法
∗
高
需
1,2
,
武延军
2
,
郭黎敏
3
,
丁治明
3
,
陈军成
3
1
(中国科学院大学,北京 100049)
2
(中国科学院 软件研究所 协同创新中心,北京 100190)
3
(北京工业大学 计算机学院,北京 100124)
通讯作者: 高需, E-mail: gaoxu@nfs.iscas.ac.cn
摘 要: 定位技术的普遍应用,使得随时随地获取个人位置成为可能,进一步推动了基于位置的服务等新型应用
的发展,产生了海量轨迹数据.精确的路网匹配对提高这些新型应用的服务质量具有重要的研究意义,然而受众多因
素的影响,大部分轨迹的采样率较低,比如由签到类应用或低功耗设备生成的低采样轨迹,给路网匹配带来了巨大的
挑战.研究基于偏好的个性化路网匹配(driving preference based personalized map-matching,简称 DPMM),提出了在动
态道路交通网络中的用户驾驶偏好模型.基于该模型,提出了两阶段路网匹配算法:局部匹配搜索用户最可能采用的
几条局部 Skyline 路径;设计了全局匹配的动态规划算法,该算法返回在用户驾驶偏好下最可能的多条全局路径作
为最终匹配结果.实验结果充分表明,该方法是有效的和高效的,具有一定的使用价值.
关键词: 时空数据;轨迹;路网匹配;多目标优化;Skyline 路径;动态规划
中图法分类号: TP181
中文引用格式: 高需,武延军,郭黎敏,丁治明,陈军成.基于偏好的个性化路网匹配算法.软件学报,2018,29(11):3500−3516.
http://www.jos.org.cn/1000-9825/5297.htm
英文引用格式: Gao X, Wu YJ, Guo LM, Ding ZM, Chen JC. Personalized map-matching algorithm based on driving preference.
Ruan Jian Xue Bao/Journal of Soft ware, 2018,29(11):3500−3516 (in Chines e). http ://www.jos.org.cn/10 00-9825/5297.htm
Personalized Ma p-Matc hing Algorithm Base d on Drivi ng Preference
GAO Xu
1,2
, WU Yan-Jun
2
, GUO Li-Min
3
, DING Zhi-Ming
3
, CHEN Jun-Cheng
3
1
(University of Chinese Academy of S ciences, Beijing 10 0049, Chin a)
2
(Collaborative Innovation Center, Ins titute of Software , Th e Chin ese Academy of Sciences, Beijing 100190 , China)
3
(School of Computer, Beijing University of Technology, Beijing 100124, China)
Abstra ct : With the increasing proliferation of position technologies, there comes huge volumes of trajectory data, which are used in
many modern applications such as path planning and location based services. Accurate road network matching can improve the service
quality of these new applications. However, the low sampling trajectories bring a major challenge for map-matching. This paper studies
the problem of matching individual law-sampling trajectory to a dynamic multi-criteri a road network based on user ’s driving preferences.
First, a driving preference model in the dynamic road traffic network is proposed. Based on this model, a two-stage map-matching
algorithm is developed. While local matching searches multiple local likely Skyline paths, a global matching dynamic programming
algorithm is designed and the most probable k global paths are selected as the matching result. Experiments show that the proposed
method is eff ecti ve and eff ici ent .
∗ 基金项目: 国家自然科学基金(61402449, 91546111); 中国科学院战略性科技先导专项课题(XDA06010600); 北京市教委重点
项目(KZ201610005009)
Foundation it em: National Natural Science Foundation of China (61402449, 91546111); Strategic Priority Res earch Program of the
Chinese Academy of Sciences (XDA06010600); Key Project of Beijing Municipal Education Commission (KZ201610005009)
收稿时间: 2017-01-25; 修改时间: 2 017-03-12; 采用时间: 2017-04-12; jos 在线出版时间: 2018-04-16
CNKI 网络优先出版: 2018-04-16 10:59:45, http://kns.cnki.net/kcms/d etail/11.2560.TP.20180416.1059.004.html
高需 等:基于偏好的个性化路网匹配算法
3501
Key words: spatio-temporal data; trajector y; map-matching; multi-objecti ve optimization; Sk yline path; d ynamic progr amming
搭载有定位模块(例如北斗、GPS、GSM、WIFI 和蓝牙等)的智能终端不断普及,使得随时随地获得个人位
置信息成为可能,从而产生了轨迹大数据,并在基于位置的服务中得到了广泛应用,例如现代交通管理、智能导
航、位置推荐等.路网匹配(即将轨迹配准到道路交通网络)是此类应用不可缺少的关键模块,而精确的路网匹配
对提高服务质量起到了至关重要的作用.
然而,受建筑物遮挡、定位模块错误、低能耗的模块设计、多模式和多样化精度的定位技术等因素的影响,
大部分轨迹的采样率较低.社交网络的签到和其他位置共享服务(例如 Weibo、Facebook、Twitter 等)也仅能提
供低采样的轨迹.相似的低采样轨迹也可能来自具有位置标签的图片(例如 Flickr、Panorami o) 和稀疏的道路监
控获取的车辆快照,此类位置序列也形成了低采样轨迹.低采样轨迹的两个相邻采样点分别匹配到道路交通网
络中不相邻的边,补全轨迹实际经过的所有中间缺失边而构成完整的路径,是本文研究的主要内容.
如图 1 所示,p
1
和 p
2
是轨迹中的两个相邻采样点,分别匹配到路网中不相邻的边 e
1
和 e
13
,然而难以确定轨
迹实际采用的真实路径.可能的路径是 P
1
~P
4
中的某一条,查找出具体的路径称为路网匹配或路径推理.
Fig.1 Low-Sampling trajector y and its p ossible paths
图 1 低采样轨迹及其可能路径
已有路网匹配方面的研究大多仅考虑单属性道路交通网络,比如仅考虑旅行距离
[1]
、旅行时间
[2,3]
或路径频
繁度
[4]
.然而在实际的路径规划中存在着多重属性,不再是单一属性的最短路径、最快路径、最频繁路径或最省
油路径,而是多个属性的权衡(比如以权重将多属性线性组合为单一属性且组合后的属性代价最优,或选择至少
在某个属性上比其他所有路径优的路径).例如,在旅行距离和旅行时间双属性道路交通网络中,一个用户的旅
行距离和旅行时间权重分别为 0.3 和 0.7, 这表明该用户喜爱较短的旅行时间;而另一个用户的旅行距离和旅行
时间权重分别为 0. 8 和 0. 2, 表明他更喜爱较短的旅行距离.这两个用户选择了不同路径,但产生同样的低采样轨
迹,那么该轨迹将匹配到不同的路径.然而,已有工作由于忽略了轨迹产生者之间的个性化差异,最终把属于两
个用户的相似轨迹匹配到相同路径,而产生较大的误差.为了解决该问题,本文将构建多属性路网中的用户偏好
模型,从而体现用户在路径规划时的个性化差异.
如图 1 所示,路径 P
1
~P
4
都有可能是连接低采样轨迹相邻采样点 p
1
和 p
2
匹配到的边 e
1
和 e
13
,从而构成轨迹
的完整路径.然而,作为旅行距离和旅行时间的均衡路径 P
2
与最快路径 P
1
、最短距离路径 P
3
和最省油路径 P
4
差异较大,不同用户可能选择不同路径.已有研究表明,来自不同用户的相似的低采样轨迹,根据路网匹配考虑
的属性代价区别,最终可能匹配到的路径有所不同
[1−4]
.
一般来讲,在多属性路网中的每条路径都对应一个多属性的综合权重,如图 1 所示路径 P
2
在双属性路网中
(即旅行距离和旅行时间),两者的权重分别为 0.5 和 0.5.大部分用户在路径规划时不再选取单一属性最优
[5]
,而
是在多属性之间权衡,得到 Sky line 或 Pareto 路径.若用户知道了基本的路网代价,就倾向于不去选择所有旅行代
价都比其他路径要弱的路径(非优化路径).
本文提出在动态多属性道路交通网络中,从用户所有历史高采样轨迹中学习出用户驾驶偏好,并以多目标
优化或数据分析中普遍使用的 Sky line 或 Pareto 技术指导路网匹配,解决了现有路网匹配算法忽略用户个性化
of 17
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论