Author(s): Matos, Telmo Manuel Sampaio Pinto de
Date: 2011
Persistent ID: http://hdl.handle.net/10400.22/11098
Origin: Repositório Científico do Instituto Politécnico do Porto
Subject(s): Localização de Instalações,; Primal-Dual; RAMP; CFLP; UFLP; Informática
Os 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.
Facility Location Problems (FLP) are complex combinatorial optimization problems which general goal is to locate a set of facilities that serve a particular set of customers with minimum cost. Being NP-Hard problems, using exact methods to solve large instances of these problems can be seriously compromised by the high computational times required to obtain the optimal solution. To overcome this difficulty, a significant number of heuristic algorithms of various types have been proposed with the aim of finding good quality solutions in reasonable computational times. We propose RAMP (Relaxation Adaptive Memory Programming) approaches for two FLP problems: the Uncapacitated Facility Location Problem (UFLP) and the Capacitated Facility Location Problem (CFLP). The success obtained with the simplest level of the RAMP framework applied to the UFLP, suggested that an application of a more sophisticated level of RAMP to the same problem should improve the results. This expectation was confirmed by the excellent results obtained by this new RAMP application to the UFLP. Guided by the success of the RAMP applications to the UFLP we proposed a new approach for the CFLP. The RAMP algorithm for the CFLP produced very good results in comparison with the best algorithms in the literature, demonstrating the potential of RAMP for new applications to other extensions and variations of Facility Location Problems.
