Improved Ant Colony System And Its Application On Vehicle Routing Problem

Optimization technology is a technology based on mathematics and applied to all kinds of optimization solution to engineering problems. As an important branch of science, it is always attached wide importance to and rapidly extended and applied to industry and economy, and so on. Because of complication, large-scale, non-linear and difficulties of modeling in engineering optimization, it has been a main research object and direction that finds an intelligent and general-purpose global optimization method for large-scale parallelization.Since 1980s, some novel heuristics algorithms are created by simulating or showing some natural phenomena, such as Genetic Algorithms, Simulated Annealing, Taboo Search, Ant Colony Optimization. The particular advantage and mechanism of these algorithms have brought a hot-spot of research, especially Ant Colony Optimization has been developed for more than ten years.A population-based simulated evolutionary algorithm called ant colony optimization (ACO for short) was proposed by Italian M. Dorigo. ACO adopts parallel computation mechanism, has strong robustness and is easy to combine with other methods in optimization. Because of its characteristics, the research of theory and application of ACO has great merit. Firstly, this paper analyzes the basic theory and model of ACO, introduces the features of ACO and selects some key parameters' value of ACO by experiments. Secondly, the slow convergence and stagnation behavior, so an improved algorithm is proposed. This algorithm is able to restrain stagnation during the iteration process effectively, and enhance the capability of search. The improved algorithm is applied to traveling salesmen problem (TSP). Experimental results for solving TSP are proved to be effective.. Finally, the improved algorithm is applied to vehicle routing problem(VRP). Simulation results of the VRP example demonstrated the effectiveness of this algorithm.