Computational methods for deterministic and stochastic network interdiction problems
Loading...
Authors
Cormican, Kelly James
Subjects
Advisors
Wood, R. Kevin
Morton, David P.
Date of Issue
1995-03
Date
March 1995
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
Abstract
Using limited resources, a network interdictor attempts to disable components of a capacitated network with the objective of minimizing the maximum network flow achievable by the network user. This problem has applications to reducing the importation of illegal drugs and planning wartime air attacks against an enemy's supply lines. A deterministic model using Benders decomposition is developed and improved upon with an original "flow-dispersion heuristic." An extension is made to accommodate probabilistic scenarios, where each scenario is an estimate of uncertain arc capacities in the actual network. A unique sequential- approximation algorithm is utilized to investigate cases where interdiction successes are binary random variables. For a network of 3200 nodes and 6280 arcs, Benders decomposition solves the network interdiction problem in less than one-third of the time required by a direct branch-and-bound method. The flow-dispersion heuristic can decrease solution time to one-fifth or less of that required for the Benders decomposition algorithm alone. With six allowable but uncertain interdictions in a network of 100 nodes and 84 possible interdiction sites among 180 arcs, a stochastic network interdiction problem is solved to optimality in 24 minutes on a IBM RISC/6000 Model 590. With uncertain arc capacities in five scenarios, and three allowable and certain interdictions, a 900 node and 1740 arc network is solved to optimality in 17 minutes on a 60MHZ Pentium PC.
Type
Thesis
Description
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
NA
Format
61 p.
Citation
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.