進階搜尋


   電子論文尚未授權公開,紙本請查館藏目錄
(※如查詢不到或館藏狀況顯示「閉架不公開」,表示該本論文不在書庫,無法取用。)
系統識別號 U0026-2507201610181600
論文名稱(中文) 以模擬最佳化求解具有等待時間限制式之安全檢查問題
論文名稱(英文) Using Simulation Optimization to Solve Security Screening Problem with a Waiting Time Constraint
校院名稱 成功大學
系所名稱(中) 工業與資訊管理學系
系所名稱(英) Department of Industrial and Information Management
學年度 104
學期 2
出版年 105
研究生(中文) 蔡承恩
研究生(英文) Cheng-En Tsai
學號 r36031034
學位類別 碩士
語文別 中文
論文頁數 57頁
口試委員 指導教授-蔡青志
口試委員-翁慈宗
口試委員-葉英傑
口試委員-張裕清
中文關鍵字 安全檢查系統  嵌入式馬可夫鏈  回溯最佳化  模擬最佳化 
英文關鍵字 Aviation Security Screening Problem  Embedded Markov Chain  Retrospective Optimization  Simulation Optimization, 
學科別分類
中文摘要 本研究探討航空站安全檢查問題,透過滿足乘客可容許的通關時間和檢查總預算限制下,最大化航空站安全檢查系統的安全水準。隨著交通的便利,乘客往返各國的頻率逐年上升,如何在消化大量乘客的同時也能保持航空站安全水準,成為各國機場很重要的管理議題。若航空站的管理者僅考量安全水準,勢必降低航空站的通關效率,造成機場人滿為患。所以,本研究在總預算限制下考量不同安全檢查站人員數的配置,及制定長期合理的風險門檻值用以指派乘客前往適合的安全檢查站,期望能最大化航空站的安全水準,並能同時滿足乘客的期望通關時間限制。

為了準確地描述乘客的相依性,本研究將透過建構嵌入式馬可夫鏈,分析具二維度系統狀態的等候系統。在馬可夫鏈的相關假設下透過矩陣幾何法的方式求解,找出在不同服務人員組合下最佳的風險門檻值。由於矩陣幾何法需要大量的矩陣計算時間,因此設計一個模擬最佳化演算法來找尋最佳的系統設定。

