Uma análise experimental de abordagens heurísticas aplicadas ao problema do caixeiro viajante

AUTOR(ES)

Álvaro Nunes Prestes

DATA DE PUBLICAÇÃO

2006

RESUMO

Due to great difficulty of accurate solution of Combinatorial Optimization Problems, some heuristic methods have been developed and during many years, the analysis of performance of these approaches was not carried through in a systematic way. The proposal of this work is to make a statistical analysis of heuristic approaches to the Traveling Salesman Problem (TSP). The focus of the analysis is to evaluate the performance of each approach in relation to the necessary computational time until the attainment of the optimal solution for one determined instance of the TSP. Survival Analysis, assisted by methods for the hypothesis test of the equality between survival functions was used. The evaluated approaches were divided in three classes: Lin-Kernighan Algorithms, Evolutionary Algorithms and Particle Swarm Optimization. Beyond those approaches, it was enclosed in the analysis, a memetic algorithm (for symmetric and asymmetric TSP instances) that utilizes the Lin-Kernighan heuristics as its local search procedure

ASSUNTO(S)

heuristics sistemas de computacao problemas do caixeiro viajante experimental analysis otimização análise experimental traveling salesman problem optimization heurísticas

Documentos Relacionados

• Algoritmos Evolucionários Aplicados ao Problema do Caixeiro Viajante Multiobjetivo.
• Plasticidade sináptica e o problema do caixeiro viajante
• Algoritmo treansgenético na solução do problema do Caixeiro Viajante
• O problema do caixeiro viajante alugador : um estudo algorítmico
• Metaheurísticas híbridas para resolução do problema do caixeiro viajante com coleta de prêmios