1996 | OriginalPaper | Chapter
Guided Search for the Shortest Path on Transportation Networks
Authors : Yazid M. Sharaiha, Richard Thaiss
Published in: Meta-Heuristics
Publisher: Springer US
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
This paper addresses the well-known problem of locating a shortest path between a start and a terminal vertex on a network with non-negative arc costs. We present a new approach which guides the search of the shortest path algorithms under investigation. The ordering of vertices in the vertex list is performed by dividing the network into a set of disjoint regions, each represented by a queue. Each queue holds a set of vertices which fall within a range given by a heuristic measure of their current proximity to the end vertex. Computational results show that the guided algorithm outperforms the original algorithms for transportation networks with Euclidean arc costs. The results are analyzed against the queue size and the accuracy of the heuristic function used.