Relaxação Lagrangeana Aplicada ao Problema de Cobertura por Hubs

Abstract

Este trabalho tem por objetivo investigar e propôr novas formulações para o problema de cobertura por hubs capacitado de alocação única com custo fixo. Este problema envolve a localização de nós hubs e a atribuição de nós de demandas aos hubs de modo que o tempo de percurso entre qualquer par de nós origem-destino não exceda a janela máxima de tempo e a capacidade de processamento dos hubs. Uma relaxação Lagrangeana é proposta e através do método do subgradiente são obtidos limitantes primais e duais. Para acelerar o método subgradiente, uma heurística construtiva primal fornece boas soluções de partida, além disso, foi realizada uma etapa de pré-processamento das instâncias para a eliminação de variáveis dos modelos. Experimentos computacionais foram realizados com um conjunto de instâncias reais da "Australian Post". Os resultados indicam que a relaxação lagrangeana proposta, quando comparada com a solução do modelo da literatura, foi capaz de aprimorar os limitantes primais e duais sob limites de tempo de execução e de consumo de memória.