Relaxações e método de decomposição para alguns problemas de localização de facilidades modelados em grafos

• Ano de defesa: 2008
• Autor(a) principal: Francisco de Assis Corrêa
• Orientador(a): Luiz Antonio Nogueira Lorena
• Banca de defesa: Edson Luiz França Senne, Nelio Domingues Pizzolato, Reinaldo Morabito Neto
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Instituto Nacional de Pesquisas Espaciais
• Programa de Pós-Graduação: Programa de Pós-Graduação do INPE em Computação Aplicada
• País: BR
• Resumo em Inglês: Despite the great advances in computational equipment and the best known techniques for solving combinatorial optimization problems, it is not always possible to find the optimum solution to some practical facility location problems in a reasonable computational time, due to their size and classification issues. This thesis explores the representation of problem constraints in graphs and a graph partitioning strategy to solve facility location problems, using a relaxation and decomposition approach. Two problems were considered: the Uncapacitated Facility Location Problem and the Queueing Maximal Covering Location-Allocation Model. For both problems the Lagrangean Relaxation with Clusters (LagClus) and a Column Generation Method have been applied. The first has been modeled by a conflict graph. The second has been modeled by a covering graph that produces a smaller quantity of relaxed or coupling constraints for this problem, to obtain better bounds. Traditional lagrangean relaxation and linear programming relaxation have been applied to these problems in order to obtain values to compare with the results of the LagClus and Column Generation. The Queueing Maximal Covering Location-Allocation Model has also been solved using the Constructive Genetic Algorithm and the Clustering Search. The computational tests report interesting results for instances from the literature and significant conclusions are described.
• Link de acesso: http://urlib.net/sid.inpe.br/mtc-m18@80/2008/08.28.19.58

Apesar do grande avanço na área de hardware computacional e das melhores técnicas atuais para a resolução de problemas de otimização combinatória, nem sempre é possível a obtenção do ótimo global para alguns problemas práticos de localização de facilidades em um tempo computacional aceitável devido à classificação como NP-hard e ao porte do problema. Esta tese explora a representação de restrições de problemas em grafos e uma estratégia de particionamento para resolver problemas de localização de facilidades, usando relaxações e método de decomposição. São abordados dois problemas de localização de facilidades: o Problema de Localização de Facilidades não-Capacitado e o Problema Probabilístico de Localização-Alocação de Máxima Cobertura. Para os dois foram aplicados a Relaxação Lagrangeana com Clusters (LagClus) e um Algoritmo de Geração de Colunas. O primeiro problema foi modelado por meio de um grafo de conflitos. O segundo foi modelado por um grafo de cobertura, pois, devido às características do problema, gera uma quantidade menor de restrições relaxadas ou de acoplamento, permitindo a obtenção de melhores limitantes. A relaxação lagrangeana tradicional e a relaxação de Programação Linear também foram aplicadas a esses problemas, de forma a obter valores para comparar com os resultados da LagClus e da Geração de Colunas. O Problema Probabilístico de Localização-Alocação de Máxima Cobertura foi ainda resolvido usando o Algoritmo Genético Construtivo (AGC) e o Clustering Search (CS). Os testes computacionais em instâncias da literatura mostram resultados interessantes, e significativas conclusões são apresentadas.