路径规划是网络优化中的经典问题,路径规划广泛应用于交通运输、通信工程、计算机工程、电网工程等领域。道路网络中的路径规划问题本质上是图论中的最短路径问题。由于道路网络数据规模大,传统的最短路径算法并不能满足计算要求。为此一些最短路径加速技术相继被提出,其中又尤其以基于分层道路网的最短路径算法具有较大优势,该算法通过将道路网分成若干级别,并利用路径在不同级别道路网中的切换大幅度提升了计算效率。对于欲查询路线的起点和终点,该类算法一般首先在较高级别道路网中完成主干道路搜索,继而再在低级道路网中完成局部区域次要道路的搜索,并最终获得规划路径。随着浮动车技术的发展,交通信息的采集更加方便,通过出租车提供的位置与时间信息,可以获得车辆的行驶轨迹,依据出租车司机的对道路的频繁访问程度可以构建一个与时间相关的多层次道路网络结构,为分层道路网络导航提供便利。本文的主要工作有:(1)通过对大规模出租车历史轨迹的分析,探讨并总结了出租车载客状态下历史轨迹的时空分布规律。(2)考虑不同时间段的交通状况,本文依据浮动车司机对道路的选择和频繁访问程度,对不同时间段交通流量进行计算,再结合出租车司机的行驶路线构建相应时间段内具有拓扑连通性的多级道路网结构。(3)提出一种基于道路网络频繁访问经验等级启发式策略的路径搜索算法,基于相应时间段内的具有拓扑连通性的分层道路网络结构,完成顾及时间因素的分层道路路径规划。(4)由于载客状态下出租车行驶轨迹一般为符合出租车司机驾驶习惯的综合考虑多种因素的经验轨迹,具有优良性质,故对于给定起点和终点,本文直接将能够查询到的出租车司机的实际行驶轨迹作为导航路线提供给用户,从而使得导航路径更加符合人类心理认知和行驶习惯。