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: | Lysgaard Jens |
Keywords: | heuristics |
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.