A HYBRID HEURISTIC ALGORITHM FOR THE CLUSTERED TRAVELING SALESMAN PROBLEM

摘要: This paper proposes a hybrid heuristic algorithm, based on the metaheuristics Greedy Randomized Adaptive Search Procedure, Iterated Local and Variable Neighborhood Descent, to solve Clustered Traveling Salesman Problem (CTSP). Hybrid Heuristic algorithm uses several variable neighborhood structures combining intensification (using local search operators) diversification (constructive perturbation routine). In CTSP, vertices are partitioned into clusters all of each cluster have be visited contiguously. The CTSP is 𝒩𝒫-hard since it includes well-known (TSP) as special case. Our compared with three heuristics from literature an exact method. Computational experiments reported for different classes instances. Experimental results show that proposed obtains competitive within reasonable computational time.