Interdicting nuclear material on cargo containers using knapsack problem models

This paper introduces a framework for screening cargo containers for nuclear material at security stations throughout the United States using knapsack problem, reliability, and Bayesian probability models. The approach investigates how to define a system alarm given a set of screening devices, and hence, designs and analyzes next-generation security system architectures. Containers that yield a system alarm undergo secondary screening, where more effective and intrusive screening devices are used to further examine containers for nuclear and radiological material. It is assumed that there is a budget for performing secondary screening on containers that yield a system alarm. This paper explores the relationships and tradeoffs between prescreening, secondary screening costs, and the efficacy of radiation detectors. The key contribution of this analysis is that it provides a risk-based framework for determining how to define a system alarm for screening cargo containers given limited screening resources. The analysis suggests that highly accurate prescreening is the most important factor for effective screening, particularly when screening tests are highly dependent, and that moderately accurate prescreening may not be an improvement over treating all cargo containers the same. Moreover, it suggests that screening tests with high true alarm rates may mitigate some of the risk associated with low prescreening intelligence.     

An integrated model for screening cargo containers

This paper focuses on detecting nuclear weapons on cargo containers using port security screening methods, where the nuclear weapons would presumably be used to attack a target within the United States. This paper provides a linear programming model that simultaneously identifies optimal primary and secondary screening policies in a prescreening-based paradigm, where incoming cargo containers are classified according to their perceived risk. The proposed linear programming model determines how to utilize primary and secondary screening resources in a cargo container screening system given a screening budget, prescreening classifications, and different device costs. Structural properties of the model are examined to shed light on the optimal screening policies. The model is illustrated with a computational example. Sensitivity analysis is performed on the ability of the prescreening in correctly identifying prescreening classifications and secondary screening costs. Results reveal that there are fewer practical differences between the screening policies of the prescreening groups when prescreening is inaccurate. Moreover, devices that can better detect shielded nuclear material have the potential to substantially improve the system’s detection capabilities.     

Detecting nuclear materials smuggling: using radiography to improve container inspection policies

This paper proposes a layered container inspection system for detecting illicit nuclear materials using radiography information. We argue that the current inspection system, relying heavily on the Automated Targeting System (ATS) and passive radiation detectors, is inherently incapable of reliably detecting shielded radioactive materials, especially highly enriched uranium (HEU). This motivates the development of a new inspection system, which is designed to address a fundamental flaw of the ATS-based system, allowing for improved defense against sophisticated adversaries. In the proposed inspection system, all cargo containers go through x-ray imaging equipment first. From the x-ray image, a hardness measure of the container is computed. This hardness measure characterizes how likely it is that shielded HEU, if it does exist in the container, will not be detected in a subsequent passive detection step. Depending on the value of the hardness, the lower-hardness containers are sent to passive detection and the high-hardness containers are sent directly to active detection. This paper explores the trade-off between the detection probability of the new inspection system and the expected sojourn time a container spends in the system. The solution details and decision-making tools for using such a system are provided. Comparisons are made between the proposed system and the current ATS-based nuclear inspection system.     

Impact of measurement error on container inspection policies at port-of-entry

Containers arriving at a port-of-entry are inspected using sensors and devices to detect drugs, weapons, nuclear materials and other illegal cargo. Measurement errors associated with the inspection process may result in higher misclassification of containers. In this paper, we propose and formulate three inspection policies for containers at port-of-entry assuming the presence of sensor measurement errors. The optimization of the policies is carried out and the performance of each in terms of misclassification probabilities is compared. In each of the policies, the optimum settings are determined by minimizing the probability of false rejection while limiting the probability of false acceptance to a specified tolerance level. The results show that repeat inspections improve performance in terms of correct container classification. Expressions are presented for container misclassification in a single station, as well as in systems with several inspection stations arranged in different configurations such as series, parallel, series-parallel and parallel-series.     

Probability models for access security system architectures

