Efficiently interdicting a time-expanded transshipment network
By: H. Dan Derbes
Contributors: Naval Postgraduate School (U.S.) 
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1997
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Number of pages: 70
Description: A network interdictor' has a limited supply of resource with which to disrupt a network user's" flow of      supplies in a capacitated transshipment network. The interdictor's problem of minimizing the maximum flow      through the network is a difficult- to-solve integer programming problem but we show that a heuristic based      on Lagrangian relaxation is very effective in approximately solving the problem. We implement algorithms in      C to approximately solve both the static (without considering time) and dynamic network interdiction      problems. Static test networks range in size from 25 nodes and 64 arcs to 400 nodes and 1519 arcs. Using      an IBM Rs/6000 Model 590 workstation, we find optimal solutions for seven of 12 test networks and solve      the largest problem in only 31.0 seconds. We model a dynamic network in time-expanded form in order to      assign time weights of 0 or 1 to flow, include repair time of interdicted arcs, and provide a schedule to the      network interdictor that identifies arcs and time periods for interdictions. Dynamic networks range in size      from 525 nodes and 1, 344 arcs to 40,400 nodes and 153,419 arcs (in time-expanded form). We find      near- optimal solutions in 13 of 24 test networks and solve the largest network in 1729.5 seconds.
Notes: "September 1997."

Thesis advisor(s): R. Kevin Wood.

Thesis (M.S. in Operations Research) Naval Postgraduate School, September 1997.

Includes bibliographical references (p. 67-68)

Approved for public release; distribution unlimited.

Also available online.

Mode of access: World Wide Web.

System requirements: Adobe Acrobat reader.

US Navy (USN) author.

dk/dk cc:9116 04/17/98.