A Dynamic Network Interdiction Problem

Article type: Research Article

Authors: Lunday, Brian J. | Sherali, Hanif D.

Affiliations: Department of Mathematical Sciences, United States Military Academy, West Point, NY 10996, USA | Grado Department of Industrial and Systems Engineering, Virginia Polytechnic Institute and State University, Blacksburg, VA, 24061, USA, e-mail: [email protected], [email protected]

Abstract: We present a novel dynamic network interdiction model that accounts for interactions between an interdictor deploying resources on arcs in a digraph and an evader traversing the network from a designated source to a known terminus, wherein the agents may modify strategies in selected subsequent periods according to respective decision and implementation cycles. For the resulting minimax model, we develop a reformulation that facilitates a direct solution procedure using commercial software or via a proposed alternating heuristic. We examine certain related stability and convergence issues, demonstrate special convergence cases, and provide insights into the computational performance of the solution procedures.

Keywords: network interdiction, resource allocation, minimax flow problems, dynamic formulation, alternating heuristic

Journal: Informatica, vol. 21, no. 4, pp. 553-574, 2010