Article ID: | iaor20023320 |
Country: | United Kingdom |
Volume: | 29 |
Issue: | 6 |
Start Page Number: | 667 |
End Page Number: | 684 |
Publication Date: | May 2002 |
Journal: | Computers and Operations Research |
Authors: | Batta Rajan, Rump Christopher M., Wang Shoou-Jiun, D'Amico Steven J. |
Keywords: | location, heuristics, optimization: simulated annealing, queues: applications |
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.