Solving the multiple traveling salesman problem using heuristic algorithms

Nowadays, systems formed by biological structures have gained importance and attracted the attention of researchers. Some social systems in nature exhibit collective intelligence, although they are created by simple individuals with limited abilities. The organizations of these individuals and their indirect communication among these individuals are used to solve the optimization problems encountered in engineering and daily life. They also contribute to the development of the artificial intelligence systems. The Particle Swarm Optimization (PSO) algorithm which is a meta-heuristic algorithm based on the social behavior of birds. In this article, 2 algorithms based on PSO, called APSO and HAPSO, were proposed to solve the Multiple Travelling Salesman Problem (MTSP). The aim in the MTSP is to find the tours for all m salesmen, who all start and end at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized. The APSO algorithm is based on the PSO and 2-opt algorithms, the path-relink and swap operators. On the other hand, the HAPSO algorithm is based on the GRASP, PSO and 2-opt algorithms, the path-relink and swap operators. In the experiments, the 9TSP instances were used and the HAPSO and APSO algorithms were compared in detail on these samples for the 2, 3, 4, 5, 6, 7, 8 and 9 salesmen in terms of the tour charts, the computational times and the boxplots. When the tour graphs are examined, the lengths of the tours created by HAPSO algorithm are shorter. Another method used to compare algorithms is the boxplot. Through the box graph, the statistical information about the results of the algorithms are visualized and thus the interpretation of this information is easy. When the boxplots are examined, it is seen that HAPSO algorithm is more stable and more robust. In addition, on the 5 TSP instances the HAPSO and APSO algorithms were compared with the Genetic Algorithm and Ant Colony Optimization algorithms in the literature. According to the results, the HAPSO algorithm has the better performance than the other algorithms on the most instances. In addition, the HAPSO algorithm produces more stable results than the APSO algorithm and the performance of the HAPSO algorithm is better in all the MTSP instances. Therefore, the HAPSO algorithm is more robust than the APSO algorithm.