Metaheuristics for the tabu clustered traveling salesman problem

This paper considers a new variant of traveling salesman problem (TSP), called tabu clustered TSP (TCTSP). The nodes in TCTSP are partitioned into two kinds of subsets: clusters and tabu node sets, then the salesman has to visit exactly one node for each tabu node set and ensures that the nodes within a same cluster are visited consecutively, and the problem calls for a minimum cost cycle. The TCTSP can be used to model a class of telemetry tracking and command (TT&C) resources scheduling problem (TTCRSP), the goal of which is to efficiently schedule the TT&C resources in order to enable the satellites to be operated normally in their designed orbits. To solve it, two metaheuristics combined with path relinking are proposed. The one is Ant Colony Optimization (ACO) and the other is Greedy Randomized Adaptive Search Procedure (GRASP). The proposed algorithms are tested on the benchmark instances and real-life instances of the TTCRSP. The computational results show that the hybrid ACO with two path relinking strategies works the best among the studied metaheuristics in terms of solution quality within the same computational time.