Optimization Online


Core Routing on Dynamic Time-Dependent Road Networks

Daniel Delling (delling***at***ira.uka.de)
Giacomo Nannicini (giacomon***at***lix.polytechnique.fr)

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.

Download: [PDF]

Entry Submitted: 11/27/2008
Entry Accepted: 12/01/2008
Entry Last Modified: 10/28/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society