Solving the Min-Max Clustered Traveling Salesmen Problem Based on Genetic Algorithm

The min-max clustered traveling salesmen problem (MMCTSP) is a generalized variant of the classical traveling salesman problem (TSP). In this problem, the vertices of the graph are partitioned into a given number of clusters and we are asked to find a collection of tours to visit all the vertices with the constraint that the vertices of each cluster are visited consecutively. The objective of the problem is to minimize the weight of the maximum weight tour. For this problem, a two-stage solution method based on a genetic algorithm is designed according to the problem characteristics. The first stage is to determine the visiting order of the vertices within each cluster, by abstracting a TSP from the corresponding cluster and applying a genetic algorithm to solve it. The second stage is to determine the assignment of clusters to salesmen and the visiting order of the assigned clusters. In this stage, by representing each cluster as a node and using the result of the first stage and the ideas of greed and random, we define the distances between each two nodes and construct a multiple traveling salesmen problem (MTSP), and then apply a grouping-based genetic algorithm to solve it. Computational experiments indicate that the proposed algorithm can obtain better solution results for various scale instances and shows good solution performance.

Automated summary

The MMCTSP is a generalized variant of the classical TSP problem that aims to minimize the weight of the maximum weight tour. A two-stage solution method based on a genetic algorithm is proposed to solve this problem, where the first stage determines the visiting order within each cluster and the second stage determines the assignment of clusters to salesmen. Experimental results demonstrate that the algorithm can achieve better solution results for various scale instances and exhibit good solution performance.