原文传递
典型城市路网最短路径算法研究及实现
| 论文题名： | 典型城市路网最短路径算法研究及实现 |
| 关键词： | 典型城市路网;最短路径;Dijkstra算法;限制搜索区域;二树算法 |
| 摘要： | 随着现代生活节奏的加快和汽车数量的陡增，交通问题日趋凸显，为此，世界各国纷纷开展智能交通系统研究。作为智能交通系统的重要子系统，城市交通诱导系统历来是业界专家学者研究的热点和难点，也是解决现存交通问题最行之有效的方式之一。 路径诱导的核心问题是图论中的最短路径算法研究。因为对于稀疏网络，用堆可以使Dijkstra算法时间复杂度降至NlogN（N表示网络中节点个数），Dijkstra算法被广泛用于解决城市路网的单源最短路径问题。 但是，Dijkstra算法在解决两站点间的最短路径问题时，特别对于大规模的城市道路网络，Dijkstra算法仍有很大冗余度，最短路径查询难以满足人们对最短路径查询实时性和可靠性的要求。限制搜索区域的最短路径算法的研究成为改进城市路网中最短路径算法，减少路径查询时间最为直接有效方法。 本文的研究内容是典型城市路网中的椭圆限制搜索区域的改进最短路径算法的理论研究及实验验证，研究目的是保证查询结果可靠的情况下，最大程度降低最短路径查询时间，研究方法是充分研究和利用城市路网的特征参数，降低最短路径算法冗余度和复杂度，算法性能指标采用软件仿真预测和实测数据统计双重评估标准。 研究内容主要包括以下几个方面: (1)城市路网中典型特性研究及特征参数提取。具体包括路段长度取值规律研究、路段站点比取值规律研究、最短路径比规律研究等。 (2)多尺度椭圆最短路径算法研究及性能分析。具体包括不同尺度椭圆分割点取值研究，多尺度算法搜索区域面积研究和最短路径查询时间研究等。 (3)二树椭圆最短路径算法研究及其性能分析。具体包括二树椭圆算法终止条件研究，二树算法搜索区域面积研究和最短路径查询时间研究等。 仿真推测和实验结果表明:与椭圆算法相比，当起始站点和目的站点相距较远时，多尺度算法可以有效降低18％的最短路径查询时间，而且多尺度算法查的最短路径是绝对可靠的;与单源算法相比，二树算法可以有效降低约40％最短路径查询时间，而且随着起始站点和目的站点间欧式距离的增大，算法有效性改进幅度越大，所以二树算法特别适用于大规模城市道路网络中最短路径寻优。 |
| 作者： | 王世明 |
| 专业： | 通信与信息系统 |
| 导师： | 邢建平 |
| 授予学位： | 硕士 |
| 授予学位单位： | 山东大学 |
| 学位年度： | 2012 |
| 正文语种： | 中文 |
检索历史
应用推荐
