[pt] Uma facilidade é qualquer centro que presta serviços a um conjunto de clientes. Pode ser, dentre outros, uma escola, uma fabrica ou um armazém. Problemas de localização de facilidades são problemas de otimização combinatória que tratam da tomada de decisão relativa ao posicionamento destes serviços, que devem otimizar algum critério pré-definido. As medidas que usualmente são utilizadas para quantificar a qualidade de uma solução para esta classe de problemas tem seus cálculos baseados em que clientes são servidos por que facilidade. Uma conseqüência imediata é a forte relação entre os problemas de localização e os problemas de classificação de dados (clusterização). Dentre os problemas de localização de facilidades amplamente estudados esta o problema das p-Medianas (PMNC), objeto de pesquisa desta dissertação. O PMNC tem como objetivo determinar quais p facilidades devem ser abertas com o intuito de minimizar a soma das distancias de cada cliente a facilidade aberta mais próxima do mesmo. O PMNC é classificado como um problema NP - Difícil e é um dos problemas centrais na classificação automática de dados (clusterização). Esta dissertação apresenta algoritmos primais, duais e exatos para tratamento do PMNC, focando no desenvolvimento de algoritmos duais e exatos. Foram implementadas cinco heurísticas construtivas e um método de busca local. Além disto, foram propostos três novos métodos duais e um método exato. Como resultado, analisamos um conjunto de técnicas para o tratamento do problema. A escolha da melhor técnica é fortemente dependente da configuração da instancia tratada. Foi obtido o ótimo para algumas instancias e para as demais a diferença entre o valor dos limites inferior e superior nos melhores casos não ultrapassam 3%. / [en] A facility is any center that offers services to a set of clients. It may be, among others, a school, a factory or a depot. Facility location problems are combinatorial optimization problems that handle decisionmaking in respect to the positioning of those services, optimizing some defined criteria. The measures often used to assess the quality of a solution for this class of problems relate to which clients are served by which facility. An immediate consequence is the strong relationship between location problems and data clustering. One of the widely studied facility location problems is the uncapacited p-median problem (UPM), the main subject of this thesis. Given a set of possible facility locations, the UPM consists in determining a subset of locations at which the facilities shall be established, minimizing the sum of distances from each client to its closest open facility. The UPM belongs to the class of NP-hard problems and is a central problem of data clustering. This thesis presents primal, dual and exact algorithms for approaching the UPM, focusing on the development of dual and exact algorithms. Five constructive heuristics and one local search method were implemented. Furthermore, three new dual methods and one exact method were proposed. The result is the analysis of a set of techniques to solve the problem. The choice of best technique is strongly dependent of the configuration of the treated instance. We obtained the optimum for some instances and for others the difference between the value of the lower and upper bounds in the best cases do not exceed 3%.

[pt] A relação entre as atividades logísticas desempenhadas nas empresas de telecomunicações e sua prestação de serviço parece, para o público em geral, estarem desassociadas. Entretanto, a necessidade de atendimento de áreas extensas associadas a redução custos, coloca essas atividades, ditas não-essenciais, no grupo de atividades estratégicas. Através da introdução do ambiente de telecomunicações brasileiro, da importância da logística para este serviço e do estudo de problemas de localização, a presente dissertação de mestrado desenvolve um modelo MIP - Mix Integer Programming – dinâmico para o problema de localização de hubs conhecido como: ULP - Uncapacitated Hub Location Problem, sendo este modelo utilizado na análise de um estudo de caso real de uma operadora de serviços de telecomunicações via satélite, onde foram obtidos insights quanto o nível de redução de custo através do redesenho da rede de distribuição e da escolha de novos pontos de armazenagem, sendo comprovados através um estudo estocástico com 500 cenários aleatórios. / [en] The relationship between logistics activities performed on telecommunications companies and their service delivery seems, to the public, is disassociated. However, the need to service large areas associated with reducing costs, puts these activities nonessential into to the group of strategic activities. Through the introduction of the Brazilian telecommunications environment, the importance of logistics for this service and the study location problems, this master thesis develops a dynamic MIP model - Mix Integer Programming - for the hub location problem known as ULP - Uncapacitated Hub Location Problem, and this model is used in the analysis of a real case study of an satellite telecommunications operator. which were obtained insights into the level of reducing cost by redesigning of distribution network and the choice of new warehouse points, being demonstrated by a stochastic study of 500 random scenarios.