A fast algorithm for shortest path problem for network with turn penalties and prohibitions

A fast algorithm for shortest path problem for network with turn penalties and prohibitions

0.00 Avg rating0 Votes
Article ID: iaor2000963
Country: South Korea
Volume: 23
Issue: 3
Start Page Number: 17
End Page Number: 26
Publication Date: Sep 1998
Journal: Journal of the Korean ORMS Society
Authors: , ,
Keywords: networks: path
Abstract:

Shortest path problem in road network with turn penalties and prohibitions frequently arises from various transportation optimization models. In this paper, we propose a new algorithm for the shortest path problem with turn prohibitions and delays. The proposed algorithm maintains distance labels of arcs, which is similar to labels of nodes of Dijkstra's algorithm. Fibonacci heap implementation of the proposed algorithm solves the problem in O(mn + m log m). We provide a new insight in transforming network with turn penalties and prohibitions into another network in which turn penalties and prohibitions are implicitly considered. The proposed algorithm is implemented using new data structure and compared with Ziliaskopoulos' algorithm. Computational results show that the proposed algorithm is very efficient.

Reviews

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