公交网络路径规划问题中的一种高效索引方法

Efficient index for route planning in public transportation network

TTL是在公交网络中求解最早到达路径、最晚出发路径和最短耗时路径的一种高效索引。TTL采用Time-dependent为核心算法构建索引,存在两个不足:a)大量的昂贵的出堆操作拖慢了建立索引的效率;b)所求得的路径具有较多的换乘次数。针对这两个不足,提出了一种基于旅程的索引TAIL。TAIL预先生成部分路径,在查询阶段通过匹配部分路径得到最优解,避免在原图上进行查询,提高效率。TAIL并不是基于图结构,而是以旅程为单位存储公交数据。在生成路径时,首先扫描路过起点的旅程,找到从起点直达的站点;然后扫描从直达站点出发的旅程,找到一次换乘可达的站点;如是这般,从可达站点出发扫描旅程,发现更多的可达站点。为了在早期找到最早到达路径,从而减少旅程的扫描量,TAIL并没有严格按照换乘次数的顺序扩展站点。这种方法避免了昂贵的堆操作,也保留了旅程的完整性。在真实数据集上测试表明,与TTL相比,TAIL有较短的建立索引的时间,生成的路径的换乘次数也较少。

TTL is a highly efficient indexing structure for finding an earliest arrival path, or a latest departure path, or a shortest duration path in public transportation networks. TTL uses Time-dependent algorithm as its core algorithm to build index, and is therefore, results in two deficiencies. Firstly, it needed relatively expensive priority queue operations. Secondly, it would generate paths with more transfers. This paper proposed a new indexing structure, TAIL, which used a trip-based method to build index. TTL pre-computed some canonical paths. A query could be answered by matching up the canonical paths, which avoided traversing the entire network. Instead of the graph structure, TAIL used trip array as its input, and generated paths by scanning trips. Initially, TAIL scanned trips starting from the source stop, from which TAIL obtained direct reachable stops. After that, TAIL scanned trips starting from the direct reachable stops, from which TAIL obtained reachable stops within one transfer. Generally, TAIL discovered new reachable stops from scanning the trips starting at the already discovered reachable stops. In order to obtain the earliest arrival paths in the early stage, so as to reduce the number of trip scanning, TAIL did not scan the stops strictly in increasing order of their transfer times. In this way, TAIL avoids valuable priority queue operations, while preserves the entity of a trip. Experiments on real datasets shows that, compared to TTL, TAIL has lower index construction time and its generated path has fewer transfer times.