| 公交网络下的一种费用限制最小时态路径查询索引 |
| |
| 引用本文： | 马慧,汤庸,梁瑞仕.公交网络下的一种费用限制最小时态路径查询索引[J].软件学报,2019,30(11):3469-3485. |
| |
| 作者姓名： | 马慧 汤庸 梁瑞仕 |
| |
| 作者单位： | 电子科技大学 中山学院 计算机学院, 广东 中山 528400,华南师范大学 计算机学院, 广东 广州 510631,电子科技大学 中山学院 计算机学院, 广东 中山 528400 |
| |
| 基金项目： | 国家自然科学基金（U1811263，61772211）；广东省高等学校优秀青年教师项目（YQ2015241，YQ2015242）；中山市科技计划（2015B2307） |
| |
| 摘 要： | 私人交通网络下的最短路径查询主要考虑路径长度、行驶时间等因素，而公共交通网络下的路径查询需要考虑路径上相邻的边的时间顺序约束以及路径的费用.研究了公共交通网络下3种查询：给定起点、终点、时间区间和费用上限，查找在时间区间内不超过费用上限的最早到达路径、最晚出发路径和最短耗时路径.首先给出一种Dijkstra变种算法Dijk-CCMTP，在此基础上给出3类查询的查询算法.然后提出一种高效的索引结构ACCTL（approximate cost constrained time labelling）.ACCTL采用Dijk-CCMTP对图中的每个顶点预先计算部分从该顶点出发的和到达该顶点的基本路径.对于任意从起点s到终点d的查询，可以采用类似数据库表连接的方式从ACCTL中连接从a出发的和到达d的路径生成近似解，避免遍历原图搜索路径.ACCTL建立索引的时间复杂度是O（|V|·△max·|E|·（log|E|+△max）），其中，|V|表示顶点数，|E|表示边数，△max表示顶点的最大度数.实验验证ACCTL索引支持的查询速度比Dijkstra的变种算法的查询速度快2~3个数量级，并分析了影响建立索引时间和空间大小的因素.
|
| 关 键 词： | 时间信息图 最小时态路径 费用限制 图索引 hub-labelling |
| 收稿时间： | 2017/11/21 0:00:00 |
| 修稿时间： | 2018/4/16 0:00:00 |
Indexing Method for Approximate Cost Constrained Minimal Temporal Paths Queries in Public Transportation Networks |
| |
| MA Hui,TANG Yong and LIANG Rui-Shi.Indexing Method for Approximate Cost Constrained Minimal Temporal Paths Queries in Public Transportation Networks[J].Journal of Software,2019,30(11):3469-3485. |
| |
| Authors: | MA Hui TANG Yong and LIANG Rui-Shi |
| |
| Affiliation: | School of Computer Science, University of Electronic Science and Technology of China, Zhongshan Institute, Zhongshan 528402, China,School of Computer Science, South Normal University, Guangzhou 510631, China and School of Computer Science, University of Electronic Science and Technology of China, Zhongshan Institute, Zhongshan 528402, China |
| |
| Abstract: | |
| |
| Keywords: | time information graph minimal temporal path cost constrained graph index hub-labelling |
|
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
