Research Of Ant Colony Algorithm In Car Navigation

The shortest path problem of car navigation is either a basic problem in network analysis, or a hotspot which is closely related to traffic problem. In recent years, as a member of the family of the intelligent algorithms, the ant colony algorithm is gradually favored by the majority of scholars and increasingly being applied to solve complex problems because of its strong ability to find better solutions.Main contributions of the dissertation include:(1) By analyzing the advantages and disadvantages of the traditional network model of the data storage structure, we propose an object-oriented data storage method in this dissertation. Meanwhile, we implement the "zero" storage of unwanted elements, which greatly reduces the storage space. At the same time, this data storage structure improves the efficiency of file read.(2) In process of searching path, we discuss a phenomenon that a single ant falls into the taboo table set up their own "loop", and proposed their own solutions. In this dissertation we improve Ant Colony Algorithm to improve the success rate of a single ant to find the path. We analyze improved Ant Colony Algorithm parameters through the experiment to find the best parameters for the algorithm. Finally, we do some simulations and comparisons in the same below the algorithm proposed in other literature in the set of parameters.(3) First, we systematically analyzed the basic principle of Ant Colony Algorithm. Then, we integrate the basic characteristics of the urban road network in the cat navigation, and propose the dynamic programming search region algorithm strategy to reduce the search range. Meanwhile, we analyze the existence of location of the optimal path, design the restricted area of the search range on the basis of the location of the optimal path. These all we do improve the efficiency of the algorithm. At last, by taking advantages of combination of the A star algorithm and the improved Ant Colony Algorithm, we propose a new hierarchical Ant Colony algorithm based on dynamic regional planning. (4) We do a lot of simulation analyses. The result of these simulations presented the new algorithm proposed in this dissertation is effective.