A New Multiple Traveling Salesman Problem and its Genetic Algorithm-based Solution

This work formulates for the first time a multiple traveling salesman problem (MTSP) with ordinary and exclusive cities, denoted by MTSP* for short. In the original MTSP, a city can be visited by any traveling salesman and is thus renamed as an ordinary one in MTSP*. A new class of cities is introduced in MTSP*, called exclusive ones. They are divided into groups, each of which can be exclusively visited by a specified or predetermined salesman. To solve MTSP*, a genetic algorithm is presented. It encodes cities and salesman into two single chromosomes. Accordingly, three modes of crossover and mutation operators are designed, i.e., simple city crossover and mutation (CCM), simple salesman crossover and mutation, and mixed city-salesman crossover and mutation. All the operations of crossover and mutation follow the proper relationship between cities and salesman. With the help of an MTSP* example, the performance of the proposed algorithm with three modes of crossover and mutation operators is compared and analyzed. The simulation results show that the algorithm can solve MTSP* with rapid convergence with CCM being the best mode of the operators.