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



Abstract:In contrast to the paths queries under private transportation, which mainly concern the length or the driving time of a path, the paths queries under public transportation have to consider the time sequences between subsequent edges, as well as the total cost over a path. This study looks into three types of queries:given a source node, a destination node, a time interval, and a cost constraint, to find out a path within the given time interval which is restricted by the cost constraint, and has (i) the earliest arrival time, or (ii) the latest departure time, or (iii) the shortest duration. Firstly, a modified Dijkstra's algorithm called Dijk-CCMTP is presented based on derived algorithms respectively for the three types of queries above. After that, an effective indexing structure ACCTL (approximate cost constrained time labelling) is proposed. ACCTL invokes Dijk-CCMTP to precompute some canonical paths from (and, to) each node in the graph. For any query from source node s to destination node d, the approximate answer path can be obtain by matching those canonical paths that are from s (and, to d) in a database table join manner, so as to avoid traversing on the entire graph. The preprocessing time to build ACCTL is O(|V|·△_max·|E|·(log|E|+△_max)), where|V|is the number of nodes,|E|the number of edges, and △_max the maximal degree among the nodes in the graph. Finally, the efficiency and effectiveness of ACCTL are confirmed. Experimental results show that the query algorithm under ACCTL is 2~3 orders of magnitude faster than the Dijkstra variant methods. The index preprocessing time and index size are also analyzed.



PDF全文下载地址:

http://jos.org.cn/jos/article/pdf/5623