Research On Ant Colony Optimization Algorithm For Dynamic Traveling Salesman Proble

The traveling salesman problem is a classical combinatorial optimization problem,which has many practical applications in the real world.However,these real-world applications are often in a dynamic and changing environment,posing huge challenges to the already difficult traveling salesman problem.Meta-heuristic algorithm is inspired by the evolution process of nature or biology in dynamic environment,and has the ability to adapt to dynamic environment,so it is used to solve dynamic combinatorial optimization problems.Among them,the ant colony optimization algorithm is inspired by the foraging behavior of ant colonies in nature,providing an efficient and feasible solution for the dynamic traveling salesman problem.However,when using ant colony optimization algorithms to solve dynamic traveling salesman problems,there are usually drawbacks such as slow search speed and susceptibility to falling into local optima.In addition,the ant colony optimization algorithm only utilizes the distance information between city nodes in the traveling salesman problem,and utilizes little information of the problem.In response to the shortcomings of the ant colony optimization algorithm mentioned above in solving dynamic traveling salesman problems,this article conducts research from two aspects: balancing the utilization and exploration capabilities of the ant colony optimization algorithm,and the information utilization of the traveling salesman problem.The main tasks completed are as follows:We propose an ant colony optimization algorithm based on trade-off of exploring and utilizing to solve the problems of slow search speed and easy falling into local optima in ant colony optimization algorithms.After the environment changes,we use the simulated annealing algorithm to search the existing solution with the highest quality locally,enhance the utilization ability of the algorithm,and quickly obtain the solution with high quality.When the algorithm falls into a local optimum,an adaptive roulette wheel selection method is used to improve the ant colony exploration ability and jump out of the local optimum.The experimental results show that the proposed ant colony optimization algorithm can improve the offline performance of the ant colony optimization algorithm in solving dynamic traveling salesman problems by exploring a new strategy of capacity balancing.We propose a machine learning based ant colony optimization algorithm to overcome the drawback of insufficient utilization of information in the traveling salesman problem.We train a machine learning model using a set of solved traveling salesman problem instances to predict the probability that each edge in the problem instance belonging to the optimal path.This probability value is applied to the ant colony optimization algorithm in different ways.The experimental results show that different application methods can improve the offline performance of ant colony optimization algorithm in solving dynamic traveling salesman problems.