Research On Network Interdiction Of Shortest Path

Important network defense and attack problems can be modeled as network interdiction. The classic nerwork interdiction problem which is with one goal and individual network-oriented can lead to weak result. While the effect of interdiction is maximize, the resource consumed is often with little consideration, thus when there comes to several answers, the model cannot give out the best one with least resource. Networks in morden world is growing with the characteristic of overlay, that is multi-networks coupled together, most of the pre-research do not typically account for the interdependent nature of layered networks. Networks are generally modeled individually, as an isolated network or with minimal recognition ofinteractions. In this study, we consider a new kind of network interdiction problem which optimizes the interdiction resource of the attacker while limits the network capacities, e.g. the shortest s-t path, under certain threshold. We first present the model based on individual network, and then propose a basic dual algorithm based on Lagrange slack and a basic decomposition algorithm based on Benders decomposition, and several developments with them. Then we focus on the interdependent relationships of layered networks, we choose the representative relation of feedback to formulate the shortest path network interdiction with goal threshold of bilevel networks, and try similar method to solve the models. At last we test our algorithms on notional networks and a real world transportation network; the results show the feasibility and character of our algorithms.One large model of most layered networks, even if it existed, would be too complex to effectively manipulate and analyze in most operational time frames. The model currently exists in the open literature accounting for interdependent effects across network are mostly in terms of complex network method. Such method cannot provide the decision makers with clear interdiction plan. This research develops a methodology using the operation research optimization method to model the individual network types while explicitly modeling their interconnected effects.