| Abstract [eng] |
Simulated annealing (SA) algorithms are often used for solving various combinatorial optimization (CO) problems. In this work, an original simulated annealing algorithm for the well-known combinatorial optimization problem, the traveling salesman problem (TSP) is introduced. The analysis of the results of the experiments with the proposed algorithm by using the TSP instances from the publicly available electronic library TSPLIB is given. The influence of the algorithm control parameters on the results is discussed as well. Based on the results obtained, it is concluded that that the simulated annealing schedule length and the temperature control factors have a crucial effect on the quality of solutions. Besides the basic simulated annealing algorithm for the traveling salesman problem and its experiments, the modifications to improve the functionality of the algorithm are introduced. Detailed experiments have been carried out to prove the utility of the modifications. The experiments are also based on the TSP instances from the publicly available electronic library TSPLIB, and have been divided into two categories regarding to the size of the problem. It has been discovered that four modifications managed to improve the results of the basic SA algorithm for the smaller traveling salesman problems, and one of them is giving better results for the TSPs with larger scopes. |
