The Research Of Optimal Path Of Geographic Information System For Transportation Based On Ant Colony Algorithm

Geographic Information System for Transportation, GIS-T for short, which is an information processing system based on the GIS technology, relys on urban traffic and with the purpose of traffic inquiry, planning and decision-making. It involves many aspects of transportation, especially, the optimal path selection which is one of the most important applications, is a typical combinatorial optimization problem and it has been widely applied to the various vehicle navigation systems and urban emergency systems. The traditional optimal algorithms are represented by Dijkstra algorithm. These are all greedy which are static local optimal algorithms and have typical local optimization problem. At present, the scale of real traffic data is huge. And it should be loaded in advance of algorithm carried out into the path chosen. Obviously, this cannot reflect the actual continuous situation of traffic on the path chosen. Ant Colony Algorithm is a new bionic simulation algorithm. It has the capability in simulating colony cooperation and finding a shortest path from nest to food, which could respond dynamically to external affection in the routing search process. So it has infinite feasibility and flexibility in the optimal path chosen for traffic.Firstly, the thesis presented the researching status of GIS-T home and aboard, the key technology, the important functions and applications, secondly, it discussed and researched several traditional algorithms of optimal path chosen, which contained Dijkstra Algorithm, Floyd Algorithm and other algorithms based on intelligent computing. Thirdly, combining these traditional optimal path algorithms with ant foraging behavior, Ant Colony Algorithm (ACA) was introduced, and the thesis also researched the theory, model, implementing steps and processes of the algorithm, analyzed the setting of the important parameters, summarized the advantages and the disadvantages, and introduced some classical improved ant colony algorithms. As the traditional improved algorithms either improved the ability of global optimization or the convergence rate, for the sake of the balance between the both, the thesis introduced the dual population of Ant Colony Algorithm based on adaptive pheromone updating. Updating the pheromone by the distribution and adjusting dynamically the pheromone distribution of the paths, so that the pheromone won't be concentrated or dispersive, to avoid prematurity with accelerated convergence. Through the strategy of adaptive pheromone updating, it improved the ability of global optimization, meanwhile as well as the convergence rate through the strategy of the dual population. The experiment showed that the improved algorithm obtained good effects on both the stability and the optimization. Finally the thesis applied the improved algorithm to the solution of optimal path chosen for GIS-T in different traffic conditions.