警察巡邏路線規劃模式暨求解演算法之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：32

、訪客IP：3.137.216.240

姓名

黃品慈(Pin-Tzu Huang) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

警察巡邏路線規劃模式暨求解演算法之研究

相關論文

★ 橋梁檢測人力機具排班最佳化之研究	★ 勤業務專責分工下消防人員每日勤務排班最佳模式之研究
★ 司機員排班作業最佳化模式之研究	★ 科學園區廢水場實驗室檢驗員任務指派最佳化模式之研究
★ 倉儲地坪粉光工程之最佳化模式研究	★ 生下水道工程工作井佈設作業機組指派最佳化之研究
★ 急診室臨時性短期護理人力指派最佳化之探討	★ 專案監造人力調派最佳化模式研究
★ 地質鑽探工程人機作業管理最佳化研究	★ 職業棒球球隊球員組合最佳化之研究
★ 鑽堡於卵礫石層施作機具調派最佳化模式之研究	★ 職業安全衛生查核人員人力指派最佳化研究
★ 救災機具預置最佳化之探討	★ 水電工程出工數最佳化之研究
★ 石門水庫服務台及票站人員排班最佳化之研究	★ 空調附屬設備機組維護保養排程最佳化之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

我國現行警察勤務編排方式共有六種，分別是值班、備勤、守望、巡邏、臨檢與勤區查察，其中巡邏勤務被視為最具有主動發現問題與遏止犯罪發生之功效。近年來，政府陸續開放各類型之犯罪資料，使警政相關單位能更有效的運用這些資料，針對預期犯罪指數較高之路段進行巡邏，達到「預防犯罪」之目的，打造一個更安全的生活空間。
本研究係利用時空網路流動技巧，以定式巡邏車輛與時空中流動之情形，構建一警察巡邏路線規劃模式，本研究模式為一大型含額外限制之整數網路流動問題，屬NP-Hard問題。在求解方法上，利用C++程式語言配合數學規劃軟體CPLEX進行模式求解，當面臨實務上大型問題時，勢難以在有限時間內利用數學規劃軟體求得最佳解，緣此，本研究發展一啟發式演算法以有效地求解問題。最後，為評估模式及演算法之實用績效，本研究以國內某警察分局巡邏資料以及合理之假設進行範例測試，並針對不同參數進行敏感度分析，結果顯示本模式與演算法在實務上可有效的運用，並提供給警察單位作為警察巡邏路線規劃之參考。
關鍵詞：巡邏、路線規劃、時空網路、最佳化、啟發解法、整數網路流動

摘要(英)

Police serve in six ways nowadays: on shift, on duty, watch, patrols, check and district inspect. The patrol duty is regarded as a function of finding problems and stop ping the crime. In recent years, the government has gradually made the information of various types of crime, so that the relevant units can be more effective use of these information for the higher crime rate of the patrol road, hoping to achieve the goal of crime prevention and establishing a safer living space.
In this study, a model for police patrol routing is developed, where the time-space network flow technique is utilized to formulate the potential movements of police patrol car among all patrol spots in the dimensions of time and space. Mathematically, the model is formulated as an integer multiple-commodity network flow problem and is characterized as NP-hard. The C++ computer language, coupled with the CPLEX mathematical programming software, is employed to solve the problem. Since the problem size is expected to be huge, a solution algorithm based on a problem decomposition/collapsing technique is thus developed to efficiently solve the problem. To evaluate the performance of both models, the case studies using the real data from police station in Taiwan are tested. The test results show that the proposed model and solution algorithm could be useful for the program of the police patrol and used as a reference for the police station.
Keywords : Patrol, rout planning, time-space network, optimization, heuristic, integer multiple-commodity network flow problem

關鍵字(中)

★ 巡邏
★ 路線規劃
★ 時空網路
★ 最佳化
★ 啟發解法
★ 整數網路流動

關鍵字(英)

★ patrol
★ rout planning
★ time-space network
★ optimization
★ heuristic
★ integer multiple-commodity network flow problem

論文目次