This paper presents probability models of access control security system architectures. Access control is the process of screening objects; for example people, baggage, entering a secured area in order to detect and prevent entry by threats such as unauthorized personnel, firearms, explosives. A security system architecture consists of device technologies, as well as operational policies and procedures for utilizing the technologies. The probability models are developed based on Type I (a false alarm is given) and Type II (a threat is not detected) errors. The concept of controlled sampling, in which objects may take different paths through the system, is introduced. New architectures consisting of multiple devices and controlled sampling are proposed and analyzed. The results presented indicate that for specific threat levels, multiple-device systems can be identified which outperform single-device systems for certain error probability measures.     

Optimization of container inspection strategy via a genetic algorithm

It is estimated that 90% of the world’s freight is moved as containerized cargo, with over 125 million TEUs (Twenty foot Equivalent Units) of container being shipped by 2010. To inspect this volume of cargo for explosives, drugs or other contraband is a daunting challenge. This paper presents an optimization technique for developing an inspection strategy that will provide a specified detection rate for containers containing contraband at a minimum cost. Nested genetic algorithms are employed to optimize the topology of an inspection strategy decision tree, the placement of sensors on the tree and the sensor thresholds which partition suspicious containers (containers believed to contain contraband) from innocuous containers (containers which are believed to be free of contraband). The results of this optimization technique are compared to previously published techniques.     

Optimal design of container inspection strategies considering multiple objectives via an evolutionary approach

The size and complexity of containerized shipping across the globe has increased the vulnerability of seaports to the attack of terrorist networks and contraband smuggling. As a result, the creation of inspection strategies to check incoming containers at ports-of-entry has been necessary to enable the detection of containers carrying prohibited items. However, since costs and tardiness considerations related to the inspection process prevent all cargo to be manually checked, including different non-intrusive screening technologies as part of the inspection strategies is essential to optimize inspection needs. In this paper, inspection strategies are represented as decision-tree structures where each node illustrates a screening device, and links represent the two possible classifications a screened container can get (i.e. suspicious or unsuspicious). Based on such classification, one of three actions is taken: to continue screening, release or physically check the container. The contribution of this paper is a mathematical framework that provides an approximation to the Pareto optimal solutions (i.e. inspection strategies) that enable decision-makers to: (1)?identify tradeoffs among vulnerability, inspection cost, and tardiness for different inspection strategies, and based on this (2)?find the strategy that best suits current inspection needs. The mathematical framework includes: (1)?a?multi-objective optimization model that concurrently minimizes vulnerability, cost, and tardiness while determining screening device allocation and threshold settings, as well as, (2)?an evolutionary approach used to solve the optimization model.     

A Stackelberg game model for resource allocation in cargo container security

This paper presents a game theoretic model that analyzes resource allocation strategies against an adaptive adversary to secure cargo container transportation. The defender allocates security resources that could interdict an unauthorized weapon insertion inside a container. The attacker observes the defender’s security strategy and chooses a site to insert the weapon. The attacker’s goal is to maximize the probability that the weapon reaches its target. The basic model includes a single container route. The results in the basic model suggest that in equilibrium the defender should maintain an equal level of physical security at each site on the cargo container’s route. Furthermore, the equilibrium levels of resources to interdict the weapon overseas increase as a function of the attacker’s capability to detonate the weapon remotely at a domestic seaport. Investment in domestic seaport security is highly sensitive to the attacker’s remote detonation capability as well. The general model that includes multiple container routes suggests that there is a trade-off between the security of foreign seaports and the physical security of sites including container transfer facilities, container yards, warehouses and truck rest areas. The defender has the flexibility to shift resources between non-intrusive inspections at foreign seaports and physical security of other sites on the container route. The equilibrium is also sensitive to the cost effectiveness of security investments.     

Multiple Container Packing: A Case Study of Pipe Packing

