Core Routing on Dynamic Time‐Dependent Road Networks

Route planning in large‐scale time‐dependent road networks is an important practical application of the shortest‐path problem that greatly benefits from speedup techniques. In this paper, we extend a two‐level hierarchical approach for point‐to‐point shortest‐path computations to the time‐dependent case. This method, also known as core routing in the literature for static graphs, consists of the selection of a small subnetwork where most of the computations can be carried out, thus reducing the search space. We combine this approach with bidirectional goal‐directed search to obtain an algorithm capable of finding shortest paths in a matter of milliseconds on continental‐sized networks. Moreover, we tackle the dynamic scenario where the piecewise linear functions that we use to model time‐dependent arc costs are not fixed but can have their coefficients updated requiring only a small computational effort.