混合警車與無人機巡邏路線規劃暨求解演算法之研究

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：87

、訪客IP：18.218.6.36

姓名

賴祐謙(Yu-Chien Lai) 查詢紙本館藏

畢業系所

土木工程學系

論文名稱

混合警車與無人機巡邏路線規劃暨求解演算法之研究

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

目前警察單位正面臨警力不足的問題，衍生勤務銜接不良的狀況，亦導致基層員警負擔加重，而近年來科技執法與智慧運輸興起，警政署與工研院藉此發展空中警車，以無人機改善勤務執行時耗費警力與機動性不佳之困境，根據其功能可運用於刑案偵辦以及交通觀測，並且擁有「通訊模組」、「自動化」、「充電系統」三大關鍵技術，亦適合執行警察勤務內之巡邏勤務。因此本研究規劃以警車搭配無人機之巡邏模式，節省警力巡邏時間，達到高效率之犯罪預防與嚇阻成效。
本研究係利用時空網路流動技巧，以定式警車與無人機在時空中流動之情形，構建一混合警車與無人機巡邏路線規劃模式，本研究模式為一大型含額外限制之整數網路流動問題，屬NP-hard問題。在求解方法上，利用C++程式語言配合數學規劃軟體CPLEX進行模式求解，當面臨實務上大型問題時，勢難以在有限時間內利用數學規劃軟體求得最佳解。緣此，本研究發展兩種啟發式解法－「區域切割法」「資源分解法」。為評估模式與演算法之實用性，本研究以某警察分局進行範例測試，首先針對不同參數進行敏感度分析，其次以規模變動和搭配組合進行方案分析，最後再以不同之規模，分析演算法之績效，結果顯示本模式可有效運用，且演算法求解效率良好，可供警察單位作為未來智慧巡邏發展成熟時之參考依據。

摘要(英)

At present, police units are facing the problem of insufficient police force. This results in the poor connection of each duty, and increases the burden of basic level polices. Recent years, technology enforcement and smart transportation have emerged rapidly which could be used for criminal investigations and traffic observations. It includes three key technologies "communication module", "automation" and "charging system", which is also suitable for performing patrol duties. Therefore, this research plans to construct a patrol mode with mixed vehicles and UAVs to save police patrol time, achieve high-efficiency crime prevention, and deterrence effects.
This research makes use of the time-space network flow techniques to define the flow of police vehicle and UAVs, construct a vehicle-UAV mixed patrol route planning model. The research model is a large-scale multiple-commodity network problem with additional restrictions. Which belongs to NP-Hard problem. In terms of the solution method, the C++ programming language is used with the mathematical planning software CPLEX to solve the model. When facing large-scale problems in reality, it is difficult to use the mathematical planning software to find the best solution within a limited of time. For this reason, this research develops two Heuristic solutions-"area cutting method" and "resource decomposition method". In order to evaluate the practicality of the model and algorithm, this study takes a police station to conduct a sample test. First, we analyze the sensitivity of different parameters. Next, we analyze the plan with scale and collocation. At last, we analyze the performance of the algorithm with different scales. The results show that this model can be used effectively, and the algorithm is very efficient. This indicates that the model can be used by police units as a reference for future smart patrol development when it is more mature.

關鍵字(中)

★ 警察巡邏
★ 無人機
★ 路線規劃
★ 整數網路流動
★ 啟發式解法

關鍵字(英)

論文目次

