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

Autor(es)

C.H. SAMORA ^[1] ; F.L. USBERTI ^[2] ; C. LYRA ^[3]

Afiliação do(s) autor(es)

^[1] Universidade Estadual de Campinas. Faculdade de Engenharia Elétrica e de Computação - Brasil

^[2] Universidade Estadual de Campinas. Instituto de Computação - Brasil

^[3] Universidade Estadual de Campinas. Faculdade de Engenharia Elétrica e de Computação - Brasil

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

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
• Modalidade de apoio: Auxílio à Pesquisa - Temático