|
...transportation to minimize the probability of a successful smuggling attempt. Our work supports the Second Line of Defense (SLD) program of the US Department of Energy.
The smuggling of nuclear material, equipment, and technology has become a greater threat to international security since the dissolution of the Soviet Union. In the early 1990s, Russia inherited roughly 600-850 metric tons of highly enriched uranium and plutonium, enough material to make over 50000 explosive devices (Jones, 2002; Cobb, 2002). The "first line of defense" concerns nuclear Material Protection, Control and Accountability (MPC & A). In short, this involves securing and inventorying nuclear material at its storage sites in both civilian and defense facilities.
An International Atomic Energy Agency database includes 540 incidents of trafficking of nuclear and radioactive material from 1993-2003 that have been confirmed by a country's government (IAEA, 2004). Of these 205 involved nuclear material and 17 involved weapons-grade uranium or plutonium. With sophisticated technology, non-weapons-grade nuclear material can be processed to obtain weapons-grade material. With minimal technology it, or more widely available radioactive material, can be used with conventional explosives to build a radiological dispersal device, i.e., a dirty bomb. The majority of the incidents involved smugglers seeking to sell the illicit material. Weapons-grade material has been seized by authorities in Russia, Germany, the Czech Republic, Lithuania, Bulgaria, Kyrgyzstan, Georgia, Greece and France, and in the majority of the cases the material was traced to have originated in Russia or other parts of the FSU (IAEA, 2004). Some incidents involved kilograms of material. Some others involving smaller quantities actually represented samples of stolen material or material at risk of being stolen. This clearly points to the vulnerability of Russia's first line of defense. US efforts to assist the FSU in improving Russia's first line of defense are ongoing (National Nuclear Security Administration, 2006). These MPC & A efforts are critically important but by themselves, insufficient. An accurate inventory of the nuclear material that existed in Russia at the beginning of the 1990s seems impossible.
The SLD program seeks to reduce the risk of illicit trafficking of nuclear material through airports, seaports and border crossings in Russia and other key transit states, with the program's initial efforts in the FSU (Ball, 1998). The first SLD sensor installation was at Moscow's Sheremetyevo International Airport in September of 1998. Such sensor installations have two purposes: (i) to deter potential theft and smuggling of nuclear material, and (ii) to detect and therefore prevent actual smuggling attempts.
In this paper, we describe two types of stochastic network interdiction models that can be used to select the sites to install sensors to minimize the probability a smuggler can travel through a transportation network undetected. Our two basic models are distinguished with respect to whether the interdictor and smuggler have the same or differing perceptions of key network parameters. Our first model, in which the smuggler and interdictor have identical perceptions of the network, has been developed in collaboration with the Los Alamos National Laboratory SLD team and has been implemented for decision support for the SLD program. Our second model in which the interdictor and smuggler can have differing perceptions is an important extension. The primary emphasis in this paper is on modeling, as opposed to solution techniques and computation. Of course, modeling choices affect our ability to solve these problems, and so important parts of the development are devoted to precisely these issues. Furthermore, we describe, and motivate from a modeling perspective, a class of valid inequalities that strengthen our simplest model. Finally, in developing our basic model, we provide an outline of some of the techniques that have been successfully employed to obtain tractable network interdiction models in settings beyond the specific models of this paper.
While there are earlier references (e.g., Wollmer, 1964), the study of network interdiction in operations research began in earnest in the 1970s. During the Vietnam War, deterministic mathematical programs to disrupt flow of enemy troops and supplies were developed (McMasters and Mustin, 1970; Ghare et al., 1971). The problem of maximizing an adversary s shortest path is considered in Fulkerson and Harding (1977) and Golden (1978). A closely related problem concerns maximizing the longest path in an adversary's PERT network (Reed, 1994; Brown et al., 2004). When these are linear programs (LPs), the interdictor can continuously increase the length of an arc, subject to a budget constraint. A discrete version of maximizing the shortest path removes an interdicted arc from the network, and when the budget constraint is simply a cardinality constraint, this is called the k-most-vital-arcs problem (Corley and Sha, 1982; Ball et al., 1989; Malik et al., 1989). Generalizations of the k-most-vital arcs problem are considered in Isreali and Wood (2002). The interdiction problem of removing arcs to minimize flow in an adversary's maximum-flow network is considered in Wollmer (1964) and Wood (1993). See Washburn and Wood (1994) for game-theoretic approaches to related network interdiction problems, Chern and Lin (1995) for an interdiction model on a minimum-cost-flow network, and Israeli and Wood (2001) for interdiction models of more general systems.
The above interdiction models are deterministic in the following senses. First, the arc lengths in the shortest path and PERT problems, and the arc capacities in the maximum flow problem, are known with certainty. Second, when increasing the length of an arc in the former problems or when removing or decreasing the capacity of an arc in the latter problem, these modifications are deterministic, i.e., with certainty. The work of Wood (1993) on maximum flow network interdiction is generalized in Cormican et al. (1998) to allow for both random arc capacities and interdiction successes. An interdiction model with uncertain network topology is developed in Hemmecke et al. (2003). A stochastic interdiction model in which the adversary's response is modeled via a Markov decision process is considered in Bailey et al. (2004).
The remainder of this paper is organized as follows. In Section 2, we formulate our basic model, which we label SNIP, for stochastic network interdiction problem, as a bilevel stochastic mixed-integer program (MIP). This model exhibits a "min-max" structure, which does not lend itself to computation and so we formulate an equivalent stochastic linear MIP that can be solved, e.g., by commercial branch-and-bound solvers for integer programming. We then turn our attention in Section 3 to an important special case of SNIP that arose in our work on the SLD program, in which sensors can only be installed at border crossings of a single country, namely Russia. We show the associated MIP can be simplified in this special case. The resulting model is called BiSNIP, for bipartite stochastic network interdiction problem, because it may be viewed as an interdiction problem on a bipartite network. Section 4 generalizes SNIP and BiSNIP to models we call PSNIP and BiPSNIP, respectively. Here, the addition of "P" to the SNIP and BiSNIP labels indicates that these are models in which the interdictor and the evader differ in their perceptions of the network. Our emphasis here is on the simpler BiPSNIP case. In Section 5, we describe a class of valid inequalities, that we call step inequalities, to tighten the MIP formulation of BiSNIP, and we present computational results when using these inequalities. We conclude the paper in Section 6.
2. SNIP on a general network
We model two adversaries, an interdictor and an evader (we will use the terms "evader" and "smuggler" interchangeably), and an underlying directed network G(N, A) on which the evader travels. In the deterministic version of our model, the evader starts at a source node s [member of] N and wishes to reach a terminal node t [member of] N. The model is deterministic in that this origin-destination pair is known. The probability that the evader can traverse arc (i, j) [member of] A undetected is [p.sub.ij] if the interdictor has not installed a sensor on arc (i, j), and this probability is [q.sub.ij] < [p.sub.ij] if the interdictor has installed a sensor. An evader can be caught by indigenous law enforcement without radiation detection equipment, and so [p.sub.ij] < 1. The events of the evader being detected on distinct arcs are assumed to be mutually independent. The evader chooses an s-t path to maximize the probability of traversing the network without being detected. With limited resources, the interdictor must select arcs on which to install sensors in order to minimize this evasion probability.
Our stochastic network interdiction problem (SNIP) differs from the above description only in that the identity of the evader is unknown when the interdictor installs the sensors. In our basic SNIP model, an evader's...
NOTE: All illustrations and photos
have been removed from this article.
More articles from IIE Transactions
Rebate, returns and price protection policies in channel coordination., February 01, 2007
Hierarchical cross-training in work-in-process-constrained systems.(Au..., February 01, 2007
Risk, risk aversion and the optimal time to produce.(Author abstract), February 01, 2007
Benefits of considering inventory in service parts logistics network d..., February 01, 2007
Strategic network design for multi-zone truckload shipments.(Author ab..., February 01, 2007
Looking for additional articles?
Search our database of over 3 million articles.
Looking for more in-depth information on this industry?
Search our complete database of Industry & Market reports by text, subject, publication
name or publication date.
About Goliath
Whether you're looking for sales prospects, competitive information, company
analysis or best practices in managing your organization,
Goliath can help you meet your business needs.
Our extensive business information databases empower business
professionals with both the breadth and depth of credible,
authoritative information they need to support their business
goals. Whether it be strategic planning, sales prospecting,
company research or defining management best practices -
Goliath is your leading source for accurate information.
|
