Keywords

1 Introduction

We are the lucky witnesses of a revolution taking place in the way police agencies work. In the last decade, we have seen the rise of predictive policing, i.e., the use of mathematical and statistical methods in law enforcement to predict future criminal activity based on past data. Its importance has been even recognized by Time magazine that in November 2011 named predictive policing as one of the 50 best inventions of 2011 [15].

Apart from crime forecasting, mathematics still have a major role to play in policing and its various disciplines can help by giving police agency a new edge in the fight against crime. This is also recognized by the RAND Corporation and the National Institute of Justice of the United States (NIJ). In fact, both these prestigious institutions acknowledge the need for taking a step forward and developing explicit methodologies and tools to take advantage of the information provided by predictive policing models to support decision makers in law enforcement agencies [24].

Districting models are a natural way to make use of crime forecasts to design police districts tailored to the criminal behavior of an area. During most of the twentieth century, police districts were drawn by police officers on a road map with a marker, just by following the major streets in the area, or according to neighborhood perimeters, without considering workload efficiency or balance [3]. The first model for the design of police district was formulated by Mitchell [23], almost 50 years ago. Since then, a number of mathematical optimization models have been proposed and the police districting problem (PDP) was born. The objective of the PDP is to partition the territory under the jurisdiction of a Police Department in the “best possible way.” PDP models normally consider several attributes, such as time, cost, performance, and other topological characteristics.

Geographic information systems (GIS), thanks to their ability to represent and manipulate geographical data using a reasonable amount of computational time, gained popularity among both academics and practitioners which started to contemplate the possibility of adopting automatic methodologies for the definition of police districts [28]. However, studies integrating GIS and sophisticated mathematical modeling for police districting remain a rarity [3], and the design of police districts is often based on the experience and intuition of few experts. Nevertheless, the importance of a balanced definition of the police districts is unquestioned and the implementation of decision-aid tools for the allocation of police resources has proven to be extremely beneficial, as shown by the numerous papers presented in the academic literature in the last decades [13]. In fact, all the researches report a dramatic improvement in workload distribution compared to hand-made districts which, in turn, results in enhanced performance and efficiency.

In this chapter we provide a general definition for the PDP and analyze in detail the literature related to this topic. The PDP is formally presented in Sect. 2.2. In Sect. 2.3, previous contributions in this line of research are categorized in terms of attributes considered and methodologies and approaches adopted for the problem solution. Next, an annotated bibliography is provided, where a brief description of the most salient points of each research is given (see Sect. 2.4). Conclusions are given in Sect. 2.5.

2 The Police Districting Problem

In the USA, the territory under the jurisdiction of a police department is partitioned according to a hierarchical structure constituted by command districts (or precincts), patrol sectors (or beats), and reporting districts (or r-districts or blocks). Command districts host the headquarters where the commanding officer supervises the operations and are fractioned into patrol sectors. Patrol sectors have one or more cars assigned which patrol the area and attend to the calls for service that originate in the sector. R-districts represent the smallest geographical unit for which statistics are kept and are, de facto, the atomic element in the hierarchy. Sarac et al. [26] explain that r-districts can coincide with census block groups as it is convenient to do so for administrative reasons. The territorial structure in Europe is not as homogeneous as in the USA, as it depends on the country or the region considered. However, a hierarchal structure similar to the one adopted in USA is predominant.

The PDP concerns the optimal grouping of blocks into “homogeneous” patrol sectors in such a way that all the territory is partitioned and that no sector is empty. It is desirable for the patrol sectors to be connected and topologically efficient (e.g., compact). In fact, the car(s) assigned to the patrol sector should respond to all the incidents taking place in the area and, therefore, topologically efficient sectors would result in a diminished travel time and, in turns, in a higher operational effectiveness. Normally, if all the cars in a sector are busy responding calls, a car from a neighboring sector has to attend the incoming calls. This generally leads to a domino effect where cars are pulled from their area to another, leaving the patrol sector unattended and, therefore, more susceptible to criminal incidents (as pointed out by Mayer [21]). In the light of this scenario, balanced workload among the districts and enforcement of a maximal response time become of primary importance.

