详情

原文传递城市交通路径诱导算法研究

论文题名：	城市交通路径诱导算法研究
关键词：	城市交通;路径诱导系统;最短路径;地理信息系统
摘要：	路径诱导系统的重要功能是为行驶在道路网中的车辆提供从当前所处位置到目的地的有效的、高性价比的行车路线，即对交通网络进行路径规划，为行驶车辆提供最佳路径搜索服务。而实现路径诱导系统，关键就是解决最短路径搜索问题。本论文概述了动态路径诱导系统的研究进展，GIS与GPS应用于动态诱导系统的原理，并对求解最短路径的几种算法进行了深入的探讨和研究。最短路径搜索是图论的经典问题。本论文分析了经典Dijkstra算法、Floyd算法和启发式搜索算法、K—最短路径算法及神经网络算法、遗传算法，对它们的时间复杂度进行了简单的比较，并针对这些算法的表达方式、存储结构等方面讨论了这些算法用于城市道路网的路径诱导存在的缺陷。关于最短路径问题，目前公认的最好的求解算法是Dijkstra算法，通过经典Dijksrta算法原理，可以发现采用该算法，从一点到其他任意点都可以找到一条最短最优路径，而且不会形成回路。这样的算法在弧权值能够完全表现行驶代价的基础上可以准确无误的找出从起点到终点的理论最佳路径。但在电子地图中，网络模型的规模常常较大，节点数多达上千或上万，并且在动态路径诱导系统中对路径的查询也要求实时性。在这种情况下，经典Dijkstra算法具有算法计算量较大，时间花费较多，效率低等不足。其主要缺点可以概括为两点：存储结构和搜索区域。因此本论文针对这两点提出了改进。为了验证改进后的Dijkstra算法用于路径诱导的有效性，本论文通过对地图拓扑结构进行处理，减少了节点和路径的数目；针对具体的起点和终点，设定了合理的矩形限制搜索区域，以减少最短路径算法的搜索范围；采用Visual Basic6.0+mapobject集成开发方式，结合数字化电子地图，设计了一个动态路径诱导仿真系统，并在该系统中实现了最优路径算法。
作者：	安惜平
专业：	计算机应用技术
导师：	王亚芳
授予学位：	硕士
授予学位单位：	河北科技大学
学位年度：	2008
正文语种：	中文