Fast Patrol Route Planning in Dynamic Environments

Proper patrol route planning increases the effectiveness of police patrolling and improves public security. In this paper, we present a new approach for real-time patrol route planning in dynamic environments. We first build a mathematical formulation for the patrol route planning problem under a single patrol unit setting and then propose a fast algorithm developed from the cross entropy (CE) method to meet the real-time computation requirements needed for practical applications. We next generalized the result to the patrol team case. Since the size of feasible team routes grows exponentially as the number of patrol units increases, we propose an approximate CE (ACE) algorithm that balances convergence time with optimality. Compared with the CE algorithm, the ACE algorithm can reduce the convergence time by as much as 48.9% with a less than 1% performance loss.