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 reasona
ble time on a desktop computer. The approach begins with a previously propo
sed tight linear programming formulation and uses subgradient optimization
on a lagrangian relaxation of the model. However, to dramatically improve t
he performance of this approach, we augment a subproblem of the lagrangian
relaxation model with a cut constraint. In computational experiments on eig
hty-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 minut
es.