BidirectionalA* search on time‐dependent road networks
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: because the exact arrival time at the destination is unknown, we start a backward search from the destination node using lower bounds on arc costs to restrict the set of nodes that have to be explored by the forward search. Our algorithm is based onA* 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 more than one order of magnitude 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. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012Keywords
This publication has 26 references indexed in Scilit:
- SHARCACM Journal of Experimental Algorithmics, 2009
- Time-Dependent SHARC-RoutingAlgorithmica, 2009
- Time-Dependent Contraction Hierarchies2009
- Engineering Route Planning Algorithms2009
- Speeding Up Dynamic Shortest-Path AlgorithmsINFORMS Journal on Computing, 2008
- Landmark-Based Routing in Dynamic Graphs2007
- Fast Routing in Road Networks with Transit NodesScience, 2007
- Adaptations of the A* algorithm for the computation of fastest paths in deterministic discrete-time dynamic networksIEEE Transactions on Intelligent Transportation Systems, 2002
- Discrete Dynamic Shortest Path Problems in Transportation Applications: Complexity and Algorithms with Optimal Run TimeTransportation Research Record: Journal of the Transportation Research Board, 1998
- The shortest route through a network with time-dependent internodal transit timesJournal of Mathematical Analysis and Applications, 1966