鐵路、捷運等軌道式大眾運輸系統具有固定路線﹑班次﹑及停靠站的特性，為先進都會區內或區間的主要大眾運輸系統，肩負都會區大量人群旅運需求的運送任務，因此其維安需求十分重要。目前此類運輸系統的維安資源大多進駐於靜態的車站內，而非分配在動態的車輛上。由於軌道車輛為密閉空間，倘若車輛在兩停靠站間的運行過程中發生嚴重的危安問題時，進駐於車站等外界的維安資源勢必無法及時處理。以北捷為例，其於2014年5月21日到2015年7月20日期間發生的11起衝突事件中，即有8起是發生在移動列車上。為能即時處理移動列車上的維安任務，假設維安人力僅依靠轉乘方式於列車間移動巡邏，倘若某列車之某運行路段上有足夠之維安人力佈署，則該路段上的所有旅運人次皆可視為已受到保護，本研究以盡可能保護越多旅運人次為主要考量，探討數種最佳維安人員巡邏路線規劃問題。
首先，本研究將各列車路線上各停靠車站依不同時間以時空二維網路運行圖呈現，並依此建構整數規劃模式求解以下三個最佳維安人員巡邏路線規劃問題： (1)如何以最少維安人員來巡邏而能保證所有列車隨時至少佈署足夠之維安人員？(2)如何以給定的維安人員種類與數量，規劃其最佳之巡邏排程與路線，而使其達到最好的維安效果（譬如能保護到最多的總旅運人次）？(3)如何同時考慮攻擊者和維安人員的策略，使現有維安人員的巡邏路線能夠極小化攻擊者所能造成的最大影響？針對上述前兩種問題，本研究考量不同層級維安人員的可替代性，發展整數規劃模式求解；而第三種問題實為一個雙層規劃問題，我們發展一疊代式演算法整合整數規劃模式求解。此外，在後兩問題中，我們提出兩種路段節線的維安效果（亦即影響程度）估算方式：(1)考慮各路段的旅運人次與時間長度、(2) 只考慮各路段的旅運人次，供決策者依其需求調配權重來估算。
數值分析結果顯示2016年8月的北捷和高捷之維安人數(分別為128、68人)皆少於本論文所求出的理想安全運輸系統的維安人數，但若能依照本論文求解出的最佳巡邏路線來巡邏，現有之維安人力將可顧及約80%以上的維安需求。

Rail transit features fixed routes, schedules and stations which make it become the main public transport system within urban area and between cities. Presently, police are usually assigned to stations rather than to moving trains. However, trains are confined space which means police in the station definitely can’t rescue the passengers in time if a severe problem strikes. This research will formulate the problem as a time-space network which can show each train’s location at different time, and then propose integer programming models to solve first two main problems: (1) how many police are needed to make sure that each train can be protected by at least one police, (2) how to determine the best patrol route for the high ranking trains under the limited number of police. (3) How to determine the best patrol route to minimize the maximal damage made by attackers in a way that consider both police’ and attacker’s strategy, which is a bi-level programming problem, so we propose an iterator method with an integer programming model to solve it. This research also develops two formulations to estimate the demand of security manpower and the degree of damage for each train at different time windows. Numerical analysis shows that numbers of police in Taipei metro system are less than the optimized one; however, it can still cover up over 80% of the security demand via our optimized patrolling route.

陳思齊. (2007). 巡邏車輛途程問題. 中央大學土木工程學系學位論文, 1-103.

Birge, J. R., & Pollock, S. M. (1989). Modelling rural police patrol. Journal of the Operational Research Society, 41-54.

Chircop, P. A., Surendonk, T. J., van den Briel, M., & Walsh, T. (2013). A column generation approach for the scheduling of patrol boats to provide complete patrol coverage.In 20th International Congress on Modelling and Simulation. No. December (pp. 1-6).

Curtin, K. M., Hayslett-McCall, K., & Qiu, F. (2010). Determining optimal police patrol areas with maximal covering and backup covering location models. Networks and Spatial Economics, 10(1), 125-145.

Dantzig, G, B., and Ramser, J, H. (1959). The truck dispatching problem. Management Seicence, .6, 80-91.

Guan, M. (1962). Graphic Programming Using Odd and Even Points. Chinese Mathematics, .1, 273-277.

Hansen,P.,Jaumard,B.,&Savard,G.(1992). New branch-and-bound rules for linear bilevel
programming. SIAM Journal on Scientificand Statistical Computing,13(5),1194–1217.

Jin, J. G., Lu, L., Sun, L., & Yin, J. (2015). Optimal allocation of protective resources in urban rail transit networks against intentional attacks.Transportation Research Part E: Logistics and Transportation Review, 84, 73-87.

Keskin, B. B., Li, S. R., Steil, D., & Spiller, S. (2012). Analysis of an integrated maximum covering and patrol routing problem. Transportation Research Part E: Logistics and Transportation Review, 48(1), 215-232.

Li, S. R., & Keskin, B. B. (2013). Bi-criteria dynamic location-routing problem for patrol coverage. Journal of the Operational Research Society, 65(11), 1711-1725.

Lau, H. C., & Gunawan, A. (2012). The patrol scheduling problem. Practice and Theory of Automated Timetabling (PATAT).29-31 August 2012

Loukaitou-Sideris, A., Taylor, B. D., & Fink, C. N. (2006). Rail Transit Security in an International Context Lessons from Four Cities. Urban Affairs Review, 41(6), 727-748.

Powell, J., & Fletcher, D. (2011). The need for developing an effective and acceptable engineering response to terrorist attacks on railway systems.Proceedings of the Institution of Mechanical Engineers, Part F: Journal of Rail and Rapid Transit, 225(4), 359-371.

Starita, S., & Scaparra, M. P. (2016). Optimizing dynamic investment decisions for railway systems protection. European Journal of Operational Research,248(2), 543-557.

Snijders, H., & Saldanha, R. L. (2015). Security crew scheduling at Netherlands Railways. CASPT 2015

Washburn, A., & Wood, K. (1995). Two-person zero-sum games for network interdiction.
Operations Research, 43(2), 243-251.