【作者】 武雪玲；

【导师】 李清泉； 李平湘；

【作者基本信息】 武汉大学 ， 地图学与地理信息系统， 2005， 硕士

【摘要】 交通是国民经济发展的重要支柱。长期以来,交通问题已成为困扰城市发展的重要问题,智能交通系统(ITS)的思想由此应运而生。交通地理信息系统(GIS—T)在ITS中占有举足轻重的作用,已成为GIS的一个重要的研究方向。车辆导航系统是一种典型的GIS-T,其中路径规划模块作为整个导航系统的核心模块之一,在嵌入式设备里运行,与PC机上操作,要求路径规划时间更短和数据存储空间足够小,这就对路径规划算法设计在时间和空间上提出了新的要求。 本文在优化道路网络数据组织的基础上,基于Microsott Visual C++6.0开发环境,采用C++标准模板库(STL),设计并实践了车辆导航系统中双向启发式A~*算法。 主要内容如下: (1) 以图论作为理论基础分析道路网络,在此基础上介绍了道路网络数据组织,最后提出用STL实现高效的数据组织。 (2) 在分层搜索的前提下,综合考虑距离和转向角计算路段权重。 (3) 在分析、比较Dijkstra算法和启发式算法的基础上,针对车辆导航路径规划的特征,设计了双向启发式A~*算法并构造启发函数。最后,给出了实验结果和分析。 (4) 实现地图视图操作,包括放大、缩小、原图恢复、漫游、颜色设置。更多还原

【Abstract】 Transportation is playing an important role in national economic progress. And problems resulted from heavy traffic are more and more serious and has been become a bottleneck related urbanization progress for a long time. Therefore, Intelligent Transportation System (ITS) comes into being. GIS-T, as a typical application of ITS, has been a significant study branch of GIS. Vehicle Navigation System (VNS) is an essential part of GIS-T. And route-planning module is an indispensable function in VNS. Route-planning algorithm, which runs in embedded devices compared with personal computer, should be improved in time consuming and memory storage.Based on Microsoft Visual C++ 6.0 Environment, using C++ standard template library, the paper designs and practices a bidirectional heuristic A* algorithm.Main contents are summarized as followings:Firstly, based on graph theory, the paper utilizes STL to implement data organization of road network effectively.Secondly, the paper computes road segment weight by considering distance and turning angle simultaneously according to high-level road priority to lower.Thirdly, Dijkstra and heuristic algorithms are explained and compared. Then according to characteristics of route planning in VNS, bidirectional heuristic A* algorithm is proposed and implemented. And practice results are given and analyzed.Finally, the paper implements map displaying and view operation of zooming in, zooming out, resuming origin map, pan and etc.更多还原