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

Abstract: 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 Dijkstra’s algorithm as its core algorithm to build index, and is therefore, results in two deficiencies. Firstly, it needs relatively expensive priority queue operations. Secondly, it would generate paths with more transfers. This paper proposes a new indexing structure, TAIL, which uses a trip based method to build index. TTL pre-computes some canonical paths. A query could be answered by matching up the canonical paths, which avoids traversing the entire network. Instead of the graph structure, TAIL uses trip array as its input, and generates paths by scanning trips. Initially, TAIL scans trips starting from the source stop, from which TAIL obtains direct reachable stops. After that, TAIL scans trips starting from the direct reachable stops, from which TAIL obtains reachable stops within one transfer. Generally, TAIL discovers 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 does 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.