Exact solution method for stochastic single-allocation hub location problems

Abstract

problem with single allocation, incorporating uncertainties in origin–destination flows, transportation costs, and hub capacities. A scenario-based model is used to minimize the expected overall costs, requiring two decisions: (i) the location of hubs, which remains fixed across all scenarios; and (ii) the allocation of each origin/destination to one of these hubs in each scenario. We propose a compact mixed-integer linear programming formulation strengthened by valid inequalities. A branch-and-cut algorithm is developed to obtain optimal solutions, starting with a constraint-relaxed formulation after applying a preprocessing phase to fix variables, followed by the addition of cuts via smart separation methods. Computational results demonstrate that this solution procedure outperforms existing methods, even for specialized versions of the model introduced in this paper.