Figure 2.1 shows a crime heat-map for a Saturday night shift in the Central District of Madrid, Spain, and the corresponding PDP solution. The borders of the census districts have been plotted in black, the streets in gray and each patrol sector is represented by a different color. It can be observed that the sector design is adjusted to provide an equitable territory partition among the beats.

Fig. 2.1
figure 1

Crime heat-map for a Saturday night shift in the Central District of Madrid, Spain (left), and sample solution obtained by a PDP model. The borders of the census districts have been plotted in black, the streets in gray and each patrol sector is represented by a different color. Source: Liberatore and Camacho-Collados [20]

Full size image

A generic formulation for the PDP is given in the following.

$$\displaystyle \begin{aligned}\begin{array}{r*{20}l} \min \quad & obj\left(P\right){} \end{array}\end{aligned} $$
(2.1a)
$$\displaystyle \begin{aligned}\begin{array}{r*{20}l} \mathrm{subject to} \quad & \emptyset\notin P{} \end{array}\end{aligned} $$
(2.1b)
$$\displaystyle \begin{aligned}\begin{array}{r*{20}l} & \bigcup_{A\in P}A=N{} \end{array}\end{aligned} $$
(2.1c)
$$\displaystyle \begin{aligned}\begin{array}{r*{20}l} & A\cap B=\emptyset && A, B\in P\left|A\neq B\right.{} \end{array}\end{aligned} $$
(2.1d)
$$\displaystyle \begin{aligned}\begin{array}{r*{20}l} & \left| P \right| = p {} \end{array}\end{aligned} $$
(2.1e)
$$\displaystyle \begin{aligned}\begin{array}{r*{20}l} & Conn\left(A\right) = 1 &\qquad & A \in P{} \end{array}\end{aligned} $$
(2.1f)

The model optimizes a certain objective function evaluated on a partition P. Constraints (2.1b)–(2.1d) represent the conditions held by a partition P defined on the set of blocks N: P should not contain the empty set ∅ (2.1b), the partition covers entirely N (2.1c), and the sectors are pairwise disjoint (2.1d). The restriction (2.1e) concerns the partition cardinality and enforces the number of patrol sectors to be exactly p. Finally, condition (2.1f) regards the geometry of the patrol sectors. \(Conn\left (A\right )\) is an indicator function that equals 1 when A is connected and zero otherwise. Therefore, this constraint establishes that only connected partition blocks are feasible. This condition implies that an agent cannot be assigned to a patrol sectors spanning two or more separate areas of the city.

In its most basic form, the PDP is not different from any districting problem. Of course, the basic formulation can be enriched with specific constraints and conditions. In particular, the different PDP presented in the literature includes attributes and parameters that represent the idiosyncrasies of the policing context, as explained in the following section.

3 Literature Review

This section is devoted to an analysis and categorization of the attributes and methodologies adopted in the literature on the PDP. A summary of the findings is illustrated in Table 2.1, where the most salient characteristics of each contribution are presented.

Table 2.1 Mapping of attributes considered and methodology adopted, by article
Full size table

3.1 Attributes

While analyzing the existing literature on the PDP, certain basic features common to all contributions emerged. In fact, all the applications considered include measures for workload, response time, and geometrical properties of the districts. Nevertheless, the implementation shows significant variations. Differently from Kalcsics and Schröeder [17], the denomination “attributes” has been adopted instead of “criteria” with the aim to provide a more generic framework that classifies all the relevant characteristics of a PDP solution, regardless of whether they are optimized in the objective function, or expressed as constraints.

3.1.1 Workload

