| 摘要: | 我國現行警察勤務編排方式共有六種，分別是值班、備勤、守望、巡邏、臨檢與勤區查察，其中巡邏勤務被視為最具有主動發現問題與遏止犯罪發生之功效。近年來，政府陸續開放各類型之犯罪資料，使警政相關單位能更有效的運用這些資料，針對預期犯罪指數較高之路段進行巡邏，達到「預防犯罪」之目的，打造一個更安全的生活空間。
本研究係利用時空網路流動技巧，以定式巡邏車輛與時空中流動之情形，構建一警察巡邏路線規劃模式，本研究模式為一大型含額外限制之整數網路流動問題，屬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 |
