A hybrid genetic-simulated annealing algorithm for multiple traveling salesman problems

Abstract

The Multiple Traveling Salesman Problem (MTSP) was able to model and solve various theoretical and real-life applications. This problem is one of the many difficult issues that have no perfect solution yet. In this paper, on the one hand genetic algorithms with different combinations of operators and simulated annealing were used to solve the MTSP. On the other hand, the genetic algorithm with the combination of operators that gave the best solutions of the MTSP was hybridized with a Simulated Annealing algorithm. The simulation results showed that the hybrid algorithm significantly outperforms most of the comparable methods in obtaining the best-fitness solutions compared to the other methods in most of the test cases. In addition, by scaling the fitness function according to the amplitude of tours, it was obvious that the non-dominated front obtained by the hybrid algorithm was better than the non-dominated front obtained by the other algorithms.