隨機需求下警察巡邏勤務排程規劃最佳化

Police patrol duty is the core one among all police duties. Its schedule quality willaffect the related downstream plans, such as police manpower supply and policecrew assignment. However, with a shortage of manpower for the police unitsrecently, the patrol duty shift scheduling is conducted manually and each stationindependently assigns its patrol duties, without a systematic analysis. In addition,in real practice the patrol duty demands vary in different times, which would evenmore affect the patrol duty scheduling effectiveness. In literature, the relatedmodels and tests did not take into account the stochastic characteristics of patrolduties, making the schedule not complying with the reality and too optimistic inpractice. If the stochasticity of patrol duty demands is significant, the plannedschedule could be infeasible and has to be repeatedly adjusted in practice,possibly losing its planned optimality. In view of this, it is an important issue forthe police units to efficiently plan an effective police patrol duty schedule,considering the crime intensity of their responsible areas and stochastic demandsof police patrol duties, under limited police manpower in order to prevent crimeoccurrences.In this study, considering integration of mutual supports between different policestations, stochastic demands of patrol duties and related operating constraints,we utilize the mathematical programming method to develop a stochasticindividual planning model and a stochastic integrated planning model,respectively, based on the perspective of the decision makers in police units forpolice patrolling. These models are expectedly formulated as integer linearprograms which are characterized as NP-hard. As the number of stochasticscenarios increases, the problem scale will significantly increase. If they cannotbe solved directly using CPLEX, a heuristic algorithm based on a problemdecomposition techniques based on the problem feature, coupled with CPLEX,will be developed to efficiently solve the problems. To suitably evaluate bothmodels and solution algorithm, a case study using the real data from a policeprecinct in Taiwan will be performed, with parameter sensitivity analyses. Theperformance of the two models will also be compared. Moreover, since anaverage of all stochastic demands can be used as a deterministic demand, adeterministic model with a deterministic demand scenario can be deemed as aspecial case of a stochastic model. We will further compare the performancebetween the deterministic models and the stochastic models. Finally, theproposed models, the solution algorithm and the test results would be usefulreferences for the police units to effectively plan their police patrol duty schedulesand enhance their patrol efficiencies under limited police manpower.