Integer programming models and analysis for a multilevel passenger screening problem

Designing effective aviation security systems has become a problem of national interest and concern. Passenger prescreening is an important component of aviation security. Effectively using passenger prescreening information to develop screening strategies can be quite challenging. Moreover, it can be difficult to measure the effectiveness of such systems after they are in place. To address these issues, this paper introduces the Multilevel Passenger Screening Problem (MPSP). In MPSP, a set of classes are available for screening passengers, each of which corresponds to several device types for passenger screening, where each device type has an associated capacity and passengers are differentiated by their perceived risk levels. The objective of MPSP is to use prescreening information to determine the passenger assignments that maximize the total security subject to capacity and assignment constraints. MPSP is illustrated with examples that incorporate flight schedule and passenger volume data extracted from the Official Airline Guide.

Keywords:

• Integer programming
• discrete optimization
• aviation security
• homelands

Acknowledgements

This research was supported in part by the National Science Foundation (DMI-0114046, DMI-0114499) and the Air Force Office of Scientific Research (FA9550-04-1-0110). The authors would like to thank Dr. Lyle Malotky and Dr. John J. Nestor of the Transportation Security Adminstration, Department of Homeland Security, for their guidance and feedback on the research results reported in this paper. The author would also like to thank Dr. Candace Yano and an anonymous referee for their comments and feedback on this work. The computational work was done in the Simulation and Optimization Laboratory at the University of Illinois.