A new robust capacitated hub interdiction problem under ambiguous demand and its benders decomposition

In this paper, we study the capacitated hub interdiction problem on a multiple allocation hub-and-spoke network and formulate it as a bi-level optimization model. The rational attacker in the upper-level model interdicts a subset of hubs and maximizes the damage to the defender in the lower-level model. Given that hubs operate with limited capacity, an interdiction would lead to unfulfilled demand, thereby incurring additional penalty costs. In reality, however, demand in urban logistics transportation tends to exhibit significant variation due to its inherent non-stationarity and spatial correlation. Therefore, we model demand uncertainty to make robust hub location and routing decisions. Methodologically, a sub-Gaussian-based ambiguity set is constructed using statistical methods, which involves the family of all probability distributions consistent with known mean, variance and support information about demand. We develop a distributionally robust optimization model for our capacitated hub interdiction problem under the constructed ambiguity set, and then reformulate it as a mixed integer linear programming model, which facilitates us to design an accelerated Benders decomposition algorithm. In particular, we derive robust solutions with both a priori and a posteriori probability guarantees. Case study on the well-known CAB dataset demonstrates the advantages of our optimization method in balancing robustness and conservatism. Furthermore, computational results on the TR dataset illustrate that our proposed algorithm outperforms the CPLEX solver.