A robust approach to the capacitated hub location problem: a budget uncertainty perspective

Formulations for the robust capacitated single and multiple allocation hub location problems under polyhedral demand uncertainty are proposed and corresponding solutions with budget uncertainty are discussed. We first develop a generic framework and show that a problem with data variability only in the objective a) can be modelled directly as a minimisation problem and b) has an equivalent nonlinear MIP formulation if deterministic and robust optimal solutions happen to be frequently the same. The proposed framework is then extended to formulate the robust counterparts of the two capacitated hub location problems where data uncertainty occurs in both the objective and constraints. Based on an extensive empirical experiment, we show that the robust formulations can be efficiently linearised and solved by a commercial optimiser like CPLEX for instance. To validate the proposed modelling approach and to demonstrate its wider applications, we have solved 256 instances of the robust uncapacitated variations of the two-hub location and the robust sorting problems and favourably compared our results with those obtained by the formulations based on the Bertsimas and Sim approach.