Given the complex nature of police procedures and operations, and the great variability of tasks that an agent can undertake, defining workload could be complicated. Bruce [3] poses a number of questions that can help to clarify what to consider as part of the workload. Albeit difficult, an accurate definition of workload is desirable as it ensures homogeneity in terms of quality and speed of service, and equalizes the burden on police officers [2].

In the literature on the PDP, different definitions of workload have been adopted. Mitchell [23] computes the workload as the sum of the total expected service time and the total expected travel time. Curtin et al. [11, 12] use the number (or frequency) of calls (or incidents) occurring at each district as a proxy for the workload. As different calls can have different service time, some authors reckon that this measure is too naïve as it might produce unbalanced patrol districts. For Bodily [2] and D’Amico et al. [13] workload is defined as the fraction of working time that an agent spends attending to calls. An equivalent measure is proposed by Benveniste [1]. Given the stochastic nature of her model, workload is measured in terms of probability of a patrol car being busy. Once the probability is known, the time spent attending and answering calls can be easily calculated. More recently, workload has been defined as a combination of different characteristics. Sarac et al. [26] aggregate population and call volume. Kistler [18] makes use of the convex combination of total hours worked (i.e., from dispatch to call clearance), number of calls, and population. Zhang and Brown [29,30,31] consider both average travel time and response time. Camacho-Collados et al. [6] and Liberatore and Camacho-Collados [20] define workload as the weighted combination of multiple attributes: area, risk, isolation, and diameter. Finally, Piyadasun et al. [25] define the workload as the sum of the distance of the district center to its crime points, weighted by the severity of the crime. Interestingly, equality in the distribution of the workload among patrol sectors is measured using the Gini coefficient.

3.1.2 Response Time

Response time is an important performance measure representing the time between the arrival of a call for service and the arrival of a unit at the incident location. According to Bodily [2], the reduction of the response time results in a number of beneficial effects such as:

  • Increased likelihood of intercepting a crime in progress.

  • Deterrent effect on criminals.

  • Increased confidence of citizens in the police.

Generally speaking, most of the authors consider exclusively travel times [2, 18, 23, 29,30,31] or travel distances [1, 11, 12]. The only study considering queuing effect is by D’Amico [13], where the authors apply an external model—PCAM [7, 8]—to compute the total response time including calls queuing time and travel time to the incident location.

3.1.3 Geometry

In 1812, Albright Gerry, the Governor of the State of Massachusetts at the time, manipulated the division of his state and proposed a salamander-shaped district to gain electoral advantage, leading to the expression “gerrymandering” (resulting from merging “Gerry” and “salamander”). Since then, designing electoral districts having certain geometric properties is of primary importance to ensure neutrality and prevent political interference in the districting process.

In the context of the PDP, geometric attributes are still relevant for efficiency (e.g., establishing boundaries that would be easy to patrol and would not frustrate patrol officers) and for administrative reasons (e.g., coordination with other agencies). A number of researches explicitly include geometric properties in the design process, as the properties of compactness [6, 13, 18, 20, 26], contiguity [6, 13, 20, 26], and convexity [6, 13, 20] are generally obtained as a consequence of optimizing the travel distance or the travel time. Also, the district area is considered in all the mentioned works. Camacho-Collados et al. [6] and Liberatore and Camacho-Collados [20] achieve compactness by minimization of the sectors’ diameter. Additionally, Kistler [18], Camacho-Collados et al. [6], and Liberatore and Camacho-Collados [20] include the total length of the streets in a patrol sector.

3.1.4 Other Attributes

Recently, a number of attributes that do not fall into any of the previous categories have been introduced by some works. These attributes generally try to capture complex real-world requirements. The Buffalo Police Department needed to redesign r-districts in such a way that the existing district boundaries would be respected, and the access to demographic data as well as the use by other agencies would be easy [26]. The Tucson Police Department needed to consider the boundaries of gang territories, city council wards, neighborhood associations, and the Davis–Monthan Air Force Base [18]. Curtin et al. [12] introduce backup coverage (i.e., multiple coverage) of incident locations. Camacho-Collados et al. [6] and Liberatore and Camacho-Collados [20] define an isolation attribute that expresses how far the sector is with respect to the others. The rationale is that a more isolated sector can receive less support than a more central one. Finally, Bucarey et al. [4] propose a prevention demand component that represents the need for police resources used for preventive patrols. This component is calculated as the maximum between three factors, each multiplied by a scaling coefficient. The factors considered are reported crime, population, and total kilometers of roads in the sector.

