Lecture VIII - Police Districting
Applied Optimization with Julia
Introduction
Police Service District Planning
Challenges
Question: What makes the work of emergency services complex?
- Dynamic urban development
- Changing population patterns
- Resource constraints
- Need for rapid response
- Multiple stakeholder interests
Emergency Services
Emergency services address the needs of three interest groups:
- Citizens
- Service personnel
- Administrators
Question: What could be the objectives of these groups?
Stakeholder Objectives
- Citizens
- Fast response times
- Reliable service coverage
- Service Personnel
- Manageable workloads
- Safe working conditions
- Administrators
- Cost efficiency
- Resource optimization
Aligning the objectives of the three interest groups is challenging.
Emergency Service Districting
Question: Why might current district layouts be suboptimal?
- Many layouts date back several decades
- Often designed along highways and regions (Bruce 2009)
- Extensive data not used for data-driven improvement
The Role of Data
Question: What data can help improve emergency services?
- Historical incident patterns
- Response time analysis
- Resource utilization metrics
- Population densities and traffic patterns
. . .
Extensive data collected, but often lack of tools or knowledge to leverage it.
Optimization
- Operations research (OR) models can help!
- Based on incident records and geographical information
- Improve the response of emergency services
- Help administrators in making strategic decisions
- Locate new departments or close departments (Liberatore, Camacho-Collados, and Vitoriano 2020)
Case Studies
Police Districting
For an efficient and effective distribution of resources, police jurisdictions are divided into precincts or command districts with separate departments. These are further divided into patrol beats (D’Amico et al. 2002).
Service Priority Extremes
- High Priority
- Life-threatening situations
- Active crimes in progress
- Multiple unit response needed
- Low Priority
- Minor incidents
- Administrative tasks
Case Studies
- Different urban contexts
- Study of jurisdictions in
- Germany: Large metropolitan area
- Belgium: Large rural area
- Focus on response time optimization
. . .
Part of the force patrols the streets, another part is stationed at the departments.
Dispatching
- Dispatchers assign all CFS to vehicles from the corresponding districts and patrol areas
- Officers are familiar with the area and are thus better prepared to respond appropriately (Bodily 1978)
- To cope with high demands, dispatchers can assign vehicles from nearby districts or beats
Potential Problem
Question: What could be the potential problem?
. . .
- This can lead to a domino effect
- Transferring vehicles from other districts or beats reduces coverage in those locations (Mayer 2009)
- This makes them vulnerable to missing resources when they need assistance themselves
Overloaded Systems
- This can lead to overloaded systems!
- Long dispatching delays due to staff shortages
- Preventive patrol hardly possible (Miller and Knoppers 1972)
- Dispatchers constantly draw on patrol resources
- Reduces the response time of emergency services
. . .
This is a common problem in many emergency services.
Response Time
- Central criterion to measure the effectiveness of emergency services is the response time
- Time between a call for aid and the arrival at the incident location
- Low response time increases the likelihood of helping and improves confidence (Bodily 1978)
Response Time Influencers
Question: What affects response time?
- Initial contact
- Information gathering
- Unit assignment
- Resource coordination
- Route to location
- Traffic conditions
Territory Design Problem
Territory Design Problem
Aggregation of small geographic areas, called basic areas (BAs), into geographic clusters, called districts, so that these are acceptable according to pre-defined planning criteria1.
Objective
Question: What could be the objective?
. . .
- Minimize the response time to help citizens faster while increasing the confidence in the service
. . .
Question: What could be further objectives?
. . .
- Reallocate only part of the police department’s
- Compact and contiguous territories to improve patrol
- Prevention of isolated departments
Basic Structure
Question: How can we structure this?
- Model as a digraph with vertices and edges
- Each BA centroid becomes a vertex
- \(\mathcal{J}\) : set of BAs, indexed by \(j\)
- \(\mathcal{I}\) : set of potential district centres \((\mathcal{I} \subseteq \mathcal{J})\)
Why Hexagons?
Question: Advantages of hexagons?
- Equal distances to all neighboring centroids
- Reduces sampling bias from edge effects (Wang and Kwan 2018)
- Special properties that help with the enforcement of compactness
- Better representation of urban geography
Response Time Components
Question: How can we model response time?
- Call length is independent of territory
- Dispatch time is difficult to model
- Driving time can be minimized directly
We focus on minimizing expected driving times between departments and incident locations.
Model Formulation
Key Model Components
Question: What could be our key model components?
. . .
- Basic areas (BAs) and potential department locations
- Driving times between basic areas
- Forecasted incident data
- Assignment decisions
. . .
Question: Which are sets, parameters, and variables?
Sets and Indices
- \(\mathcal{J}\) - Set of BAs, indexed by \(j\)
- \(\mathcal{I}\) - Set of potential district centres (\(\mathcal{I} \subseteq \mathcal{J}\)), indexed by \(i\)
. . .
The depot locations are a subset of the basic areas!
Parameters
Question: What parameters do we need?
- \(p\) - Number of district centres (departments)
- \(t_{i,j}\) - Expected driving times between \(i\) and \(j\)
. . .
Parameters should be carefully calibrated with real-world data!
Decision Variable(s)?
- BAs, indexed by \(j \in \mathcal{J}\)
- Potential department locations, indexed by \(i \in \mathcal{I}\)
. . .
Minimize the expected response time of the emergency services by optimizing the assignment of BAs to departments.
. . .
Question: What decisions do we need to model?
Decision variable/s
- \(X_{i,j}\): 1 if BA \(j\) assigned to department \(i\), 0 otherwise
. . .
Question: What is the domain of our decision variable?
. . .
- \(X_{i,j} \in \{0,1\} \quad \forall i \in \mathcal{I}, \forall j \in \mathcal{J}\)
Objective Function?
Minimize the expected response time of the emergency services by optimizing the assignment of BAs to departments.
. . .
Question: How do we minimize response time?
- We want to minimize total driving time
- Consider frequency of incidents in each BA
- Don’t include fixed costs (handled by constraints)
Objective Function
Question: What could be our objective function?
. . .
\[ \text{minimize} \quad \sum_{i \in \mathcal{I}}\sum_{j \in \mathcal{J}} t_{i,j} \times X_{i,j} \]
. . .
- Total driving time across all assignments
- Weighted by incident frequency
- Considers all possible BA-department pairs
Constraints
Key Constraints
Question: Constraints needed?
- BA must have one department
- Limit number of departments
- Only assign active departments
- Ensure contiguous districts
- Maintain district compactness
Single Assignment Constraint?
Question: Why do we need this constraint?
. . .
- Each BA must be assigned to exactly one department
- Prevents overlapping jurisdictions
- Ensures complete coverage
. . .
- \(X_{i,j}\) - 1 if BA \(j\) assigned to department \(i\), 0 otherwise
Single Assignment Constraint?
Question: What could the constraint look like?
. . .
\[ \sum_{i \in \mathcal{I}} X_{i,j} = 1 \quad \forall j \in \mathcal{J} \]
. . .
Each BA must be assigned to exactly one department.
Department Count Constraint?
Ensure that exactly \(p\) departments are opened.
. . .
- \(\mathcal{I}\) - Set of potential department locations, indexed by \(i\)
- \(\mathcal{J}\) - Set of BAs, indexed by \(j\)
- \(X_{i,j}\) - 1, if BA \(j\) assigned to department \(i\), 0 otherwise
- \(p\) - Number of departments
Department Count Constraint
Question: What could the constraint look like?
. . .
\[ \sum_{i \in \mathcal{I}} X_{i,i} = p \]
. . .
Question: What happens if we have more departments than potential locations?
. . .
- We can’t open more departments than there are locations
- The model will be infeasible
Active Department Constraint?
Ensure that each BA is assigned to an active department, e.g. a department that is opened and that could dispatch vehicles.
. . .
- \(X_{i,j}\) - 1, if BA \(j\) assigned to department \(i\), 0 otherwise
Question: How do we ensure assignments only to active departments?
Active Department Constraint
\[ X_{i,j} \leq X_{i,i} \quad \forall i \in \mathcal{I}, \forall j \in \mathcal{J} \]
. . .
This constraint creates a logical connection between department locations and BA assignments where BAs can only be assigned to opened departments.
p-Median Problem
\[\begin{align} \text{minimize} \quad & \sum_{i \in \mathcal{I}}\sum_{j \in \mathcal{J}} t_{i,j} \times X_{i,j} \\ \text{subject to:} \quad & \sum_{i \in \mathcal{I}} X_{i,j}= 1 && \forall j \in \mathcal{J} \\ & \sum_{i \in \mathcal{I}} X_{i,i} = p && \\ & X_{i,j} \leq X_{i,i} && \forall i \in \mathcal{I}, \forall j \in \mathcal{J} \\ & X_{i,j} \in \{0,1\} && \forall i \in \mathcal{I}, \forall j \in \mathcal{J} \end{align}\]
Contiguity and Compactness
Contiguity Introduction
Question: Why is contiguity important?
- Prevents isolated areas
- Ensures contiguous patrol routes
- Maintains operational coherence
What is compactness?
. . .
Compactness has no univocal definition; a district is commonly declared compact if it is ‘somehow round-shaped and undistorted’ (Kalcsics, Nickel, and Schröder 2005).
Contiguity and Compactness
Question: Are our resulting districts based on the model contiguous and compact?
- This depends on \(t_{i,j}\)
- If Euclidean distance
- Districts will be contiguous
- Likely of compact shape
Compactness p-Median
Question: Is this likely for police service districting?
- No, as we minimize the driving time within a city
- Highways, Tunnels, etc.
- Multiplied by the differing number of requested cars
- This can contribute to distorted district shapes
Contiguity Sets
Additional Set and Parameter
- \(e_{i,j}\) - Euclidean distance between centroids
- \(\mathcal{A}_j\) - Sets of BAs adjacent to BA \(j\)
. . .
\[ \mathcal{N}_{i,j}=\{v \in \mathcal{A}_j | e_{i,v} < e_{i,j}\} \quad \forall i\in \mathcal{I}, \forall j\in \mathcal{J} \]
. . .
BAs closer to department \(i\) than BA \(j\) on euclidian distance and adjacent to \(j\)!
Example A
Example A
Example B
Example B
Enforcing Contiguity
All districts have to be contiguous
\[ X_{i,j} \leq \sum_{v \in \mathcal{N}_{i,j}} X_{i,v} \quad \forall i \in \mathcal{I}, \forall j \in \mathcal{J} \setminus \mathcal{A}_i: i \neq j \]
. . .
At least one department has to be assigned to a BA that is adjacent to BA \(j\) and closer to department \(i\)!
Contiguity and Compactness
All districts have to be contiguous and compact
\[\begin{align*} X_{i,j} &\leq \sum_{v \in \mathcal{N}_{i,j}}X_{i,v} && \forall i \in \mathcal{I}, \forall j \in \mathcal{J} \setminus \mathcal{A}_i:|\mathcal{N}_{i,j}|= 1 \wedge i \neq j \\ 2X_{i,j} &\leq \sum_{v \in \mathcal{N}_{i,j}}X_{i,v} && \forall i \in \mathcal{I}, \forall j \in \mathcal{J} \setminus \mathcal{A}_i:|\mathcal{N}_{i,j}|> 1 \wedge i \neq j \end{align*}\]
. . .
At least one department has to be assigned to two BAs that are adjacent to BA \(j\) and closer to department \(i\)!
Comparison
. . .
Due to the constraints, there is always a path back to the department if a BA is assigned to a department!
Model Characteristics
Characteristics
Questions: On model characteristics
- Is the model formulation linear/ non-linear?
- What kind of variable domains do we have?
- What do you think, can the model be solved quickly?
- Have we prevented isolated districts?
Model Assumptions
Questions: On model assumptions
- What assumptions have we made?
- Use Euclidean distances to approximate driving time?
- Can we rely on incident data collected by the police?
Implementation and Impact
Overview of Studies
Question: Where did we apply our model?
- Two distinct environments:
- Large metropolitan area (Germany)
- Rural region (Belgium)
- Different challenges and requirements
- Focus on response time optimization
German Metropolitan Case
. . .
- 1.8 mio incidents (2015-2019)
- ~20 department locations
- 1,596 basic areas
- Dense urban environment
. . .
Goal: Redesign districts to improve response time.
German Metropolitan Results
Belgian Rural Case
. . .
- 50,000 incidents (2019-2020)
- 2 existing + 1 planned location
- 1,233 basic areas
- Dispersed rural setting
. . .
Goal: Optimize coverage with limited resources.
Belgian Rural Results
Simulation Framework
Question: How did we validate the results?
. . .
- Spatial and temporal patterns
- Shift schedules
- Priority handling
- Rush hours
- Inter-district support
- Variable driving times
Results
- Response time reduction up to 14.52%
- Better workload distribution
- Improved coverage equity
- More efficient resource utilization
. . .
All improvements are without additional staff!
Conclusions
- Model adaptability crucial
- Local context matters
- Stakeholder buy-in essential
- Data quality critical
. . .
Success requires balancing theoretical optimization with practical constraints!
Future Applications
Question: Where else could this approach be useful?
- Other emergency services
- Different urban contexts
- Resource allocation problems
- Service territory design
. . .
The methodology is adaptable to various public service optimization scenarios.
Wrap Up
We now have covered districting problems and are ready to start solving some tasks in the upcoming tutorial.
Literature
Literature I
For more interesting literature to learn more about Julia, take a look at the literature list of this course.