Abstract
Faster pathfinding in time-dependent transport networks is an important andchallenging problem in navigation systems. There are two main types oftransport networks: road networks for car driving and public transport routenetwork. The solutions that work well in road networks, such as Time-dependentContraction Hierarchies and other graph-based approaches, do not usually applyin transport networks. In transport networks, non-graph solutions such as CSAand RAPTOR show the best results compared to graph-based techniques. In ourwork, we propose a method that advances graph-based approaches by usingdifferent optimization techniques from computational geometry to speed up thesearch process in transport networks. We apply a new pre-computation step,which we call timetable nodes (TTN). Our inspiration comes from an iterativesearch problem in computational geometry. We implement two versions of the TTN:one uses a Combined Search Tree (TTN-CST), and the second uses FractionalCascading (TTN-FC). Both of these approaches decrease the asymptotic complexityof reaching new nodes from $O(k\times \log|C|)$ to $O(k + \log(k) +\log(|C|))$, where $k$ is the number of outgoing edges from a node and $|C|$ isthe size of the timetable information (total outgoing edges). Our solutionsuits any other time-dependent networks and can be integrated into otherpathfinding algorithms. Our experiments indicate that this pre-computationsignificantly enhances the performance on high-density graphs. This studyshowcases how leveraging computational geometry can enhance pathfinding intransport networks, enabling faster pathfinding in scenarios involving largenumbers of outgoing edges.