得了丰硕的成果。目前车载导航系统主要沿着个性化的路线导航、动态导航系统、高精度、低成本、可扩展性好、智能化、小型化、多功能化等几个方面进行发展[7-8]。路径规划作为车载导航系统的核心技术之一, 它根据电子地图的拓扑信息,实时、可靠、准确为驾驶人员选定一条出发地和目的地之间的最优行车路径。路径规划中可采用的优化标准很多,如行车距离最短, 行车时间最少,费用最低等。但是无论采用何种优化标准,路径规划最终都将归结为在某一特定的道路网中寻找具有最小代价的最短路径问题。因此最优路径至少需要满足三个条件,即可靠、适用、快速。可靠是指最优路径是准确的、连通的、可行驶的,不出现断点,它需要依据道路的交通信息以及优化标准进行路径规划,即使在重要的节点(如立交桥、高速路进和十字路口等)也能够非常准确的引导用户。快速是指不仅要求系统运算花费的时间要少,并且还要能满足动态需求。当车辆在行驶过程中,若用户偏离了原来规划好的路径,需要重新进行路径规划时,其路径规划的计算速度要尽量短,能够及时的满足用户的需要。适用是指在满足用户需求(如行车时间最短、距离最短、增加途径点或避让点、避免高速公路等)的前提下所规划出的路径时所有路径中最优的,其算法的实时性和最优性是衡量导航系统优劣的重要指标之一。最短路径算法是一种基于图论的搜索算法,即规划出一条基于起点和终点之间且总代价最小的路径。随着经典图论、计算机数据结构和算法的有效结合促进了新的最短路径算法的不断涌现[9]。最短路径算法因问题特征、网络特性的纷繁复杂而表现出多样性。根据出发地和目的地之间的路段数目以及特征,文献[10] 将最短路径问题分为五种类型,即单点对单点的最优路径、多点对多点的最优路径、K-最短路径、经过特殊节点的最短路径和实时最短路径问题。基本类型的最短路径问题又可以衍生出其他特殊类型的最短路径问题。最短路径的划分如图 1-2所示: 万方数据
全文预览
