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

NCU Institutional Repository > 工學院 > 土木工程研究所 > 博碩士論文 > Item 987654321/87077

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/87077

題名:	混合警車與無人機巡邏路線規劃暨求解演算法之研究
作者:	賴祐謙;Lai, Yu-Chien
貢獻者:	土木工程學系
關鍵詞:	警察巡邏;無人機;路線規劃;整數網路流動;啟發式解法
日期:	2021-07-20
上傳時間:	2021-12-07 14:53:51 (UTC+8)
出版者:	國立中央大學
摘要:	目前警察單位正面臨警力不足的問題，衍生勤務銜接不良的狀況，亦導致基層員警負擔加重，而近年來科技執法與智慧運輸興起，警政署與工研院藉此發展空中警車，以無人機改善勤務執行時耗費警力與機動性不佳之困境，根據其功能可運用於刑案偵辦以及交通觀測，並且擁有「通訊模組」、「自動化」、「充電系統」三大關鍵技術，亦適合執行警察勤務內之巡邏勤務。因此本研究規劃以警車搭配無人機之巡邏模式，節省警力巡邏時間，達到高效率之犯罪預防與嚇阻成效。本研究係利用時空網路流動技巧，以定式警車與無人機在時空中流動之情形，構建一混合警車與無人機巡邏路線規劃模式，本研究模式為一大型含額外限制之整數網路流動問題，屬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.
顯示於類別:	[土木工程研究所] 博碩士論文

文件中的檔案:

檔案	描述	大小	格式	瀏覽次數
index.html		0Kb	HTML	55	檢視/開啟

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....