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

Autor: SAMORA, C.H., USBERTI, F.L., LYRA, C.
Jazyk: angličtina
Rok vydání: 2018
Předmět:
Zdroj: TEMA, Vol 19, Iss 3, Pp 547-558 (2018)
TEMA (São Carlos) v.19 n.3 2018
TEMA (Sociedade Brasileira de Matemática Aplicada e Computacional. Online)
Sociedade Brasileira de Matemática Aplicada e Computacional
instacron:SBMAC
TEMA (São Carlos), Volume: 19, Issue: 3, Pages: 547-558, Published: DEC 2018
ISSN: 2179-8451
Popis: 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. ABSTRACT This paper proposes new formulations for the single allocation fixed-cost hub covering problem. This problem concerns on determining the location of hubs and the assignment of demand nodes to hubs, respecting the hubs capacities and maintaining the traversal time between any pair of nodes within a time-window. A Lagrangean relaxation is proposed and through the subgradient method, lower and upper bounds are obtained. To improve the method performance, a primal constructive heuristic obtains good warm-start solutions. In addition, a pre-processing reduces the solution space. Computational experiments were conducted with a set of real-life instances from the Australian Post. The results indicate that the proposed Lagrangean relaxation, when compared with the solution of reference model from literature, was capable of improving the upper and lower bounds, under restrictions on the execution time and memory usage.
Databáze: OpenAIRE
Externí odkaz: