Estudo de problemas de alocação de unidades de patrulhamento em malha urbana: uma abordagem de otimização combinatória

Abstract

In this work, we study three optimization problems related to the allocation and routing of patrol units. In the Diameter-Constrained Partitioning problem (DCP), we minimize the number of allocated vehicles while ensuring a maximum response time. We show the equivalence between DCP and the Vertex Coloring Problem (VCP), propose a new formulation for VCP and an exact method to solve this formulation, as well as a post-processing algorithm to improve the balance of patrol areas. Experiments with real instances of DCP showed the efficiency of the exact algorithm in obtaining optimal solutions. In the Min-Max Diameter Partitioning problem (MMDP), we minimize the maximum response time of a given number of vehicles. We show that MMDP is equivalent to the Min-Max Diameter Clustering Problem (MMDCP) and present an exact method for MMDCP. We compare the proposed method with another method from the literature and find that both methods are effective in solving MMDP, with the proposed method offering a more controlled maximum execution time, while the other is faster on average. In the Foot Patrol Problem (FPP), we maximize a weight function on routes that pass through hot segments (street segments with a high crime density). We present a formulation for FPP and use it to develop a column generation-based matheuristic. In experiments, we observed that our heuristic outperformed two other heuristics from the literature in crime coverage.