Double-layer Benders decomposition for large-scale robust uncapacitated hub location

This paper models the robust counterpart for uncapacitated hub location problem with multiple assignments (UHLP), which simultaneously considers uncertainties associated with setup costs and flow amounts. A strong and tractable mixed-integer linear programming formulation is proposed, which can be reformulated in a Benders decomposition fashion, and a double-layer Benders decomposition algorithm is developed to efficiently solve large-scale instances of the problem. In the first layer, we propose a Benders decomposition algorithm to solve the LP relaxation of the master problem, obtaining a pool of valid optimality cuts; in the second layer, we exploit the obtained cuts to warm up the Benders decomposition algorithm on the master problem. In each of the two Benders decomposition algorithms, we design tailored efficient methods to exactly solve the subproblems and develop effective cuts refinement skills to generate strong optimality cuts. Extensive computational experiments are performed on well-known instances with up to 500 nodes to investigate the effect of incorporating uncertainty and verify the superior performance of the proposed solution method.