For a wide range of transportation network path search problems, the A* heuristic significantly reduces both search effort and running time when compared to basic label-setting algorithms. The motivation for this research was to determine if additional savings could be attained by further experimenting with refinements to the A* approach. We propose a best neighbor heuristic improvement to the A* algorithm that yields additional benefits by significantly reducing the search effort on sparse networks. The level of reduction in running time improves as the average outdegree of the network decreases and the number of paths sought increases.
Best Neighbor Heuristic Search for Finding Minimum Paths in Transportation Networks
Transportation Research Record: Journal of the Transportation Research Board
Transportation Research Record: Journal of the Transportation Research Board ; 1651 , 1 ; 48-52
1998-01-01
Article (Journal)
Electronic Resource
English
Best Neighbor Heuristic Search for Finding Minimum Paths in Transportation Networks
Online Contents | 1998
|Heuristic Search for the Best Paths in an Intermodal Transportation System
British Library Conference Proceedings | 1997
|Finding the best multimodal paths in urban transportation networks
British Library Conference Proceedings | 1997
|Heuristic search for the best paths in an intermodal tranportation system
Tema Archive | 1997
|Identifying Multiple and Reasonable Paths in Transportation Networks: A Heuristic Approach
Online Contents | 1997
|