Stochastic single-allocation hub location

This paper considers the single allocation hub location problem under demand uncertainty where the allocation of the spokes to the hubs is optimized as second stage decision after the uncertainty in the demand is realized. We refer to this case as the variable allocation case, meaning that the allocation of the spokes to the hubs can be altered after the uncertainty is realized. This is in contrast to the fixed allocation case that is addressed in the literature, where the spokes are allocated to the chosen hubs before the uncertainty is realized. As shown in the paper, the fixed allocation case can be solved as a deterministic problem using the expected values of the random variables. However, the variable allocation model is a two-stage stochastic program that is challenging to solve. An alternative convex mixed-integer nonlinear formulation is presented for the variable allocation and a customized solution approach based on cutting planes is proposed to address the computational challenges. The proposed solution approach is implemented in a branch-and-cut framework where the cut-generating subproblems are solved combinatorially, i.e. without an optimization solver. Extensive computational results on the single allocation hub location problem and two of its variants, the capacitated case and the single allocation p-median problem are presented. The proposed cutting plane approach outperforms the direct solution of the problem using the state-of-the-art solver GUROBI as well the L-shaped decomposition, which is a common approach for addressing two-stage stochastic programs with recourse.