Core Routing on Dynamic Time-Dependent Road Networks

INFORMS Journal on Computing · 2012 · Volume 24 · Issue 2

Abstract

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.

Keywords

shortest paths, route planning, time-dependent networks, dynamic road networks

Enable JavaScript for citation tools and additional paper interactions.