Two-Stage Adaptive Robust Hub Location Problem Under Demand Uncertainty

This paper studies a two-stage adaptive robust hub location problem with multiple assignments under demand uncertainty. In our setting, the capacitated hubs are strategically located in the first stage to minimize the worst-case scenario cost over a budgeted uncertainty set, and the routing decisions, which are adaptive to uncertainty realizations, are made in the second stage to transport all commodities. For the large-scale instances of the problem, we develop a novel column-and-constraint generation approach that integrates Benders decomposition. In this approach, we design a customized Benders decomposition to efficiently solve the master problem involving a subset of uncertain scenarios, in which a tailored cutting plane algorithm is developed to solve Benders dual subproblems and a cut refinement strategy is proposed to generate strong Benders cuts. Besides, to quickly identify possible uncertain scenarios, we reformulate the second-stage problem into a more tractable form, which is further simplified by significantly reducing the number of redundant variables and constraints. Extensive computational experiments on the well-known instances with up to 200 nodes are conducted to evaluate the effectiveness of proposed model and the performance of the solution method. The computational results demonstrate that our developed solution method outperforms the conventional column-and-constraint generation or Benders decomposition. Compared with the two-stage stochastic programming model, our proposed model can provide more reliable and robust solutions with superior out-of-sample performance. The results also illustrate the effect of uncertainty budgets and highlight the advantages of incorporating features such as hub capacity and multiple assignments into our model. Moreover, we make extensions by applying our framework to handle more general polyhedral uncertainty sets.