计算机应用研究

作者：马慧,汤庸,梁瑞仕,

单位：1.电子科技大学中山学院计算机学院,广东中山528400；2.华南师范大学计算机学院,广州510631；

关键词：最短路径,公交网络,路径规划,索引,时间表,换乘次数,

基金：国家自然科学基金资助项目(61772211)；广东省高等学校优秀青年教师项目(YQ2015241,YQ2015242)；广东省青年创新人才类项目(2015KQNCX206)；中山市科技计划项目(2015B2307,2016B2158)；；

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

来源：2019年第8期

《计算机应用研究》期刊编辑部

查看计算机应用研究杂志2019年第8期