摘　要 I
ABSTRACT II
目錄 IV
圖目錄 VII
表目錄 VIII
第一章緒論 1
1.1 研究背景與動機 1
1.2 研究目的與範圍 2
1.3 研究方法與流程 2
第二章文獻回顧 5
2.1 警察巡邏勤務 5
2.2 警察巡邏路線規劃方法 8
2.3 時空網路 10
2.4 大型含額外限制整數網路流動問題啟發式演算法 12
2.5 文獻評析 14
第三章模式構建 15
3.1 問題描述 15
3.2 模式架構 16
3.2.1 模式基本假設 16
3.2.2 巡邏路線規劃時空網路 18
3.2.3 符號說明與數學定式 24
3.2.3.1模式之符號說明 24
3.2.3.2數學定式 25
3.2.4 模式驗證 25
3.2.5 模式求解方法 28
3.2.5.1啟發解演算法 29
3.2.5.2目標值上限解 32
3.2.6 模式應用 33
3.3 小結 34
第四章範例測試 35
4.1 資料輸入 35
4.1.1 巡邏點相關資料 35
4.1.2 路段成本相關資料 36
4.1.3 其他相關參數設定 37
4.1.3.1模式參數設定 37
4.1.3.2演算法參數設定 38
4.2 電腦演算環境及設定 38
4.2.1 電腦演算環境 38
4.2.2 電腦參數設定 38
4.3 模式發展 40
4.3.1 測試之輸入與輸出資料 40
4.3.1.1輸入資料 40
4.3.1.2輸出資料 41
4.3.2 問題規模 41
4.4 測試結果分析 42
4.4.1 啟發解演算法之參數測試分析 42
4.4.2 模式結果分析 47
4.4.3 模式及演算法求解結果與實際規劃情況之比較 51
4.5 模式之參數敏感度分析 52
4.5.1 行駛距離限制之敏感度分析 52
4.5.2 巡邏時段之敏感度分析 55
4.5.3 巡邏車輛數之敏感度分析 57
4.5.4 派出所數量之敏感度分析 58
4.6 小結 61
第五章結論與建議 62
5.1 結論 62
5.2 建議 63
5.3 貢獻 64
參考文獻 65
附錄 70
附錄一 CPLEX CALLABLE LIBRARY CODE 70
附錄二派出所及巡邏點輸入資料 72
附錄三警察巡邏路線之細部解 78

參考文獻

