Improved Hybrid Ant Colony Algorithm

Many scholars have been a lot of theoretical research and experimental analysis since Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP) are proposed and notable progress is made. TSP and VRP have become the central issue in operational research and combinatorial optimization. Precise algorithm, approximate algorithm and heuristic algorithm are used to solve the problems. Among all the algorithms, ant colony algorithm has better performance. This bionic intelligence algorithm is quite different from the traditional ones, it’s more robust, positive feedback, concurrency and easy to combine with other algorithms. Since ant colony algorithm is proposed, breakthrough progress has been made both in theoretical research and realistic application. Not only optimal results are achieved but also proven to be effective in scheduling jobs, graph coloring, multi-objective function and other scopes. It has a very broad prospect.In this paper, a mixed ant colony algorithm is introduced firstly. The algorithm is based on the traditional ant colony system algorithm, construct an initial result using the nearest neighbor method and then improve the results using2-opt partial search strategy, and update the global pheromone for the best two colonies with a maximum and minimum constraint. The simulation using MATLAB for the classic kroa200and other twelve TSP problems showed us very good results. All the results have deviations less than1percent compared to the best-known results and some problems even achieved better results. In this paper, I also compared the results to two updated ant colony algorithms and two self-organization algorithms, the better results indicated us our mixed ant colony algorithm is a better one.Afterwards we used a method of counting the sum of the route edges to measure the population diversity of our algorithm. Then we compared the population diversity of our improved mixed algorithm and the base ACO algorithm. The result shows our algorithm has higher population diversity which gives us a theory support why our algorithm can achieve best result than ever known.Then we applied the algorithm to VRP. We simulated the classic N34K6and other nine VRP problems using the MATLAB tool, the results of which have small deviations compared to the best-known results. All the deviations are all smaller than6percent. And we got the result same as the best-known result for N33K6. In this paper, I also compared the results to the results of the base ant colony optimization algorithm; the better results indicated us our mixed ant colony algorithm is a better one to solve the VRP.