Capacitated multiple allocation hub location problems under the risk of interdiction: model formulations and solution approaches

Hub-and-spoke networks play a critical role in reducing cost and enhancing service levels in various infrastructural sectors since hubs act as the consolidation and transshipment points of the flows. The failure of hubs in such a network can cause severe disruptions. While disruptions can be natural or man-made, a disruption by a rational individual or entity can be significantly detrimental to the network and is often studied as an interdiction problem. It is important to take interdiction effects at the design stage; therefore, we study the three-level capacitated hub-and-spoke network design problem from the perspective of a defender who considers the risk of interdiction by a rational attacker. Within the three levels, the upper level represents the network design level, and the lower two levels represent the bi-level hub interdiction problem. The introduction of capacity constraints within an interdiction model dramatically increases the complexity of the problem, as there can be some unfulfilled flows post-interdiction. Moreover, a flow may or may not be fulfilled through the least-cost route using the nearest hubs. This work makes two major contributions: the first contribution is on the efficient handling of the bi-level hub interdiction problem using the Dual-based approach and the Penalty-based approach, and the second contribution is on solving the overall three-level problem using a super valid inequality. These two contributions allow us to solve large-scale versions of the capacitated multiple allocation p-median hub location problem under the risk of interdiction, which is otherwise mathematically intractable and can be handled only using complete enumeration techniques.