1、 1 引言引言 1.1 课题研究背景及意义 1.2 主要研究内容及关键问题 2 路径规划概述路径规划概述 路径规划是智能交通系统研究的重要内容， 同时也是车辆定位与导航系统的重要组成 部分，智能交通系统是包含若干子系统的复杂系统，其每个子系统都具有不同的功能，车辆 定位与导航系统是智能交通系统的一个主要的应用子系统而路径规划是车辆定位与导航系 统的重要组成部分。所以可以用下图来描述三者之间的关系。 2.1 路径规划的概念 路径规划是车辆定位系统与导航系统的重要组成部分，是它必不可少的核心功能之一。 车辆定位与导航系统中的路径规划是在车辆行驶前或行驶过程中为司机提供从起始点到目 标点的一条或若干
2、条路线， 来对司机的行车进行导航。 路径规划可分为单车辆路径规划和多 车辆路径规划， 单车辆路径规划是在一个特定的道路网上根据一个车辆的当前位置和目标给 出单个路径规划， 属于用户优化问题； 多车辆路径规划是在一个特定的道路网上为所有的车 辆规划各自的目标路径，属于系统优化问题。 在计算机科学中， 通常把求解两点之间一条路径的问题和多源最短路径问题， 这些算法 可视为单车辆路径规划的问题， 多车辆路径规划比单车辆路径规划更复杂， 单用于解决单车 辆路径规划问题的背景知识将有利于研究多车辆路径规划的情形。 2.2 路径规划问题的效率 针对一个特定的应用， 在进行路径规划是可以采用多种标准来优化路
3、线， 这取决于系 统的设计和用户的意愿。 一条路径的好坏取决于许多因素， 有些司机可能选择行驶距离最短 的路径， 而有些司机宁愿行驶距离长些但必须行车条件好一些。 这些路径选择标准可由设计 决定，也可由司机通过一个用户界面来选定。在选择最好路径时，必须具备一个数字地图， 来挑选使属性值如时间和距离最小的路径。 计算机中存储的具有拓补结构的车市路网由节点、 边及相应的拓补关系构成。 其中节点 是道路的交叉点、端点，边是两节点间的一段道路，用于表示分段道路，边的权值可以定义 为道路的距离或距离与其它信息的综合信息，此时可以将数字道路地图转化为带权有向图， 因此无论采用何种标准， 求解路网中两点之间
4、的路径问题就可以归结为带权有向图的路径问 题。 在图论中有许多比较成熟的最短路径算法可供采用， 但在车辆定位与导航系统中， 这些 算法通常不能直接使用，原因有两个：一、对于实时车辆导航系统，路径规划必须在一定的 时间内完成，这就要求路径规划算法具有较高的运算效率；二、对于车辆导航系统，负责路 径规划的导航计算机系统受车载环境和成本制约， 处理能力和存储资粮十分有限， 而在实际 应用中的数字道路数据库往往规模庞大。 因此在车辆定位与导航系统中路径规划的研究目的 和任务是改进图论中的算法或者构造新的算法， 实现在尽可能短的时间内找到一条理想的路 径。只考虑了路径规划的时效性，可能导致规划后的路径不是最优路径，但却是比较理想的 智能 交通 系统 车辆定位与导航系统 路径规划 次优路径，能够被人们所接受，此时达到了时效性和最优性的平衡。这也是车辆定位与导航 系统所要求的。 2.3 路径规划的研究现状 目前，国内外对路径规划方法的研究主要有两大类，传统方法与智能方法。传统方法主 要包括：梯度法、栅格法、枚举法、可视图法、人工势场法、自由空间法、A*算法、随机 搜索法等。其中人工势场法、梯度法易陷
