Hub interdiction problems: Models and solution approaches

Abstract

Hub-and-spoke networks are used in the operations of businesses like telecommunication, transportation and energy systems. The network has special facilities known as hubs which act as interim nodes between source and destination nodes in the network. Flows from the same origin with different destinations are consolidated on their route at hubs, where they are combined with flows that have different origins but the same destination, so as to benefit from economies of scale in transportation. Since hubs act as transshipment points for huge volume of traffic, their interdiction has the potential to cause severe disruptions in the operations of the businesses that employ hub-and-spoke network. In this thesis, we study the design of hub-and-spoke networks under such an interdiction. In the first essay, we study hub interdiction problem, which identifies the critical hubs in a given hub-and-spoke network. The problem is modeled as a bilevel mixed integer program (MIP). We study different ways to reduce this problem to single level to solve it efficiently. Our proposed techniques are faster than the method studied in literature by at least an order of magnitude. As an extension of the interdiction problem, we study the protection problem, where the network operator can select a subset of hubs to protect, so as to minimize the impact of interdiction. This problem is modeled as a trilevel MIP and is solved using an Implicit enumeration + Benders decomposition algorithm. In the second essay, we study a hub location problem considering the risk of interdiction. In this problem, the initial hub network is itself so designed that the loss due to interdiction is minimized. The resulting model is a trilevel MIP and is solved using a cutting plane method based on super valid inequalities. We show that the problems that are intractable to be solved by greedy methods is solved very efficiently by our cutting-plane algorithm. In the final essay, we study a hub interdiction problem under demand uncertainty. The uncertainty in demand is modeled using robust optimization approach through five different uncertainty sets. All the five robust problems are modeled as trilevel optimization problems. We present tractable single level robust counterparts of all these problems and solve it using CPLEX.