Abstract

Networks such as telecommunication, transportation, and logistics play a vital role in sustaining social, economic, and industrial operations. However, networks are at risk of natural and man-made disruptions. With the increasing interconnectivity of networks, a disruption in one network can negatively affect other networks. We use network interdiction models to analyze the effects of disruptions on the networks. Interdiction models represent a two-player sequential game between the interdictor, seeking to maximize damage, and the network operator, striving to optimize operations after interdiction. Network interdiction models identify the critical nodes and/or arcs of the network and can be extended to fortify the existing networks or design resilient networks. In this thesis, we study the design of distribution and multicommodity networks and the fortification of spanning trees under stochastic interdictions.

The first paper investigates the distribution network design problem considering the effect of interdictions. Since interdiction outcomes can be uncertain in the real world, we consider the interdiction outcome as an uncertain parameter. We extend the model to consider the correlated facility interdictions where interruptions at one facility affect the nearby facilities. We Benders decomposition algorithm. Improved by two acceleration techniques to solve the model.

In the second paper, we focus on the design of a multicommodity network with interdictions. The designer does not have information about the interdiction resources; therefore, we consider the uncertainty in the number of interdictions by presenting a tri-level stochastic mathematical model. We present a branch-and-Benders-cut (BBC) algorithm enhanced by several acceleration techniques to solve the model.

In the third paper, we study the fortification of minimum spanning tree (MST) and optimum communication spanning tree (OCST) problems under stochastic number of interdictions. The MST aims to connect all nodes in a graph with minimal installation cost while satisfying communication requirements with minimum communication cost. The goal is to find the optimal fortification strategy so that the increase in the MST/OCST costs due to the interdiction of unfortified edges is minimized by presenting a tri-level stochastic model. We use backward sampling framework with acceleration technique to solve the deterministic and stochastic MST/OCST fortification problems.