An efficient procedure for designing single allocation hub and spoke systems

Given the widespread use of the hub and spoke network architecture and its growing importance to competitiveness in logistics, communication, and mass transportation, there has been considerable interest by practitioners and researchers alike in finding efficient methods for designing such networks. This paper provides a method that delivers both high quality solutions and firm measures of that quality, and allows problems to be solved in reasonable time on a desktop computer. The approach begins with a previously proposed tight linear programming formulation and uses subgradient optimization on a lagrangian relaxation of the model. However, to dramatically improve the performance of this approach, we augment a subproblem of the lagrangian relaxation model with a cut constraint. In computational experiments on eighty-four standard test problems, average gaps are 0.048%. Maximum gaps are under 1% while average solution times on a Pentium-166 are under five minutes.