Efficiently interdicting a time-expanded transshipment network
Derbes, H. Dan
Wood, R. Kevin
MetadataShow full item record
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
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Naval Postgraduate School Center for Homeland Defense and Security (CHDS) (Monterey, California. Naval Postgraduate SchoolCenter for Homeland Defense and Security, 2006-07);July 2006. The July 2006 issue of Homeland Security Affairs offers articles about risk perception, domestic right wing extremist groups, social network analysis, and the impact of foreign policy on homeland security. It ...
Sullivan, Jeffrey Edward (Monterey, California. Naval Postgraduate School, 1996-06);The military is heavily reliant on the transfer of information among various networks in its day-to-day operations. With fewer defense dollars available for the development of new systems, the use of commercial- off-the-shelf ...
Mitigating risk to DOD information networks by improving network security in third-party information networks Kansteiner, Michael J. (Monterey, California: Naval Postgraduate School, 2016-06);Poorly defended third-party information networks can act as an attack vector for cyber attackers to successfully breach larger and more robustly defended information networks. Therefore, third-party networks connecting to ...