Genetic Algorithms for the Multiple Travelling Salesman Problem

Abstract—We consider the multiple travelling salesman
Problem (MTSP) that is one of the generalization of the
travelling salesman problem (TSP). For solving this problem
genetic algorithms (GAs) based on numerous crossover operators
have been described in the literature. Choosing effective
crossover operator can give effective GA. Generally, the
crossover operators that are developed for the TSP are applied to
the MTSP. We propose to develop simple and effective GAs using
sequential constructive crossover (SCX), adaptive SCX, greedy
SCX, reverse greedy SCX and comprehensive SCX for solving
the MTSP. The effectiveness of the crossover operators is
demonstrated by comparing among them and with another
crossover operator on some instances from TSPLIB of various
sizes with different number of salesmen. The experimental study
shows the promising results by the crossover operators,
especially CSCX, for the MTSP.