Protection of capacitated hubs under demand uncertainty: a robust optimization approach
研究需求不确定时，如何保护有容量限制的枢纽网络免受攻击，提出三层优化模型和求解算法，为网络运营商提供决策支持。
Existing hub protection problems primarily consider deterministic demand and accordingly allocate protection resources to the most vulnerable hubs in the network that are at risk of attack. We study the protection problem of a capacitated hub-and-spoke network under the risk of an attack when the demand is uncertain. To model this, we propose a multi-level capacitated u-hub protection problem, with the network operator’s protection decision at the first level. At the second level, we model the interdiction problem of the network evader who intends to attack r hubs to maximise the post-interdiction re-routing cost of the network operator. At the third level, the network operator minimises the re-routing cost through the surviving hubs under the worst-case realisation of the demand, which is drawn from different robust uncertainty sets, namely, column, ellipsoidal, hose, and hybrid. A dual-based single-level reduction is proposed for the interdiction problem, which is then used within an implicit enumeration algorithm to solve the overall protection problem. We also propose tight values for bigM that are introduced due to complementary slackness conditions upon single-level reduction. Based on extensive experiments on the well-known CAB Dataset, we discuss several managerial and computational insights under different network parameter settings and uncertain scenarios.