Research On TSP And Extension Problems Based On Hybrid Ant Colony Algorith

The Traveling Salesman Problem(TSP)and its extensions,such as the Multiple Traveling Salesman Problem(MTSP)and the Uncertain Multiple Traveling Salesman Problem(UMTSP),are traditional combinatorial optimization problems that have been widely applied to various practical scenarios,such as logistics planning,task scheduling,traffic management,air transportation,etc.By adopting appropriate constraints,they can help people solve many problems in daily life more effectively.However,due to the increase in problem size,TSP and its extensions are difficult to obtain satisfactory solutions by using exact methods.Researchers tend to use intelligent optimization algorithms such as the ant colony algorithm to solve this problem because it can obtain high-quality solutions in a short time.The purpose of this paper is to explore the improved ant colony algorithm for solving TSP and its extensions.The specific research work mainly includes the following three parts.To address the problems of slow convergence speed and easy trapping into local optima in the traditional ant colony algorithm,this paper proposes a new hybrid ant colony algorithm(Hybrid Ant Colony Optimization,HACO),which combines the improved circle strategy and the ant colony algorithm.In each iteration,the algorithm uses the improved circle strategy to optimize the solution obtained by the ant colony algorithm,transforming it into a better solution and uses the uniform design method to find the optimal parameter combination.By comparing with eight problem instances from the TSPLIB standard library,the experimental results show that the proposed algorithm is superior to other algorithms in terms of solution quality and efficiency,indicating its high solving ability and better efficiency in solving the traveling salesman problem.Based on the previous research,a new hybrid ant colony algorithm is proposed,namely Balanced Hybrid Ant Colony Optimization(BHACO).This algorithm enhances the ability to escape from local optima and find better solutions by using a pheromone balancing operation when solving MTSP.By comparing with eight problem instances from the TSPLIB standard library,the experimental results show that the BHACO algorithm has better performance in solving MTSP and can obtain better solutions.In view of the unreliability of the idealized traveling salesman problem in practical environments,this paper studies UMTSP and proposes a hybrid ant colony algorithm with road condition coefficient(Road-Condition Balanced Hybrid Ant Colony Optimization,RBHACO)based on the previous research.This algorithm treats the road condition coefficient as a weight factor and multiplies it with the original pheromone to consider the influence of the path on the pheromone distribution.At the same time,it uses the road condition coefficient to update the heuristic information,better reflecting the information of the path.By comparing with eight problem instances from the TSPLIB standard library,the experimental results show that the proposed hybrid ant colony algorithm can obtain better solutions when solving UMTSP.