本研究計畫探討航空站安全檢查問題，我們透過滿足乘客可容許的通關時間和檢查總預算限制下，最大化航空站安全檢查系統的安全水準。自從美國911事件發生後，如何達到良好的航空站安全水準成為各國機場海關最重要的管理議題。但若航空站海關的管理僅考量安全水準，勢必犧牲乘客的通關時間，降低航空站的通關效率。所以，本研究在總預算限制下考量不同安全檢查站的人員數分配，制定長期合理的風險門檻值用以指派乘客前往適合的安全檢查站，期望能最大化航空站的安全水準，並能同時滿足乘客的期望通關時間限制。

為了計算乘客的期望通關時間，我們透過建構嵌入式馬可夫鏈，分析具二維度系統狀態的等候系統。另外，我們也使用幾何矩陣法計算出乘客通關時間的解析解，而因為使用矩陣幾何法計算通關時間會花費大量的矩陣計算時間，所以我們也利用M/M/s等候模型來估計乘客的平均通關時間，以加速模擬最佳化的求解效率。同時，我們透過數值實驗分析此最佳化模型之特性，並針對違反馬可夫過程的情形下，提出演算法1，實驗結果中雖然發現解的品質佳，但此問題之函數圖形並非單調遞增及遞減，迭代點可能會跑至錯誤的方向，使得求解時間上升。所以我們發展演算法2，雖然解的品質會有所下降，但求解效率呈現大幅提升。

This research studies aviation security screening problems. Under the constraints of passenger waiting times and total budget (including staff and device cost), we want to maximize the security level of the airport. Since the 9/11 attacks, the issue of how to achieve better levels of aviation security has been a very important
managerial problem. Our goal is to achieve better aviation risk management and to satisfy the constraint of passenger waiting times. To calculate average passenger waiting time, we studied a queueing system with a two-dimensional state space through applying embedded Markov chain. In addition, due to the huge computation time necessary to calculate the average waiting time, we also estimated the average passenger waiting time by applying the M/M/s queueing model. Meanwhile, we studied the characteristics of the optimization model through the numerical analysis of computer experiments, and have proposed the Algorithm 1 in a non-Markovian hypothesis. The results of our experiments show that Algorithm 1 can deliver a promising final solution, but may incur excessive sampling costs, so, we also designed Algorithm 2, and although the quality of the solution may be worse than Algorithm 1, the numerical efficiency is better.

[1] Andrad´ottir, S., Kim, S.H. (2010) Fully sequential procedures for comparing constrained systems via simulation. Naval Research Logistics, 57, 403–421.

[2] Almehdawe, E., Jewkes, B., He, Q.-M. (2013) A Markovian queueing model for ambulance offload delays. European Journal of Operational Research, 226, 602–614.

[3] Batur, D., Kim, S.H. (2010) Finding feasible systems in the presence of constraints on multiple performance measures. ACM Transactions on Modeling and Computer Simulation, 20, 1–26.

[4] Chen, H. (1994). Stochastic root finding in system design. Ph.D. Dissertation, School of Industrial Engineering, Purdue University, West Lafayette, IN.

[5] Chen, H., Schmeiser, B.W. (1994). Retrospective approximation algorithms for stochastic root finding. In Proceedings of the 26th conference on Winter simulation. Society for Computer Simulation International, 255–261.

[6] Chen, H., Schmeiser, B.W. (2001). Stochastic root finding via retrospective approximation. IIE Transactions, 33, 259–275.
[7] Cavusoglu, H., Koh, B., Raghunathan, S. (2010) An analysis of the impact of passenger profiling for transportation security. Operations Research, 58, 1287–1302.

[8] Feng, Q. (2007) On determining specifications and selections of alternative technologies for airport checked-baggage security screening. Risk Analysis, 27, 1299–1310.

[9] Jacobson, S.H., Virta, J.E., Bowman, J.M., Kobza, J.E., Nestor, J.J. (2003) Modeling aviation baggage screening security systems: A case study. IIE Transactions, 35, 259-269.

[10] Jacobson, S.H., Karnani, T., Kobza, J.E. (2005) Assessing the impact of deterrence on aviation checked baggage screening strategies. International Journal of Risk Assessment and Management, 5, 1–15.