後續的數值實驗分析中,會透過兩種不同的問題參數設定進行比較。例子一為最佳風險門檻值較小較難搜尋,但服務人員組合較少。例子二為最佳風險門檻值較大較好搜尋,但服務人員組合較多。在兩種的問題參數設定下,求解的品質相差都不大。而預算限制式的處理方式也分為兩種,方式一是與搜尋過程分開處理,方式二則是同時處理。方式二的求解品質略優於方式一,但是在求解所花費的樣本則明顯少於方式一。
英文摘要 SUMMARY
Our research is to solve the aviation security screening problem. With the constraints of passenger waiting times and total budget (including staff and device costs), we want to maximize the security level of an airport. With the development of transportation, passengers travel around countries much more frequently than before. How to reach better levels of aviation security when serving a large number of passengers has become an important managerial issue for the airports of every country. Our goal is to reach a better aviation security level while satisfying the constraint of passenger waiting times.
To calculate average passenger waiting time, we studied a queueing system with a twodimensional state space through applying an embedded Markov chain. We constructed
a matrix to calculate passenger waiting time using the Markov chain hypothesis. This matrix can help us figure out optimal risk thresholds in the presence of different numbers of servers of each lane (s1; s2). Due to the huge amount of computation time used to calculate average waiting time, we propose a simulation optimization algorithm to find the best combination of (s1; s2).
We conducted two experiments using different parameters to find the ones which were most suitable for our algorithm. In experiment 1, the optimal risk threshold was more difficult to find since it is relatively small. But the fewer number of feasible combinations of (s1; s2) makes it easier to solve the problem. In contrast, the optimal
risk threshold could be found more easily since it is relatively big in experiment 2. And the number of feasible combinations of (s1; s2) in experiment 2 was more than
that in experiment 1. In terms of sampling costs and the quality of solutions, there were no obvious differences between these two experiments. Besides, we proposed two
different approaches to solve these two experiments. In the first approach, we solved the problems considering the two constraints simultaneously; however, these constraints
were considered separately in the other approach. We found that the latter performed slightly better on the quality of solutions than the former. Further, the sampling cost of the latter was much lower than the former.
論文目次 目錄
摘要 i
英文延伸摘要 ii
誌謝 v
目錄 vi
表目錄 viii
圖目錄 ix
第一章 緒論 1
1.1 研究背景與動機...1
1.2 研究目的...2
1.3 貢獻...3
1.4 小結...4
第二章 文獻探討 5
2.1 安全檢查系統相關研究...5
2.1.1 安全檢查系統...5
2.1.2 風險值...6
2.1.3 指派乘客問題...6
2.1.4 分配設備...8
2.1.5 通關系統績效考量方式...8
2.2 方法相關文獻...9
2.2.1 模擬最佳化(Optimization via Simulation;OvS)...9
2.2.2 回溯最佳化(Retrospective Optimization;RO)...11
2.2.3 懲罰函數(penalty function)...13
第三章 研究方法 17
3.1 航空站檢查問題與問題假設...17
3.2 建構系統具有相依性的等候模型...26
3.3 模擬最佳化演算法...32
3.3.1 等候績效計算...32
3.3.2 限制式處理方式...34
3.3.3 模擬最佳化演算法...36
第四章 實驗結果與分析 41
4.1 利用矩陣幾何法求解...41
4.2 實驗評估...43
4.3 實驗設定與結果...43
第五章 結論與未來研究方向 48
5.1 目前已進行的研究工作...48
5.2 未來研究方向...48
參考文獻 51
參考文獻 References
[1] 黃耀輝(2015)。考量具有等待時間限制式之航空站安全檢查問題。國立成功大學工業與資訊管理系碩士論文。
[2] Andradóttir, S. (1999). Accelerating the convergence of random search methods ´ for discrete stochastic optimization. ACM Transactions on Modeling and Computer Simulation , 9, 349–380.
[3] Almehdawe, E., Jewkes, B., He, Q.-M. (2013). A Markovian queueing model for ambulance offload delays. European Journal of Operational Research, 226, 602– 614.
[4] Bulgak, A. A., Sanders, J. L. (1988). Integrating a modified simulated annealing algorithm with the simulation of a manufacturing system to optimize buffer sizes in automatic assembly systems. In Proceedings of the 1988 conference on Winter simulation 684–690.
[5] Chang, K. H., Wan, H. (2009). Stochastic trust region response surface convergent method for generally-distributed response surface. In Proceedings of the 2009 conference on Winter simulation 563–573.
[6] Chen, H., Schmeiser, B.W. (2001). Stochastic root finding via retrospective approximation. IIE Transactions, 33, 259–275.
[7] Gong, W. B., Ho, Y. C., Zhai, W. (2000). Stochastic comparison algorithm for discrete optimization with estimation. SIAM Journal on Optimization, 10, 384–404.
[8] Haddock, J., Mittenthal, J. (1992). Simulation optimization using simulated annealing. Computers and Industrial Engineering, 22, 387–395.
[9] Hemker, T., Fowler, K. R., Farthing, M. W., von Stryk, O. (2008). A mixed-integer simulation-based optimization approach with surrogate functions in water resources management. Optimization and Engineering, 9, 341–360.
[10] Hong, L. J., Nelson, B. L. (2006). Discrete optimization via simulation using COMPASS. Operations Research, 54, 115–129.
[11] Hsu, J. C. (1984). Constrained simultaneous confidence intervals for multiple comparisons with the best. The Annals of Statistics, 12, 1136–1144.
[12] Hsu, J. C. (1996). Multiple comparisons: theory and methods. London, England, CRC Press.
[13] Jin, J. (1998). Simulation-based retrospective optimization of stochastic systems. Ph.d. Thesis. Purdue University, West Lafayette, Indiana, USA.
[14] Kim, S. H., Nelson, B. L. (2006). On the asymptotic validity of fully sequential selection procedures for steady-state simulation. Operations Research, 54, 475–488.
[15] Kushner, H. J., Sanvicente, E. (1975). Stochastic approximation of constrained systems with system and constraint noise. Automatica, 11, 375–380.
[16] Lee, A.J., Nikolaev, A.G., Jacobson, S.H. (2008). Protecting air transportation: a survey of operations research applications to aviation security. Journal of Transportation Security, 1, 160–184.
[17] 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.
[18] Lee, A.J., Jacobson, S.H. (2012). Identifying changing aviation threat environments within an adaptive homeland security advisory system. Risk Analysis, 32, 319–329.
[19] Lee, A.J., Jacobson, S.H. (2012). Addressing passenger risk uncertainty for aviation security screening. Transportation Science, 46, 189–203.
[20] Lee, Y. H., Azadivar, F. (1985). An application of optimization-by-simulation to discrete variable systems. In Proceedings of the 17th conference on Winter simulation .173–177.
[21] Luo, Y., Lim, E. (2013). Simulation-based optimization over discrete sets with noisy constraints. IIE Transactions, 45, 699–715.
[22] Matejcik, F. J., Nelson, B. L. (1995). Two-stage multiple comparisons with the best for computer simulation. Operations Research, 43, 633–640.
[23] McLay, L.A., Jacobson, S.H., Kobza, J.E. (2006). A multilevel passenger prescreening problem for aviation security. Naval Research Logistics, 53, 183–197.
[24] 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.
[25] McLay, L.A., Jacobson, S.H., Nikolaev, A.G. (2009). A sequential stochastic passenger screening problem for aviation security. IIE Transactions, 41, 575–591.
[26] McLay, L.A., Lee, A.J., Jacobson, S.H. (2010). Risk-based policies for airport security checkpoint screening. Transportation Science, 44, 333–349.
[27] Nagaraj, K., Pasupathy, R. (2014). Stochastically constrained simulation optimization on integer-ordered spaces: The cgR-SPLINE algorithm.
[28] Nelson, B. L., Matejcik, F. J. (1995). Using common random numbers for indifference-zone selection and multiple comparisons in simulation. Management Science, 41, 1935–1945.
[29] Nelson, B. (2013). Foundations and methods of stochastic simulation: a first course. New York, Springer.
[30] 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.
[31] 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.
[32] 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.
[33] Onwunalu, J. E., Durlofsky, L. J. (2010). Application of a particle swarm optimization algorithm for determining optimum well location and type. Computational Geosciences, 14, 183–198.
[34] Park, C., Kim, S. H. (2015). Penalty function with memory for discrete optimization via simulation with stochastic constraints. Operations Research, 63, 1195–1212.
[35] Pasupathy, R., Schmeiser, B. W. (2009). Retrospective-approximation algorithms for the multidimensional stochastic root-finding problem. ACM Transactions on Modeling and Computer Simulation, 19, 5.
[36] Pasupathy, R. (2010). On choosing parameters in retrospective-approximation algorithms for stochastic root finding and simulation optimization. Operations Research, 58, 889–901.
[37] Pichitlamken, J., Nelson, B. L. (2003). A combined procedure for optimization via simulation. ACM Transactions on Modeling and Computer Simulation , 13, 155– 179.
[38] Rinott, Y. (1978). On two-stage selection procedures and related probabilityinequalities. Communications in Statistics-Theory and methods, 78, 799–811.
[39] 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.
[40] 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.
[41] Sewell, E.C., Lee, A.J., Jacobson, S.H. (2013). Optimal allocation of aviation security screening devices. Journal of Transportation Security, 6, 103–116.
[42] Shi, L. (2000). Nested partitions method for stochastic optimization. Methodology and Computing in Applied probability, 2, 271–291.
[43] Snyman, J. A., Stander, N., Roux, W. J. (1994). A dynamic penalty function method for the solution of structural optimization problems. Applied Mathematical Modelling, 18, 453–460.
[44] Wang, H., Pasupathy, R., Schmeiser, B. W. (2013). Integer-ordered simulation optimization using R-SPLINE: Retrospective search with piecewise-linear interpolation and neighborhood enumeration. ACM Transactions on Modeling and Computer Simulation, 23, 17.
[45] Wang, H. (2012). Retrospective optimization of mixed-integer stochastic systems using dynamic simplex linear interpolation. European Journal of Operational Research, 217, 141-148.
[46] Zhang, Z.G., Luh, H.P., Wang, C.H. (2011). Modeling security-check queue. Management Science, 57, 1979–1995.
論文全文使用權限
  • 同意授權校內瀏覽/列印電子全文服務,於2021-07-25起公開。


  • 如您有疑問,請聯絡圖書館
    聯絡電話:(06)2757575#65773
    聯絡E-mail:etds@email.ncku.edu.tw