Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-graduação em Engenharia de ProduçãoNeste trabalho são implementadas e analisadas as heurísticas de Teitz e Bart, Busca Tabu e Algoritmo Genético aplicadas ao problema das p-medianas. O objetivo foi avaliar o desempenho dos algoritmos em redes pequenas, médias e grandes levando-se em consideração o valor da solução e o tempo de resolução. Para isso foram realizados testes em 115 problemas gerados aleatoriamente. Os resultados demonstraram bom desempenho dos algoritmos de Busca Tabu e Algoritmo Genético em redes pequenas e médias. Já em problemas de grande porte, o algoritmo de Teitz e Bart modificado forneceu melhores respostas em menor tempo.