Made available in DSpace on 2014-12-17T15:47:44Z (GMT). No. of bitstreams: 1 AlvaroNP.pdf: 769620 bytes, checksum: a6a391c5417e2fcb7b544cc7f3b2140f (MD5) Previous issue date: 2006-07-27 / 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 / Devido ? grande dificuldade de solu??o exata dos Problemas de Otimiza??o Combinat?ria, v?rios m?todos heur?sticos t?m sido desenvolvidos e durante muitos anos, a an?lise de desempenho dessas abordagens n?o foi realizada de maneira sistem?tica. A proposta deste trabalho ? fazer uma an?lise estat?stica de abordagens heur?sticas aplicadas ao Problema do Caixeiro Viajante. O foco da an?lise ? avaliar o desempenho de cada abordagem em rela??o ao tempo computacional necess?rio at? a obten??o da solu??o ?tima para uma determinada inst?ncia do PCV. Para essa an?lise, foi utilizada uma metodologia estat?stica chamada An?lise de Sobreviv?ncia, auxiliada por m?todos para o teste da hip?tese de igualdade entre fun??es. Para uma melhor compreens?o, as abordagens avaliadas foram divididas em tr?s classes: Algoritmos Lin-Kernighan, Algoritmos Evolucion?rios e Algoritmos de Otimiza??o por Nuvem de Part?culas. Al?m das abordagens j? existentes, foi inclu?do na an?lise, um algoritmo mem?tico (para inst?ncias sim?tricas e assim?tricas do PCV) que utiliza o algoritmo de Lin e Kernighan como procedimento de busca local