The Application Of The Hybrid Ant Colony Algorithm On Capacitated Vehicle Routing Problem

As "the third profit source", Logistics has drawn more and more attention and is becoming the basic industry of the national economy. Logistics distribution is an important part of logistics, accounting for more than 60% of logistics costs. Capacitated vehicle routing problem is the core issue of the logistics distribution system. It devotes to optimize vehicle routes in logistics, so as to reduce the operator’s distribution costs and realize scientific logistics. Ant colony optimization algorithm is a heuristic search algorithm based on population optimization, which searches faster and has high search efficiency. It is easy to fall into local optimum, therefore the hybrid ant colony algorithm is proposed to solve capacity constraints vehicle routing problem.The main work of this paper includes the following aspects:(1) It has a systematic studying on the vehicle routing problem, colony optimization algorithm and particle swarm optimization algorithm. Then a mathematical model of vehicle routing problem with capacity constraints is proposed based on the studying. Models of the ant colony optimization algorithm and particle swarm optimization algorithm are made and their advantages and disadvantages have been proposed.(2) It designs a hybrid ant colony algorithm. The hybrid algorithm combines the global search capability of ant colony optimization algorithm and the local optimization ability of particle swarm optimization algorithm. It avoids severeal shortcomings of the ant colony optimization algorithm which is easy to fall into premature convergence, local optimum and has poor local optimization capacity. The main thought of the hybrid algorithm is to use ant colony optimization algorithm to find the initial solution by all nodes traversal, then the particle swarm optimization algorithm updates the solution, and to find the better solution.(3) It uses the hybrid ant colony algorithm to solve vehicle routing problem with capacity constraints, and also makes the comparative tests using the standard data sets to verify the superiority of the algorithm.The study, in theory, plays a positive role in promoting the development for both the ant colony optimization algorithm and particle swarm optimization algorithm. It provides a new way for the integration of the two algorithms. In practice, it can solve large-scale vehicle routing problems effectively. So the paper not only has great theoretical significance, but also has practical value.