Algorithms for Port-of-Entry Inspection

摘要

Finding ways to intercept illicit nuclear materials and weapons destined for the United States via the maritime transportation system is an exceedingly difficult task. Until recently, only about 2% of ships entering U.S. ports have had their cargoes inspected. The percentage at some ports has now risen to 6%, but this is still a very small percentage. The purpose of this project was to develop decision support algorithms that help to optimally intercept illicit materials and weapons. The algorithms developed focused on finding inspection schemes that minimize total cost, including the 'cost' of false positives and false negatives. The project viewed the inspection problem as a stream of entities arriving at a port, with a decision maker having to decide how to inspect them, which to subject to further inspection, and which to allow to pass through with only minimal levels of inspection. This is a complex sequential decision making problem. Sequential decision making is an old subject, but one that has become increasingly important with the need for new models and algorithms as the traditional methods for making decisions sequentially do not scale. Previous algorithms for optimally intercepting illicit cargo assumed that sensor performance, operating characteristics of ports, and overall threat level were all fixed. The author's approach involved decision logics and was built around problem formulations that led to the need for combinatorial optimization algorithms as well as methods from the theory of Boolean functions, queueing theory, and machine learning. Algorithms for designing port-of-entry inspection rapidly come up against the combinatorial explosion caused by the many possible alternative inspection strategies. In this project, the authors worked to develop an approach that brings many of these complications explicitly into the analysis.