Rationalizing police patrol beats using heuristic-based clustering

Abstract

The division of police patrol districts affects patrol performance, such as average response time and workload variation. However, the possible sample space is large and the corresponding graph-partitioning problem is NP-complete. Moreover, the resulting patrol beats must be contiguous and compact.We propose a heuristic based, clustering method to divide a given police district into optimal patrol beats based on crime and census data. Use of past crime data, their severity, and census data results in more compact shapes with lower crime response time and equitable workload. Moreover, it enables defining patrol beats for different seasons and time shifts. Furthermore, we considered the actual road distance than the traditional Euclidean distance in responding to crimes. We demonstrated the utility of the proposed method using a real-world crime and census dataset. For the given dataset, maximum response time for Calls For Service (CFS) was 35.2 seconds, which is the time taken to travel to any point in the patrol beat from the optimum positioning of police patrol car. Compactness was measured using Isoperimetric Quotient values for each patrol beat, and the average compactness was 0.7 indicating good compactness. Gini Coefficient was 0.036, which indicates balanced workload distribution among patrol beats.