公交网络下的一种费用限制最小时态路径查询索引

• 作者: 梁瑞仕 汤庸 马慧
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 时间信息图 最小时态路径 费用限制 图索引 hub-labelling
• 年，卷（期）: 2019,（11）
• 所属期刊栏目: 计算机网络与信息安全
• 页码范围: 3469-3485
• 页数: 17页
• 分类号: TP393
• 字数: 18795字
• 语种: 中文
• DOI: 10.13328/j.cnki.jos.005623

摘要

私人交通网络下的最短路径查询主要考虑路径长度、行驶时间等因素,而公共交通网络下的路径查询需要考虑路径上相邻的边的时间顺序约束以及路径的费用.研究了公共交通网络下3种查询:给定起点、终点、时间区间和费用上限,查找在时间区间内不超过费用上限的最早到达路径、最晚出发路径和最短耗时路径.首先给出一种Dijkstra变种算法Dijk-CCMTP,在此基础上给出3类查询的查询算法.然后提出一种高效的索引结构ACCTL(approximate cost constrained time labelling).ACCTL采用Dijk-CCMTP对图中的每个顶点预先计算部分从该顶点出发的和到达该顶点的基本路径.对于任意从起点s到终点d的查询,可以采用类似数据库表连接的方式从ACCTL中连接从s出发的和到达d的路径生成近似解,避免遍历原图搜索路径.ACCTL建立索引的时间复杂度是O(| V|·△max·|E|·(log|E|+△max)),其中,|V|表示顶点数,|E|表示边数,△max表示顶点的最大度数.实验验证ACCTL索引支持的查询速度比Dijkstra的变种算法的查询速度快2～3个数量级,并分析了影响建立索引时间和空间大小的因素.

作者信息

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