ESTG - DM - Engenharia Informática
URI permanente para esta coleção:
Navegar
Percorrer ESTG - DM - Engenharia Informática por orientador "Gamboa, Dorabela Regina Chiote Ferreira"
A mostrar 1 - 4 de 4
Resultados por página
Opções de ordenação
- Algoritmos RAMP para o Problema de Localização de Instalações com Restrições de Capacidade e um Único ServidorPublication . Oliveira, Óscar António Maia de; Gamboa, Dorabela Regina Chiote FerreiraOs Problemas de Localização de Instalações são problemas de otimização combinatória complexos que têm centrado a atenção da comunidade científica. A importância dada à resolução destes problemas deve-se principalmente à sua relevância nas mais variadas áreas, tais como, economia, indústria, saúde, entre muitas outras. Neste estudo é considerado o Problema de Localização de Instalações com Restrições de Capacidade e um Único Servidor (Single Source Capacitated Facility Location Problem - SSCFLP). No SSCFLP, dado um conjunto de possíveis localizações para a abertura de instalações e um conjunto de clientes a servir, o objetivo é determinar que instalações abrir de forma a satisfazer com custo mínimo a procura dos clientes, garantindo que cada cliente é servido apenas por uma instalação. Neste problema são considerados os custos de abertura das instalações e os custos de afetação dos clientes. O SSCFLP tem várias aplicações práticas, como por exemplo, no planeamento de sistemas de distribuição e na conceção de redes informáticas. Os métodos exatos conseguem garantir a obtenção da solução ótima dos problemas à custa de recursos computacionais elevados, tornando pertinente a investigação de abordagens alternativas, nomeadamente heurísticas/metaheurísticas, que permitam com recursos mais reduzidos, a obtenção de soluções de elevada qualidade. As heurísticas/metaheurísticas têm centrado a sua atenção apenas num dos lados do espaço de soluções dos problemas de otimização combinatória. A dualidade dos problemas tem sido, maioritariamente, utilizada para a criação de soluções iniciais para uma exploração mais intensiva do espaço de soluções por parte de heurísticas primais. A metaheurística RAMP (Relaxation Adaptive Memory Programming), proposta por Rego [1], pretende criar algoritmos que explorem de forma mais eficiente a relação primal-dual dos problemas de otimização combinatória, permitindo, de forma iterativa, a manipulação da informação que é obtida de ambos os lados do espaço de soluções. A aplicação do método RAMP a vários problemas de otimização combinatória, demonstrou a enorme potencialidade desta metaheurística, obtendo algoritmos de estado-da-arte para todos esses problemas. O objetivo deste trabalho é verificar se a aplicação do método RAMP ao SSCFLP também é capaz de rivalizar com outros métodos propostos para a resolução deste problema. Neste trabalho, são apresentados dois novos algoritmos para a resolução do SSCFLP, ambos baseados no método RAMP, que designamos por Dual RAMP e PD-RAMP. O primeiro algoritmo (Dual RAMP) segue a abordagem RAMP na sua versão mais simples. O Dual RAMP baseia-se na resolução do dual lagrangeano do SSCFLP, através de otimização por subgradiente. A solução dual é projetada para o espaço de soluções primal através da aplicação de um método simples de projeção, e a solução primal obtida é sujeita a um método de melhoramento baseado numa abordagem simples da pesquisa tabu. Iterativamente, a informação obtida do lado primal é utilizada para o ajuste dos parâmetros do dual. O segundo algoritmo (PD-RAMP) baseia-se numa versão mais sofisticada da abordagem RAMP. Este algoritmo integra o Dual RAMP com um método evolutivo de forma a fortalecer a relação primal-dual do problema. Na implementação proposta, o método primal do PDRAMP é baseado numa pesquisa por dispersão com um conjunto de referência atualizado por ambos os lados, primal e dual. Os resultados obtidos pelo Dual RAMP e pelo PD-RAMP permitem concluir que a aplicação da metaheurística RAMP ao SSCFLP consegue resultados excelentes, obtendo soluções de elevada qualidade em tempos computacionais reduzidos. Acresce ainda o facto de, ao contrário da maioria das abordagens existentes na literatura, ambos os algoritmos propostos demonstrarem ser extremamente robustos, conseguindo muito bons resultados para todos os conjuntos de testes utilizados.
- Algoritmos RAMP para o problema P-MedianPublication . Veloso, José Carlos Sousa; Gamboa, Dorabela Regina Chiote FerreiraA vasta aplicabilidade dos Problemas de Localização de Instalações em variados cenários do mundo real (como a escolha da localização de um hospital ou armazém) associada à complexidade de resolução caraterística destes problemas, atrai grande atenção por parte da comunidade científica, que procura continuamente novos métodos de resolução, mais eficazes e eficientes. O presente trabalho incide naquele que é considerado um dos Problemas de Localização de Instalações mais estudado: o problema P-Median. Este problema tem por finalidade a escolha de um conjunto de p instalações (medianas) de entre um conjunto de instalações candidatas, de modo a minimizar o somatório da distância de cada cliente à respetiva mediana mais próxima. Uma vez que a resolução deste problema através de métodos exatos implica recursos computacionais elevados, com alguma naturalidade surgem abordagens heurísticas, que garantem boas soluções com recursos computacionais reduzidos. Neste estudo são apresentados dois novos algoritmos para a resolução do problema PMedian baseados na metaheurística RAMP (Relaxation Adaptive Memory Programming), caraterizada pela sua eficiente exploração dos espaços primal e dual de um problema. Os novos algoritmos propostos, Dual-RAMP e PD-RAMP, produzem resultados de qualidade que demonstram o sucesso da abordagem RAMP na resolução do problema PMedian.
- RAMP para o Problema de Localização de Hubs com Afetação Múltipla e sem Restrições de CapacidadePublication . Maia, Fábio José Magalhães; Gamboa, Dorabela Regina Chiote FerreiraOs 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.
- RAMP para o problema de localização de instalações com restrições de capacidadePublication . Matos, Telmo Manuel Sampaio Pinto de; Gamboa, Dorabela Regina Chiote FerreiraOs problemas de Localização de Instalações fazem parte do conjunto de problemas complexos de otimização combinatória em que o objetivo é a determinação de um conjunto de localizações onde colocar instalações, de forma a satisfazer a procura de um determinado número de clientes com custo mínimo. Tratando-se de problemas NP-difíceis, a utilização de métodos exatos na resolução de problemas de grande dimensão pode ser seriamente comprometida pelos tempos computacionais elevados para a obtenção da solução ótima. Para ultrapassar esta dificuldade, um número significativo de algoritmos heurísticos de vários tipos têm sido propostos com o objetivo de encontrarem soluções de boa qualidade em tempos tão reduzidos quanto possível. Neste trabalho é explorada a aplicação da abordagem RAMP (Relaxation Adaptive Memory Programming) a dois problemas de localização de instalações: o problema de Localização de Instalações sem Restrições de Capacidade (Uncapacitated Facility Location Problem – UFLP) e o problema de Localização de Instalações com Restrições de Capacidade (Capacitated Facility Location Problem – CFLP). O sucesso obtido com a versão mais simples da abordagem RAMP ao UFLP, tornou interessante a exploração de uma nova abordagem RAMP, com um nível de sofisticação mais elevado, que produziu resultados ainda mais competitivos, dos que os conseguidos com a versão inicial. Como a aplicação da abordagem RAMP ao UFLP produziu muito bons resultados, foi proposta uma nova aplicação, neste caso ao CFLP. O algoritmo RAMP desenvolvido obteve resultados muito competitivos com os melhores da literatura, evidenciando, novamente, o potencial desta abordagem para outras extensões e variantes dos problemas de localização de instalações.