马慧,汤庸,梁瑞仕.公交网络下的一种费用限制最小时态路径查询索引.软件学报,2019,30(11):3469−3485.

http://www.jos.org.cn/jos/ch/reader/create_pdf.aspx?file_no=5623&journal_id=jos

摘 要: 私人交通网络下的最短路径查询主要考虑路径长度、行驶时间等因素,而公共交通网络下的路径查询需 要考虑路径上相邻的边的时间顺序约束以及路径的费用.研究了公共交通网络下 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 个数量级,并分析了影响建立索引时间和空间大小的因素.