3.2 Methodologies and Approaches

Many districting approaches have appeared in the literature. In this subsection, the contributions are categorized according to the methodology adopted and their main characteristics are presented.

3.2.1 Optimization Models

According to Kalcsics and Schröeder [17], the first mathematical program for the Districting Problem was proposed by Hess et al. [16], and regarded the neutral definition of political district. Since then, a large number of models have been presented, mostly in the context of location analysis. Mitchell [23] defines a set partitioning model that considers minimizing the expected distance inside of each subset and equalizing workload among all the subsets. Curtin et al. [11, 12], propose maximal covering models. Cheung et al. [9] and Chow et al. [10] consider both the p-median problem and the maximum coverage problem. Bucarey et al. [4] formulate their problem as an enriched p-median model. Finally, Camacho-Collados et al. [6] and Liberatore and Camacho-Collados [20] introduce a multi-criteria police districting problem that provides a balance between efficience and workload homogeneity, according to the preferences of a decision maker. It is important to notice that all these formulations, due to the size of the application context, are often solved heuristically. This is also the case for Piyadasun et al. [25] that, despite not presenting any mathematical formulation for their problem, solve it by means of an ad-hoc clustering heuristic.

A different perspective is adopted by Benveniste [1] and D’Amico et al. [13], where patrol cars and agents are modeled as servers in a stochastic model. In particular, Benveniste [1] proposes a stochastic optimization model, while D’Amico et al. [13] include a queuing model inside of a simulated annealing algorithm to compute response times that incorporate queuing effects.

3.2.2 Geographic Information Systems (GIS)

The first application of geography to crime analysis dates back to 1829, when the Italian geographer Adriano Balbi and the French lawyer André-Michel Guerry drew three maps of crimes in France, highlighting geographic patterns of crime and their relations [19]. Since then, the marriage between geography and criminology gave birth to numerous methodologies. When the GIS were developed, their implementation in law enforcement agencies and crime research was only natural, and in the last decade we are assisting to an extremely rapid growth of adoption, supported by the promotion of the NIJ (United States National Institute of Justice). For a review of GIS application to crime research the reader is referred to the overview by Wang [28].

According to this trend, the last works on the PDP are developed in the framework of the GIS. Kistler [18] uses a GIS to redesign the Tucson Police Department districts. Most commercial GIS can be extended to integrate optimization routines. Curtin et al. [11, 12] use GIS in conjunction with a maximal covering model. Finally, Zhang and Brown [29,30,31] implement agent-based simulation, and discrete-event simulation inside of a GIS.

3.2.3 Other Methods

Two studies adopted approaches that do not fall into any of the other categories. Bodily [2] devises a decision model based on utility theory to achieve the best solution with respect to the surrogate utility of three interest groups. The work by Sarac et al. [26] is an example of the idiomatic expression “simpler is better.” After attempting to redesign r-districts by using a multi-criteria set partitioning model, the authors realized that census blocks satisfied all the requirements. It is important to notice that their approach is successful because of the specific requisites the Buffalo PD had on the r-district configuration (e.g., easy access to demographic data, suitable for use by other agencies).

4 Annotated Bibliography

In the following, an annotated bibliography providing a description of the most salient points, achievements, and characteristics of the most relevant contributions in the PDP is given. The contributions are presented in chronological order.

4.1 Mitchell [23]

