Publication
RAMP para o Problema de Localização de Hubs com Afetação Múltipla e sem Restrições de Capacidade
| datacite.subject.fos | Informática | pt_PT |
| dc.contributor.advisor | Gamboa, Dorabela Regina Chiote Ferreira | |
| dc.contributor.author | Maia, Fábio José Magalhães | |
| dc.date.accessioned | 2018-03-12T18:03:32Z | |
| dc.date.available | 2018-03-12T18:03:32Z | |
| dc.date.issued | 2011 | |
| dc.date.submitted | 2011 | |
| dc.description.abstract | 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. | pt_PT |
| dc.identifier.tid | 201851199 | pt_PT |
| dc.identifier.uri | http://hdl.handle.net/10400.22/11101 | |
| dc.language.iso | por | pt_PT |
| dc.subject | Localização de Instalações | pt_PT |
| dc.subject | Localização de Hubs | pt_PT |
| dc.subject | UFLP | pt_PT |
| dc.subject | UMAHLP | pt_PT |
| dc.subject | RAMP | pt_PT |
| dc.subject | Relaxação Matemática | pt_PT |
| dc.title | RAMP para o Problema de Localização de Hubs com Afetação Múltipla e sem Restrições de Capacidade | pt_PT |
| dc.type | master thesis | |
| dspace.entity.type | Publication | |
| rcaap.rights | openAccess | pt_PT |
| rcaap.type | masterThesis | pt_PT |
| thesis.degree.name | Mestrado em Engenharia Informática | pt_PT |
Files
Original bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- DM_FabioMaia_MEI_2011.pdf
- Size:
- 2.36 MB
- Format:
- Adobe Portable Document Format
- Description:
- DM_FabioMaia_MEI_2011
License bundle
1 - 1 of 1
No Thumbnail Available
- Name:
- license.txt
- Size:
- 1.71 KB
- Format:
- Item-specific license agreed upon to submission
- Description: