Organizing Hot-Spot Police Patrol Routes

We address the problem of planning patrol routes to maximize coverage of important locations (hot spots) at minimum cost (length of patrol route). We model a road network using an edge-weighted graph in which edges represent streets, vertices represent intersections, and weights represent importance of the corresponding streets. We describe efficient methods that use this input to determine the most important patrol routes. In addition to the importance of streets (edge weights), important routes are affected by the topology of the road network. Our methods permit automation of a labor-intensive stage of the patrol-planning process and aid dynamic adjustment of patrol routes in response to changes in the input graph (as a result of a developing situation, for instance).