Police Patrol Routing
Arc routing · coverage constraints · contested fairness
Given a street network, a set of patrol cars, and an incident-rate signal on each street segment, design patrol routes that cover high-incident areas within shift constraints. The underlying mathematics is standard arc routing — polynomial relaxations plus VRP heuristics. The mathematics is not the interesting part. What matters is what happens when efficiency-maximising routes reinforce historical over-policing, and whether optimisation should be the framing at all. This page gives the model honestly, and then gives the critical scholarship honestly — the latter is the larger half of the page.
Problem context
Patrol routes as arc routing, with everything that complicates it
The traditional OR framing of police patrol is a capacitated arc-routing problem (CARP): cover a set of street segments with a fleet of patrol cars, each constrained by shift length and starting from a precinct depot. Each segment carries a weight — typically an incident-rate estimate or a coverage requirement — and the objective minimises travel time (or maximises covered weight within shift budget). This framing traces to Larson & Odoni's Urban Operations Research (1981) and to earlier hypercube-queuing models for emergency response (Larson 1974).
The complications begin when you ask where does the incident-rate weight come from? In most production patrol-allocation tools, it comes from recorded police activity — prior arrests, prior stops, prior calls-for-service — all of which reflect not just where crime happens but where policing has already happened. Lum & Isaac (2016) analysed predictive-policing tools and documented a specific feedback loop: heavier patrols in historically over-policed neighbourhoods generate more recorded incidents, which then justify still heavier patrols. The optimiser does its job faithfully; the data betray it.
A broader literature has since formalised this phenomenon. Ensign, Friedler, Neville, Scheidegger & Venkatasubramanian (2018) at FAccT gave an explicit model of runaway feedback. Richardson, Schultz & Crawford (2019) documented the specific “dirty data” problem: predictive-policing systems trained on data generated during periods of unconstitutional enforcement in Chicago, New Orleans, and other cities. Chouldechova (2017) and Kleinberg, Mullainathan & Raghavan (2017) proved that basic notions of group fairness (calibration, predictive parity, equalised odds) cannot in general be satisfied simultaneously by any scoring system — including whatever scoring drives the patrol-routing weights.
Multi-stakeholder framing
Mathematical formulation
The arc-routing model used, with explicit caveats on the input weights
| Symbol | Definition | Domain |
|---|---|---|
| G = (V, E) | Street network (vertices = intersections, edges = segments) | undirected multigraph |
| we | Weight on edge e — often an estimated incident-rate signal | ℝ⁺ |
| te | Traversal time for edge e | ℝ⁺ |
| K | Number of patrol cars | ℕ⁺ |
| T | Shift-length budget per car | ℝ⁺ |
| d | Depot (precinct starting point) | d ∈ V |
| xek | Number of times car k traverses edge e | ℕ (≥ 0) |
s.t. Σe te xek ≤ T ∀ k // shift-length budget per car
tourk starts and ends at depot d ∀ k
tourk forms a connected walk in G
xek ∈ ℕ (integer)
Complexity NP-hard in general (generalises the Capacitated Postman / CARP — Golden-Wong 1981). Polynomial for K=1 unconstrained (Chinese Postman, Edmonds-Johnson 1973). Practical heuristics: Clarke-Wright-style savings, path-scanning, iterated local search.
Critical caveat on we // w_e is typically derived from recorded police activity (stops, arrests, CFS) in the
// preceding period. This data is a CONVOLUTION of underlying incident frequency WITH
// prior patrol allocation. Optimising over w_e therefore propagates prior allocation
// decisions into the next period. See Lum & Isaac (2016) and Ensign et al. (2018).
Interactive solver
Small-zone arc-routing demo with heuristic solver
Patrol-Route Solver
About the solver. Synthetic graph of zones connected by corridors; each edge has a traversal time and an incident-weight. The solver runs greedy savings-style route construction (K cars departing from a shared depot) with a weight-maximising coverage objective under shift budget T. The Biased-data scenario option multiplies weights in ~25% of zones by a prior-patrol factor; this is purely illustrative of the feedback-loop effect and is not real data.
Solution interpretation
Reading the dashboard — and what the dashboard does not tell you
Higher shift budget T lets each car cover more ground, so coverage rates improve nearly linearly until the routes overlap redundantly. Adding cars helps similarly, with diminishing returns as zones get over-covered.
Switching to the “hotspot” profile concentrates the objective value in a few zones, and the optimiser responds by routing all cars through them. This is mathematically correct behaviour for the given weights. Whether those weights reflect the right thing to maximise is a policy question, not a mathematical one.
The biased-data scenario is the instructive one. Multiplying weights in historically over-patrolled zones pulls the optimal routes further toward those zones, even though the underlying problem is identical. A closed-loop deployment (next period trains on this period's incident data) would compound the effect over time.
What the dashboard does not show: community harm from sustained high-intensity patrol, incidents that happen without a patrol response anywhere on the graph, crime that is displaced rather than prevented, or the alternatives to patrol as an intervention (community investment, violence interrupters, mental-health co-response). None of those are in the objective function.
Limitations & Critique
The section you should read before any real-world use
Feedback loops in predictive-policing data
Incident-rate weights derived from past police activity conflate where crime happens with where policing has already happened. Optimising over such weights is a control-theoretic feedback loop in which the controller is blind to its own influence on the signal.
Ensign, Friedler, Neville, Scheidegger & Venkatasubramanian (2018). Runaway feedback loops in predictive policing. FAccT.
Dirty data from past unconstitutional enforcement
Multiple US cities (Chicago, New Orleans, Baltimore) have had historical periods of unconstitutional stop-and-frisk or other biased enforcement. Predictive systems trained on that era's data embed those biases into forward decisions. The Department of Justice itself documented this in consent-decree reports.
Fairness impossibility — Chouldechova 2017, Kleinberg et al. 2017
Multiple natural group-fairness criteria (calibration across groups, equalised false-positive rates, equalised false-negative rates) cannot in general all hold simultaneously for any scoring system. A patrol-routing optimiser that weights zones by a score inherits this impossibility: there is no neutral score.
Kleinberg, Mullainathan & Raghavan (2017). Inherent trade-offs in the fair determination of risk scores. ITCS.
Displacement vs. prevention
Optimised patrols may displace crime geographically rather than prevent it. The routing objective counts “zones covered” but not “crimes prevented overall.” Evaluating patrol interventions requires counterfactual analysis that is rarely done rigorously.
Community consent & legitimacy
Production patrol-allocation systems have been deployed in many cities without public consultation, stakeholder review, or disclosure of the weighting function. The legitimacy costs of opaque algorithmic decision-making compound over time; once trust is lost, it is hard to restore.
Is optimisation the right framing at all?
The most serious critique is not that patrol-routing optimisation does it badly but that it does the wrong thing. Investments in housing, mental-health response, violence-interruption programmes, and community-led safety initiatives have in many studies produced larger crime reductions per dollar than increased patrol intensity. Optimising patrol routes takes “more patrol” as given.
Vera Institute of Justice (ongoing). Research on community safety alternatives.
Algorithmic-accountability practice
Frameworks such as algorithmic impact assessment (AI Now Institute), model cards (Mitchell et al. 2019), and periodic disparate-impact audits are active areas. Deploying any patrol-optimisation tool without such safeguards is below the standard that the fairness literature has spent a decade developing.
Barocas, Hardt & Narayanan (ongoing). Fairness and Machine Learning.
What OR can responsibly contribute
Arc-routing machinery has legitimate uses: auditing disparate impact across candidate patrol patterns, sensitivity analysis on weight inputs, explicit multi-objective formulations that penalise over-concentration, and scenario comparison for policy-maker deliberation. The technique is not the problem; uncritical deployment is.
Extensions & variants
Responsible, and less-responsible, directions
Fairness-constrained arc routing
Explicit equity constraints — e.g., cap patrol-intensity variance across demographic zones. Bansal et al. (2021) on fair-coverage ILPs.
Multi-objective weighting
Weighted sum across coverage, equity, and community-consent proxies. Not a technical fix for the feedback-loop problem but useful for sensitivity analysis.
Randomised patrol schedules
Introduce randomisation into route selection to prevent adversarial adaptation (game-theoretic view); Tambe's Stackelberg-security models.
Co-response & alternative-responder routing
Route mental-health and social-worker teams alongside or instead of police for specific call types. Different mathematics, different objective, different community signal.
Hypercube-queuing emergency response
Larson (1974) for 911 / EMS dispatch — distinct problem from patrol, less contested framing.
Beat-design districting
Partition a jurisdiction into patrol beats; closer kin to political districting than to arc routing. Similar equity concerns.
Evaluation, not prescription
Use the same machinery descriptively: audit existing patrol-coverage disparities, surface inequalities to policy-makers and community stakeholders.
Participatory-design approaches
Involve affected communities in defining weights and constraints. See Costanza-Chock (2020), Design Justice.
Key references
Technical AND critical — do not separate the two
Related applications
Arc-routing siblings and critical-lens companions