智能车辆导航系统及带限条件下最优路径算法的研究和实现

摘要

路线优化子系统是车辆导航系统研究的核心内容，它通过接收交通信息服务子系统发布的动态交通信息，结合车辆定位子系统所确定的车辆在路网中所处的位置，向出行者提供符合最优目标的路线行驶方案，以达到安全、迅速、舒适和经济的出行目的。 论文对最优路径规划算法进行了深入地研究和描述。在分析了各种常用算法的时间复杂度和空间复杂度的基础上，采用前向关联边的邻接表存储结构和直线启发实现了对Dijkstra算法和蚁群算法的优化，理论分析和实际运行的结果表明，这些改进大大提高了算法的计算速度，有效的减小了存储空间。然后，对有必经节点序列、避开节点序列及节点权重等限制条件下的最优路径搜索问题，以西安市的典型路网为研究对象进行了测试，结果证明，带限制条件下的最优路径搜索算法能够规划出符合用户要求的最优路径。

目录

文摘

英文文摘

声明

第一章绪论

1.1智能交通系统(ITS)的发展概况

1.1.1国外的发展概况

1.1.2我国智能交通的发展状况

1.2智能交通系统的研究内容

1.3现代车辆导航系统

1.4现有的车辆导航软件产品

1.5论文主要研究内容及章节安排

第二章 智能车辆导航系统的关键技术

2.1智能车辆导航系统的组成

2.2 GPS概述

2.2.1 GPS的组成

2.2.2 GPS定位基本原理

2.2.3 GPS定位的主要误差

2.2.4 GPS导航系统的特点

2.2.5 GPS在车辆导航领域的主要应用

2.3数字道路电子地图

2.3.1路网的表示方法

2.3.2 MapInfo与导航电子地图

2.4智能车辆导航系统

2.4.1硬件系统

2.4.2软件系统

2.4.3智能车辆导航系统开发流程

2.5本章小结

第三章 路线规划算法的研究与实现

3.1路径规划的最优目标

3.1.1路阻函数的定义

3.1.2常用的路线规划优化目标

3.1.3最优目标的确定

3.2经典最短路径算法介绍

3.2.1 Dijkstra算法

3.2.2 Floyd算法

3.3 最短路径算法的优化

3.3.1车辆导航路径优化算法的特点

3.3.2前向关联边存储结构

3.3.3直线优化Dijkstra算法

3.3.4启发式蚁群算法

3.4带限制条件下最优路径搜索算法

3.4.1必经节点序列最优路径实现

3.4.2避开节点序列最优路径的实现

3.4.3结点权重条件下最优路径实现

3.4.4考虑交叉口延误条件下的时间最短路径实现

3.4.5综合路径规划

3.5本章小结

第四章总结与展望

致 谢

参考文献

研究成果