基于经验路径的路径规划系统
发布时间：2020-05-25 16:55
【摘要】：随着移动智能设备的广泛运用,基于位置服务(LBS)的应用得到了飞速发展,其中路径规划是基于位置服务的核心功能。路径规划系统的作用是为用户提供一条查询点间的优质路径,提高出行效率。现有的路径规划系统以指标驱动,需要考虑路程、时间、费用等多个指标,但是对于多指标的综合评估很难建立精确的模型,因此时常发生给出的路径不符合用户需求的情况。商业公司在提供服务的同时收集了大量的轨迹数据,这些数据记录了用户的时空信息,反映了用户的出行行为,具有较高的学习价值。很多研究都在尝试利用轨迹数据来优化路径规划的结果。不同于传统的指标驱动的路径规划系统,本文通过对收集到的原始采样信息进行合理的处理及筛选,构建经验轨迹数据库,用转向概率、转移概率两种方法来量化经验轨迹数据库中用户的出行经验并计算产生经验路径,最终将经验路径推荐给用户实现路径规划。最后我们在北京路网上设计并实现了基于经验路径的路径规划系统。本文的主要贡献可以概括为以下几个方面:(1)给出了从原始采样数据集中获取经验轨迹的方法。该方法便于在分布式计算平台上运用,满足海量数据处理对算力的需求。(2)提出了用转向概率、转移概率两种方法量化经验轨迹中的出行经验,并依据获得的知识计算产生经验路径。为了降低空间复杂度,进一步提出了基于分区的经验路径的处理框架。(3)实现了基于经验路径的路径规划系统,并在真实数据集上进行试验,通过与成熟的商业应用进行结果对比证明了该系统的实用性。
【图文】：
索中h(n)相当于搜索的雷达，可以为搜索指明方向，对搜索域可视化时，如图2-1所示A-Star算法通常会沿着目标方向搜索从而大大减少不必要的结点计算，因此h(n)预估代价的准确性会直接影响搜索的结果与性能。图2-1 Dijkstra和A-Star搜索域对比2.1.2 Contraction Hierarchies算算法法Contraction Hierarchies(以下简称CH)算法[9]是一种图上的索引技术。最短路径问题可以通过经典的算法如Dijkstra、A-Star等算法解决，，但在现今复杂的交通路网上这些经典算法具有明显的性能瓶颈，CH算法提出的目的是为了通过索引提高在大规模路网上进行路径规划的处理速度，在对路网的处理过程中引入了路网结点重要性的思想。对路网有向图G = (N, E) 在预处理阶段将所有的路口结点依据重要性进行排序，通常可以使用路口等级作为衡量结点重要性的标准，如果u<v则说明路口结点u的重要性小于路口结点v ,对于路径<v,u,w>，当<v,u,w> 是v至w的最短路径时可以通过捷径边<v,w> 来表示该条路径，此时的u就是一个非重要路口结点
第二章 相关理论及技术 基于经验路径的路径规划系统图2-4 google map和用户实际路径相似性置工作环境的变化难以保证数据传输可靠性导致的数据缺失；国内地图数据坐标系问题导致的不同公司的GPS数据坐标表示标准各异，数据格式不统一；部分轨迹数据导出、备份导致的数据冗余问题等等。这些数据质量问题导致原始轨迹数据不能直接使用，需要通过一些技术进行坐标转换、数据校准、补全缺失数据后才能用于数据挖掘。一般而言，轨迹数据预处理主要包括数据清洗，轨迹分割，路网匹配[2, 29]这三个步骤。数据清洗(data cleaning)是把原始输入的数据通过一系列的数据监测和数据修复后转换为干净、可用数据的过程，并且去除轨迹中因为误操作导致的冗余数据，冗余数据是指可以通过差值等计算导出的冗余采样点或是由软硬件设备异常导致的错误采样点、缺失采样点、不一致采样点等。这种“问题“采样点不仅占用了系统存储、浪费了计算资源，还会极大的影响后续处理分析的结果[29]。现有的数据清洗方法主要是从单条轨迹的角度清洗数据，借鉴平滑曲线思想，使用轨迹清洗算法[30, 31]智能的选取少量具有“代表性“的采样点，去除大量的冗余采样，使得轨迹的完整时空投影依然能够被有效表示。数据清洗的最终目的是提高数据质量。轨迹分割(trajectory segmentation)是指对含有多次出行意图的长轨迹进行合理切分
【学位授予单位】：苏州大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP391.3
【图文】：
索中h(n)相当于搜索的雷达，可以为搜索指明方向，对搜索域可视化时，如图2-1所示A-Star算法通常会沿着目标方向搜索从而大大减少不必要的结点计算，因此h(n)预估代价的准确性会直接影响搜索的结果与性能。图2-1 Dijkstra和A-Star搜索域对比2.1.2 Contraction Hierarchies算算法法Contraction Hierarchies(以下简称CH)算法[9]是一种图上的索引技术。最短路径问题可以通过经典的算法如Dijkstra、A-Star等算法解决，，但在现今复杂的交通路网上这些经典算法具有明显的性能瓶颈，CH算法提出的目的是为了通过索引提高在大规模路网上进行路径规划的处理速度，在对路网的处理过程中引入了路网结点重要性的思想。对路网有向图G = (N, E) 在预处理阶段将所有的路口结点依据重要性进行排序，通常可以使用路口等级作为衡量结点重要性的标准，如果u<v则说明路口结点u的重要性小于路口结点v ,对于路径<v,u,w>，当<v,u,w> 是v至w的最短路径时可以通过捷径边<v,w> 来表示该条路径，此时的u就是一个非重要路口结点
第二章 相关理论及技术 基于经验路径的路径规划系统图2-4 google map和用户实际路径相似性置工作环境的变化难以保证数据传输可靠性导致的数据缺失；国内地图数据坐标系问题导致的不同公司的GPS数据坐标表示标准各异，数据格式不统一；部分轨迹数据导出、备份导致的数据冗余问题等等。这些数据质量问题导致原始轨迹数据不能直接使用，需要通过一些技术进行坐标转换、数据校准、补全缺失数据后才能用于数据挖掘。一般而言，轨迹数据预处理主要包括数据清洗，轨迹分割，路网匹配[2, 29]这三个步骤。数据清洗(data cleaning)是把原始输入的数据通过一系列的数据监测和数据修复后转换为干净、可用数据的过程，并且去除轨迹中因为误操作导致的冗余数据，冗余数据是指可以通过差值等计算导出的冗余采样点或是由软硬件设备异常导致的错误采样点、缺失采样点、不一致采样点等。这种“问题“采样点不仅占用了系统存储、浪费了计算资源，还会极大的影响后续处理分析的结果[29]。现有的数据清洗方法主要是从单条轨迹的角度清洗数据，借鉴平滑曲线思想，使用轨迹清洗算法[30, 31]智能的选取少量具有“代表性“的采样点，去除大量的冗余采样，使得轨迹的完整时空投影依然能够被有效表示。数据清洗的最终目的是提高数据质量。轨迹分割(trajectory segmentation)是指对含有多次出行意图的长轨迹进行合理切分
【学位授予单位】：苏州大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP391.3
【参考文献】
相关期刊论文 前2条
1 许佳捷;郑凯;池明e
本文编号：2680454
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/2680454.html
