随着社会经济和科学水平的不断发展,人们对出行的需求日益提高,城市汽车数量的持续增长使得交通系统出现了诸如交通拥堵、尾气污染、停车困难等问题。为了解决这些交通问题,推进智慧城市的建设,智能交通系统(Intelligent transportation system,简称ITS)应运而生。通过结合先进的信息交通技术,智能交通系统在实时交通流预测、实时动态导航、交通拥堵缓解、交通质量等改善方面取得了较好的进展。作为智能交通系统的关键技术,最优路径算法在导航系统中有着重要的应用。传统导航系统常用的最优路径算法主要有Dijkstra算法、A~*算法、蚁群算法,但传统的导航系统多是以静态的交通路网为处理对象,忽略了交通路网状态的实时变化规律,其结果并不能反映真实情况,这使得导航效果并不理想。本文通过对地理交通系统(Geographic Information System,简称GIS)和导航系统的关键技术进行分析,详细阐述了城市路网拓扑构建方法、常用的最优路径算法及其优化方法。在已有算法和优化方法的基础上,结合城市实时交通流的特征,提出了一种空间优化A~*算法,该算法对A~*算法进行了两方面的优化:一是基于路网规模控制的改进,通过划分连通子网来减小路网规模,并建立空间索引以提高路网的匹配与加载速度;二是基于路网空间特性的优化,通过限制搜索方向,减小搜索范围,从而降低算法时间复杂度。空间优化A~*算法能够大大降低时间复杂度,更好地适用于实时导航系统。最后,本文利用Eclipse及SUMO(Simulation of Urban MObility)模拟仿真平台实现了实时动态导航算法,并结合克拉玛依市真实的路网和实时的交通流数据,通过实验的方式证明改进方法是有效的。同时,本文还对基于道路拥堵、道路油耗的实时导航方式进行了初步探索。实验结果表明:基于拥堵的导航能够避开拥堵,选择交通情况更好的道路;基于油耗的导航能够考虑道路的油耗情况,选择总体油耗更低的路径,这对改善交通拥堵和低碳出行具有较大的参考意义。