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

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

来源：软件学报, 2019, (11): 3469-3485.

DOI：10.13328/j.cnki.jos.005623

• 时间信息图
• 最小时态路径
• 费用限制
• 图索引
• hub-labelling time information graph
• minimal temporal path
• cost constrained
• graph index
• hub-labelling

私人交通网络下的最短路径查询主要考虑路径长度、行驶时间等因素,而公共交通网络下的路径查询需要考虑路径上相邻的边的时间顺序约束以及路径的费用.研究了公共交通网络下3种查询:给定起点、终点、时间区间和费用上限,查找在时间区间内不超过费用上限的最早到达路径、最晚出发路径和最短耗时路径.首先给出一种Dijkstra变种算法Dijk-CCMTP,在此基础上给出3类查询的查询算法.然后提出一种高效的索引结构ACCTL(approximate cost constrained time labelling).ACCTL采用Dijk-CCMTP对图中的每个顶点预先计算部分从该顶点出发的和到达该顶点的基本路径....

• 单位
  华南师范大学; 电子科技大学