基于GPS数据及频繁模式挖掘的路径推荐研究
发布时间：2022-01-12 17:49
随着经济的发展,城市道路建设也日渐完善。然而城市化进程的飞快加速,使得道路建设的速度仍赶不上人民对交通的需求的增长速度,而道路交通作为国民经济的基础设施,对国家的经济发展起着重要作用,因此,城市道路交通的协调与优化变得十分重要。优化出行路线是缓解交通压力的有效手段,也是当前世界各国的研究热点。传统的路径推荐方法通常从路径距离或行程耗时等方面考虑,将路网转化为图,根据深度优先搜索或广度优先搜索对路径进行穷举,计算得出符合要求的最优路径。然而由于它需要对路径进行穷举,因此在路网庞大的情况下往往成为困难问题,无法满足计算效率上的需求。并且,在有海量GPS历史数据做为支撑的情况下,可以结合数据挖掘对路径进行推荐。因此,本文结合海量GPS历史轨迹数据,从路径使用频率的角度出发,引入频繁模式挖掘,对两点间的路径进行推荐。在数据预处理阶段,本文首先针对所使用的开源GPS数据的特点,提出了有效的数据清洗方法,对缺陷数据、定位点信息遗漏以及采样稀疏的轨迹数据进行识别与过滤,同时对轨迹中的漂移数据进行了平滑处理,从而保证了轨迹数据信息的完整与丰富。其次,本文从轨迹形态出发,通过计算轨迹的方向角对路网路口进...
【文章来源】：西南交通大学四川省 211工程院校 教育部直属院校
【文章页数】：69 页
【学位级别】：硕士
【部分图文】：
道路交叉点判断示意图
利用相交路口定位点密度更大的特点，通过对固定范围内的道路自动识别路口交叉点。但第一步中滚动式聚类只在定位点严格以有较高的效率，而一般情况下，定位点的存储在空间上是呈杂定位点 p 进行一次聚类，就需要对所有定位点进行一次遍历才离阈值的定位点。假设定位点个数为 N，最终聚合得到的道路作的时间复杂度约为 O(nN)。于基于密度的道路交叉点识别算法外，文献[43]中提出了一种基点提取算法，利用于道路之间的方向角来识别道路交叉点。它的迹点进行预处理，对于邻域密度过大、相邻点运动方向角过大，利用快速滑动拟合算法对连续的空间轨迹数据进行拟合，在引入一个集合对已识别过的点进行保存，在遍历点的过程中不免对点的重复计算；最后运用 K-阶夹角求解拟合的方向向量，势进行分析，当某一点的 K-阶夹角大于给定阈值时，将此点加后对可能的路口进行聚合，提取出路口。算法执行流程如图 2
路点密度的方法，对原始 GPS 定位点数据的采样密度有更好的包容性，但其的根据滑动拟合来计算 K-阶夹角的方法较为复杂。.2 路径推荐算法随着城市化进程的飞快加速，城市道路的规模也在不断地庞大，两点之间来越复杂交错。这在给人民生活带来便捷的同时，也给从两点间的繁多道路最优路径带来了更大的困难与挑战。如何快速地向用户推荐最适宜的路径成重要的课题。针对此问题，有许多学科领域的学者进行对此进行了研究，本些研究做出一定的归纳与分析。2.1 基于图论的最短路径选择基于图论的最短路径选择是提出较早也较为经典的一类算法。它的问题原设存在一个连通结构如下图 2-3(a)左所示，在给定的两个位置(图中黑点所示多条可达路线，如何从中选择最短的路径。
【参考文献】：
期刊论文
[1]SA*:一种多线程路径规划算法[J]. 孙经纬,孙广中,詹石岩,毛睿,周英华. 地球信息科学学报. 2018(06)
[2]基于混合多种群自适应蚁群算法的无人机航路规划[J]. 李增,顾文灿,张宏亮,魏斌,黄雷. 计算机测量与控制. 2015(05)
[3]基于步行GPS轨迹的路网提取方法[J]. 欧阳鸿,刘建勋,刘毅志,廖祝华,陈佘喜. 计算机与现代化. 2014(02)
[4]遗传算法研究综述[J]. 葛继科,邱玉辉,吴春明,蒲国林. 计算机应用研究. 2008(10)
[5]GIS支持下的城市交通网络最短路径研究[J]. 王行风,贾凌. 计算机与现代化. 2005(03)
[6]最短路径算法:分类体系与研究进展[J]. 陆锋. 测绘学报. 2001(03)
[7]模拟退火算法综述[J]. 谢云. 计算机应用研究. 1998(05)
[8]关于最短路径的SPFA快速算法[J]. 段凡丁. 西南交通大学学报. 1994(02)
硕士论文
[1]基于GPS数据的地图拓扑提取的关键技术与应用研究[D]. 王玉林.西安理工大学 2018
[2]基于GPS数据的交通行为及出租车行驶路线推荐研究[D]. 杜娜娜.北京邮电大学 2018
[3]多影响因素下的导航路网数据路径规划研究[D]. 孔祥丽.武汉大学 2018
[4]分层道路的频繁路径查询算法研究[D]. 葛恩泉.杭州电子科技大学 2016
[5]基于GPS轨迹的道路拓扑构建和路径选择方法研究[D]. 谭康.湖南科技大学 2015
[6]大规模动态自适应图划分算法[D]. 许金凤.宁波大学 2015
[7]城市客流分布与出租车出行路线推荐算法的研究[D]. 孔蕙心.北京邮电大学 2015
[8]基于Pick-up树的路径推荐研究[D]. 胡昊然.南京大学 2013
本文编号：3585200
【文章来源】：西南交通大学四川省 211工程院校 教育部直属院校
【文章页数】：69 页
【学位级别】：硕士
【部分图文】：
道路交叉点判断示意图
利用相交路口定位点密度更大的特点，通过对固定范围内的道路自动识别路口交叉点。但第一步中滚动式聚类只在定位点严格以有较高的效率，而一般情况下，定位点的存储在空间上是呈杂定位点 p 进行一次聚类，就需要对所有定位点进行一次遍历才离阈值的定位点。假设定位点个数为 N，最终聚合得到的道路作的时间复杂度约为 O(nN)。于基于密度的道路交叉点识别算法外，文献[43]中提出了一种基点提取算法，利用于道路之间的方向角来识别道路交叉点。它的迹点进行预处理，对于邻域密度过大、相邻点运动方向角过大，利用快速滑动拟合算法对连续的空间轨迹数据进行拟合，在引入一个集合对已识别过的点进行保存，在遍历点的过程中不免对点的重复计算；最后运用 K-阶夹角求解拟合的方向向量，势进行分析，当某一点的 K-阶夹角大于给定阈值时，将此点加后对可能的路口进行聚合，提取出路口。算法执行流程如图 2
路点密度的方法，对原始 GPS 定位点数据的采样密度有更好的包容性，但其的根据滑动拟合来计算 K-阶夹角的方法较为复杂。.2 路径推荐算法随着城市化进程的飞快加速，城市道路的规模也在不断地庞大，两点之间来越复杂交错。这在给人民生活带来便捷的同时，也给从两点间的繁多道路最优路径带来了更大的困难与挑战。如何快速地向用户推荐最适宜的路径成重要的课题。针对此问题，有许多学科领域的学者进行对此进行了研究，本些研究做出一定的归纳与分析。2.1 基于图论的最短路径选择基于图论的最短路径选择是提出较早也较为经典的一类算法。它的问题原设存在一个连通结构如下图 2-3(a)左所示，在给定的两个位置(图中黑点所示多条可达路线，如何从中选择最短的路径。
【参考文献】：
期刊论文
[1]SA*:一种多线程路径规划算法[J]. 孙经纬,孙广中,詹石岩,毛睿,周英华. 地球信息科学学报. 2018(06)
[2]基于混合多种群自适应蚁群算法的无人机航路规划[J]. 李增,顾文灿,张宏亮,魏斌,黄雷. 计算机测量与控制. 2015(05)
[3]基于步行GPS轨迹的路网提取方法[J]. 欧阳鸿,刘建勋,刘毅志,廖祝华,陈佘喜. 计算机与现代化. 2014(02)
[4]遗传算法研究综述[J]. 葛继科,邱玉辉,吴春明,蒲国林. 计算机应用研究. 2008(10)
[5]GIS支持下的城市交通网络最短路径研究[J]. 王行风,贾凌. 计算机与现代化. 2005(03)
[6]最短路径算法:分类体系与研究进展[J]. 陆锋. 测绘学报. 2001(03)
[7]模拟退火算法综述[J]. 谢云. 计算机应用研究. 1998(05)
[8]关于最短路径的SPFA快速算法[J]. 段凡丁. 西南交通大学学报. 1994(02)
硕士论文
[1]基于GPS数据的地图拓扑提取的关键技术与应用研究[D]. 王玉林.西安理工大学 2018
[2]基于GPS数据的交通行为及出租车行驶路线推荐研究[D]. 杜娜娜.北京邮电大学 2018
[3]多影响因素下的导航路网数据路径规划研究[D]. 孔祥丽.武汉大学 2018
[4]分层道路的频繁路径查询算法研究[D]. 葛恩泉.杭州电子科技大学 2016
[5]基于GPS轨迹的道路拓扑构建和路径选择方法研究[D]. 谭康.湖南科技大学 2015
[6]大规模动态自适应图划分算法[D]. 许金凤.宁波大学 2015
[7]城市客流分布与出租车出行路线推荐算法的研究[D]. 孔蕙心.北京邮电大学 2015
[8]基于Pick-up树的路径推荐研究[D]. 胡昊然.南京大学 2013
本文编号：3585200
本文链接：https://www.wllwen.com/kejilunwen/ruanjiangongchenglunwen/3585200.html