In his seminal work, Mitchell presents a mathematical formulation for the problem of designing police patrol sectors. The model is based on the assumption that incident distribution is known and that each call is serviced by the nearest available units. Multiple incident types are considered. Each type is characterized by a service time and a vector of weights that define the importance of the incident being attended by a specified number of units. The model minimizes the total expected weighted distance. Also, the workload, defined as the sum of the expected service time and the expected travel time, is equalized across the sectors. The problem is solved by means of an adapted clustering heuristic and applied to incident data for Anaheim, California. The solution improves the sector plan adopted at the time.

4.2 Bodily [2]

Bodily proposes a decision model based on utility theory, which makes use of the preferences of three interest groups in the design process of police sectors: citizens (minimize travel time, equalize travel time), administrators (minimize travel time, equalize travel time, and equalize workload), and service personnel (equalize workload). The problem is solved by a local search algorithm that transfers one block from one sector to another, so that the greatest improvement in terms of surrogate utility is achieved. The algorithm stops when no improvement is possible.

4.3 Benveniste [1]

The author presents a stochastic optimization problem for the combined zoning and location problem for several emergency units. Namely, the problem involves the division of an area in sectors, the definition of location for the servers, and a set of rules, assigning for service an alarm to a list of servers in order of preference. The objective function considered minimizes the total expected distance between the alarm and the first available server. Stochastic alarms rates, alarms spatial density functions, and probabilities that the servers are busy are considered. The resulting model is a non-linear program. The author proposes an approximation algorithm. An equal workload case is also examined and solved.

4.4 Sarac et al. [26]

The authors describe a study undertaken to reconfigure the police reporting districts used by the Buffalo Police Department. The following districting criteria were considered:

  • Homogeneity in terms of population, area, and call volume.

  • Geometrical properties such as compactness and contiguity.

  • Feasibility with respect to existing boundaries of five police districts.

  • Easy access to demographic data for each district.

  • Suitability for use by other agencies.

Initially, the authors formulated the problem as a multi-objective set partition problem which proved incapable to solve the real-world size problem at hand. Subsequently, a practical approach has been proposed: basically, the new districts were defined according to the census block groups that intrinsically present most of the desired characteristics (homogeneity in terms of population, compactness, contiguity, easy access to demographic data, and suitable for use by other agencies). With minor modifications, this solution proved to be very effective.

4.5 D’Amico et al. [13]

The authors solve a PDP subject to constraints of contiguity, compactness, convexity, and equal size. The novelty of the model lies in the incorporation of queuing measures to compute patrol offices workloads and response times to calls for service, computed by external software, PCAM. PCAM optimizes a queuing model for deployment of police resources, providing the optimal number of cars per district. The authors solve the problem by means of a simulated annealing algorithm that iteratively calls the PCAM routine. At each step, the neighborhood is determined by a simple exchange procedure that takes into account the following constraints:

  • The average response time per district is bounded from above.

  • The ratio of the size of the largest and smallest districts is bounded from above.

  • Sectors must be connected.

  • The ratio of the longest Euclidean path and the square root of the area in each sector is bounded from above to preserve compactness.

  • Sectors must be convex.

The algorithm is applied to a real-world case for the Buffalo Police Department. The following objectives were considered: minimization of the maximum workload (by decremental bounding constraining) and minimization of the maximum average response time.

4.6 Curtin et al. [11]

The authors apply a covering model to determine police patrol sectors. The covering model defines the centers of police patrol sectors in such a way that the maximum number of (weighted) incidents is covered. An incident is considered to be covered if it lies within an acceptable service distance from the center of a patrol sector. The model is integrated in a GIS and applied to a case study on the City of Dallas, Texas. In the final part of this chapter, the authors present a number of possible refinements to their model, including a maximum workload restriction (in terms of number of weighted incidents).

4.7 Scalisi et al. [27]

