| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| DM_FabioMaia_MEI_2011 | 2.36 MB | Adobe PDF |
Authors
Advisor(s)
Abstract(s)
Os Problemas de Localização de Instalações (Facility Location Problems – FLP) são
problemas complexos que assumem um grande foco de estudo por parte da comunidade
científica. Os FLP têm várias aplicações no mundo real e em diversas ´áreas, tais como,
telecomunicações, redes de computadores, redes de transporte, rede elétrica, localização
de hospitais, localização de aeroportos, entre muitos outros.
O Problema de Localização de Hubs com Afetação múltipla e Sem Restrições de Capacidade
(Uncapacitated Multiple Allocation Hub Location Problem – UMAHLP) faz parte do
grupo de problemas de localização extensivamente estudados. Tratando-se de um problema
de otimização combinatória NP-difícil, a utilização de métodos exatos na resolução
de problemas práticos de grande dimensão pode ser seriamente comprometida pelos tempos
computacionais necessários para a obtenção da solução ótima. Para ultrapassar esta
dificuldade, um número significativo de algoritmos heurísticos têm sido propostos com o
objetivo de encontrar soluções de boa qualidade em tempos tão reduzidos quanto possível.
O sucesso da metaheurística Relaxation Adaptive Memory Programming (RAMP) aplicada
ao Problema de Localização de Instalações sem Restrições de Capacidade (Uncapacitated
Facility Location Problem – UFLP) apresenta esta abordagem como bastante
promissora na aplicação a outros problemas de localização. O UMAHLP ´e um exemplo
clássico destes problemas.
Neste contexto, pretende-se com este estudo, explorar as vantagens da aplicação da abordagem
RAMP ao UMAHLP. A abordagem RAMP baseia-se na exploração da relação
primal-dual do problema, orientando a pesquisa com base em princípios de memória
adaptativa. O m´etodo RAMP faz uso de vários níveis de sofisticação, definidos pelo grau
de intensidade que são explorados os lados primal e dual do problema. Deve-se começar
pela implementação da versão mais simples do método e só avançar para formas mais
complexas, caso seja necessário, uma vez que o método RAMP é incremental.
Para o UFLP foram implementados dois algoritmos, um com base na metaheurística
Pesquisa por Dispersão (Scatter Search – SS) e outro tendo por base a versão mais sofisticada
do método RAMP, designada de PD-RAMP, que explora intensivamente ambos os
lados da relação primal-dual. O algoritmo PD-RAMP implementado engloba uma versão
mais simples do algoritmo SS proposto, para explorar o espaço de soluções do lado primal,
sendo o lado dual explorado pelo método Dual-Ascent. No UMAHLP foi aplicada uma
versão mais simples do RAMP, intensificando a exploração do lado dual do Problema,
através do método Dual-Ascent, enquanto que o lado primal é explorado, de uma forma
mais simples, tendo por base o método de Pesquisa Tabu (Tabu Search – TS).
A aplicação do método RAMP aos problemas UFLP e UMAHLP, revelou-se muito robusta
e eficiente, demonstrando bons resultados para as instâncias de teste padrão existentes
para cada um dos problemas. Em ambos os problemas tratados os algoritmos propostos
conseguem encontrar a maior parte das melhores soluções conhecidas, obtendo excelentes
resultados. Para o UMAHLP são encontradas duas soluções melhores do que as conhecidas.
O método RAMP demonstrou, mais uma vez, ser uma metaheurística, que apesar de ser
recente, já apresenta um elevado nível de sucesso na resolução de problemas complexos.
Description
Keywords
Localização de Instalações Localização de Hubs UFLP UMAHLP RAMP Relaxação Matemática