Hub interdiction & hub protection problems: Model formulations & exact solution methods

Abstract

In this paper, we present computationally effcient formulations for the hub interdiction and hub protection problems, which are bi-level and tri-level mixed integer linear programs, respec- tively. In the hub interdiction problem, the aim is to identify a set of r critical hubs from an existing set of p hubs that when interdicted results in the greatest disruption cost to the hub-and- spoke network. Reduction of the bi-level interdiction model to single level is straightforward using Karush-Kuhn-Tucker (KKT) conditions corresponding to the lower level problem; however, this turns out to be computationally ineffcient in this context. Therefore, we exploit the structure of the problem using various closest assignment constraints to reduce the hub interdiction problem to single level. The modifications lead to computational savings of almost an order of magnitude when compared against the only model existing in the literature. Further, our proposed modifi- cations offer structural advantages for Benders decomposition, which lead to substantial savings, particularly for large problems. Finally, we study and solve the hub protection problem exactly by utilizing the ideas developed for the hub interdiction problem. The tri-level protection problem is otherwise intractable, and to our best knowledge, has not been solved in the literature.