An improved simulated annealing algorithm with genetic characteristics and the traveling salesman problem

There are two major criticisms about simulated annealing (SA) as a general method for solving combinatorial optimization problem: its effectiveness when compared with other well-designed heuristics and its excessive running time. In this paper, an improved simulated annealing (ISA) technique is proposed. Consider genetic characteristics and processes, the ISA can more efficiently search the solution space starting with multiple initial solutions, and handle the obtained multiple solution sequences of Markov chains such that they close progressively to the optimal one of them, and obtain the set of global optimization solutions. Taking the traveling salesman problem as the background for investigating, the experimental quantitative evaluation and the practical example evaluation for 106 cities in China have shown that the ISA improves enormously the performances of SA.