Exact solution method for stochastic single-allocation hub location problems

This paper presents an efficient exact solution procedure for a general stochastic hub location 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. • A hub location problem with uncertainties in hubs, OD-flows, and arcs is studied. • Some stochastic versions are proven to be reduced to the deterministic problems. • A compact MILP formulation is proposed for this problem. • Families of valid inequalities are proposed to reinforce this formulation. • Smart separation methods for some of these families has been designed.