Determining optimal police patrol areas with maximal covering and backup covering location models. (English) Zbl 1183.90288

Summary: This paper presents a new method for determining efficient spatial distributions of police patrol areas. This method employs a traditional maximal covering formulation and an innovative backup covering formulation to provide alternative optimal solutions to police decision makers, and to address the lack of objective quantitative methods for police area design in the literature or in practice. This research demonstrates that operations research methods can be used in police decision making, presents a new backup coverage model that is appropriate for patrol area design, and encourages the integration of geographic information systems and optimal solution procedures. The models and methods are tested with the police geography of Dallas, TX. The optimal solutions are compared with the existing police geography, showing substantial improvement in number of incidents covered as well as total distance traveled.


90B90 Case-oriented studies in operations research
90B80 Discrete location and assignment
90C27 Combinatorial optimization
Full Text: DOI


[1] AdensoDiaz B, Rodriguez F (1997) A simple search heuristic for the MCLP: Application to the location of ambulance bases in a rural region. Omega-Int J Manag Sci 25:181–187
[2] Aly AA, Litwhiler DW (1979) Police briefing stations: a location problem. AIIE Trans 11:12–22
[3] Aly AA, Litwhiler DW, Heggy T (1982) Operations research: a useful police management tool. J Police Sci Adm 3:279–283
[4] Berman O, Krass D (2002) The generalized maximal covering location problem. Comput Oper Res 29:563–581 · Zbl 0995.90056
[5] Birge JR, Pollock SM (1989) Modelling rural police patrol. J Oper Res Soc 40:41–54
[6] Bodily SE (1978) Police sector design incorporating preferences of interest groups for equality and efficiency. Manage Sci 24:1301–1313 · Zbl 0386.90037
[7] Brown K, Coulter PB (1983) Subjective and objective measures of police service delivery. Public Administration Review 43:50–58
[8] Carroll JM, Laurin PG (1981) Using simulation to assign police patrol zones. Simulation 36:1–12
[9] Chaiken JM (1978) Transfer of emergency service deployment models to operating agencies. Manage Sci 24:719–731 · Zbl 0375.90045
[10] Chaiken JM, Dormont P (1978a) Patrol car allocation model–background. Manage Sci 24:1280–1290 · Zbl 0386.90036
[11] Chaiken JM, Dormont P (1978b) Patrol car allocation model–capabilities and algorithms. Manage Sci 24:1291–1300 · Zbl 0386.90036
[12] Chung CH (1986) Recent applications of the Maximal Covering Location Planning (MCLP) Model. J Oper Res Soc 37:735–746 · Zbl 0601.90043
[13] Church RL (2002) Geographical information systems and location science. Comput Oper Res 29:541–562 · Zbl 0995.90067
[14] Church RL, ReVelle CS (1974) The maximal covering location problem. Pap Reg Sci Assoc 32:101–118
[15] Church RL, ReVelle CS (1976) Theoretical and computational links between p-median, location set-covering, and maximal covering location problem. Geogr Anal 8:406–415
[16] Church RL, Sorenson P (1994) Integrating normative location models into GIS: problems and prospects with p-median model. Report No. 94-5. National Center for Geographic Information and Analysis. Santa Barbara, CA
[17] Church RL, Current J, Storbeck J (1991) A Bicriterion maximal covering location formulation which considers the satisfaction of uncovered demand. Decis Sci 22:38–52
[18] Church RL, Stoms DM, Davis FW (1996) Reserve selection as a maximal covering location problem. Biol Conserv 76:105–112
[19] Craglia M, Haining R, Wiles P (2000) A comparative evaluation of approaches to urban crime pattern analysis. Urban Stud 37:711–729
[20] Current JR, Okelly M (1992) Locating emergency warning sirens. Decis Sci 23:221–234
[21] Current JR, Schilling DA (1990) Analysis of errors due to demand data aggregation in the set covering and maximal covering location–problems. Geogr Anal 22:116–126
[22] Curtin KM, Hayslett-McCall K (2006) Survey of crime mapping professionals (August)
[23] Curtin KM, Qiu F, Hayslett-McCall K, Bray TM (2005) Integrating GIS and maximal covering models to determine optimal police patrol areas. In: Wang F. (ed.) Geographic Information Systems and Crime Analysis Hershey: IDEA Group Publishing, pp 214–235
[24] D’Amico SJ, Wang S, Batta R, Rump CM (2002) A simulated annealing approach to police district design. Comput Oper Res 29:667–684 · Zbl 0995.90609
[25] Dallas Police Department (2002a) Cartographic boundary files. Dallas, TX
[26] Dallas Police Department (2002b) Crime incident database
[27] Dantzig G (1957) Discrete-variable extremum problems. Oper Res 5:266–277
[28] Daskin MS (1995) Network and discrete location. John Wiley & Sons, Inc., New York
[29] Daskin MS, Stern EH (1981) A hierarchical objective set covering model for emergency medical service vehicle deployment. Transp Sci 15:137–152
[30] Galvao RD, ReVelle C (1996) A Lagrangean heuristic for the maximal covering location problem. Eur J Oper Res 88:114–123 · Zbl 0913.90200
[31] Galvao RD, Espejo LGA, Boffey B (2000) A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem. Eur J Oper Res 124:377–389 · Zbl 0967.90068
[32] Green LV (1984) A multiple dispatch queueing model of police patrol operations. Manage Sci 30:653–664 · Zbl 0551.90027
[33] Green LV, Kolesar PJ (1984a) A comparison of the multiple dispatch and M/M/c priority queueing models of police patrol. Manage Sci 30:665–670 · Zbl 0551.90028
[34] Green LV, Kolesar PJ (1984b) The feasibility of one-officer patrol in New York City. Manage Sci 30:964–981
[35] Green LV, Kolesar PJ (1989) Testing the validity of a queueing model of police patrol. Manage Sci 35:127–148
[36] Green LV, Kolesar PJ (2004) Improving emergency responsiveness with management science. Manage Sci 50:1001–1014
[37] Harries K (1999) Mapping crime: principle and practice. NCJ178919. National Institute of Justice, Washington DC
[38] Hill B (2006) Crime analyst via crimemap Listserve
[39] Hillier FS, Lieberman GJ (1995) Introduction to operations research. McGraw-Hill, New York
[40] Hogan K, ReVelle C (1986) Concepts and applications of backup coverage. Manage Sci 32:1434–1444
[41] Kane K (2006) Strategic crime analyst via crimemap Listserve
[42] Kern GM (1989) A computer simulation model for the study of police patrol deployment. Simulation 52:226–232
[43] Kwak NK, Leavitt MB (1984) Police patrol beat design–allocation of effort and evaluation of expected performance. Decis Sci 15:421–433
[44] Larson RC (1975) Approximating performance of urban emergency service systems. Oper Res 23:845–868 · Zbl 0326.60117
[45] Larson RC (1978) Police deployment–introduction. Manage Sci 24:1278–1279
[46] Levine N (2006) Developer Crimstat via Crimemap Listserve
[47] Maranzana F (1964) On location of supply points to minimize transport costs. Oper Res Q 15:261–270
[48] Marble D (2006) Professor Emeritus. The Ohio State University, via Crimemap Listserve
[49] Mitchell P (1972) Optimal selection of police patrol beats. J Crim Law Criminol Police Sci 63:577–584
[50] Moonen M (2005) Patrol deployment, districting, and dispatching within the urban police: state of the art. Centre for Industrial Management, Leuven
[51] Pirkul H, Schilling DA (1988) The siting of emergency service facilities with workload capacities and backup service. Manage Sci 34:896–908
[52] Pirkul H, Schilling DA (1991) The maximal covering location problem with capacities on total workload. Manage Sci 37:233–248 · Zbl 0732.90045
[53] Priest TB, Carter DB (1999) Evaluations of police performance in an African American sample. J Crim Justice 27:457–465
[54] ReVelle C, Snyder S (1995) Integrated fire and ambulance siting: a deterministic model. Socio Econ Plann Sci 29:261–271
[55] ReVelle C, Schweitzer J, Snyder S (1996) The maximal conditional covering problem. Infor 34:77–91 · Zbl 0868.90084
[56] Sacks SR (2000) Optimal spatial deployment of police patrol cars. Soc Sci Comput Rev 18:40–55
[57] Sherman LW, Gottfredson D, MacKenzie D, Eck J, Reuter P, Bushway S (2004) Preventing crime: what works, what doesn’t, what’s promising. Department of Criminology and Criminal Justice: University of Maryland
[58] Skogan WG (2004) CAPS at ten: community policing in Chicago: an evaluation of Chicago’s alternative policing strategy. Institute for Policy Research, Northwestern University, Chicago
[59] Taylor PE, Huxley SJ (1989) A break from tradition for the San-Francisco police–patrol officer scheduling using an optimization-based decision support system. Interfaces 19:4–24
[60] Teitz MB, Bart P (1968) Heuristic methods for estimating the generalized vertex median of a weighted graph. Journal of the Operational Research Society of America 16:955–961 · Zbl 0165.22804
[61] Zanakis SH, Evans JR, Vazacopoulos AA (1989) Heuristic methods and applications–a categorized survey. Eur J Oper Res 43:88–110 · Zbl 0681.90090
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.