The issue of Geography & Public Safety presents numerous articles by police analysts describing their experiences with police redistricting within their police department.

  • Bruce [3]: C. Bruce, President of the International Association of Crime Analysts, poses some interesting questions that an analysts should answer to determine how workload should be measured.

  • Kistler [18]: A. Kistler, from the Tucson Police Department, devises a district evaluation measure built as the weighted sum of the following criteria: total hours worked, number of call responses, average response time, total length of all streets within the division, area of the division, and population. TPD staff used a GIS in combination with a software program called Geobalance to manually design alternative districting configurations. Future evaluations of the implemented plan showed that the projected workload ratios were reliable and realistic.

  • Douglass [14]: J. Douglass, from the Overland Park Police Department, explains how the introduction of a new real-time deployment paradigm, based on criminal hot-spots identification and treatment, had been implemented in the department. Unfortunately, no long-term statistical analysis was available at the time the article was written.

  • Mayer [21]: A. Mayer, from the East Orange Police Department, reports a similar strategy. In fact, the East Orange Police Department implemented a geographical technology called tactical automatic vehicle locator (TAC-AVL). TAC-AVL allows for GPS tracking, visualization on a map, and recording of information regarding patrol cars and incidents. This tool has been coupled with a new deployment strategy that allows for the introduction of impact, resource, response, and conditions cars to backup understaffed zones of the jurisdiction.

  • Mielke [22]: P. Mielke, from Redlands Police Department, explains how to use ESRI districting tool, a free extensions for ESRI ArcGIS that allows creating new police districts in a city or region.

  • Other successful applications of geographical technologies to police redistricting have been reported from Austin PD and Charlotte-Mecklenburg PD.

4.8 Curtin et al. [12]

Following Curtin et al. [11], the authors extend the covering model to include backup coverage (e.g., multiple coverage of high priority locations). The resulting model is bi-objective in nature. The authors propose a single objective model that maximizes the priority weighted coverage (each time a location is covered is accounted for separately), while ensuring a minimum covering level in terms of priority weighted number of locations covered (each covered location is accounted for only once). The model is tested with the police geography of Dallas, Texas, and refinements on the model are proposed (e.g., maximum workload per patrol sector).

4.9 Wang [28]

The author takes us on a journey across the main application areas of GIS in police practices. Among the various applications, Wang mentions the possibility of using GIS as a police force planning tool. Namely, he refers to hot-spot policing and police districting. Concerning the latter, Wang identifies three main objectives: meeting a response time threshold, minimizing the cost of operation, and balancing workload across districts. The author mentions the work by Curtin et al. [11, 12] and states that future works in this area should explore other goals, such as minimizing total cost (response time), minimizing the number of sectors (dispatch centers), maximizing equal accessibility, or a combination of multiple goals.

4.10 Zhang and Brown [29]

In this work a parameterized redistricting procedure for police patrols sectors is proposed. The methodology consists of a heuristic algorithm that generates alternative districting configurations. Next, the configurations are evaluated in terms of average response time and workload. With this aim, an agent-based simulation model was implemented in a GIS. The location and times of the incidents taking place at each sector are modeled by an empirical distribution based on real incident data. Finally, the procedure identifies the set of non-dominated solutions. The methodology has been tested on a case study based on the Charlottesville Police Department, VA, USA.

4.11 Zhang et al. [32]

The focus of this research is the evaluation of three different methods for scoring police districting designs: a closed form probability based approach, a discrete-event simulation based on hypercube models for spatial queuing systems, and an agent-based simulation model. The scoring measures are evaluated on designs generated using the methodology presented in Zhang and Brown [29]. According to the authors, the three methods provide similar evaluations of the districting plans when the emergency response system is not stressed. However, in the face of high system stress, only the agent-based simulation model is capable of accurately representing the significant changes in the workload scores due to complex behaviors of the system such as cross-boundary support, that is, when an agent assigned to a district services a call for service in another district.

4.12 Zhang and Brown [30]

