Comparative study of crossover operators for the MTSP

Abstract:
The multiple traveling salesman problem (MTSP) is one of the combinatorial optimization problems, which can be defined as follows: There are a `m' number of salesmen who must travel to `n' number of cities starting with depot and ending at the same depot. Furthermore, the salesmen must travel from one city to another continuously without repeating any city that has been crossed over by the salesmen and considering the shortest path during this travel. The MTSP is a generalization of the travelling salesman problem (TSP), where more than one salesman is used in the solution. The problem is NP-hard, and it has many applications in real life. This research aims to develop genetic algorithms (GAs) that considers six different crossover operators separately in order to find optimal solutions, and then compare GAs using different crossover operators. The efficiency of the algorithms is shown by experimental study on benchmark TSPLIB instances of various sizes. Experimental study shows that GA using sequential constructive crossover (SCX) is the best crossover method among six crossover methods.