QUANTUM INSPIRED PARTICLE SWARM COMBINED WITH LIN-KERNIGHAN-HELSGAUN METHOD TO THE TRAVELING SALESMAN PROBLEM

AUTOR(ES)

Herrera, Bruno Avila Leal de Meirelles, Coelho, Leandro dos Santos, Steiner, Maria Teresinha Arns

FONTE

Pesqui. Oper.

DATA DE PUBLICAÇÃO

2015-12

RESUMO

ABSTRACT The Traveling Salesman Problem (TSP) is one of the most well-known and studied problems of Operations Research field, more specifically, in the Combinatorial Optimization field. As the TSP is a NP (Non-Deterministic Polynomial time)-hard problem, there are several heuristic methods which have been proposed for the past decades in the attempt to solve it the best possible way. The aim of this work is to introduce and to evaluate the performance of some approaches for achieving optimal solution considering some symmetrical and asymmetrical TSP instances, which were taken from the Traveling Salesman Problem Library (TSPLIB). The analyzed approaches were divided into three methods: (i) Lin-Kernighan-Helsgaun (LKH) algorithm; (ii) LKH with initial tour based on uniform distribution; and (iii) an hybrid proposal combining Particle Swarm Optimization (PSO) with quantum inspired behavior and LKH for local search procedure. The tested algorithms presented promising results in terms of computational cost and solution quality.

Documentos Relacionados

• A SOLVABLE CASE OF THE TRAVELING SALESMAN PROBLEM*
• A HYBRID HEURISTIC ALGORITHM FOR THE CLUSTERED TRAVELING SALESMAN PROBLEM
• Algoritmos heuristicos para o prize collecting traveling salesman problem
• O problema do caixeiro viajante com restrições de empacotamento tridimensional
• Rede neural recorrente com perturbação simultânea aplicada no problema do caixeiro viajante