Relaxa??o Lagrangeana Aplicada ao Problema de Cobertura por Hubs

摘要

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.