Dynamic Multilayer Network Interdiction Of Shortest Path Problem

Network interdiction problem is a kind of the network optimization with characteristics of game theory,which usually involves two entities,an evader and an interdictor,who compete in a special case of Stackelberg game.The interdiction models are widely applied to contexts involving industrial,military or organizational competition,and these models are mainly formulated as the bi-level mixed integer programming.Previous studies on network interdiction mainly focus on problems on single-layer network;however,modern infrastructures consist of multiple networked systems,such as electricity,telecommunication,and transportation,which interact with each other.Since these multi-layer networks influence the optimization on networks profoundly,a framework for multilayer network interdiction of shortest path,as well as corresponding algorithms,are proposed in this dissertation based on the problem of single-layer network interdiction of shortest path.The contributions of this work are specified as follows:1)Modeling and algorithm design of single-layer network interdiction of shortest path.By introducing the transforming constrains of nodal interdiction,a nodal network interdiction model of shortest path is developed,which is formulated as the bi-level mixed integer programming.To solve this problem,an interdiction subgraph decomposition algorithm is proposed on the base of dual programming and Benders decomposition algorithm.In addition,a bi-objective shortest path network interdiction model is developed in which the interdictor seeks to interdict a set of nodes in the network that is Pareto-optimal with respect to two objectives,i.e.,maximization of shortest path length and minimization of resources cost.A novel subgraph sequence algorithm is developed to identify the efficient frontier.Moreover,to make a trade-off between the resource investment and the interdiction performance,the definition and the computing method of saturation point are introduced.2)Proposing the framework and algorithms for multilayer network interdiction of shortest path.The interdependent function is proposed to transform the multilayer network interdiction problem to single-layer network interdiction problem.The feedback relation of multilayer networks is modeled in the framework for multilayer network interdiction of shortest path by adding logical constrains,and these constrains are converted to linear constrains.To obtain the optimal solution of this problem,the dual programming approach and decomposition approach are used to design the algorithms.Besides,a strategy to enhance the algorithm is proposed in this dissertation based on the definition of upper bound of feedback stable stage,which can help to reduce a great number of logical constrains.3)Experiments and analyzing based on simulated network data and real-world network data.The performance of proposed algorithms is analyzed by comparing the running time under different interdiction resources and different size of networks.The experimental results show that the proposed interdiction subgraph decomposition algorithm performs better than other algorithms;hence the subgraph sequence algorithm performs well.Besides,the enhanced algorithm for multilayer network interdiction of shortest path enlarges the size of solvable networks in given time.In conclusion,the shortest path network interdiction problems on both single-layer and multilayer networks have been systemically studied in this dissertation.And both the framework and algorithms are proposed for the multilayer network interdiction of shortest path,which is contributive to the decision-making of the multilayer network interdiction problems.