一、中文參考資料
1. 尤國楨（2003），警察巡邏管理制度之研究－以台北縣警察局為例，中國文化大學政治學研究所，碩士論文。
2. 呂宏軒（2014），市區公車路線及排程最佳化模式，國立中央大學土木工程學系，碩士論文。
3. 李郁華（1982），警察勤務，桃園：中央警察大學出版，修訂版。
4. 周義華、邱榮川（1987），配合捷運系統公車路網設計方法之研究，運輸計劃季刊，第16卷第1期，頁319-344。
5. 孟維德（2008），巡邏勤務效能的實驗研究，警察行政管理學報，頁27-93。
6. 林志誠（2007），警察巡邏勤務實施成效之研究－從問題導向警政策略探討，銘傳大學社會科學院國家發展與兩岸關係研究所，在職專班碩士論文。
7. 洪瓊絨（2004），警察巡邏勤務之研究－以屏東縣警局為例，國立中央警察大學行政警察研究所，碩士論文。
8. 崔世選、黃俊平（2013），正交網格網路之不連續線段的重複路徑研究，國立虎尾科技大學工業工程與管理學系，碩士論文。
9. 張志森（2016），105年警察勤務（含概要），台北：千華數位文化，頁124。
10. 張育銘（2014），應用時空網路建構貨櫃場內拖車排程與路線規劃模型，國立台灣海洋大學航運管理學系，碩士論文。
11. 張清峰（2012），警察機關巡邏勤務規劃與執行之研究－以新北市政府警察局分駐（派出）所為例，國立政治大學行政管理研究所，碩士論文。
12. 梅可望（1970），警察學原理，桃園：中央警察大學出版，頁367。
13. 許聖臣（1981），警察勤務，桃園：中央警察大學出版。
14. 熊銳、陳浩勳（1996），一種計劃與車間調度的集成模型及其拉氏鬆弛求解法，西安電子科技大學學報，第23卷第1期，頁509-516。
15. 陳春益、余秀梅（1993），次梯度資源導向分解演算法應用於動態貨櫃調度模式之研究，成功大學學報，第28卷，頁199-214。
16. 蔡文昉、王晉元（2000），大眾運輸排班系統之研究，交通大學運輸與物流管理學系，碩士論文。
17. 黃泊晴（2010），人工智慧最佳化於警車巡邏問題之研究，虎尾科技大學工業管理系研究所，碩士論文。
18. 楊瑞宇（2012），穩健公共自行車租用系統車輛配置模式，國立台北科技大學資訊與運籌管理研究所，碩士論文。
19. 劉政軒（2014），軸輻式貨運網路之駕駛排班問題，國立台灣科技大學工業管理系，碩士論文。
20. 蔡崑佑（2009），警察巡邏路線之研究，朝陽科技大學建築及都市設計研究所，碩士論文。
21. 蕭玉文（2011），警察勤務實用論，台北：臺灣警察專科學校，頁266-268。
22. 顏上堯、范琇綾、陳怡君（2016），橋樑定期檢測作業排程最佳化模式之研究，運輸計劃季刊，第45卷第1期，頁63-80。
23. 顏上堯、張紫鈺、陳怡君（2015），防災避難疏散排程規劃之研究，運輸學刊，第27卷第1期，頁565-588。
24. 顏上堯、陳俊穎、王領（2014），現有道路系統下通勤型自行車道初步路網設置之研究，運輸學刊，第26卷第4期，頁529-553。
25. 顏上堯、盧宗成、徐鸛侖（2015），考慮護運風險下保全運鈔車路線與排程模式暨演算法之研究，運輸計畫，第44卷第1期，頁45-68。
26. 警察機關設置及巡簽巡邏箱實施要點總說明，2012。
?
二、英文參考資料
27. Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W., & Vance, P. H. (1998). Branch-and-price: Column generation for solving huge integer programs. Operations research, 46(3), 316-329.
28. Benders, J. F. (1962). Partitioning procedures for solving mixed-variables programming problems. Numerische mathematik, 4(1), 238-252.
29. Chen, C. Y., & Kornhauser, A. L. (1990). Decomposition of convex mulitcommodity network flow problem. Report SOR-90-19, Dept. of Civil Engineering and Operations Research, Princeton University, Princeton, NJ.
30. Chen, H., Cheng, T., & Wise, S. (2017). Developing an online cooperative police patrol routing strategy. Computers, Environment and Urban Systems, 62, 19-29.
31. Chen, X. (2012). Fast patrol route planning in dynamic environments. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, 42(4), 894-904.
32. Chen, X. (2013). Police patrol optimization with security level functions. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 43(5), 1042-1051.
33. Chih, K. C. K. (1986). A real time dynamic optimal freight car management simulation of the multiple railroad, multiple commodity temporal spatial network flow problem (No. 86-16674 UMI).
34. Chu, J. C., Yan, S., & Chen, K. L. (2012). Optimization of earth recycling and dump truck dispatching. Computers & Industrial Engineering, 62(1), 108-118. Desaulniers, G., Desrosiers, J., Dumas, Y., Solomon, M. M., & Soumis, F. (1997). Daily aircraft routing and scheduling. Management Science, 43(6), 841-855.
35. Gilmore, P. C., Lawler, E. L., Shmoys, D. B., & Lawler, E. L. (1986). The Traveling Salesman Problem. A guided tour of combinatorial optimization. Lawler, Lenstra, Rinnooy Kan (Eds), 87-143.
36. Kennington, J., & Shalaby, M. (1977). An effective subgradient procedure for minimal cost multicommodity flow problems. Management Science, 23(9), 994-1004.
37. Lamatsch, A. (1992). An approach to vehicle scheduling with depot capacity constraints. In Computer-Aided Transit Scheduling (pp. 181-195). Springer, Berlin, Heidelberg.
38. Laporte, G. (1992), "The Vehicle Routing Problem：An Overview of Exact and Approximate Algorithms", European Journal of Operational Research, Vol. 59, 345-358.
39. Lu, C. C. (2016). Robust multi-period fleet allocation models for bike-sharing systems. Networks and Spatial Economics, 16(1), 61-82.
40. Mahmoudi, M., & Zhou, X. (2016). Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state–space–time network representations. Transportation Research Part B: Methodological, 89, 19-42.
41. Melo, A., Belchior, M., & Furtado, V. (2005, July). Analyzing police patrol routes by simulating the physical reorganization of agents. In International Workshop on Multi-Agent Systems and Agent-Based Simulation (pp. 99-114). Springer, Berlin, Heidelberg.
42. Mesquita, M., & Paixao, J. (1992). Multiple depot vehicle scheduling problem: A new heuristic based on quasi-assignment algorithms. In Computer-Aided Transit Scheduling (pp. 167-180). Springer, Berlin, Heidelberg.
43. Or, I. (1977), Traveling Salesman-type Combinatorial Problems and Their Relation to the Logistics of Regional Blood Banking, Ph.D. Dissertation, Northwestern University, Evanston, IL.
44. Reis, D., Melo, A., Coelho, A. L., & Furtado, V. (2006, May). Towards optimal police patrol routes with genetic algorithms. In International Conference on Intelligence and Security Informatics (pp. 485-491). Springer Berlin Heidelberg.
45. Telep, C. W., Mitchell, R. J., & Weisburd, D. (2014). How much time should the police spend at crime hot spots? Answers from a police agency directed randomized field trial in Sacramento, California. Justice Quarterly, 31(5), 905-933.
46. Yan, S. Y., Fan, H. L., Chen, Y. C. (2016), "An optimal routing and scheduling model for regular bridge inspections", Transportation Planning Journal, Vol. 45 No.1, 63-80.
47. Yan, S., & Chen, H. L. (2002). A scheduling model and a solution algorithm for inter-city bus carriers. Transportation Research Part A: Policy and Practice, 36(9), 805-825.
48. Yan, S., Hsiao, F. Y., & Chen, Y. C. (2015). Inter-school bus scheduling under stochastic travel times. Networks and Spatial Economics, 15(4), 1049-1074.
49. Yan, S., Lin, C. K., & Chen, S. Y. (2014). Logistical support scheduling under stochastic travel times given an emergency repair work schedule. Computers & Industrial Engineering, 67, 20-35.

指導教授

顏上堯(Shang-Yao Yan)

審核日期

2018-8-10

推文