A two-phase shortest path algorithm for networks with node coordinates

A two-phase shortest path algorithm for networks with node coordinates

0.00 Avg rating0 Votes
Article ID: iaor19981845
Country: Netherlands
Volume: 87
Issue: 2
Start Page Number: 368
End Page Number: 374
Publication Date: Dec 1995
Journal: European Journal of Operational Research
Authors:
Keywords: heuristics
Abstract:

This paper presents a new algorithm for finding the shortest path from a source to a single sink in a network, in which the location in the plane of each node is known. The algorithm consists of two phases. In the first phase a heuristic solution to the shortest path problem is found. In the second phase the upper bound provided by the heuristic solution is utilized in a modification of a standard shortest path algorithm. Estimates based on computational tests show that on average the computation time of the presented algorithm is on the order of 40–60% of the computation time required if the information on node locations is not utilized.

Reviews

Required fields are marked *. Your email address will not be published.