A Tabu Search based heuristic for police units positioning

Public safety is one of most demanding areas in public administration, having direct consequences on people welfare. Creating crime containment strategies or providing a fast answer to emergency situations when they occurs is a challenge. In this paper, we use Operations Research techniques to solve a police units positioning problem, in order to maximize the profit associated with police coverage in a city. We propose a model to describe the problem, heuristic methods based on Tabu Search and a penalty function for infeasible solutions. The tests are performed using instances with real street network of three different cities. The results show the efficacy of the penalty method, increasing the number of feasible solutions found, the good quality of the solutions generated by the Tabu Search, and a low convergence time, even for large instances.