Hub interdiction problem variants: Models and metaheuristic solution algorithms

Hub location problem (HLP) is one of the strategic problems encountered in designing transportation and telecommunication networks. Regardless of the considered objective in design of hub networks, such as cost minimization or service level maximization, the located hubs can be subject to natural or intentional disruptions after installation. In this paper, we address the multiple allocation p-hub median, p-hub maximal covering, and p-hub center problems under intentional disruptions. In each case, the problem is considered as a Stackelberg game where the leader locates p hubs to optimize his/her objective function, whereas the follower tries to identify and interdict r hubs that their loss would diminish the network performance the most. Bilevel and single level mathematical formulations are presented to model the problem from the leader's and the follower's perspectives. Furthermore, efficient Simulated Annealing (SA) heuristics are proposed for solving the problems. Extensive computational experiments show the capability of the proposed SA algorithms to obtain the optimal solutions in short computational times. Some managerial insights are also derived based on the obtained numerical results.