Research On Urban Traffic Routing Based On Improved A* Algorithm

With the advent of the internet age and the increasing enlargement of urban scale, people usually locate their travel routes through network terminal devices before setting out on their journey. At present, while there are a variety of travel route query systems, the functions of these query systems still need to be improved, of which the path search algorithm for travel routes needs further optimization.A star search algorithm is one of the most-widely-used urban travel route search algorithms currently. It is a heuristic search algorithm and the evaluation function it employed is: F(n) = G(n) + H(n), where G(n) represents the actual value of the distance from the starting node to the current node, and H(n) represents an estimated value of the distance from the previous node to the target node. The figure that G(n) and H(n) add up to is the Value of valuation function. The node with the lowest Value is selected as the next node, and the optimal path is hence generated by such cycle run of valuation function.Based on its practical application, this paper makes two improvements of standard A algorithm as follows:Use the technology of the smallest binary heap to optimize 0PEN vertextable lookup speed and improve routing efficiency.As for valuation function of A star algorithm, the author of this papermakes the following improvements:1. Selection of the appropriate heuristic function.2. An increase in the proportion of the heuristic function of the valuationfunction.3. By the use of gravity vector inner product value, an increase in theproportion of the heuristic function of the valuation function is reachedfor.4. Further optimization of valuation function by inner product value filter.There by the number of vertices map traversal is reduced, and the routing efficiency is dramatically increased while the routing efficiency is dramatically improved.Based on the development platform of Visual Studio 10.0, the path search algorithms of standard A star and improved A star are achieved by the use of C ++ language, On this basis, the statistics are routing length, routing time, the number of vertices routing process traversal, in order to verify the feasibility and effectiveness of the improved A star algorithm.The simulation experiments in the fourth chapter of this paper prove that:The A star algorithm routing efficiency is increased by 10% by the use ofthe data in OPEN table stored by means of the minimum binary heap.Filtered inner product value is set as the proportion of the heuristic functionof valuation function so that the A star algorithm routing efficiency can beincreased by at least 5.2 times, and traversing vertices reduced by at least57%, which greatly improves the routing efficiency, while the quality ofrouting algorithms remain unchanged.The optimized algorithm has achieved the anticipated effect, which is proved by simulation experiment.