摘　要 I
ABSTRACT II
謝　誌 IV
目錄 VI
圖目錄 IX
表目錄 XI
第一章緒論 1
1.1 研究背景與動機 1
1.2 研究目的與範圍 4
1.3 研究方法與流程 5
第二章文獻回顧 7
2.1 警察巡邏勤務規劃方式 7
2.2 無人機於交通物流領域之應用 10
2.3 車輛途程問題 (VRP) 13
2.4 時空網路 17
2.5 文獻評析 19
2.6 大型含額外限制整數網路流動問題啟發式演算法 20
第三章模式構建 22
3.1 現況分析與問題描述 22
3.2 模式架構 24
3.2.1 模式基本假設 24
3.2.2 警車巡邏時空網路 26
3.2.3 無人機巡邏時空網路 33
3.2.4 符號說明與數學定式 36
3.2.4.1 模式之符號說明 36
3.2.4.2 數學定式 39
3.2.5 模式驗證 43
3.2.6 模式求解方法 48
3.2.6.1區域切割法 49
3.2.6.2資源分解法 51
3.3 小結 56
第四章範例測試 57
4.1 資料輸入 57
4.1.1 巡邏點相關資料 57
4.1.2 警車與無人機成本相關資料 59
4.1.3 其他相關參數設定 60
4.2 電腦演算環境及設定 62
4.2.1 電腦演算環境 62
4.2.2 電腦參數設定 62
4.3 模式發展 65
4.3.1 測試之輸入與輸出資料 65
4.3.1.1輸入資料 65
4.3.1.2輸出資料 66
4.3.2 問題規模 67
4.4 測試結果分析 69
4.4.1 資源分解法測試結果 69
4.4.2 區域切割法測試結果 71
4.4.3 測試結果比較 73
4.5 模式之參數敏感度分析 76
4.5.1 重複巡邏之折減犯罪涵蓋率值敏感度分析 76
4.5.2 規劃時間長度敏感度分析 79
4.5.3 無人機耗電量敏感度分析 82
4.5.4 無人機充電時間敏感度分析 84
4.6 模式之方案分析 86
4.6.1 派出所數量之方案分析 87
4.6.2 巡邏資源搭配方案分析 89
4.6.2.1 純無人機巡邏模式 89
4.6.2.2 純警車巡邏模式 92
4.6.2.3 搭配方案之結果分析 94
4.7 演算法績效分析 95
4.8 小結 101
第五章結論與建議 102
5.1 結論與貢獻 102
5.1.1 結論 102
5.1.2 貢獻 104
5.2 建議 104
參考文獻 106
附錄 111
附錄一 VRP相關問題之中英對照圖 111
附錄二派出所及巡邏點輸入資料 113
附錄三警察巡邏路線之細部解 119

參考文獻

