A simulated annealing approach to police district design

This paper considers the problem of redistricting or redrawing police command boundaries. We model this problem as a constrained graph-partitioning problem involving the partitioning of a police jurisdiction into command districts subject to constraints of contiguity, compactness, convexity and size. Since the districting affects urban emergency services, there also exist quality-of-service constraints, which limit the response time (queue time plus travel time) to calls for service. Confronted with the combinatorial challenge of the districting problem, we propose a simulated annealing algorithm to search for a "good" partitioning of the police jurisdiction. At each iteration of the algorithm, we employ a variant of the well-known PCAM model to optimally assign the patrol cars and assess the "goodness" of a particular district design with respect to some prescribed performance measures. This approach differs from the well-known Hypercube queuing model, which simply evaluates the performance of a user-specified district design and allocation. A computational case study using data from the Buffalo, New York, Police Department reveals the merits of this approach. Two of the primary concerns of urban police departments are the effective use of patrol cars and the workload balance between officers in different geographical districts. In recent years, a well known, public domain software package based on the Patrol Car Allocation Model (PCAM) has been developed. PCAM was designed to help police management specify the number of patrol cars should be on management also faces the thorny problem of designing these districts. To address this problem, we employ a simulated annealing search method to determine the geographic boundaries between the police districts. PCAM is used to evaluate the "goodness" of each district design encountered in this search, where "goodness" involves minimizing the disparity between the maximum workload and the minimum workload of the police officers. Working with the Buffalo, New York, Police Department, we were able to significantly reduce officer workload disparity while maintaining current levels of response time.