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 of cost of path, some non-terminal nodes are used, which called Steiner nodes. The Steiner tree problem has various usages that 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 is desired. Since these problems usually have wide scales, we should use heuristic algorithms, which find the near optimum Steiner tree in polynomial time. In this paper, a heuristic algorithm is proposed that needs O (n (m + n log n)). The algorithm 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 the previous ones.