Transit Node routing reconsidered

Abstract. Transit Node Routing (TNR) is a fast and exact distance oracle for road networks. We show several new results for TNR. First, we give a surprisingly simple implementation fully based on Contraction Hierarchies that speeds up preprocessing by an order of magnitude approaching the time for just finding a Contraction Hierarchies (which alone has two orders of magnitude larger query time). We also develop a very effective purely graph theoretical locality filter without any compromise in query times. Finally, we show that a specialization to the online many-to-one (or one-to-many) shortest path further speeds up query time by an order of magnitude. This variant even has better query time than the fastest known previous methods which need much more space. 1 Introduction and Related Work Route planning in road networks has seen a lot of results from the algorithm engineering community in recent years. With Dijkstra’s seminal algorithm being the baseline, a number of techniques preprocess the static input graph to achieve drastic speedups. Contraction Hierarchies (CH) [1,2] is a speedup-technique that has a convenient trade-off between preprocessing effort and query efficiency. Road network with millions of node