A multilevel passenger screening problem for aviation security

Laura A. McLay, Sheldon H. Jacobson, John E. Kobza

Research output: Contribution to journalArticlepeer-review


Passenger prescreening is a critical component of aviation security systems. This paper introduces the Multilevel Allocation Problem (MAP), which models the screening of passengers 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 screening 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 assignments and budget constraints. This paper shows that MAP is NP-hard 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. 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.

Original languageEnglish (US)
Pages (from-to)183-197
Number of pages15
JournalNaval Research Logistics
Issue number3
StatePublished - Apr 2006


  • Aviation security
  • Dynamic programming
  • Heuristics
  • Integer programming
  • Policy modeling

ASJC Scopus subject areas

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research


Dive into the research topics of 'A multilevel passenger screening problem for aviation security'. Together they form a unique fingerprint.

Cite this