SIA OpenIR  > 信息服务与智能控制技术研究室
面向合乘行为分析的相似轨迹匹配算法研究
其他题名Similar Trajectory Matching in Carpooling
张顺龙1,2
导师库涛
分类号TP301.6
关键词车辆合乘 相似轨迹 合乘匹配 轨迹聚类 轨迹匹配
索取号TP301.6/Z34/2015
页数62页
学位专业控制工程
学位名称硕士
2015-05-26
学位授予单位中国科学院沈阳自动化研究所
学位授予地点沈阳
作者部门信息服务与智能控制技术研究室
摘要随着汽车社会的发展,环境污染、交通拥堵等问题越来越严重,国家发布了《小客车合乘出行意见》鼓励私家车合乘出行。合乘作为一种绿色的出行方式也被越来越多的人知晓与接受,过去的一年国内的拼车市场得到了高速发展。高效的合乘信息交流平台是促进合乘发展的重要手段,而合乘匹配是促进合乘信息交流的重要方面。本文主要关注面向合乘的相似轨迹匹配问题,在认真分析了国内外学者相关研究的基础上提出了面向大规模轨迹建立合乘请求匹配表的方法。首先,文章对合乘问题以及相似轨迹匹配问题进行了描述,对轨迹模型进行了讨论,并对匹配轨迹进行了分类阐述。介绍了已有的轨迹匹配算法,分析了不同算法存在的不足,并在此基础上提出了本文的方法。然后,针对本文研究中反复使用到的K-Means聚类算法进行了有针对性的改进,针对多聚类中心空间聚类中时间开销和内存开销大的问题首先提出了改进的K-Means算法DIACK算法。K-Means聚类过程中,数据点的调整一般只在数据点附近的几个类之间进行,通过内外围中心划分、距离上下限维护、动态及时更新类心,有效的减少了算法的迭代次数和维护距离上下限的内存开销,从而大大降低了算法的时间和内存开销。然后,针对路网中的轨迹特点,提出了基于交通流关键点挖掘的带权路网构建算法,包含转向点提取、关键点挖掘、关键点连通关系构建、路段权值计算以及路网中的轨迹压缩与构建方法五个部分。并对关键点挖掘中的聚类算法进行了改进,以提高算法的速度和精度。 然后,针对已有方法不能处理大规模轨迹匹配和不能处理复杂轨迹匹配的缺点,文章提出了先聚类进行初始划分再进行精细匹配的方法。详细讨论了初始划分方法中涉及的相似离度、基准线选取、边界效应等问题,并给出了本文的解决办法,在此基础上进一步定义轨迹匹配度,建立合乘请求匹配表。 实验表明,本文提出的方法能有有效应对大规模轨迹匹配问题,并能保证多种合乘轨迹的匹配成功率。
其他摘要The development of auto society has brought a series of problems such as air pollution, traffic jams, etc. Car-sharing viewed as a green travel way is encouraged by the government and now known and accepted by more and more people. In the past one year, the carpool market has grown up at a high speed. The development of carpool needs an efficient information exchange platform, and a carpool matching system based on similar trajectory is the most important part. This paper mainly focused on developing an efficient method to solve the similar trajectory matching problem. With a full study of related research, we proposed a method consists of two steps: first step divide the trajectories into small groups based on clustering technique and then find the matching pair within each group. First of all, we described the carpool matching problem, then give the trajectory model that will be used in this paper. Then we discussed different type of matching trajectories. All related methods are also introduced in this chapter, then we proposed our algorithm. Then proposed a new acceleration method based on the thought of dynamical and immediate adjustment of the center K-means with triangle inequality. The triangle inequality is used to avoid redundant distance computations; But unlike Elkan's algorithm, the centers are divided into outer-centers and inner-centers for each data point in the first place, and only the tracks of the lower bounds to inner-centers are kept; On the other hand, by adjusting the data points cluster by cluster and updating the cluster center immediately right after finishing each cluster’s adjustment, the number of iteration is effectively reduced. The experiment results show that our algorithm runs much faster than Elkan's algorithm with much less memory consumption when the cluster center number is larger than 20 and the dataset records number is greater than 10 million, and the speedup becomes better when the k increases. To better deal with the trajectory, we also proposed a time-weighted-netword build algorithm based on key trajectory points clustering.
语种中文
产权排序1
文献类型学位论文
条目标识符http://ir.sia.cn/handle/173321/16756
专题信息服务与智能控制技术研究室
作者单位1.中国科学院沈阳自动化研究所
2.中国科学院大学
推荐引用方式
GB/T 7714
张顺龙. 面向合乘行为分析的相似轨迹匹配算法研究[D]. 沈阳. 中国科学院沈阳自动化研究所,2015.
条目包含的文件
文件名称/大小 文献类型 版本类型 开放类型 使用许可
面向合乘行为分析的相似轨迹匹配算法研究.(1711KB) 开放获取CC BY请求全文
个性服务
推荐该条目
保存到收藏夹
查看访问统计
导出为Endnote文件
谷歌学术
谷歌学术中相似的文章
[张顺龙]的文章
百度学术
百度学术中相似的文章
[张顺龙]的文章
必应学术
必应学术中相似的文章
[张顺龙]的文章
相关权益政策
暂无数据
收藏/分享
所有评论 (0)
暂无评论
 

除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。