Patrol districting and routing with security level functions

Public security is a key concern around the world. Efficient patrol strategy increases the effectiveness of police patrolling and improves public security. In this paper we propose a new general security measure by defining the security level function. Based on this, we present the balanced patrol districting solution for the multiple units assignment problem. For the patrol routing problem in a patrol district, we first formulate the patrol routing process as a graph-based Markov decision process, and then propose an ε-optimal patrol routing strategy to deal with the curse of dimensionality. The strategy is derived based on the concept of ε-optimal horizon approximation. Numerical studies demonstrate that the strategy is adaptive to the generalized security measure by security level function, and has significant performance improvement over the referenced strategies in previous works. In addition, as the randomness is an important factor for practices, we design the randomized patrol routing strategy on the basis of the randomized exploration method in the Reinforcement Learning.