A comparative study between SA and GA in solving MTSP
Wenze Zhang, Chenyang Xu · Theoretical and Natural Science · 2023
The multiple traveling salesmen problems (MTSP) is a combinatorial optimization and np-hard problem. In practice, the computational resource required to solve such problems is usually prohibitive, and, in most cases, using heuristic algorithms is the only practical option. This paper implements genetic algorithms (GA) and simulated annealing (SA) to solve the MTSP and does an experimental study based on a benchmark from the TSPLIB instance to compare the performance of two algorithms in reality. The results show that GA can achieve an acceptable solution in a shorter time for any of the MTSP cases and is more accurate when the data size is small. Meanwhile, SA is more robust and achieves a better solution than GA for complex MTSP cases, but it takes more time to converge. Therefore, the result indicates that it is hard to identify which algorithm is comprehensively superior to the other one. However, It also provides an essential reference to developers who want to choose algorithms to solve MTSP in real life, facilitating them to balance the algorithm’s performance on different metrics they value.