2024/10/21 by Andrii Rohovyi, Peter J. Stuckey, Rohovyi, Andrii +3
Computer Science · Decision Sciences · Engineering · #Artificial Intelligence (cs.AI) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Mobile Agent-Based Network Management #Railway Systems and Energy Efficiency #Scheduling and Timetabling Solutions
paper · pdf · doi:10.48550/arxiv.2410.15715
openalex publication_date 2024/10/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Faster pathfinding in time-dependent transport networks is an important and challenging problem in navigation systems. There are two main types of transport networks: road networks for car driving and public transport route network. The solutions that work well in road networks, such as Time-dependent Contraction Hierarchies and other graph-based approaches, do not usually apply in transport networks. In transport networks, non-graph solutions such as CSA and RAPTOR show the best results compared to graph-based techniques. In our work, we propose a method that advances graph-based approaches by using different optimization techniques from computational geometry to speed up the search process in transport networks. We apply a new pre-computation step, which we call timetable nodes (TTN). Our inspiration comes from an iterative search problem in computational geometry. We implement two versions of the TTN: one uses a Combined Search Tree (TTN-CST), and the second uses Fractional Cascading (TTN-FC). Both of these approaches decrease the asymptotic complexity of reaching new nodes from O(k× log|C|) to O(k + log(k) + log(|C|)), where k is the number of outgoing edges from a node and |C| is the size of the timetable information (total outgoing edges). Our solution suits any other time-dependent networks and can be integrated into other pathfinding algorithms. Our experiments indicate that this pre-computation significantly enhances the performance on high-density graphs. This study showcases how leveraging computational geometry can enhance pathfinding in transport networks, enabling faster pathfinding in scenarios involving large numbers of outgoing edges.