基于重叠社团划分的道路网络路由搜索算法的研究

摘要

随着复杂网络的研究受到越来越多的关注，网络中的许多特性被不断的发现并应用到不同的领域，尤其是社团结构越来越发挥着重要的作用。本文基于复杂网络中社团发现的理论，将重叠社团应用到路由策略中，结合城市道路网络数据进行研究，进一步发现社团对城市道路网络中路由策略的重要意义。
　　实际的道路网络中可能存在部分重叠，但是现今的很多社团划分算法都没有将社团重叠的因素考虑进去，尤其是在做分层路由算法中。网络分层的路由算法可以有效的减少网络中不必要节点的访问，降低算法的时间复杂度，在能接受的范围内得到最优解。但是，在大规模道路网络中，道路可能会存在重叠的社团，直接影响到路由算法的时间复杂度，更加会影响我们最后需要得到的最优结果。因此，在分层的路由算法中引入重叠社团的思想，找出可能存在的道路重叠节点，能够提高整体路由策略的可靠性。
　　本文研究了基于重叠社团划分的道路网络路由搜索算法。该算法结合美国多个城市道路网络数据，对道路网络进行社团划分，找出重叠社团，降低算法的复杂度；在做路由选择时，保存网络模型最上层网络节点中有效的节点，即社团边缘节点之间的信息，再应用传统的启发式搜索算法，进行有效的路由选择。本文提出的算法可以比传统搜索算法更快的查找最短路径，在路由选择中具有更加重要的意义。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1.1 研究的背景及意义

1.2 复杂网络的基本模型

1.3 基于重叠社团划分的道路网络路由搜索算法的研究现状

1.4 本文的研究方法、创新点和研究内容

第2章 社团划分及路由搜索策略相关概念及研究进展

2.1 引言

2.2 社团的基本的划分算法

2.3 重叠社团结构检测

2.4 路由搜索策略

2.5 本章小结

第3章 基于重叠社团划分的道路网络路由搜索策略的研究

3.1 引言

3.2 道路网络数据的获取与处理

3.3 基于重叠社团划分的道路网络路由搜索算法

3.4 仿真研究

3.5 本章小结

第4章 道路网络重叠节点的编码压缩在路由搜索上的应用

4.1 引言

4.2 基于UB树的稀疏矩阵压缩

4.3 仿真研究

4.4 本章小结

第5章 结论与展望

5.1 结论

5.2 展望

参考文献

致谢

攻读学位期间参加的科研项目和成果