Parallel Time-Dependent Contraction Hierarchies

Time-Dependent Contraction Hierarchies is a routing technique that solves the shortest path problem in graphs with time-dependent edge weights, that have to satisfy the FIFO property. Although it shows great speedups over Dijkstra’s Algorithm the preprocessing is slow. We present a parallelized version of the preprocessing taking advantage of the multiple cores present in todays CPUs. Nodes in-dependent of one another are found and processed in parallel. We give experimental results for the German road network. With 4 and 8 cores a speedup of up to 3.4 and 5.3 is achieved respectively.