Hub network design problem with capacity, congestion, and stochastic demand considerations

Abstract

Our study introduces 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 decisions and congestion cost effect into the problem and allowing dynamic routing for origin-destination (OD) pairs. Connecting strategic and operational level decisions, HNDC jointly decides hub locations and capacity acquisitions by considering the expected routing and congestion costs. 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 proposed approach's performance and 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 network design and the resulting performance of the system.