A Heuristic Algorithm for Solving Steiner Tree Problem on Urban Traffic Network

The Steiner tree problem connects a subset of given nodes called terminals that this connection is absolutely a tree and it has the minimum cost. In this tree due to the reduction ofcost of path, some non-terminal nodes are used, which called Steiner nodes. The Steiner tree problem has various usagesthat one of them is routing in the urban traffic networks. In such networks with a large amount of nodes and edges, finding the optimum path which connects small amounts of terminals isdesired. Since these problems usually have wide scales, we should use heuristic algorithms, which find the near optimumSteiner tree in polynomial time. In this paper, a heuristic algorithm is proposed that needs O ( ( + log )). Thealgorithm finds the near optimum answer of Steiner tree on the given graph. The results of investigations show that this algorithm finds more accurate answers in comparison to theprevious ones

کلیدواژه ها:

Steiner tree ، Heuristic Algorithm ، Undirected weighted graph