Efficient shortest time query in public transportation networks

The public transportation networks are usually modeled as timetable graphs, where edges represent station connections associated with multiple departure and arrival times. The shortest time query returns the path with minimum travel time for a given source and destination pair on a departure time. The existing expansion-based methods are inefficient due to the extensive combinations of timetables, while the timetable labeling (TTL), which is the state-of-the-art index-based method, suffers from high computational costs for those short-distance queries because a lot of common labels have to participate in the calculation. This paper extends Hierarchical 2-hop (H2H), which constructs a tree structure through tree decomposition, to public transportation network to obtain higher query efficiency. Since edges have multiple timetables instead of single weights for the public transportation network, it will generate a large number of paths during connecting edges. To efficiently filter invalid paths, we introduce Connect and Dominate operations, and construct timetables through timetable updates and vertex elimination. Furthermore, to enhance query performance, departure times at each vertex are sorted, and an efficient query algorithm is proposed to quickly locate the relevant timetable. Extensive experiments under 11 real world datasets show that our algorithm significantly outperforms existing techniques in terms of query efficiency, achieving an improvement of over one order of magnitude in the best case. The preprocessing time is also reduced by one to two orders of magnitude. Copyright © 2025 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.