Hub Network Design Problem with Capacity, Congestion and Stochastic Demand Considerations

We introduce the hub network design problem with congestion, capacity, and stochastic demand considerations (HNDC), which generalizes the classical hub location problem in several directions. In particular, we extend state-of-the-art by integrating capacity acquisition decision and congestion cost effect into the problem and allowing dynamic routing for origin-destination pairs. Connecting strategic and operational level decisions, HNDC jointly decides hub locations and capacity acquisitions by taking the expected routing and congestion costs into account. A path-based mixed-integer second-order cone programming (SOCP) formulation of the HNDC is proposed. We exploit SOCP duality results and propose an exact algorithm based on Benders decomposition and column generation to solve this challenging problem. We use a specific characterization of the capacity-feasible solutions to speed up the solution procedure and develop an efficient branch-and-cut algorithm to solve the master problem. We conduct extensive computational experiments to test the performance of the proposed approach and to derive managerial insights based on realistic problem instances adapted from the literature. In particular, we found that including hub congestion costs, accounting for the uncertainty in demand, and whether the underlying network is complete or incomplete have a significant impact on hub