基于预处理的交通网最短路径实时查询研究

发布时间：2019-05-12 11:42

【摘要】：最短路径问题是图论与算法设计中的经典问题,同时也在路径规划、物流规划、GPS导航、社交网络、基于位置的服务(LBS)等现实世界的应用中扮演着重要的角色。交通路网上最短路径问题由最短路径问题衍生而来,特点为交通网数据规模大(如北京市主干路网就包含了10万个顶点与10万条边),计算请求频繁且实时性要求很高,传统的最短路径算法并不能满足计算需求。 “预处理——查询”模型是一种交通路网上最短路径问题的两阶段方法。在第一阶段对数据进行预处理,包括获得待使用的中间数据,以降低问题的求解难度；第二阶段被称为查询阶段,给定查询请求的源点与目标点,每个请求须在极短时间内进行响应。两阶段的想法源自路网是静态的,因此预处理阶段可以仅执行一次,其结果可以应对相同路网上大规模的查询请求。本文主要工作有： 1,基于预处理——查询模型的几种点到点最短路径算法性能分析本文针对“预处理——查询”模型上的两类算法——空间相干为基础的方法和顶点重要性为基础的方法,选出两类方法中具有代表性的算法,就预处理时间、空间消耗、查询效率进行分析比较。 2,针对一种基于代表元的有效最短路径近似算法,对代表元选取策略进行研究由于代表元的选取策略直接影响近似算法的求解精度,因此如何对路网进行区域划分、如何在区域中分配代表元成为了算法是否高效的关键点。本文将结合已提出的高效划分方案,提出一种适合最短路径近似算法的划分策略,并分析其与求解精度之间的联系。 3,通过模拟真实环境下路网上的实时查询请求,对最短路径长度的估算策略进行研究本文通过结合可视化的路网动态查询演示,说明近似算法对于最短路径中源点与目标结点的近似距离可做进一步优化,并提出一种基于代表元的两点间距离估算策略,对估算误差进行分析。
[Abstract]:The shortest path problem is a classical problem in graph theory and algorithm design. It also plays an important role in the real world applications such as path planning, logistics planning, GPS navigation, social network, location-based service (LBS) and so on. The shortest path problem on the traffic network is derived from the shortest path problem. It is characterized by the large scale of traffic network data (for example, the Beijing backbone network contains 100000 vertices and 100000 edges). The computation request is frequent and the real-time requirement is very high. The traditional shortest path algorithm can not meet the computing requirements. Preprocessing query model is a two-stage method for the shortest path problem on traffic network. In the first stage, the data is preprocessed, including obtaining the intermediate data to be used in order to reduce the difficulty of solving the problem. The second stage is called the query stage. Given the source and target points of the query request, each request must be responded to in a very short period of time. The idea of two stages originates from the fact that the road network is static, so the preprocessing phase can be executed only once, and the result can deal with large-scale query requests on the same road network. The main work of this paper is as follows: 1, Performance Analysis of several Point-to-Point shortest path algorithms based on pre-processing-query Model this paper focuses on the spatial coherence-based method and vertex importance-based method for two kinds of algorithms on the "pre-processing-query" model. The representative algorithms of the two methods are selected, and the preprocessing time, space consumption and query efficiency are analyzed and compared. 2. Aiming at an effective shortest path approximation algorithm based on representative element, this paper studies the selection strategy of representative element, because the selection strategy of representative element directly affects the accuracy of the approximate algorithm, so how to divide the region of the road network is carried out. How to allocate representative elements in the region becomes the key point of whether the algorithm is efficient or not. In this paper, combined with the proposed efficient partition scheme, a partition strategy suitable for the shortest path approximation algorithm is proposed, and the relationship between it and the accuracy of the solution is analyzed. 3. By simulating the real-time query request on the road network, the estimation strategy of the shortest path length is studied in this paper by combining the visual dynamic query demonstration of the road network. It is shown that the approximate distance between the source point and the target node in the shortest path can be further optimized by the approximate algorithm, and a distance estimation strategy between the two points based on the representative element is proposed, and the estimation error is analyzed.
【学位授予单位】：中国科学技术大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：U491

【共引文献】