Core Routing on Dynamic Time-Dependent Road Networks
Daniel Delling (dellingira.uka.de)
Abstract: Route planning in large scale time-dependent road networks is an important practical application of the shortest paths problem that greatly benefits from speedup techniques. In this paper we extend a two-levels hierarchical approach for point-to-point shortest paths computations to the time-dependent case. This method, also known as core routing in the literature for static graphs, consists in 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 in order to obtain an algorithm capable of finding shortest paths in a few 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, time-dependent networks, dynamic road networks, goal directed search
Category 1: Network Optimization
Citation: Unpublished: LIX, Ecole Polytechnique, F-91128, Palaiseau, France. November 2008.
Entry Submitted: 11/27/2008
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|