Timetable-based Routing in Fixed Schedule Dynamic Networks

A fixed schedule dynamic network has a set of nodes (eg. vehicles or satellites) that move using a known schedule and trajectory, so that the connections between nodes in the network appear and disappear in a predictable manner. We study the problem of finding a foremost journey in such a network: given a query time, source and destination node, we find a temporal path that arrives at the earliest time at the destination. We give a new approach to the problem that uses a timetable sorted in order of the start time of connections, and describe three algorithms using this approach. We prove their correctness and give tight bounds on their worst-case time complexities. We also show extensive experimental results that show that our new algorithms outperform the previous best algorithm given in [1].