Application Of Improved Ant Colony Algorithm For Vehicle Routing Problem

Vehicle Routing Problem has been widely used in many areas such as modern logistics, transportation planning, communication and computer technology, so as to VRP has been the research focus of operations research, graph theory, applied mathematics, simulation science, computer science and many other subjects, and achieved fruitful results in theory and application. But how to find the optimal solution efficiently in large-scale VRP are still hot issues in this area. This paper described the following two aspects.(1) This paper summed up the research status of VRP and various kinds of solving method at home and abroad, described the basic principles of ACA, models and some solving methods. Analyzed of the complexity of ACA and the impact of key parameters such asα,βandρ. Artificial ant colony algorithm is a classical heuristics of positive feedback mechanism Proposed by simulating the swarm intelligence of ant foraging. But the traditional ant colony algorithm in solving VRP exist in the shortcoming of slow searching speed and easy to fall into the local best results. In the application of ant colony algorithm for large-scale VRP problems, how to obtain more satisfactory optimal solution in relatively short time are the main contents of this article.(2) This paper proposed a kind of improved ant colony algorithm with Taboo search capability. The improved algorithm integrated taboo search ideas on the basis of the ant system. The improved algorithm influence the next choice of ants by macro-controlling best route and the worst route in order to increase the diversity of solution, and more suitable for solving VRP problems. Finally, according to the improved algorithm write Matlab code and testing algorithm by solving CVRP.The results showed that new improved algorithm significantly improved the performance on optimizing CVRP; more satisfactory optimal solution can be obtained in relatively short time.