Police Patrol Routing
Team Orienteering Problem — Coverage VRP
A police department must assign 2 patrol vehicles to shift routes maximizing coverage of 14 priority zones rated by crime risk (1–10). Each unvisited high-risk zone increases incident probability by 12–18%. The Team Orienteering Problem maximizes total collected score within shift time constraints.
Where This Decision Fits
Public safety operations chain — the highlighted step is what this page optimizes
The Problem
From patrol precincts to optimization theory
A central police station (depot) dispatches 2 patrol vehicles across 14 priority zones. Each zone has a crime-risk score from 1 to 10 reflecting recent incident data, intelligence reports, and community complaints. Patrol vehicles operate within a fixed shift time budget (4–8 hours), and travel time between zones depends on distance. The objective is to maximize the total priority score of visited zones across both vehicles while respecting shift time limits.
This maps directly to the Team Orienteering Problem (TOP): given a set of nodes with scores, a depot, and m vehicles each with a time budget T, find routes starting and ending at the depot that maximize total collected score. Unlike the VRP which visits every customer, the TOP selects which nodes to visit — it is a Coverage VRP.
subject to
Σk yik ≤ 1 // each zone visited at most once
Σi Σj tij · xijk ≤ T // shift time budget per vehicle
Σj x0jk = Σi xi0k = 1 // each vehicle starts & ends at depot
xijk, yik ∈ {0, 1} // binary routing & visit variables
Where wi is the crime-risk score for zone i, tij is the travel time between zones, T is the shift time budget, xijk indicates whether vehicle k travels from i to j, and yik indicates whether vehicle k visits zone i.
The TOP is NP-hard — it generalizes the Orienteering Problem (single vehicle) and contains the Traveling Salesman Problem as a special case. With 14 zones and 2 vehicles, the number of feasible route-subset combinations grows exponentially.
See full TOP theory and all algorithmsTry It Yourself
Route patrol vehicles across priority crime zones
Patrol Route Optimizer
14 Zones · 2 Vehicles · 6h ShiftReady. Click “Solve & Compare All Algorithms” to run.
| Algorithm | Score | Zones | Time Used | % Max |
|---|---|---|---|---|
| Click Solve & Compare All Algorithms | ||||
The Algorithms
Heuristics for the Team Orienteering Problem
Greedy (Score / Distance Ratio)
O(m · n²)For each vehicle, repeatedly select the unvisited zone with the highest score-to-travel-time ratio. This balances zone priority against the cost of reaching it. Continue adding zones until the shift time budget would be exceeded (including return to depot). The approach favours high-value, nearby zones and produces good solutions quickly.
Nearest Unvisited + Greedy
O(m · n²)Build routes by always visiting the nearest unvisited zone first, but only if it fits within the remaining shift time. When no nearby zone fits, try the next-nearest. This produces geographically compact routes that minimize backtracking. After initial construction, zones are assigned to vehicles based on angular proximity from the depot.
2-Opt Improvement
O(m · n²) per passStart with the Greedy solution, then iteratively improve by: (1) swapping the order of two zones within a route to reduce travel time and free budget for additional zones; (2) inserting currently unvisited zones into freed time slots. Continue until no improvement is found. This local search typically improves the initial solution by 5–15%.
Real-World Complexity
Why patrol routing goes beyond the basic TOP
Beyond Standard TOP
- Dynamic incidents — Real-time 911 calls interrupt planned patrol routes, requiring rapid re-optimization mid-shift
- Dwell time requirements — High-risk zones may require 15–30 minutes of visible presence, not just a pass-through
- Time-varying risk — Crime risk scores change throughout a shift; bar-closing hours spike risk in entertainment districts
- Multiple shift overlap — Night shift vehicles must coordinate with day shift units to avoid coverage gaps during handoff
- Terrain and access — One-way streets, construction zones, and highway barriers affect real travel times
- Community engagement — Patrol routes must balance enforcement coverage with community policing visibility in residential areas
- Fatigue and breaks — Officers require meal breaks and rest periods, reducing effective patrol time below nominal shift length
Key References
Foundational works in orienteering and patrol routing
- (1996). “The team orienteering problem.” European Journal of Operational Research, 88(3), 464–474.
- (2011). “The orienteering problem: A survey.” European Journal of Operational Research, 209(1), 1–10.
- (2014). “Police patrol routing for crime prevention.” Omega, 44, 46–57.
- (2015). “A review of the team orienteering problem.” Computers & Operations Research, 56, 1–13.
- (2007). “Organizing hot-spot police patrol routes.” Proc. IEEE Intelligence and Security Informatics, 79–86.
Need to optimize your patrol operations?
From patrol routing to resource allocation and incident response planning, mathematical modeling can transform public safety operations. Let’s discuss how Operations Research can work for your department.