一、中文參考資料
1. 工業技術與資訊月刊，(2018)，「電信操控無人機隊解決方案提升維安效率」，第323期，頁28-29。
2. 工業技術研究院與通訊研究所，(2017)，《電腦與通訊171期》智慧應用專輯。
3. 工業技術研究院與通訊研究所，(2020)，《電腦與通訊182期》智慧應用專輯。
4. 中光電智能機器人官方網站，https://www.coretronic-robotics.com/tw/product。
5. 內政部警政署，(2012)，《警察機關設置及巡簽巡邏箱實施要點》。
6. 中時新聞網，https://www.chinatimes.com/?chdtv。
7. 尤國禎，(2003)，「警察巡邏管理制度：以台北縣警察局為例」，中國文化大學政治學研究所，碩士論文。
8. 中華民國內政部警政署全球資訊，https://www.npa.gov.tw/NPAGip/wSite/mp?mp=1。
9. 石大明、陳一元、吳德常、林正軒，(2020)，「無人機山區物流應用技術分析」，機械工業雜誌，第448期，頁29-35。
10. 李美儀，(2016)，「車輛路線相關問題之回顧與國內發展之分析」，國立陽明交通大學運輸與物流管理學系碩士班，碩士論文。
11. 何冠緯，(2019)，「風向鄉村型多郵差途程問題研究-以多輛無人車巡邏途程規劃為例」，國立成功大學工業與資訊管理學系，碩士論文。
12. 邵珮琪、林清一、吳東凌，(2020)，「無人機於交通運輸領域應用與政策推動之探討」，運輸計畫季刊，第49卷，頁201-234。
13. 沈宗緯、洪迎哲、林雨萱，(2019)，「最鄰近點為準之集群調整法於求解具容量限制之車輛途程問題」，運輸學刊，第31卷，第4期，頁449-480。
14. 桃園市政府主管法規查詢系統，(2019)，《桃園市政府警察局勤務實施細則》。
15. 陳竹正，(2019)，「無人飛行器於化災的應用及管理方式」，環境事故簡訊電子報，第71期，專題文章欄。
16. 陳佳佑，(2010)，「台北市都市犯罪空間之研究-以治安顧慮地圖為研究方法」，臺北大學都市計劃研究所，學位論文。
17. 許政智、顏智平、鄧少華、董正談，(2015)，「警察巡邏勤務創新作為－結合近場通訊及全球衛星定位技術之運用」，資訊科技與社會學報，第15卷，頁21-35。
18. 張文彥、郭家勳、洪祥予、劉安倫、蔡旻亨、曾玟晴、吳賦哲，(2018)，「無人機路徑規劃」，TANET2018 臺灣網際網路研討會，頁1687-1692。
19. 國家發展委員會政府機關資訊通報，(2019)，「創新科技應用-警用無人機系統」，第360期。
20. 黃品慈，(2018)，「警察巡邏路線規劃模式暨求解演算法之研究」，國立中央大學土木工程系，碩士論文。
21. 曾麗卿、侯玉松、陳美珠，(2012)，「護理人員排班程式設計與實作」，醫療資訊雜誌，臺灣醫學資訊學會，21:1期，頁1-9。
22. 經緯航太官方網站，https://www.geosat.com.tw/TW/product-uav-alias.aspx。
23. 經濟部工業局「創業歸故里創新創業競賽」，https://sccontest.tca.org.tw/。
24. 潘育華，(2019)，「電信詐騙提款犯罪熱點之環境特性分析-以新竹市為例」，國立清華大學環境與文化資源學系，碩士論文。
25. 劉擇昌、鄧煌發、黃明昭、張智維、游柏輝，(2012)，「差異區域層次犯罪空間集群態樣分析-以台北市大安區住宅竊盜為例」，犯罪學期刊，第15卷，第1期，頁43-69。
26. 謝晨仰，(2016)，「運用資料探勘方法預測城市之犯罪類型」，國立陽明交通大學管理學院資訊管理學程，畢業論文。
27. 顏上堯、張紫鈺、陳怡君，(2015)，「防災避難疏散排程規劃之研究」，運輸學刊，第27卷，第4期，頁565-588。
28. 顏上堯、盧宗成、洪逸樺，(2020)，「機場出境行李卸載轉盤指派最佳化模式與演算法」，運輸計劃期刊，第49卷，第1期，頁93-116。
29. 顏上堯、盧宗成、徐鸛侖，(2015)，「考慮護運風險下保全運鈔車路線與排程模式暨演算法之研究」，運輸計劃季刊，第44卷，第1期，頁45-68。
30. 藍奕丞，(2020)，「以無人機配送餐點之最佳化排程問題」，國立陽明交通大學運輸與物流管理學系，碩士論文。
二、英文參考資料
22. Cokyasar, T. (2021) “Optimization of battery swapping infrastructure for e-commerce drone delivery”, Computer Communications, Vol 168, Pages 146-154.
23. Chen, H., Cheng, T., & Wise, S. (2017). “Developing an online cooperative police patrol routing strategy”, Computers, Environment and Urban Systems, Vol. 62, Pages 19-29.
24. Chung, S. H., Sah, B. & Lee, J., (2020), “Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions”, Computers & Operations Research, Vol. 123, 105004.
25. Dantzig, G. B. & Ramser, J. H. (1959). “The truck dispatching problem”. Management Science, 6 (1), Pages 80-91.
26. Felipe, A., Ortuño, M.T., Righini, G. & Tirado, G., (2014), “A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges”, Transportation Research Part E: Logistics and Transportation Review, Vol. 71, Pages 111-128.
27. Hessler, K. & Irnich, S., (2021), “A branch-and-cut algorithm for the soft-clustered vehicle-routing problem”, Discrete Applied Mathematics, Vol. 288, Pages 218-234.
28. Keisuke M., (2017), “A new model and approach to electric and diesel-powered vehicle routing”, Transportation Research Part E: Logistics and Transportation Review, Vol.107, Pages 23-37.
29. Karak, A. & Abdelghany, K., (2019), “The hybrid vehicle-drone routing problem for pick-up and delivery services”, Transportation Research Part C: Emerging Technologies, Vol. 102, Pages 427-449.
30. Koskosidis, A. Y., Powell, B. W. & Solomon, M.M, (2012), “A model with a solution algorithm for the cash transportation vehicle routing and scheduling problem”, Computers & Industrial Engineering, Vol. 63, Issue 2, Pages 464-473.
31. Lu, C. C., Yan, S. & Huang, Y. W. (2018), “Optimal scheduling of a taxi fleet with mixed electric and gasoline vehicles to service advance reservations”, Transportation Research Part C: Emerging Technologies, Vol. 93, Pages 479-500.
32. Murray, C. C., & Chu, A. G., (2015), “The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery”, Transportation Research Part C: Emerging Technologies, Vol 54, Pages 86-109.
33. Matos, M. R. S., Frota, Y. & Ochi, L. S., (2018), “Green Vehicle Routing and Scheduling Problemwith Split Delivery”, Electronic Notes in Discrete Mathematics, Vol. 69, Pages 13-20.
34. 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, Vol. 89, Pages 19-42.
35. Pedro L. Gonzalez-R, Canca, D., Jose L. Andrade-Pineda, Calle, M. & Jose M. Leon-Blanco., (2020), “Truck-drone team logistics: A heuristic approach to multi-drop route planning”, Transportation Research Part C: Emerging Technologies, Vol. 114, Pages 657-680.
36. Rosenfeld, A. & Maksimov, O., (2019), “Optimal cruiser-drone traffic enforcement under energy limitation”, Artificial Intelligence, Vol. 277, 103116.
37. Shu, C. F. & Huang, N. D., (2018), “Vulnerability of Snatch Thefts and Environmental Situations - Case Studies on a City in Taiwan”, Architecture Science, Vol. 17, Pages 31-56.
38. Vlahovic, N., Knezevic, B. & Batalic, P., (2016) “Implementing Delivery Drones in Logistics Business Process： Case of Pharmaceutical Industry”, International Journal of Mechanical and Industrial Engineering, Vol. 10, No. 12, Pages. 4026-4031.
39. Yaprak, U., Kılıç, F. & Okumuş, A. (2021), “Is the Covid-19 pandemic strong enough to change the online order delivery methods? Changes in the relationship between attitude and behavior towards order delivery by drone”, Technological Forecasting and Social Change, Vol 169, 120829.
40. Yang, L., Di, Z., Dessouky, M. M, Gao, Z. & Shi, J., (2020), “Collaborative optimization of last-train timetables with accessibility: A space-time network design based approach”, Transportation Research Part C: Emerging Technologies, Vol. 114, Pages 572-597
41. Yan, S., Lin, C. K. & Kuo, Z. Q., (2020), “Optimally locating electric scooter battery swapping stations and battery deployment”, Engineering Optimization, Vol 53, No. 5, Pages. 754-769 (16).
42. Yiannis, A. K., Warren, B. P. & Marius M. S., (1992), “An Optimization-Based Heuristic for Vehicle Routing and Scheduling with Soft Time Window Constraints”, Transportation Science, Vol. 26, issue 2, Pages 69-85.
43. Yan, S., Wang, S.S. & Wu, M.W., (2012), “A model with a solution algorithm for the cash transportation vehicle routing and scheduling problem”, Computers & Industrial Engineering, Vol. 63, Issue 2, Pages 464-473.
44. Zhen, Y., Zhou, K., Fang, H., Hu, L., Dai, Z., Liang, W. & Zhou, S., (2020), “Research on Hybrid Artificial Intelligence Optimization Algorithm for Grain Transportation”, Journal of Computers, Vol. 31, No. 2, Pages 35-44.

指導教授

顏上堯

審核日期

2021-7-20

推文