论文部分内容阅读
日益增长的汽车购买量,使得城市交通环境日渐严峻。智能的导航系统无论在方便出行,还是提高道路运输效率上,都起到了十分重要的作用。路径规划作为导航系统的核心部分,根据存储在其内部的电子地图拓扑信息,在出发地和目的地确定的情况下,按照合理的策略快速准确地向出行者提供行驶方案,以达到迅速、安全、经济的出行目的。因此,导航中路径规划的优化算法研究显得尤其重要。 电子地图是导航进行路径规划的基础。本文在Visual C++6.0平台下,结合MapInfo MapX组件生成用于导航的电子地图,并实现了地图的基本功能,如放大、缩小、漫游、居中等。 路网的拓扑构建是路径规划的前提和关键。在详细分析MapInfo地图数据的内部结构,以及路网表达及存储的特点和所须满足的条件后,确定使用图的结构抽象表达路网。根据本文定义的拓扑数据信息的数据结构和文件结构,研究并实现了动态及静态两种路网拓扑构建的方法。动态拓扑构建的范围根据用户指定的起点与终点确定,拓扑构建结果存储在内存的节点表及路段表中,当路径规划完毕时,会自动删除。静态拓扑构建在动态拓扑构建的基础上提出,解决了动态拓扑在大范围内构建时间过长的问题。静态拓扑构建在用户离线使用选择工具选取的任意范围内进行拓扑构建,并能够拼接各个静态拓扑分块,静态拓扑完成后存储静态拓扑文件,在加载地图的同时自动由拓扑文件读入已有的拓扑信息,省去了路径规划在拓扑构建部分的耗时,缩短了路径规划的总时间,提高了实时性。构建所得的拓扑信息可用于一般意义下的路径规划程序,具有一定的通用性。 为了高效实现路径规划,本文从图论切入,详细介绍了经典的Dijkstra算法及Floyd算法,并给出了具体实现步骤。分析二者的优缺点后,选择简单易实现的Dijkstra算法从搜索区域及搜索方向两个方面进行优化,研究并实现了限制搜索区域和双向搜索的最优路径规划算法。最后在拓扑构建的电子地图中实现了路径规划的功能,验证了改进Dijkstra算法的正确性及有效性,并将优化后的Dijkstra算法与原经典Dijkstra及Floyd算法进行分析比较,结果表明本文改进的Dijkstra算法搜索路径的平均时间小于原经典Dijkstra及Floyd算法所需时间,由此可见,优化后的Dijkstra算法提高了路径规划的效率。