Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search

摘要

The traveling salesman problem (TSP) is a classical problem in discrete or combinatorial optimization and belongs to the NP-complete classes, which means that it may be require an infeasible processing time to be solved by an exhaustive search method, and therefore less expensive heuristics in respect to the processing time are commonly used in order to obtain satisfactory solutions in short running time. This paper proposes an effective local search algorithm based on simulated annealing and greedy search techniques to solve the TSP. In order to obtain more accuracy solutions, the proposed algorithm based on the standard simulated annealing algorithm adopts the combination of three kinds of mutations with different probabilities during its search. Then greedy search technique is used to speed up the convergence rate of the proposed algorithm. Finally, parameters such as cool coefficient of the temperature, the times of greedy search, and the times of compulsive accept and the probability of accept a new solution, are adaptive according to the size of the TSP instances. As a result, experimental results show that the proposed algorithm provides better compromise between CPU time and accuracy among some recent algorithms for the TSP.