[硕士论文]ITS车辆导航系统中最优路径算法的研究.pdf

上海交通大学
硕士学位论文
ITS车辆导航系统中最优路径算法的研究
姓名:沈方方
申请学位级别:硕士
专业:模式识别与智能系统
指导教师:孙敏
20070101
上海交通大学硕士学位论文摘要
ITS 车辆导航系统中最优路径算法的研究

摘要

近年来,世界各国纷纷致力于新兴交通科技,如智能交通系统的研
究和应用,以应对目前严峻的交通环境。本文研究的车辆导航系统是智
能交通系统的一个重要课题,它通过向驾驶员提供基于实时交通信息的
最优路径来达到诱导驾驶员行为、减少车辆在道路上的停留时间,进而
实现改善城市交通和避免交通拥挤、阻塞的目的,同时还能降低尾气排
放量,达到降低环境污染的目的。最优路径规划技术是车辆导航系统中
的核心技术之一,是准确有效的导航功能得以实现的基础。
本文首先研究了实施动态路径导航系统的必要性及可能性,并基于
现实的交通特点提出了一个动态导航系统的建设性设计框架。此后着重
研究了最优路径规划的问题,此间设计了一个可行性较强的处理实时交
通数据的方法。众所周知,传统的最短路径算法通常采用图论和数学规
划方法进行寻优,计算时间长,计算量大,对于交通路网难以满足动态
实时性要求,所以本文提出了基于改良的 A*算法的最优路径规划方案,
即时间最优路径算法,能够更精确更快速地搜索到最优解。
在本文所设计的时间最优路径算法中,主要做了以下的改进:在路
段权值的确定上,以行驶时间为主要标准,给出了一个改进的动态计算
方法,即将路段区分为阻塞、空闲、繁忙三种状态,从而简化了运算模
式、提高了计算效率;将静态交通限制信息加入到了路网节点的数据结
构中,以此可以防止盲目扩展节点;优化了已搜索节点集和待搜索节点
集的数据结构,简化了重点判断的标准,从而提高了运算效率。
通过简易的仿真对比实验,可知本文的改进算法确实在效率和精确
度上有了一定程度的提高。

关键词:智能交通系统,车辆导航系统,最优路径算法, A*算法
I
上海交通大学硕士学位论文 ABSTRACT
OPTIMAL PATH ALGORITHM RESEARCH IN ITS
VEHICLE NAVIGATION SYSTEM

ABSTRACT

These years every country applies modern science and technology, such
as Intelligent Transportation System (ITS), to solve traffic problem. The
study on Vehicle Navigation Systems (VNS) is an important research in the
field of ITS, Which guides the travelers by providing them with optimal
route based on real-time traffic information. As a result the travel time
should be shorted and the traffic congestion should be avoided. Meanwhile
the environmental pollution should be alleviated. Being one of the core
technologies of VNS, Optimal Path Algorithm is the basis of a correct and
effective route guidance function.
Firstly this paper studies the necessity and the implementing possibility
of the dynamic path navigation system, then puts forward a constructive
design framework of dynamic vehicle navigation system according to the
transportation characteristics of the reality. After that the paper puts
emphasis on studying optimal path algorithm, and at the same time designs