Made available in DSpace on 2015-05-14T12:36:55Z (GMT). No. of bitstreams: 1 parte1.pdf: 1169586 bytes, checksum: 685986454ee5e2cc58d709e7d646732f (MD5) Previous issue date: 2009-08-28 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This work presents a new heuristic, called Heurística 1, and the implementations of the GRASP, Simulated Annealing and Genetic Algorithms metaheuristics for the rectilinear Steiner minimum tree problem (RSMTP), talking about its theoretical aspects, like computational complexity, and practical ones, like pseudo-codes and implementation strategies. The new techniques for RSMTP presented, especially the Genetic Algorithms, have computational results of superior quality in comparison to the best heuristics in present litera / Este trabalho apresenta uma nova heurística, denominada Heurística 1, e a implementação das metaheurísticas GRASP, Simulated Annealing e Algoritmos Genéticos para o problema da árvore retilínea mínima de Steiner (RSMTP), discorrendo sobre seus aspectos teóricos, como a complexidade computacional; e práticos, como pseudocódigos e estratégias de implementação. As novas abordagens para o RSMTP apresentadas, em especial os Algoritmos Genéticos, ostentam resultados computacionais de qualidade superior às apresentadas pelas melhores heurísticas da literatura atual.