The research presented in this paper focuses on the definition of a simulated annealing algorithm for the problem of finding optimal police patrol districting designs. The optimization procedure makes use of a discrete-event simulation to evaluate the solutions according to multiple criteria, such as average response time and workload variation among sectors. Districting designs are generated using a simulated annealing procedure. In this procedure two different neighborhoods are compared. In the first one, only changes of one block are allowed. The second one consists of a cutting and merging process that allows for more significant changes. The authors show empirically that the second approach uses fewer iterations to reach good solutions and is, therefore, preferable when used in conjunction with discrete-event simulation.

4.13 Zhang and Brown [31]

In this paper, Zhang and Brown extend their previous research in Zhang and Brown [29]. The main changes with respect to the previous contribution are the following. First, both discrete-event simulation and agent-based simulation are considered. The former is more computational efficient while the latter is more precise. Second, an iterative searching procedure is used to optimize the parameters of the districting algorithm, instead of adopting a completely randomized approach. The authors propose using experimental design methods to explore the parameter space, but classical metaheuristics, such as simulated annealing and genetic algorithms, could be used as well. The methodology is tested on real data provided by the Charlottesville Police Department, VA, USA.

4.14 Bucarey et al. [4]

In this paper the authors define a variant of the classical p-median problem to tackle the problem of defining balanced police sectors. The model is designed keeping in mind the requirements of the Chilean National Police Force, but can be applied to any country. The model proposed enriches the classical p-median in a number of ways. First, it enforces bounds on the demand of each sector. The bounds can be specified according to the acceptable percentage of deviation from the average demand in order to ensure homogeneity. The objective function is defined as the weighted sum of three terms. The first one is the sum of the blocks distances to the associated median. The second term enforces compactness by considering the sum of a measure of the sectors’ boundaries size. The function measuring the boundaries is non-linear in nature and is approximated by a piece-wise linear function. Finally, the third term represents the prevention demand component associated with a block. This component is defined as the maximum of three factors: the length of roads in the block, the amount of reported crime in the block, and the population of the block. The model is solved on a realistic case study considering 1266 blocks and up to p = 7 neighbors. Due to the size of the problem, the model is solved by means of a location-allocation heuristic algorithm.

4.15 Camacho-Collados et al. [6]

This paper presents the multi-criteria police districting problem (MC-PDP), a multi-criteria optimization model for partitioning the territory under the jurisdiction of a Police Department into sectors. The goal is the automatic definition of sectors that adapts to a particular shift. Initially, the territory is divided into a square grid. Each cell of the grid (which represents a block) is characterized by a crime risk, representing the expected crime, and an area, representing the total street length. A feasible design requires the sectors to be connected and convex. The workload for each sector is computed as the weighted sum of different factors: area, risk, isolation (i.e., how far the sector is from other sectors), and diameter. The objective function minimizes the weighted combination of the total workload and of the maximum workload. Assigning more weight to the first term results in solutions that are more efficient, while favoring the second term provides solutions that are more equal in terms of workload distribution. The model is solved by means of a multi-start randomized local search algorithm. The algorithm is tested on a real dataset including data from Central District of Madrid, Spain. A comparison with the configuration currently adopted by the Spanish National Police shows how this is suboptimal compared to the solutions found by the algorithm.

4.16 Camacho-Collados and Liberatore [5]

In this article, the authors embed the model and algorithm presented in Camacho-Collados et al. [6] within a decision support system for predictive police patrolling. The decision support system combines predictive policing features with the MC-PDP for the automatic definition of police districts that are tailored to the requirements of future shifts. The authors tackle the problem of adequately describing crime events in which the time and the location of the incidents are indeterminate. Previous research on the subject only contemplated temporally indetermined crimes.

4.17 Cheung et al. [9]

In this paper, a police force deployment optimization framework is proposed. The framework is comprised of two optimization problems solved in sequence: a police location problem and a patrolling area problem, respectively. The first problem is tackled as a p-median problem where nodes represent centroids generating crime and/or feasible locations for police facilities and the distances are weighted by the crime rate associated to the node. In the second problem, given the locations of police stations, the model determines the patrol area of the police force such that the total covered area of the police force is maximized. This is obtained by means of a maximum coverage problem. The framework is applied to a case study on the Greater London Area.

