Urban Road Network, Ant Colony Shortest Path Algorithm

The shortest path problem 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.This dissertation constructs topology network platform for studing the ant colony algorithm for the shortest path, it is mainly based on the electronic map of Kunming City, then according to the low speed of constringency and easy to stagnation in ant colony algorithm,the dissertation proposes some improved schemes.The dissertation also studies the application of the ant colony optimization algorithm in traffic jam problem.Main contributions of the dissertation include:(1)Through the extraction of points and roads in the map of Kunming City by the further development with MapX and VC++, based on the electronic map of Kunming City, the dissertation completes the construction of topology network which can be used as a platform for the research of follow-up algorithms.(2) TSP is used as an example to analyse the ant colony algorithm.This dissertation compares the differences between TSP problem and the shortest path problem, then, achieves the purpose of solving the shortest path problem by using the ant algorithm, and makes an in-depth analysis of the affects of the parameters to the algorithm.(3)According to the low speed of constringency and the poor search accuracy, This dissertation improves the algorithm through changing the form of the heuristic information of the distance and the rules of updating global pheromone trails, then proposes an ant colony algorithm based on lighting elements. The experimental results have proved the efficiency of the algorithm in running time, the quality of solution and any other aspects.(4) This dissertation uses the concentration of the pheromone to simulate the traffic jam, designs the AS-BTJ algorithm to solve the shortest path problem when there is traffic jam problem, and the experimental results have verified the feasibility of the algorithm.