LOCALIZAÇÃO DE HUBS COM ROTEAMENTO DE DEMANDAS: UMA PROPOSTA DE SOLUÇÃO ATRAVÉS DA METAHEURÍSTICA BRKGA
Problema de Localização de Hub, Roteamento de demandas, Metaheurística BRKGA, Otimização Combinatória, NP-Difícil. |
Este trabalho apresenta uma proposta de solução através de uma metaheurística populacional para o problema de localização de hub e roteamendo de demandas (Hub Location-Routing Problem - HLRP), problema este de otimização combinatória classificado como NP-Dificil. Os hubs são instalações usadas para tratar e despachar recursos em uma determinada rede. O objetivo do Hub Location-Routing Problem é localizar um conjunto de hubs em uma rede e rotear recursos de origens para destinos, de forma que o custo total de atender a todas as demandas seja minimizado. Neste contexto, tratamos o problema de localização de hub com roteamendo de demandas em rotas circulares, formando estas rotas a nível de cluster (o hub e seus spokes alocados) e a nível de hubs. A proposta de solução consiste na customização e aplicação da metaheurística Biased Random-Key Genetic Algorithm (BRKGA) para o problema. Para validação dos resultados um grupo de instâncias já conhecidas na literatura foram utilizadas. Os principais parâmetros da metaheurística foram ajustados com o uso do software IRACE (Iterated Race for Automatic Algorithm Configuration). Os resultados obtidos mostraram que a metaheurística BRKGA implementada foi bastante competitiva quando comparada a resultados desponibilizados na literatura, pois o método foi capaz de produzir melhores soluções para algumas instâncias do problema com valores ótimos desconhecidos.