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

摘要

最短路径问题是图论与算法设计中的经典问题，同时也在路径规划、物流规划、GPS导航、社交网络、基于位置的服务(LBS)等现实世界的应用中扮演着重要的角色。交通路网上最短路径问题由最短路径问题衍生而来，特点为交通网数据规模大（如北京市主干路网就包含了10万个顶点与10万条边），计算请求频繁且实时性要求很高，传统的最短路径算法并不能满足计算需求。
　　“预处理——查询”模型是一种交通路网上最短路径问题的两阶段方法。在第一阶段对数据进行预处理，包括获得待使用的中间数据，以降低问题的求解难度;第二阶段被称为查询阶段，给定查询请求的源点与目标点，每个请求须在极短时间内进行响应。两阶段的想法源自路网是静态的，因此预处理阶段可以仅执行一次，其结果可以应对相同路网上大规模的查询请求。
　　本文主要工作有:
　　1，基于预处理——查询模型的几种点到点最短路径算法性能分析
　　本文针对“预处理——查询”模型上的两类算法——空间相干为基础的方法和顶点重要性为基础的方法，选出两类方法中具有代表性的算法，就预处理时间、空间消耗、查询效率进行分析比较。
　　2，针对一种基于代表元的有效最短路径近似算法，对代表元选取策略进行研究
　　由于代表元的选取策略直接影响近似算法的求解精度，因此如何对路网进行区域划分、如何在区域中分配代表元成为了算法是否高效的关键点。本文将结合已提出的高效划分方案，提出一种适合最短路径近似算法的划分策略，并分析其与求解精度之间的联系。
　　3，通过模拟真实环境下路网上的实时查询请求，对最短路径长度的估算策略进行研究
　　本文通过结合可视化的路网动态查询演示，说明近似算法对于最短路径中源点与目标结点的近似距离可做进一步优化，并提出一种基于代表元的两点间距离估算策略，对估算误差进行分析。

目录

声明

摘要

插图目录

表格目录

第1章 绪论

1．1 研究问题概述

1．1．1 点到点的最短路径问题

1．1．2 预处理——查询模型

1．2 相关工作介绍

1．2．1 基本算法概述

1．2．2 基于预处理——查询模型的两类最短路径算法

1．2．3 一种基于代表元的有效最短路径近似算法

1．3 论文工作与内容组织

1．3．1 研究内容

1．3．2 组织结构

1．4 本章小结

第2章 基础算法与实验数据说明

2．1 点到点最短路径基础算法

2．1．1 Dijkstra算法

2．1．2 A*算法

2．2 基于预处理-查询模型的点到点最短路径算法

2．2．1 以空间相干为基础的方法(以SILC为例)

2．2．2 以顶点重要性为基础的方法(以TNR为例)

2．3 实验说明

2．3．1 实验环境

2．3．2 数据来源

2．3．3 数据特点

2．3．4 实验实现

2．4 本章小结

第3章 路网中基于预处理——查询模型的主要算法研究

3．1 中转结点路由算法(TNR)

3．1．1 算法概述

3．1．2 算法定义

3．1．3 计算接入节点

3．1．4 指派中转节点

3．1．5 计算距离表

3．1．6 计算本地过滤器

3．2 空间诱导联动认定算法(SILC)

3．2．1 预备知识

3．2．2 顶点染色编码

3．2．3 区域染色编码

3．2．4 检索最短路径

3．2．5 距离编码

3．2．6 距离函数

3．3 实验分析与比较

3．4 本章小结

第4章 一种针对距离实时查询的有效预处理技术

4．1 背景分析

4．2 问题定义与符号表示

4．3 近似算法概述

4．3．1 代表元选取策略

4．3．2 预处理技术

4．3．3 查询技术

4．4 实验分析

4．4．1 代表元选取与分配策略实验

4．4．2 预处理与查询策略实验

4．5 本章小结

第5章 模拟真实路况下的最短路径实时查询

5．1 引言

5．2 动态模拟实时查询系统介绍

5．3 预处理与查询策略调整

5．4 演示实验

5．5 本章小结

第6章 总结与展望

6．1 全文总结

6．2 不足之处

6．3 未来工作

参考文献

致谢

在读期间发表的学术论文与取得的其他研究成果