Using genetic algorithms to minimize the distance and balance the routes for the multiple Traveling Salesman Problem

The Traveling Salesman Problem (TSP) has been used to model many real world applications. In this problem, a salesman travels using the shortest route between the cities that he must visit and returns to the depot. If it is required to use more than one salesman in the solution, the problem is called multiple Traveling Salesman Problem (mTSP), and the objective is to minimize the overall distance traveled by them. However, when only the overall distance is minimized, depending on the distribution of the cities, some salesmen tend to travel much more than others. This paper presents the development of Genetic Algorithms (GAs) to reduce both the overall distance and the difference between the distance traveled by each salesman. Since there are more than one objective to be optimized, two approaches were evaluated. A multi-objective GA and a mono-objective GA with a fitness function that combines both objectives. In order to find the best results for each approach, different methods for crossover and selection have been used. Experimental results show the effectiveness of the proposed GAs. The results further indicate that, considering both objectives, the multi-objective GA generates more balanced solutions for almost all instances.