Trilevel shortest path network interdiction with partial fortification. (April 2017)

• Record Type: Journal Article
• Authors: Sadeghi, Somayeh; Seifi, Abbas; Azizi, Elnaz
• Is Part Of: Computers & industrial engineering. Volume 106(2017)
• Page Start: 400
• Page End: 411
• Publication Date: 2017-04
• Subjects: Network interdiction -- Shortest path -- Partial fortification -- Benders' decomposition -- Trilevel programming; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2017.02.006
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: We present a new formulation and solution method for trilevel network interdiction. We consider partial fortification and interdiction of network links in the model. The cost of interdiction and fortification are minimized in the objective functions. The obtained optimal values are better than those of total interdiction models. The solution times are significantly better than those of existing algorithms. Abstract: This paper presents a new formulation and solution method for partial fortification and interdiction of a trilevel shortest path problem that is a generalization of existing network interdiction models to a more practical setting. We consider a trilevel problem in which a defense plan is determined at the top level to reinforce some network components against a potential attack. The middle-level problem is solved to predict the most damaging potential attack plan to the hardened network, while the bottom-level problem is used to determine the shortest path in the surviving network. In the proposed model, partial interdiction and fortification are permitted to make the model more general and practical. In addition, the costs of interdiction and fortification are minimized in the attacker's and defender's objective functions, and the corresponding budget constraints are relaxed. We have devised a trilevel decomposition algorithm to solve the proposed model in a reasonable time. Furthermore, we transform the trilevel partial fortification problem into a bilevel problem using duality and propose a bilevel decomposition algorithm to solve it. We also study three different formulations for a trilevel shortest path interdiction problem with total fortification and solve these problems using a combination of duality, decomposition and relaxation methods. The numerical results show that the optimal objective values obtained by the proposed models are better than those of the total interdiction models. The solution times of the proposed algorithm applied on a set of test problems are significantly less than those of the existing algorithms. This implies that the budget relaxations in the proposed model improve the total traversing cost in the presence of partial attack and fortification.