基于大数据分析的城市交通网最短路径算法设计

摘要

最短路径问题是图论中较为经典也是相对基础的问题，其经过了大半个世纪的研究，受到许多领域研究人员的关注，最短路径算法的研究成果十分丰富。最短路径算法广泛运用在各种现实场景中，其中交通网中选取最优出行路径就是最短路径算法的一项具体应用。随着城市的发展，城市交通网的规模逐渐扩大，网络节点数量庞大且网络结构复杂多元，使得经典最短路径算法无法使用，因此，应用于大规模网络中最短路径的优化技术和优化算法成为近几年最短路径算法研究的重点。在这些研究中，并行计算成为大规模网络最短路径算法的主要研究方向。近几年，国内外学者针对大规模网络和动态网络提出了一系列最短路径算法，其中部分算法使用了启发式路径搜索方式、并行计算方式或使用网络分层模型进行最短路径计算。　　本文在现有的研究成果中总结出相关经验，综合了并行计算思想和启发式搜索方式，提出了一个适合于城市交通网任意节点间最短路径计算的层次最短路径算法。本算法主要由三个子算法组成，分别是大图分解过程、PFloyd算法和SPS算法。由于最短路径计算的时间复杂度与图中节点个数相关，因此，在图分解过程中，我们设计了一个两层网络模型，即将原始网络分割为若干个子网，再将子网抽象为节点并构造二层网络。当路径查询的起点与终点同属于一个子图时，本文设计了并行的任意节点间最短路径算法PFloyd算法，该算法根据任意节点间最短路径计算迭代公式与矩阵乘法运算公式之间的映射关系，将任意节点间最短路径计算移植至MapReduce上，通过MapReduce的logn2次矩阵迭代相乘，计算出最短路径的权值矩阵和路径矩阵，算法通过对权值矩阵和路径矩阵的查询得到所求的最短路径。当路径查询的起点与终点属于不同的子图时，本文设计了一个跨子图的路径搜索算法SPS算法。SPS算法采用了启发式的搜索模式以构建路径，它定义了子图间的距离计算方式，并将子图间距离信息作为启发式的引导信息，在当前访问子图的邻接子图中，递归选取若干个与当前子图相近的子图作为下一次访问的子图对象。SPS算法采用双向搜索模式，前向搜索与后向搜索同步进行，使得前向搜索与后向搜索的对象快速逼近，从而实现搜索算法的加速。通过对参数的调整，可以提升路径搜索的精确度，减少路径搜索的时间。当路径构建完成后，只需挑选出所有路径中最短的那条即为SPS算法所求。文中选取美国旧金山港湾区交通网路径数据作为本文实验数据，对层次最短路径算法进行实验分析，验证了算法的可用性。　　本文的层次最短路径算法在层次网络模型中进行，三个子算法共同配合，完成了算法在子图层与二层网络中的路径搜索与路径拼接。二层网络中的路径搜索采用双向的启发式路径搜索模式，加快了算法的搜索效率。针对交通网路段的权值根据时间动态变化的问题，算法在图分解过程中将原始网络进行切分，使得路段权值以子图为单位动态更新，减少了权值更新带来的额外消耗。通过实验结果，证明了本文算法在大规模交通网最短路径计算中有良好表现。

目录

声明

摘要

1 绪论

1．1 研究背景与意义

1．2 国内外研究现状

1．2．1 经典最短路径算法

1．2．2 大规模网络最短路径研究

1．3 研究内容与组织架构

2 预备知识分析

2．1 城市交通网存储

2．2 基于MapReduce的矩阵运算

2．3 交通网数据获取

2．3．1 高德地图API

2．3．2 Kafka消息队列

2．3．3 动态数据获取

2．4 本章小结

3 层次最短路径算法设计

3．1 问题描述

3．2 算法模型定义

3．3 图分解

3．3．1 图分解模型定义

3．3．2 子图分割方案

3．3．3 网络分层方案

3．4 PFloyd算法

3．4．1 PFloyd算法分析

3．4．2 PFloyd算法实现

3．5 SPS算法

3．5．1 SPS算法分析

3．5．2 SPS算法实现

3．6 算法复杂性分析

3．7 应用场景分析

3．8 本章小结

4 实验分析

4．1 实验环境

4．1．1 实验环境

4．1．2 实验数据

4．1．3 评价指标

4．2 图分解实验

4．3 PFloyd算法测试

4．4 SPS算法测试

4．4．1 参数选取分析

4．4．2 对比实验与性能测试

4．5 本章小结

5 总结与展望

5．1 本文总结

5．2 工作展望

参考文献

附录

致谢