当前,我国城市道路建设速度远远落后于汽车数量增长的速度,再加上交通资源配置不合理,造成了经常性的交通拥堵,导致严重的资源浪费和环境污染。智能交通系统作为一种新型运输系统,可以合理分配资源、提高道路通行能力,有效地改善交通状况。电子地图是智能交通系统的最基本元素,其基本功能包括路网显示、实时导航、路径推荐等等,因其信息丰富、交互性好等优点,极大地方便了人们的出行。但是,传统的电子地图制作方法成本高、更新慢,难以适应当前路网更新频繁的现状,因此,研究如何快速有效地更新路网信息,从而为人们提供最新的导航、路径推荐等功能,具有很强的现实意义和广阔的应用前景。GPS数据记载了移动对象的轨迹信息,如果对这些数据加以分析,就可以为路网更新提供辅助信息,节省电子地图的制作成本。此外,带有定位功能的硬件设备价格降低和智能手机的迅速普及,使得人们可以很容易收集到道路GPS数据。因此,基于GPS轨迹的时空数据挖掘技术逐渐成为了智能交通系统领域的研究热点之一。出租车作为商业性的交通工具,具有行驶时间长、轨迹范围广、车辆基数大、数据收集成本低的优点,因此,使用出租车GPS轨迹数据进行路网更新及路径选择具有非常大的优势。本文采用微软亚洲研究院(MSRA)提供的公开数据集(2007年4月到2010年10月的北京市出租车GPS数据),主要做了以下三个方面的工作:(1)GPS轨迹预处理。首先去除带有误差的数据,再利用滚动式聚类算法得到所有轨迹数据区域内主干道的道路,最后通过与Google Map对比,证明了路网的准确性;(2)提出一种基于出租车GPS轨迹的路网拓扑构建方法。它是路径导航和道路选择的前提。为了获得最新的道路及其连接关系,本文采用基于出租车GPS轨迹的路口识别方法,利用(1)中获得的道路,考虑路口处道路点数目要多的特征提取出路口,并进一步完成路网的拓扑构建,最后通过与Google Map、北京市shp地图对比,证明了路口的准确性;(3)提出了一种基于四叉堆的道路选择方法。根据(1)中的道路以及(2)中获得的拓扑关系和各条道路段长度,结合历史GPS轨迹数据,使用一个基于四叉堆优先队列的Dijkstra方法进一步实现了最短、最优路径选择的功能。