Lagrangian relaxation based approaches to capacitated hub-and-spoke network design problem

The main purpose of this paper is to introduce the capacitated hub-and-spoke network design problem in which hubs have limited capacity for channelling flows between the nodes served by the system. The problem is formulated under a networking policy allowing both direct (nonstop) and hub connected (one-hub-stop and two-hub-stop) services between the nodes. A branch and bound algorithm and a heuristic procedure partitioning the set of solutions on the basis of hub locations are presented. In both algorithms, after identifying a set of hub locations, the problem is reduced into a smaller routing problem. Subgradient optimization is then applied to a Lagrangian relaxation of the reduced problem. The model and the proposed algorithms were applied to the air transportation system using data on passenger flows between the top forty US cities in 1989 (accounting for 73.32% of the surveyed passenger flow). Computational results from 141 problems suggest that both algorithms are effective at finding good solutions to this problem.