Multilevel passenger screening strategies for aviation security systems

Passenger prescreening is a critical component of aviation security. This paper intro-duces the Multilevel Allocation Problem (MAP), which models the screening of passen-gers and baggage in a multilevel aviation security system. A passenger is screened by one of several classes, each of which corresponds to a set of procedures using security screen-ing devices, where passengers are differentiated by their perceived risk levels. Each class is defined in terms of its fixed cost (the overhead costs), its marginal cost (the additional cost to screen a passenger), and its security level. The objective of MAP is to assign each passenger to a class such that the total security is maximized subject to passenger as-signments and budget constraints. This paper shows that MAP is NP-hard, introduces two dynamic programming algorithms for solving MAP in pseudo-polynomial time, and introduces a Greedy heuristic that obtains approximate solutions to MAP that use no more than two classes. Examples are constructed using data extracted from the Official Airline Guide (OAG). Analysis of the examples suggests that fewer security classes for passenger screening may be more effective and that using passenger risk information can lead to more effective security screening strategies