An Efficient Procedure for Designing Single Allocation Hub and Spoke Systems
提出一种结合线性规划与拉格朗日松弛的方法，通过添加切割约束来高效设计枢纽网络，在84个标准测试中平均误差仅0.048%，求解时间在5分钟内。
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.