While the problem of packing single containers and pallets has been thoroughly investigated very little attention has been given to the efficient packing of multiple container loads. Normally in practice a multiple container load is packed by a single container algorithm used in a greedy fashion. This paper introduces the issues involved in multiple container loading. It lays out three different strategies for solving the problem: sequential packing using a single container heuristic, pre-allocating items to the containers and choosing container loads using simultaneous packing models. The principal simultaneous models are pattern selection IP models. We present an application of packing pipes in shipping containers using two pattern selection IP models, a pattern selection heuristic, a sequential greedy algorithm and a pre-allocation method. The experimental results use randomly generated data sets. We discuss several useful insights into the methods and show that for this application the pattern selection methods perform best.     

Automating the planning of container loading for Atlas Copco: Coping with real-life stacking and stability constraints

The Atlas Copco^☆ distribution center in Allen, TX, supplies spare parts and consumables to mining and construction companies across the world. For some customers, packages are shipped in sea containers. Planning how to load the containers is difficult due to several factors: heterogeneity of the packages with respect to size, weight, stackability, positioning and orientation; the set of packages differs vastly between shipments; it is crucial to avoid cargo damage. Load plan quality is ultimately judged by shipping operators.This container loading problem is thus rich with respect to practical considerations. These are posed by the operators and include cargo and container stability as well as stacking and positioning constraints. To avoid cargo damage, the stacking restrictions are modeled in detail. For solving the problem, we developed a two-level metaheuristic approach and implemented it in a decision support system. The upper level is a genetic algorithm which tunes the objective function for a lower level greedy-type constructive placement heuristic, to optimize the quality of the load plan obtained.The decision support system shows load plans on the forklift laptops and has been used for over two years. Management has recognized benefits including reduction of labour usage, lead time, and cargo damage risk.     

Analytical method to identify the number of containers to inspect at U.S. ports to deter terrorist attacks

In this paper, we investigate how many containers would need to be screened in order to deter attackers from attempting to smuggle weapons into a defending country in container freight. We hypothesize that with a sufficiently high probability of being detected, attackers might be deterred from smuggling attempts. Thus, our goal is to identify the optimal proportion of containers to inspect in order to minimize the defender’s expected loss, using game theory to reflect the fact that attackers are simultaneously trying to maximize their expected rewards. Moreover, our model recognizes that the container-screening policy must simultaneously protect against different types of threats (such as nuclear bombs, dirty bombs, and assault rifles). Finally, our model also suggests that threatening to retaliate against attacks may be beneficial to defenders, as long as the threat is credible.     

A heuristic for sea-freight container selection,cargo allocation and cargo orientation

A model is proposed to generate solutions for container selection, for the allocation of cargo to containers, and for cargo orientation within a container. The model is in the form of a mixed integer program with the objective of minimizing the total shipping cost. The practical requirements of loading priority and weight distribution along the main dimension of the container are incorporated into the model. A heuristic solution strategy is proposed and used to control the computation time by pre-setting the search increments. Three case examples are presented. The first and third examples show that the proposed model can produce a better solution than the manual schedulers. The second example is taken from the literature and is compared with the solution generated by the proposed model, demonstrating that the practical considerations incorporated into the model do not necessarily lead to increased shipping costs.     

Network deployment of radiation detectors with?physics-based detection probability calculations

We describe a model for deploying radiation detectors on a transportation network consisting of two adversaries: a nuclear-material smuggler and an interdictor. The interdictor first installs the detectors. These installations are transparent to the smuggler, and are made under an uncertain threat scenario, which specifies the smuggler??s origin and destination, the nature of the material being smuggled, the manner in which it is shielded, and the mechanism by which the smuggler selects a route. The interdictor??s goal is to minimize the probability the smuggler evades detection. The performance of the detection equipment depends on the material being sensed, geometric attenuation, shielding, cargo and container type, background, time allotted for sensing and a number of other factors. Using a stochastic radiation transport code (MCNPX), we estimate detection probabilities for a specific set of such parameters, and inform the interdiction model with these estimates.     

Storage space allocation models for inbound containers in an automatic container terminal

