An improved Ant Colony algorithm for Urban Transit Network Optimization

This paper develops an improved Ant Colony Optimization (IACO) algorithm to solve Urban Transit Network Optimization (UTNO) which is a typical nonlinear combinatorial optimization problem. An innovative concept of stagnation counter is used to determine the stages of the IACO. Extra pheromone intensity will be reinforced for the newly discovered path. To trade off between exploration and exploitation, a dynamic parameter setting method is also presented in this paper. It is verified that the solution quality and the convergence speed of our IACO have been improved significantly. A candidate node list for each city and a penalty mechanism for the dead ant are applied in UTNO. The numerical results obtained from a series of benchmark problem instances confirm that our IACO has achieved good results in direct passenger flow rate, line nonlinear factor and line overlap factor.