随着全球定位系统,地理信息系统,电子技术,计算机技术的快速发展,车载导航系统正成为综合技术应用的热门领域之一,它可以最大限度地防止交通阻塞的发生,减少车辆在道路上的逗留时间,并最终实现交通流量在网络中各路段上的最优分配,使道路网络得到最合理、最有效地利用。路径规划作为车载导航系统的核心部分,要求能够按照存储在其内部的电子地图的拓扑信息,帮助车辆驾驶人员在车辆出发地和目的地确定的情况下按照某种策略快速准确地规划出一条最优路径。因此,车载导航系统中路径规划算法的设计与研究显得尤为重要。如何实现高效的路径规划是本文研究的重点内容。本文根据最优路径规划的需求,介绍了经典的基于Dijkstra算法的路径规划方案,并给出了具体的实现步骤。然而由于该算法耗时长,占用空间大的缺点,不适合导航系统的要求。因此重点对在规划最优路径的效率上有很大提高的启发式搜索算法——A~*算法进行了研究。在对A~*算法的深入理解之上重点探讨了估价函数的选取策略,提出了四种估价函数的构造方法,并采取二叉堆节点排序策略对A~*算法进行优化,以提高算法的执行效率,改善搜索速度。考虑到实际的交通状况,本文对交通管制,交叉口延误,终点和起点问题进行了研究并提出解决的方法。考虑到驾驶者的实际需求,论文对如何实现距离最短、时间最优、费用最少等不同的路径规划标准也进行了相关的讨论。最后利用MapInfo公司的MapX5.0控件,以通用软件开发工具VB6.0为开发平台进行集成开发。通过加载MapInfo格式的数字地图,实现最优路径规划的功能,验证了改进A~*算法的有效性和合理性,并将优化后的A~*算法与Dijkstra算法及原A~*算法的性能进行了分析比较,结果表明引入二叉堆排序策略后,改进A~*算法搜索路径所需要的平均时间要小于Dijkstra算法以及原A~*算法所需时间,因此得出优化后的A~*算法在规划路径的效率上有很大提高的结论。