New Heuristic Algorithms for Solving Single-Vehicle and Multi-Vehicle Generalized Traveling Salesman Problems (GTSP)

Among numerous np-hard problems, the traveling salesman problem (tsp) has been one of the most explored, yet unknown one. even a minor modification changes the problem’s status, calling for a different solution. the generalized traveling salesman problem (gtsp) expands the tsp to a much more complicated form, replacing single nodes with a group or cluster of nodes, where the objective is to find a minimum-length tour containing exactly one node from each cluster. in this paper, a new heuristic method is presented for solving singlevehicle single-depot gtsp with the ability of controlling the search strategy from conservative to greedy and vice versa. a variant algorithm is then developed to accommodate the multi-vehicle single-depot condition, which is modified afterwards to accommodate the multi-vehicle multi-depot gtsp.