4.18 Chow et al. [10]

The authors apply classical operational research models—i.e., the p-median and the maximum coverage problems—for the location of p police facilities. Travel costs (distances) and crime generated at each location are considered. The solutions to these problems provide a definition of police districts, that is crisp for the p-median problem (i.e., a location is always assigned to the closest facility) and fuzzy for the maximum coverage problems (i.e., a location is assigned to all the facilities that “cover” it, that is, the distance between the location and the facility is inferior to a predefined distance). The algorithms are tested on data representing the crime rate in January 2014 for all wards (i.e., blocks) in Greater London.

4.19 Liberatore and Camacho-Collados [20]

The focus of this article is the extension of the MC-PDP [6] to general graph structures. This allows for increased versatility in terms of applicability of the model. With respect to the model, the same criteria (i.e., area, risk, isolation, and diameter) and objective function are considered. However, the authors defined an efficient and practical condition for set convexity derived from the classical definition of convexity in graphs. In terms of solution methodologies, the authors propose three local search algorithms for the MC-PDP on a graph: simple hill climbing, steepest descent hill climbing, and Tabu search. Thanks to its ability to escape from local optima, the Tabu search algorithms find solutions that are on average better than the other two methodologies.

4.20 Piyadasun et al. [25]

Piyadasun et al. [25] propose a multi-step heuristic procedure that clusters census blocks into sectors. Initially, crimes are assigned to census blocks and the crime-weighted centroid of each census block is identified. Distances are determined using actual road distance. Then, k non-contiguous centroids are chosen as the sector seeds. Next, the sectors are grown by adding a census block to a single sector at each iteration. The census block to be added is chosen in such a way that the resulting sector is as compact and efficient as possible. This is achieved by considering both the distance between the census block and the sector center (close census blocks are preferred) and the increase in terms of minimum rectangular area needed to cover the whole sector after the census block is added to it (small increases are preferred). The algorithm has been applied to crime data for the San Francisco County, CA, USA, corresponding to years from 2003 to 2015. The performance of the solutions obtained has been evaluated considering workload distribution, compactness of the districts, and patrol car response time. The workload definition used by the authors considers the number of calls for service in a district, as well as their severity and the distance travelled to service them. Homogeneity in workload distribution is computed using the Gini index. Concerning compactness, the measure adopted is the isoperimetric quotient (i.e., the ratio of the polygon area to the area of a circle with same perimeter). Finally, efficiency is obtained by considering the average time taken to travel to any point in the sector from the seed point (which is where the patrol car is hypothetically located).

5 Conclusions

District design is the problem of grouping elementary units of a given territory into larger districts, according to relevant attributes. Depending on the problem faced, the attributes considered might belong to different contexts, including economical, demographic, geographical, etc. In the last decades, the districting problems have been applied to a broad number of fields. The application of this family of problems to the policing context has given rise to the police districting problem.

In this chapter, a comprehensive review of the police districting problem is given. Initially, a general definition of the problem is provided. Next, the literature on the subject is analyzed in terms of attributes and methodology. Then an annotated bibliography is presented, where the most salient points of each contribution are summarized.

The results of the analysis show that the models proposed in the literature mostly differ on the definitions adopted for the most relevant attributes. In fact, it can be observed a great variability in terms of how sector workload is computed, or on which geometric and topological characteristics should be considered. Also, there is no common agreement on how homogeneity among sectors should be measured. It is the authors’ opinion that the research community should work toward a standard definition of the police districting problem. This would allow us to focus most the efforts on a single model, similar to what happened in other areas, such as location analysis or vehicle routing. In particular, it would permit to take steps toward the definition of exact solution approaches for the police districting problem.