Relaxações e método de decomposição para alguns problemas de localização de facilidades modelados em grafos / Relaxations and decomposition approach for some facility location problems modeled by graphs

AUTOR(ES)

Francisco de Assis Corrêa

DATA DE PUBLICAÇÃO

2008

RESUMO

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.

ASSUNTO(S)

relaxação lagrangeana com clusters localização de facilidades column generation algorithm facility location graph partitioning lagrangean relaxations with clusters relaxação lagrangeana lagrangean relaxation algoritmo de geração de colunas particionamento de grafos

Documentos Relacionados

• Relaxações e método de decomposição para alguns problemas de localização de facilidades modelados em grafos
• Relaxações e método de decomposição para alguns problemas de localização de facilidades modelados em grafos
• Relaxação langrangena com divisão em clusters para alguns problemas de otimização modelados em grafos de conflitos
• Relaxação langrangena com divisão em clusters para alguns problemas de otimização modelados em grafos de conflitos
• Heuristic location-allocation for facilities location problems