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.