Esta tese define os problemas das p-medianas conectadas e o de localização de facilidades não-capacitadas conectadas. Possíveis aplicações incluem problemas de planejamento regional e o projeto de redes de telecomunicações ou de transporte. Para o primeiro problema, duas formulações de programação linear inteira são apresentadas e comparadas. Um destes modelos é adaptado para o segundo problema. Para o problema das p-medianas conectadas, algoritmos aproximados são desenvolvidos. Uma estratégia de busca local híbrida é proposta. Para acelerar as iterações do algoritmo de busca local, idéias como circularidade, melhoria iterativa e o descarte de vizinhos são incorporadas. Heurísticas GRASP e VNS são desenvolvidas incluindo a utilização de um filtro com o objetivo de diminuir os tempos de processamento e do procedimento de reconexão por caminhos com o objetivo de melhorar a qualidade das soluções encontradas. Diversos testes são realizados comparando-se esses algoritmos. Os resultados mostraram a necessidade de se executar um passo adicional de pós-otimização às heurísticas GRASP e VNS propostas.