A random-permutation based GA for generalized traveling salesman problem in imprecise environments

A random-permutation technique and the features of the genetic algorithm (GA) are combined together to develop a novel heuristic for solving generalized travelling salesman problem. Here, the random-permutation technique is used to find the sequence of clusters of a probable solution in which a complete tour to be commenced. The features of GA are used to select the cities from different clusters of the sequence. The algorithm has the ability to solve the problems in both the crisp as well as in the imprecise environments. A fuzzy membership-based selection process is proposed to select a solution for the mating pool. A general comparison rule of the solutions is proposed to rank the potential solutions of the population in imprecise environments. In the crisp environment, the efficiency of the proposed approach is tested against a set of different benchmark test problems from GTSPLIB having sizes up to 226 cities with 26 clusters. It is observed from the experimental results that the algorithm produces 100% accurate results for all the benchmark test problems under consideration. Imprecise test problems are generated from different benchmark crisp test problems of TSPLIB and are used to test the algorithm in the imprecise environments. It is also observed from the experimental results that the proposed approach finds multiple optimal paths (i.e, more than one path), if exists, for the problems in the crisp as well as in the imprecise environments.

Automated summary

A novel heuristic algorithm, combining random-permutation technique and genetic algorithm, is proposed for solving generalized travelling salesman problem. The algorithm can handle both crisp and imprecise environments, and has achieved promising results in experiments.