Optimization Online


Bidirectional A* Search on Time-Dependent Road Networks

Giacomo Nannicini (giacomon***at***lix.polytechnique.fr)
Daniel Delling (delling***at***ira.uka.de)
Dominik Schultes (schultes***at***ira.uka.de)
Leo Liberti (liberti***at***lix.polytechnique.fr)

Abstract: The computation of point-to-point shortest paths on time-dependent road networks has a large practical interest, but very few works propose efficient algorithms for this problem. We propose a novel approach which tackles one of the main complications of route planning in time-dependent graphs, which is the difficulty of using bidirectional search: since the exact arrival time at the destination is unknown, we start a backward search from the destination node using lower bounds on arc costs in order to restrict the set of nodes that have to be explored by the forward search. Our algorithm is based on A* with landmarks (ALT); extensive computational results show that it is very effective in practice if we are willing to accept a small approximation factor, resulting in a speed-up of several times with respect to Dijkstra’s algorithm while finding only slightly suboptimal solutions. The main idea presented here can also be generalized to other types of search algorithms.

Keywords: Shortest paths, time-dependent costs, large-scale road net- works, goal directed search

Category 1: Network Optimization

Citation: Unpublished: LIX, Ecole Polytechnique, F-91128 Palaiseau, France. May 2008.

Download: [PDF]

Entry Submitted: 11/26/2008
Entry Accepted: 11/26/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