Aplicação de P-Medianas para atendimento aos colégios estaduais por viaturas do Batalhão de Patrulha Escolar

Abstract

Resumo: O objetivo deste trabalho é comparar a atual distribuição dos colégios estaduais atendidos pelas equipes\viaturas do Batalhão de Patrulha Escolar Comunitária (BPEC) no município de Curitiba/PR, utilizando o problema das pmedianas como nova proposta de designação, reagrupando os setores de forma a ficar distribuída uniformemente a quantidade de colégios por viatura. Também foi verificado se é possível realizar a designação com a capacidade de cada equipe adotando-se o número de alunos por viatura. Por fim, foi elaborado um aplicativo para uso diário pelo Batalhão, para possibilitar de maneira dinâmica realizar novas distribuições dos setores onde cada equipe deve atender caso aumente ou diminua a quantidade de equipes de serviço disponível, bem como aumente o número de estabelecimentos de ensino. Foram mapeados todos os 164 estabelecimentos de ensino estadual, e através de suas coordenadas geodésicas foi possível obter as distâncias euclidianas entre eles, para utilizar na implementação dos algoritmos exato e heurístico. Verificou-se melhora em todas as simulações, que abordaram três formas diferentes de agrupamento, sendo a Geral BPEC, que adota todos os colégios, sem nenhuma restrição quanto a localidade de atuação das equipes, a Pelotão BPEC, que respeita as posições dos colégios conforme a localização dentro de cada pelotão, e a ultima forma foi semelhante a atual, que respeita a área de atuação de cada viatura, conforme as unidades operacionais de área, que são os batalhões de policia militar. O algoritmo exato, como já esperado demorou um tempo grande, passando de dez horas sem chegar ao ótimo global para apresentar resultados e representou uma melhoria de 20% no percurso com a nova designação para visitar todos os estabelecimentos de ensino. O desempenho do algoritmo heurístico também foi satisfatório, pois além de não necessitar de utilização de outro aplicativo comercial, ficou entre apenas 4% a 7% em relação ao apresentado pelo algoritmo exato. Conclui-se que existe a necessidade de rever a forma de distribuição da abrangência de cada pelotão para se chegar aos resultados encontrados.

Abstract: The objective of this study is to compare the distribution of actual state schools attended by teams/patrol cars Battalion School Community (BPEC) in the municipality of Curitiba / PR, using the p-median problem as a new proposal for the appointment by regrouping sectors so that it's evenly distributed the number of colleges per vehicle. The study also tested if it is possible to perform the assignment with the ability of each team taking the number of students per car. Finally, an application was designed for daily use by the Battalion, to enable dynamically achieve new distributions of sectors where each team must meet if it increases or decreases the amount of service teams available as well as increase the number of schools. All the 164 schools statewide have been mapped, and through it's geodetic coordinates it was possible to obtain the Euclidean distances between them, to use in the implementation of exact and heuristic algorithms. There was improvement in all the simulations, which addressed three different ways of grouping, the General BPEC, which adopts all schools, with no restrictions on the location of work teams, the Platoon BPEC, that regards the positions of the schools as location inside each platoon, and the last form was similar to today, with regard each vehicle operation area, according to area operational units, which are the military police battalions. The exact algorithm, as expected took a long time, passing ten hours without reaching the global optimum to present results and represented a 20% improvement in route with a new designation to visit all the schools. The heuristic algorithm performance was also satisfactory, was not necessary to use another commercial application, and it's result was among 4% to 7% compared to that presented by the exact algorithm. It's possible to conclude that there is need to review each platoon distribution coverage to reach the results found in this study.