A HYBRID HEURISTIC ALGORITHM FOR THE CLUSTERED TRAVELING SALESMAN PROBLEM

AUTOR(ES)

Mestria, Mário

FONTE

Pesqui. Oper.

DATA DE PUBLICAÇÃO

2016-04

RESUMO

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

Documentos Relacionados

• A SOLVABLE CASE OF THE TRAVELING SALESMAN PROBLEM*
• Algoritmos heuristicos para o prize collecting traveling salesman problem
• QUANTUM INSPIRED PARTICLE SWARM COMBINED WITH LIN-KERNIGHAN-HELSGAUN METHOD TO THE TRAVELING SALESMAN PROBLEM
• A hybrid heuristic for the multi-plant capacitated lot sizing problem with setup carry-over
• An efficient hybrid heuristic method for the 0-1 exact k-item quadratic knapsack problem