CAPES / Estudos mostram que a violência nas escolas resulta em consequências prejudiciais para as vítimas e para a sociedade. Entre os principais meios de prevenção da violência escolar tem-se o patrulhamento policial como o mais efetivo. O patrulhamento policial escolar é realizado por viaturas policiais que atendem a uma rede de escolas e consiste na manutenção das viaturas em cada escola da rede por um determinado período de tempo (patrulhamento de rotina). Contudo, durante o patrulhamento de rotina, as viaturas devem prestar atendimento imediato a chamadas de emergência em escolas da rede que não estejam sendo patrulhadas naquele momento (patrulhamento emergencial). O presente trabalho propõe um método baseado em modelos matemáticos para auxiliar o programa de patrulha escolar na definição das rotas de patrulhamento de rotina e rotas emergenciais. A abordagem aplicada para resolver o problema foi a de algoritmos de grafos. O patrulhamento de rotina foi por meio do Problema do caixeiro viajante e solucionado por meio da heurística do vizinho mais próximo e da meta-heurística de Busca tabu. A situação de emergência foi modelada utilizando o Caminho mais curto e as rotas emergenciais foram determinadas por meio do algoritmo de Floyd-Warshall. Um estudo de caso em uma rede de escolas foi utilizado para demonstrar a utilização do método. Os resultados mostram que o método proposto é efetivo para tratar o problema de seleção de rotas de patrulhamento escolar em cidades com restrições de recursos tecnológicos. / Studies have shown that school violence produces harmful effects on victims and society alike. Police patrols have proved to me the most effective among the main forms of preventing school violence. School police patrols take place using squad cars that serve a network of schools and consist of placing vehicles at network schools for a given period of time (routine patrol). Nevertheless, during routine patrol police vehicles must immediately answer emergency calls at network schools that are not being patrolled at that moment (emergency patrolling). This work proposes a method based on mathematical models to assist the school patrol program in defining the routes for routine patrol and emergency routes. The approach used to solve the problem consisted of graph algorithms. Routine patrol was treated as a model of the Traveling Salesman Problem, and was solved using the Nearest Neighbor Heuristic and Tabu Search metaheuristic. The emergency situation was modeled using the Shortest Path Problem, and emergency routes were determined through the Floyd-Warshall algorithm. A case study was used to demonstrate the application of the method. Results show that the proposed method is effective to treat the problem of route selection for school patrols in cities with shortcomings in technological resources.

Submitted by Marco Antônio de Ramos Chagas (mchagas@ufv.br) on 2016-02-15T08:18:36Z No. of bitstreams: 1 texto completo.pdf: 975311 bytes, checksum: 2370ab5f5a769402c498fc4adcc292cb (MD5) / Made available in DSpace on 2016-02-15T08:18:36Z (GMT). No. of bitstreams: 1 texto completo.pdf: 975311 bytes, checksum: 2370ab5f5a769402c498fc4adcc292cb (MD5) Previous issue date: 2015-09-24 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O provimento de segurança pública é uma questão de grande relevância na administração pública e que interfere diretamente na qualidade de vida das pessoas. Dentre vários fatores que podem tornar uma sociedade mais ou menos segura, está a boa organização e o uso das forças policiais. Este trabalho apresenta uma abordagem computacional baseada em técnicas de Pesquisa Operacional para o problema de alocação de forças policiais em uma área urbana. Tal problema consiste em determinar onde unidades policiais, a pé ou em algum veículo, devem ser posicionadas de forma a prover uma cobertura eficiente de uma área, de acordo com critérios pré-determinados. São apresentados dois modelos matemáticos para descrever o problema. O primeiro é um modelo determinístico baseado no modelo de cobertura máxima gradual e no modelo de cobertura máxima com restrições de obrigatoriedade de proximidade. Ele aparece em duas versões, com poucas diferenças entre si, sendo a última mais rápido de ser resolvido por softwares de otimização inteira-mista, tal como o CPLEX. Além da solução exata, foram propostos algoritmos baseados em simulated annealing e busca tabu para resolução de grandes instâncias. O segundo modelo é estocástico, baseado na teoria das filas, no Modelo De Filas em Hipercubo (Hypercube Queuing Model ), no MERLP(Maximal Expected Response Location Problem) e no primeiro modelo. Para este modelo, foi proposta uma heurística baseada no VND (Variable Neighborhood Descent), com inicialização por busca tabu. / The public security provision is a matter of great importance in public administration that directly affects the quality of life. Among many factors that can turn a society a more or less safe, is the good organization and use of police forces. This work presents a computational approach based on Operations Research techniques to the problem of police forces allocation in an urban area. Such problem is to define where police units, on foot or in a vehicle, should be positioned to provide efficient coverage of an area, according to predetermined criteria. Two mathematical models are presented to describe the problem. The first is a deterministic model based on gradual maximum coverage model and maximum coverage model with proximity mandatory restrictions. It appears in two versions, with few differences between them, and the last is faster to be solved by a mixed-integer optimization software, such as CPLEX. Besides the exact solution we have proposed algorithms based on simulated annealing and tabu search for solving large instances. The second model is stochastic, based on queuing theory, the Hypercube Queuing Model, the MERLP (Maximal Expected Response Location Problem) and the first model. For this mo- del, a heuristic based on VND (Variable Neighborhood Descent) was proposed, using a tabu search to provide a initial solution.