This paper studies the problem of improving the operations efficiency for retrieving inbound containers in a modern automatic container terminal. In the terminal, when an external truck arrives to collect a container stored in a specific container block, it waits at one end of the block where an automatic stack crane will retrieve the container and deliver it to the truck. With the aim of reducing the expected external truck waiting time which is determined by how the containers are stored in a block, we propose two correlated approaches for the operations efficiency improvement, (1) by designing an optimized block space allocation to store the inbound containers after they are discharged from vessels, and (2) by conducting overnight re-marshaling processes to re-organize the block space allocation after some containers are retrieved. For the block space allocation problem, we consider three optimization models under different strategies of storing containers, namely, a non-segregation model, a single-period segregation model, and a multiple-period segregation model. Optimal solution methods are proposed for all three models. For the re-marshaling problem with a given time limit, we find that the problem is NP-hard and develop a heuristic algorithm to solve the problem. We then use simulation to validate our models and solution approaches. Simulation results reveal important managerial insights such as the advantage of the multiple-period segregation over the myopic single-period segregation, the possibility of overflow of the segregation model, and the benefit of re-marshaling.     

Simulation-based Selectee Lane queueing design for passenger checkpoint screening

There are two kinds of passenger checkpoint screening lanes in a typical US airport: a Normal Lane and a Selectee Lane that has enhanced scrutiny. The Selectee Lane is not effectively utilized in some airports due to the small amount of passengers selected to go through it. In this paper, we propose a simulation-based Selectee Lane queueing design framework to study how to effectively utilize the Selectee Lane resource. We assume that passengers are classified into several risk classes via some passenger prescreening system. We consider how to assign passengers from different risk classes to the Selectee Lane based on how many passengers are already in the Selectee Lane. The main objective is to maximize the screening system’s probability of true alarm. We first discuss a steady-state model, formulate it as a nonlinear binary integer program, and propose a rule-based heuristic. Then, a simulation framework is constructed and a neighborhood search procedure is proposed to generate possible solutions based on the heuristic solution of the steady-state model. Using the passenger arrival patterns from a medium-size airport, we conduct a detailed case study. We observe that the heuristic solution from the steady-state model results in more than 4% relative increase in probability of true alarm with respect to the current practice. Moreover, starting from the heuristic solution, we obtain even better solutions in terms of both probability of true alarm and expected time in system via a neighborhood search procedure.     

Modelling of containerized air cargo forwarding problems under uncertainty

This paper examines air container renting and cargo loading problems experienced by freight forwarding companies. Containers have to be booked in advance, in order to obtain discounted rental rates from airlines; renting or returning containers on the day of shipping will incur a heavy penalty. We first propose a mixed-integer model for the certain problem, in which shipment information is known with certainty, when booking. We then present a two-stage recourse model to handle the uncertainty problem, in which accurate shipment information cannot be obtained when booking, and all cargoes have to be shipped without delay. The first-stage decision is made at the booking stage, to book specific numbers of different types of containers. The second-stage decision is made on the day of shipping, depending on the extent to which the uncertainty has been realized. The decisions include number of additional containers of different types that are required to be rented, or the number of containers to be returned, under the scenario that might occur on the day of shipping. We then extend the recourse model into a robust model for dealing with the situation in which cargoes are allowed to be shipped later. The robust model provides a quantitative method to measure the trade-off between risk and cost. A series of experiments demonstrate the effectiveness of the robust model in dealing with risk and uncertainty.     

The management of intrusion detection: Configuration,inspection, and investment

This paper analyzes intrusion detection decisions in the presence of multiple alarm types, which differ in occurrence probabilities, damage and investigation costs. Specifically, multi-period optimization models are used to study three critical decisions associated with intrusion detection: (i) Allocation of the investigation budget to different periods and to different alarm types; (ii) Configuration of an intrusion detection system (IDS), i.e. choosing a false alarm rate for a given IDS; and (iii) Allocation of an appropriate amount of the investigation budget in the presence of alternative investment opportunities. Three models that cascade onto each other are presented. We minimize the sum of security costs including damages, due to ignored alarms, the investigation cost and the undetected intrusion cost. We show that it can be optimal to ignore non-critical alarms in order to allocate more of the investigation budget to critical alarms that may occur in the future. We establish that the security costs decrease as the investigation budget increases. Our last model deals with security investments—in the form of an investigation budget. The investigation budget must be increased until the rate of increase in savings in security costs due to the additional budget are equal to the internal rate of return of an organization. These analyses are done with explicit (derived) cost functions, as opposed to implicit (assumed) cost functions. We conclude by providing additional managerial insights and numerical examples.     

