The Improved Genetic Algorithms for Multiple Maximum Scatter Traveling Salesperson Problems

Maximum scatter traveling salesperson problem (MSTSP), as a variant of traveling salesman problem (TSP), has been successfully applied to the practical cases in manufacturing and medical imaging. However, it cannot model the application problems where there are multiple objectives or individuals. This paper proposes a new model named multiple maximum scatter traveling salesperson problems (MMSTSP) for modeling such problems. The paper applies three improved genetic algorithms (GAs) to solve MMSTSP, where three methods are used to improve GA, the first one is greedy initialization for optimization, the second one is climbing-hill algorithm, and the last one is simulated annealing algorithm. Furthermore, many real-world problems can be modeled by MMSTSP, and the scale of constructed model is usually up to large scale, it is necessary to study large scale MMSTSP problem. Therefore, the paper uses the improved GAs to solve the small scale to large scale MMSTSP. By extensive experiments and analysis, it shows that the improved algorithms are effective, and can demonstrate different characteristics in solving the problem.