A Novel Heuristic for the Generalized Traveling Salesman Problems with Imprecise Cost Matrices

A meta-heuristic approach with multiple perturbation rules is proposed to solve the generalized traveling salesman problems in different environments. The proposed approach consists of two phases. The first phase is devoted for the sequencing of the groups and in the second phase one node is selected from each group to minimize the tour cost. In the first stage a group sequence is generated randomly. After that a [Formula: see text]-bit shuffling approach is used to regenerate the new group sequences. In the second phase, for every group sequence several selection rules are used for selecting the nodes/cities from different groups of a particular group sequence. At a regular interval, [Formula: see text]-opt operation is used to update the paths and the corresponding group sequences are updated according to the group elements. The proposed algorithm is capable of solving the problem in crisp as well as different imprecise environments, like fuzzy environment, rough environment, etc. Proper decision making approaches are outlined for decision-making in fuzzy and rough environments. Simulation approaches in fuzzy and rough environments are also presented to deal with the problem for different types of fuzzy and rough estimations. In the crisp environment, the algorithm has been tested using different sizes benchmark test instances from GTSPLIB having sizes upto 226 nodes with 26 groups. There are no benchmark data sets available for the GTSPs in imprecise environments. Test problems in imprecise environments are generated from different benchmark crisp test problems of the GTSPLIB and are used to test the algorithm in the corresponding imprecise environments. It is observed from the numerical illustration and graphical representation that the proposed approach obtains 100% accurate results in all the runs of the algorithm for different seeds of the random number generator for all the considered benchmark test problems under consideration. Another observation is visualized from the table that the algorithm has found multiple optimal paths for some test instances. It can be concluded from the observations that the proposed algorithm is capable of solving the GTSPs in crisp as well as in imprecise environments for a significantly large size problems.