Improved Ant Colony Algorithm And It's Application On Urban Transit Network Optimization

With the rapid development of our society, the amount of resident trips is multipling, which leads to urban traffic congestion. An effective way of solving this problem is to develop urban public transport vigorously, and to improve its contribution rate in the whole amount of people traveling. Urban Transit Network Optimization (UTNO) can maximize the potential of urban public transport system by line optimization and rational distribution based on the existing city transportation system and public transportation capacity. It is an effective measure which needs small additional investment but leads to fast improvement, also, it is an easy way to be implemented. Ant Colony Algorithm (ACA) is a new heuristic algorithm which has made great effective progress in a series of hard combinatorial optimization problems, while the urban transit network optimization is a typical nonlinear combinatorial optimization problem, so in this paper, ant colony algorithm will be applied to solve the problem of urban transit network optimization. The major contents of the research presented in this paper are as following:First of all, this paper introduces the basic contents of ant colony algorithm and urban transit network optimization. Then, this paper presents the two limitations of ACA which can not be well solved by the existing study of algorithm, including the problem of ACA that is easy to fall into stagnation and the problem of algorithm parameters that is difficult to be set up. In order to solve these problems, this paper puts forward the innovative concept of stagnation counter whose function is to judge the stage of algorithm. According to the different stages of algorithm, the improved ACA will carry out some additional pheromone update of the newly discovered better path, so as to enhance the learning to the ants' occasional findings of much more excellent paths. Furthermore, this paper presents a dynamic parameters setting method based on the different stages of algorithm, in order to achieve a balance between exploration and exploitation. At last, with a numerical test, compared with the basic MMAS, the solution quality and convergence speed of the improved algorithm applied the above-mentioned methods have been improved significantly. The effectiveness of the improved ACA proposed in this paper is verified.Finally, with the comprehensive analysis of the goals and constraints of the urban transit network optimization problem, this paper proposes minimum transfers and maxmum dynamically direct traveler flow per unit time as the target, and establishs its mathematical model. And this paper makes a further improvement to the improved algorithm by putting forward innovative candidate list of city nodes and mechanism of death ants' penalty adapting to the specific problem of UTNO. Then this paper uses the improved ACA to resolve the UTNO problem. The improved algorithm presented in this paper has achieved good results in the rate of direct traveler flow, nonlinear coefficient and line repetition factor. It makes direct traveler flow per unit time much larger and transit network configuration more scientific.