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

• 作者: 梁瑞仕 汤庸 马慧
• 来源期刊: 计算机应用研究
• 关键词: 最短路径 公交网络 路径规划 索引 时间表 换乘次数
• 年，卷（期）: 2019,（8）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 2342-2348
• 页数: 7页
• 分类号: TPT311.13
• 语种: 中文
• DOI: 10.19734/j.issn.1001-3695.2018.02.0088

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	汤庸	华南师范大学计算机学院	92	593	13.0	19.0
2	马慧	电子科技大学中山学院计算机学院	14	32	4.0	5.0
3	梁瑞仕	电子科技大学中山学院计算机学院	20	80	4.0	8.0