New approaches for the two-level facility location problem: models and algorithms

Abstract

Esta tese investiga a aplicação de algoritmos exatos e heurísticos para a resolução de diferentes variantes do problema de localização de facilidades em dois níveis, versões estas poucos estudadas pela literatura. Trata-se de um tema de grande importância dentro da área de Otimização de Sistemas de Grande Porte, tendo ainda ampla aplicação em diversos sistemas logísticos existentes. De forma geral, o problema consiste em selecionar de um conjunto de locais candidatos um subconjunto de pontos que atuarão ou como suprimento ou como transbordo no atendimento, a custo mínimo de instalação e transporte, de clientes espalhados geograficamente. Nas variantes estudadas, a rede de atendimento ou distribuição é hierarquizada, sendo formada por um primeiro nível composto por facilidades que suprem as demandas dos clientes via pontos de transbordo pertencentes ao segundo nível. As três variantes estudadas do problema são: (i) a versão na qual facilidades e transbordos são não capacitados; (ii) o caso no qual a demanda dos clientes varia num horizonte de planejamento discretizado em períodos, resultando num problema de localização multi-período ou dinâmico; (iii) e a alternativa que considera custos adicionais oriundos dos efeitos de congestionamento em função do acúmulo de fluxo nas facilidades e pontos de transbordo. Em todas as variantes investigadas consideram-se duas possibilidades de interligação entre o primeiro e segundo níveis. Na alocação simples, um ponto de transbordo só pode interagir com uma única facilidade; enquanto, na atribuição múltipla, um ponto de transbordo pode estar conectado com um número qualquer de facilidades. Como o grande desafio destes tipos de problemas é a natureza combinatória deles, para cada uma das variantes estudadas, modelos matemáticos e métodos especializados baseados na decomposição de Benders e GRASP foram propostos e avaliados tanto em relação ao tempo computacional quanto à qualidade das soluções obtidas.