An exact method for trilevel hub location problem with interdiction

Abstract

In this paper, we study the problem of designing a hub network that is robust against deliberate attacks (interdictions). The problem is modeled as a three-level, two-player Stackelberg game, in which the network designer (defender) acts first to locate hubs to route a set of flows through the network. The attacker (interdictor) acts next to interdict a subset of the located hubs in the designer’s network, followed again by the defender who routes the flows through the remaining hubs in the network. We model the defender’s problem as a trilevel optimization problem, wherein the attacker’s response is modeled as a bilevel hub interdiction problem. We study such a trilevel problem on three variants of hub location problems studied in the literature namely: p-hub median problem, p-hub center, and p-hub maximal covering problems. We present a cutting plane based exact method to solve the problem. The cutting plane method uses supervalid inequalities, which is obtained from the solution of the lower level interdiction problem. To solve the lower level hub interdiction problem efficiently, we propose a penalty-based reformulation of the problem. Using the reformulation, we present a branch-and-cut based exact approach to solve the problem efficiently. We conduct experiments to show the computational advantages of the above algorithm. To the best of our knowledge, the cutting plane approach proposed in this paper is among the first exact method to solve trilevel location–interdiction problems. Our computational results show interesting implications of incorporating interdiction risks in the hub location problem.