1471
18
0
2019-11-14 13:13:54
2019-11-14
马慧,汤庸,梁瑞仕.公交网络下的一种费用限制最小时态路径查询索引.软件学报,2019,30(11):3469−3485.
摘 要: 私人交通网络下的最短路径查询主要考虑路径长度、行驶时间等因素,而公共交通网络下的路径查询需 要考虑路径上相邻的边的时间顺序约束以及路径的费用.研究了公共交通网络下 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 个数量级,并分析了影响建立索引时间和空间大小的因素.