Modeling and analyzing the performance of aviation security systems using baggage value performance measures

Aviation security is an important concern of national interest.Baggage screening security devices and operations at airportstations throughout the United States address this concern.Determining how and where to assign (deploy) such devices canbe quite challenging. Moreover, even after such systems arein place, it can be difficult to measure their effectiveness.Uncovered flight segment (UFS) and uncovered passenger segment(UPS) performance measures provide a useful framework for measuringthe effectiveness of a baggage screening security device deploymentto a given station. However, the optimization models associatedwith these measures do not consider baggage screening strategiesthat permit partial screening of flights. To allow for suchstrategies, as well as to identify baggage screening securitysystem models where the decision to screen each individual selecteebag is made individually (rather than collectively by flight),this paper introduces performance measures in which each selecteebag is assigned an individual value. In particular, the flightsegment baggage value (FSBV) assigns a value to each selecteebag based upon the proportion of the flight segment that thebag covers. The passenger segment baggage value (PSBV) assignsa value to each selectee bag based on the proportion of thepassenger segments that the bag covers. For each of these measures,an associated decision problem and integer programming modelare introduced. In addition, several results are presented detailingboth optimization techniques for the models associated witheach measure and the relationships between the baggage valuemeasures and other baggage screening security system measures.A real-world example using actual flight data from the officialairline guide is presented to illustrate an application of thesemodels and results.     

Passenger grouping with risk levels in an airport security system

This is a follow-up to the recent paper by Lazar Babu et al. [V.L. Lazar Babu, R. Batta, L. Lin, Passenger grouping under constant threat probability in an airport security system, European Journal of Operational Research 168 (2006) 633–644] which investigated the benefit of classifying passengers into different groups, with the idea that the number of checks and the degree of inspection may vary for different groups. A basic assumption in that paper was that the threat probability is constant across all passengers. In this paper, we relax this assumption and consider the case where passenger risk levels are incorporated. We assume that passengers are classified into several risk classes via some passenger prescreening system, for example, Computer-Assisted Passenger Prescreening System II (CAPPS II). We consider the separate grouping of every class of passengers such that the overall false alarm probability is minimized while maintaining the overall false clear probability within specifications set by a security authority. Meanwhile, we consider the staffing needs at each check station. The problem is formulated as a mixed integer linear program. An illustrative example of the model is presented with comparisons to the model in Lazar Babu et al. (2006) using two performance measures: probability of false alarm and total number of screeners needed. Our conclusion is that incorporation of risk levels through passenger grouping strategies leads to a more efficient security check system.     

Conservative allocation models for outbound containers in container terminals

This paper examines location assignment for outbound containers in container terminals. It is an extension to the previous modeling work of Kim et al. (2000) and Zhang et al. (2010). The previous model was an “optimistic” handling way and gave a moderate punishment for placing a lighter container onto the top of a stack already loaded with heavier containers. Considering that the original model neglected the stack height and the state-changing magnitude information when interpreting the punishment parameter and hid too much information about the specific configurations for a given stack representation, we propose two new “conservative” allocation models in this paper. One considers the stack height and the state-changing magnitude information by reinterpreting the punishment parameter and the other further considers the specific configurations for a given stack representation. Solution qualities for the “optimistic” and the two “conservative” allocation models are compared on two performance indicators. The numerical experiments indicate that both the first and second “conservative” allocation models outperform the original model in terms of the two performance indicators. In addition, to overcome computational difficulties encountered by the dynamic programming algorithm for large-scale problems, an approximate dynamic programming algorithm is presented as well.