导航系统对于解决城市交通拥堵,缓解交通压力具有重要意义,而结合路况的路径通行时间估计是导航中的基础和关键。随着车辆轨迹数据的大量积累,使得估计动态路网中路径的通行时间变为可能,即针对给定的起点和终点,对不同路径的通行时间进行预测,从而找出通行时间最短的路径。然而通行时间最短的路径并不一定是累积概率分布最大的路径。当用户需要在指定时刻前抵达的时候,获得累积概率分布最大的路径就能发挥很大的作用。为了找出动态路网中累积分布最大的路径,就需要对路径通行时间的概率进行估计,而非仅得到一个单一值的估计结果。在现有的研究方案中,研究人员将整个道路网划分为以路段为基本单位的网络结构,基于路段对路径的通行时间进行估计,然而这种依赖于路段组合的方式忽略了完整路径通行中十字路口的拐弯时间和红绿灯的等候时间等,导致路径较长时估计结果更不准确。与基于路段的研究方案不同,为了提高估计的准确度和效率,本文提出基于子路径的路径通行时间估计方案。为了提高估计的效率,本文利用历史轨迹数据建立后缀索引树的存储结构,将实时获取的轨迹通行时间存储在后缀索引树的节点上,对于数据稀疏的子路径,由历史数据提供通行时间的结果,通过这种存储结构可以快速地获取查询路径的子路径序列,及其相应的轨迹通行时间。为了提高估计的准确性,本文对子路径序列采用线性插值算法和基于时空相关性的预测算法对其通行时间的概率估计进行验证,并采用2016年及2017年1月哈尔滨市出租车的轨迹数据集验证了算法的准确性和效率。