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

Autor(es)

C.H. SAMORA ; F.L. USBERTI ; C. LYRA

• Tipo de documento: Artigo Científico
• Fonte: TEMA (São Carlos); v. 19, n. 3, p. -, Dez. 2018.

Resumo

RESUMO Este trabalho propõe novas formulações para o problema de cobertura por hubs capacitado de alocação única com custo fixo. O 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 redução do espaço de busca. 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 de um dos modelos de referência da literatura, foi capaz de aprimorar os limitantes primais e duais sob limites de tempo de execução e de consumo de memória. (AU)

• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Linha de fomento: Auxílio à Pesquisa - Temático