公交网络路径规划问题中的一种高效索引方法

分类： 计算机科学 >> 计算机科学的集成理论 提交时间： 2018-04-24 合作期刊: 《计算机应用研究》

马慧 汤庸 梁瑞仕

摘要： TTL是在公交网络中求解最早到达路径、最晚出发路径和最短耗时路径的一种高效索引。TTL采用Time-dependent Dijkstra为核心算法构建索引，存在两个不足：大量的昂贵的出堆操作拖慢了建立索引的效率以及所求得的路径具有较多的换乘次数。针对这两个不足，提出了一种基于旅程的索引TAIL。TAIL预先生成部分路径，在查询阶段通过匹配部分路径得到最优解，避免在原图上做查询，提高效率。TAIL并不是基于图结构，而是以旅程为单位存储公交数据。在生成路径时，首先扫描路过起点的旅程，找到从起点直达的站点；然后扫描从直达站点出发的旅程，找到一次换乘可达的站点；如是这般，从可达站点出发扫描旅程，发现更多的可达站点。为了在早期找到最早到达路径，从而减少旅程的扫描量，TAIL并没有严格按照换乘次数的顺序扩展站点。这种方法避免了昂贵的堆操作，也保留了旅程的完整性。在真实数据集上测试表明，与TTL相比，TAIL有较短的建立索引的时间，生成的路径的换乘次数也较少。

 点击量 1638  下载量 881  评论