Ant Colony Algorithm And Its Application On Intelligent Transportation System

With the rapid development of economy and the continuous increasing of vehicle number, the transportation problem has increasingly become a bottleneck that hinders all country's urban development, especially China. Intelligent Transportation System (ITS) is one of the important ways to solve the contradiction of traffic demand and supply in the modern society and the best way to solve the conflict between the slow-increasing basic traffic establishment and the fast-increasing number of vehicles. In recent years, Intelligent Transportation System has been paid more attention. It is supported by the contemporary science and technology rapidly developed which seeks to introduce advanced computer technology, communication technology, database technology and artificial intelligence to transportation so as to solve the traffic congestion, ensure the safety and improve the using rate of traffic network. ITS involves many aspects of traffic field. Among these aspects, one important application is the choosing of the optimal path which is a typical combinatorial optimization problem and suitable to be solved by ant colony algorithm (ACA).Based on mathematics, combinatorial optimization technology is an applied technology, which can be used to find the optimization solutions to the engineering problems. As the development of computer technology, the intelligent-inspiring algorithms whose representative is ant colony algorithm have been rapidly developed and widely used. Ant colony algorithm is a random searching algorithm, which simulates the behavior of ant in nature. Ant colony algorithm has some strongpoints, which are not shared by other general optimization algorithms, for its base on indirect-communication of pheromone. The algorithm adopts positive feedback and parallel autocatalytic mechanism, eximious distributed computation mechanism. Its other main characteristics are stronger robustness, and apt to be combined with other inspiring algorithms.Ant colony algorithm has made great effective progresses in a series of hard combinatorial optimization problems, because of its internal searching mechanism and positive feedback. The validity of the algorithm and its advantages have already been proved by a number of results. But ant colony algorithm also has some shortcomings. Although guided by the pheromone and inspiring information, the selection of route has randomicity and usually costs long searching time when the ant moves from one city to another, especially solving large-scale combinatorial optimization problems. Furthermore, ant colony algorithm easily jumps into local optimal solution when the pheromone on individual routes is enhanced excessively. At the present time the level of research on ITS in our country is low and ant colony algorithm is a relatively new bionic algorithm. So that ant colony algorithm needs more improvement and perfection before it can be fully applied in ITS.The major contents and innovation of the research presented in this thesis are as following:(1) The research and development situation of intelligent transportation system was reviewed. Then the system structure and important effect of ITS were shown in detail.(2) The theory foundation, algorithm model and realization steps of ant colony algorithm were systematically expounded. By analyzing the algorithm, the complexity of ACA was obtained. The time complexity was O (N_c·n~2·m)and the space complexity was O (n~2 )+ O(n·m). Furthermore some factors which effected the performance of ACA were analyzed, especially the parametersα,β,ρ, illustrated by the simulation experiments. The characteristics, research and application situation of ACA were summarized finally.(3) The basic ACA model was improved from four aspects as following: the updating policy of pheromone, parameterβ, parameterρand exploration factor q0. The performance of ACA was raised in the simulation experiments.(4) By combining Genetic Algorithm and ACA, a new ant algorithm named Reward & Punishment–based Genetic Algorithm-Ant Colony Algorithm(RP-GA-ACA) was proposed. The major theory, algorithm model, realization steps and the time complexity were expounded in detail. The simulation experiment showed that RP-GA-ACA was faster than ACA and more accurate than GA.(5) By analyzing the traffic road network, the methods how to express the traffic road network and how to define the weighing were shown.(6) The improved ant colony algorithm named VRP-ACA was proposed which could solve the Vehicle Routing Problem(VRP). The major theory, algorithm model and realization steps were presented. The simulation experiment showed that VRP-ACA could optimize the transportation routines.(7) The chaos phenomenon was introduced firstly, then the chaos theory was introduced into ACA, so as to a new combined algorithm named Chaos Ant Colony Optimization (CACO) was proposed. Finally the simulation experiment verified the performance of CACO and showed that CACO was more suitable to be applied in ITS.