面向合乘行为分析的相似轨迹匹配算法研究

CORC > 沈阳自动化研究所 > 中国科学院沈阳自动化研究所 > 信息服务与智能控制技术研究室

题名	面向合乘行为分析的相似轨迹匹配算法研究
作者	张顺龙
学位类别	硕士
答辩日期	2015-05-26
授予单位	中国科学院沈阳自动化研究所
授予地点	中国科学院沈阳自动化研究所
导师	库涛
关键词	车辆合乘相似轨迹合乘匹配轨迹聚类轨迹匹配
其他题名	Similar Trajectory Matching in Carpooling
学位专业	控制工程
中文摘要	随着汽车社会的发展，环境污染、交通拥堵等问题越来越严重，国家发布了《小客车合乘出行意见》鼓励私家车合乘出行。合乘作为一种绿色的出行方式也被越来越多的人知晓与接受，过去的一年国内的拼车市场得到了高速发展。高效的合乘信息交流平台是促进合乘发展的重要手段，而合乘匹配是促进合乘信息交流的重要方面。本文主要关注面向合乘的相似轨迹匹配问题，在认真分析了国内外学者相关研究的基础上提出了面向大规模轨迹建立合乘请求匹配表的方法。首先，文章对合乘问题以及相似轨迹匹配问题进行了描述，对轨迹模型进行了讨论，并对匹配轨迹进行了分类阐述。介绍了已有的轨迹匹配算法，分析了不同算法存在的不足，并在此基础上提出了本文的方法。然后，针对本文研究中反复使用到的K-Means聚类算法进行了有针对性的改进，针对多聚类中心空间聚类中时间开销和内存开销大的问题首先提出了改进的K-Means算法DIACK算法。K-Means聚类过程中，数据点的调整一般只在数据点附近的几个类之间进行，通过内外围中心划分、距离上下限维护、动态及时更新类心，有效的减少了算法的迭代次数和维护距离上下限的内存开销，从而大大降低了算法的时间和内存开销。然后，针对路网中的轨迹特点，提出了基于交通流关键点挖掘的带权路网构建算法，包含转向点提取、关键点挖掘、关键点连通关系构建、路段权值计算以及路网中的轨迹压缩与构建方法五个部分。并对关键点挖掘中的聚类算法进行了改进，以提高算法的速度和精度。然后，针对已有方法不能处理大规模轨迹匹配和不能处理复杂轨迹匹配的缺点，文章提出了先聚类进行初始划分再进行精细匹配的方法。详细讨论了初始划分方法中涉及的相似离度、基准线选取、边界效应等问题，并给出了本文的解决办法，在此基础上进一步定义轨迹匹配度，建立合乘请求匹配表。实验表明，本文提出的方法能有有效应对大规模轨迹匹配问题，并能保证多种合乘轨迹的匹配成功率。
索取号	TP301.6/Z34/2015
英文摘要	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
页码	62页
内容类型	学位论文
源URL	[http://ir.sia.ac.cn/handle/173321/16756]
专题	沈阳自动化研究所_信息服务与智能控制技术研究室
推荐引用方式 GB/T 7714	张顺龙. 面向合乘行为分析的相似轨迹匹配算法研究[D]. 中国科学院沈阳自动化研究所. 中国科学院沈阳自动化研究所. 2015.