求解最短路径是车辆监控导航系统的主要功能之一,随着全球导航定位技术的广泛应用,人们对求解最短路径问题的要求也日趋迫切。国内外大量专家学者对最短路径问题进行过深入研究,提出了多种解决最短路径问题的算法。采用哪种最短路径算法以及怎样优化算法以提高算法运行效率是本文的研究重点之一。车辆监控导航系统中,最短路径的有效实现离不开实时的交通信息系统。道路交通网中,路况信息是随时间动态变化的,寻求从源点到终点的最短路径有很高的时限要求。因此,必须建立实时的交通信息系统,为求解最短路径提供实时、准确的路况信息,使算法求得的最短路径能够真正符合实际的交通状况,以提高路径分析的实时性和实用性,此为本文的另一研究重点,也是研究车辆监控导航系统中最短路径的最终目的所在。本文的创新点:1设计了一种基于Dijkstra算法的最优路径搜索方法,该方法提出了新的区域限定模型,并在此限定区域内实现存储结构的优化和含有启发式信息的搜索策略;2提出了更加符合交通路网的权值确定方法。论文首先概述了车辆监控导航系统的组成和原理,对涉及到的关键技术进行了阐述。详细分析和讨论了最短路径搜索策略和常见的最短路径算法。在深入研究Dijkstra算法的基础上,针对该算法在应用中存在的不足,综合区域限定、存储结构、启发式搜索策略这三方面进行优化,设计了一种基于Dijkstra算法的最优路径搜索方法。其中,区域限定是前提,通过限定区域可以直接减少不必要的结点参与运算;在限定区域的基础上对存储结构进行优化可以有效地减少存储空间;大量实验表明,应用启发式搜索策略在搜索的路径结点总数和计算时间方面有明显减少。在实际的交通路网中,各种交通信息对路径搜索有很大影响,要得到最优的出行路线必须综合考虑影响出行效率的众多因素,本文在讨论已有路网权值确定方法的基础上,设计了更加符合实际的权值确定方法。最后阐述了实时交通信息系统的系统结构,分析了实时信息的采集、处理与发布方案。