[11] Jacobson, S.H., Karnani, T., Kobza, J.E., Ritchie, L. (2006) A cost–benefit analysis of alternative device configurations for aviation checked baggage security screening. Risk Analysis, 26, 297–310.

[12] Kobza, J.E., Jacobson, S.H. (1996) Addressing the dependency problem in access security system architecture design. Risk Analysis, 16, 801–812.

[13] Kobza, J.E., Jacobson, S.H. (1997) Probability models for access security system architectures. Journal of the Operational Research Society, 48, 255–263.

[14] Lazar Babu, V.L., Batta, R., Lin, L. (2006) Passenger grouping under constant threat probability in an airport security system. European Journal of Operational Research, 168, 633–644.

[15] Lee, A.J., Jacobson, S.H. (2011) The impact of aviation checkpoint queues on optimizing security screening effectiveness, Reliability Engineering & System Safety, 96, 900–911.

[16] Lee, A.J., Jacobson, S.H. (2012) Identifying changing aviation threat environments within an adaptive homeland security advisory system. Risk Analysis, 32, 319–329.

[17] Lee, A.J., Jacobson, S.H. (2012) Addressing passenger risk uncertainty for aviation security screening. Transportation Science, 46, 189–203.

[18] de Lange, R., Samoilovich, I., van der Rhee, B. (2013), Virtual queuing at airport security lanes. European Journal of Operational Research, 225, 153–165.

[19] McLay, L.A., Jacobson, S.H., Kobza, J.E. (2006) A multilevel passenger prescreening problem for aviation security. Naval Research Logistics, 53, 183–197.

[20] McLay, L.A., Jacobson, S.H., Kobza, J.E. (2007) Integer programming models and analysis for a multilevel passenger screening problem. IIE Transactions, 39, 73–81.

[21] McLay, L.A., Jacobson, S.H., Nikolaev, A.G. (2009) A sequential stochastic passenger screening problem for aviation security. IIE Transactions, 41, 575–591.

[22] McLay, L.A., Lee, A.J., Jacobson, S.H. (2010) Risk-based policies for airport secuity checkpoint screening. Transportation Science, 44, 333–349.

[23] Nikolaev, A.G., Jacobson, S.H., McLay, L.A. (2007) A sequential stochastic security system design problem for aviation security. Transportation Science, 41, 182–194.

[24] Nikolaev, A.G., Lee, A.J., Jacobson, S.H. (2012) Optimal aviation security screening strategies with dynamic passenger risk updates. IEEE Transactions on Intelligent Transportation Systems, 13, 203–212.

[25] Nie, X., Parab, G., Batta, R., Lin, L. (2012) Simulation-based selectee lane queuing design for passenger checkpoint screening. European Journal of Operational Research, 219, 146–155.

[26] Poole, Jr., R.W., Passantino, G. (2003) A risk-based airport security policy. Technical report, Reason Public Policy Institute, Public Policy no. 308, Los Angeles, CA.

[27] Pasupathy, R., Kim, S. (2011) The stochastic root-finding problem: Overview, solutions, and open questions. ACM Transactions on Modeling and Computer Simulation, 21, 1–23.

[28] Sewell, E.C., Attagara, J., Kobza, J.E., Jacobson, S.H. (2012) Allocating explosive screening devices for aviation security. Journal of Transportation Security, 5, 141–155.

[29] Seo, S., Choi, S., Lee, C. (2012) Security manpower scheduling for smart airports. Computer science and convergence, Lecture Notes in Electrical Engineering 114, 519–527.

[30] Sewell, E.C., Lee, A.J., Jacobson, S.H. (2013) Optimal allocation of aviation security screening devices. Journal of Transportation Security, 6, 103–116.

[31] Virta, J.E., Jacobson, S.H., Kobza, J.E. (2003) Analyzing the cost of screening selectee and non-selectee baggage. Risk Analysis, 23, 897–908.

[32] Wang, X., Zhuang, J. (2011) Balancing congestion and security in the presence of strategic applicants with private information. European Journal of Operational Research, 212, 100–111.

[33] Zhang, Z.G., Luh, H.P., Wang, C.H. (2011) Modeling security-check queue. Management Science, 57, 1979–1995.