Multi-objective generalized traveling salesman problem: A decomposition approach

Using the features of shuffle, re-generation, and 4-opt operation, a novel heuristic has been proposed based on the decomposition approach for the multi-objective generalized traveling salesman problems. A three-layer solution updating mechanism, namely, a shuffle layer, a layer for re-generation, and a layer for 4-opt operation, has been designed for the same. The shuffle and re-generation operations are specially designed to solve this problem. The shuffle operation is applied to a solution sequence (complete path/tour) to improve the corresponding objectives. The re-generation operation consists of two phases- in the first phase, the objectives are improved by interchanging a few portions of the groups/clusters sequence, and in the second phase, the same is done by replacing some cities from the corresponding groups. Finally, the solution and the corresponding groups are rearranged using the 4-opt operation for the betterment of the same. Problems with varying sizes from the generalized traveling salesman problem library are solved using the proposed approach to verify its performance and for the illustration. Some widely used performance metrics for multi-objective solution methodologies have been applied to the proposed heuristic to measure its performance. Various well-established heuristics have been modified according to this problem and are implemented to compare the efficiency of the proposed heuristic. Based on the performance metrics values of the computational outputs, a conclusion can be drawn that the proposed heuristic, named SR4-MOEA/D, is the best compared to the other heuristics implemented for the same. Also, every test instance of the proposed algorithm provides the best pareto optimal front, which is distributed over the whole true pareto front of the respective problem.

Automated summary

Using shuffle, re-generation, and 4-opt operation, a novel heuristic is proposed for the multi-objective generalized traveling salesman problems. The algorithm utilizes a three-layer solution updating mechanism and achieves improved performance compared to other heuristics.