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.