[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%.
| Identifer | oai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:14550 |
| Date | 04 November 2009 |
| Creators | GLEIDSON FONSECA SOARES |
| Contributors | MARCUS VINICIUS SOLEDADE POGGI DE ARAGAO |
| Publisher | MAXWELL |
| Source Sets | PUC Rio |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | TEXTO |
Page generated in 0.0023 seconds