Back to Search
Start Over
Core Routing on Dynamic Time-Dependent Road Networks.
- Source :
-
INFORMS Journal on Computing . Spring2012, Vol. 24 Issue 2, p187-201. 15p. 4 Charts, 1 Graph. - Publication Year :
- 2012
-
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. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 10919856
- Volume :
- 24
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- INFORMS Journal on Computing
- Publication Type :
- Academic Journal
- Accession number :
- 84938202
- Full Text :
- https://doi.org/10.1287/ijoc.1110.0448