Utilização da p-mediana para simulação de bases
táticas de helicópteros policiais
Artigo
selecionado para o XII SIMPEP - SP em 2004
Isnard
Martins (Depto. Engenharia Industrial PUC-Rio) isnard@openlink.com.br
Nélio D. Pizzolato
(Depto. Engenharia Industrial PUC-Rio) ndp@ind.puc-rio.br
Resumo
Um algoritmo utilizado
como ferramenta de apoio à decisão pode otimizar a eficiência de recursos
destinados a serviços emergenciais de defesa civil ou segurança pública,
particularmente, se um fator crítico como tempo de atendimento adquire
importância maior nesta operação. Este estudo examina o problema de localização
física para um heliponto, destinado a basear aeronaves policiais mobilizadas
para apoio tático aéreo nas operações de capturas ou de repressão ao crime organizado.
Palavras Chave
Localização Física, P-mediana, Simulação,
Sistemas de Informações Geográficas.
1 - O Problema
O labirinto
característico das habitações construídas de forma desordenada nas quase
seiscentas favelas instaladas no município do Rio de Janeiro favorece o
esconderijo de uma pequena minoria de marginais de alta periculosidade dentre
os residentes locais. Somando-se a esse fato a permanente escassez de recursos
humanos e materiais disponíveis na Polícia do Estado, verifica-se cotidianamente
um alarmante aumento de conflitos armados entre marginais e forças policiais
nessas áreas densamente povoadas. Como conseqüência, ocorrem com razoável
freqüência ferimentos graves ou perdas irreparáveis de vidas de policiais ou de
moradores inocentes, atingidos por balas perdidas, disparadas a esmo por
marginais, sem qualquer responsabilidade, compromisso ou noção de civilidade. A
necessidade de otimizar os recursos policiais disponíveis tornou-se então
imperativa.
Neste cenário,
o helicóptero policial adquire uma importância singular como veículo de apoio
tático. De acordo com Damasceno; (2002), as rotas do patrulhamento em helicóptero
nas atividades de rotina devem ser planificadas à semelhança dos traçados
viários e áreas de atuação, com ênfase sobre os trechos mais densamente
habitados, em sincronia com o policiamento terrestre e patrulhamentos afins.
Esse equipamento extraordinário pode ser considerado importante e
revolucionária ferramenta no patrulhamento da polícia, integrando qualquer operação
policial, ostensiva ou reservada, desde o pronto emprego ou atividades de
rotina, até uma implacável perseguição contínua aos fugitivos,
independentemente da topografia do terreno, enquanto que o espaço aéreo é
transcontinental, obedecidas as normas aeronáuticas. As rotas devem ser
previamente estabelecidas, planejadas conforme o grau de violência que a região
apresenta, visando o exercício de uma segurança preventiva.
Para este
estudo foram selecionados 27 bairros (Figura-1), localizados no município do Rio de
Janeiro. Os bairros foram escolhidos de forma a obter uma maior participação
das principais zonas do município, desenhando a hipotética rede considerada. O
problema proposto será a identificação de um ponto geográfico ideal para a
localização temporária de um heliponto que proporcione, no menor tempo
possível, o apoio tático a grupamentos policiais terrestres chamados para
enfrentamento de marginais e situações de conflitos de média e alta gravidade.
O problema foi
segmentado em duas hipóteses. A primeira desconsidera a incidência relativa de
delitos nos bairros selecionados, levando em consideração apenas o menor
somatório possível dos tempos de vôo para chegada da aeronave aos pontos de
destino. A segunda hipótese acrescenta ao problema um indicador de violência,
utilizado com freqüência em sistemas de segurança pública, combinando o
histórico de delitos de média e alta gravidade relacionado com a população
residente para cada um dos bairros selecionados.
|
Figura 1 – Mapa físico do município do Rio de
Janeiro e bairros selecionados para o estudo |
Dados os N
bairros incluídos no estudo, deseja-se identificar um certo bairro h,
h Î N, onde o tempo médio de vôo de h
aos bairros da rede seja mínimo. Supondo-se uma velocidade v constante da aeronave em
todas as missões e a distância dij a ser coberta entre o ponto base do
helicóptero e os bairros da rede, deseja-se identificar o bairro h
tal que o somatório seja mínimo:
(
) (1)
Onde:
q wi = peso associado ao vértice i (na primeira hipótese, wi = 1)
q dij = distância mais curta entre os vértices (bairros) i e j
q N = conjunto de bairros selecionados
q r = um bairro qualquer da rede
As medidas usadas no estudo estão aproximadas, tendo em vista as imprecisões da ferramenta utilizada neste ensaio e da localização dos bairros realizada por meios visuais no mapa. As distâncias obtidas com essas ferramentas cumprem apenas a finalidade prevista neste estudo, não devendo ser utilizadas como dados geográficos efetivos ou informes precisos. Os cálculos para determinação do centro de gravidade da rede foram gerados pela ferramenta Siciliana, destinada a modelagem de soluções de localização física e tratamento de algoritmos, desenvolvida por Martins (2003).
Este estudo
pretende identificar um local alternativo para basear o helicóptero da policia,
eventualmente distinto do Heliponto oficial da Lagoa (SEGOA), de alto nível
estratégico para o Estado, e que contempla necessidades operacionais da Defesa
Civil, encontrando-se próximo às praias, onde o índice de afogamentos é
expressivo. Encontra-se também próximo de importantes áreas de risco, como
Favela da Maré, Morro do Alemão e Morro de São Carlos, o que justifica
fortemente a sua atual localização junto às margens da lagoa Rodrigo de
Freitas.
2 - Hipóteses consideradas na primeira alternativa
As distâncias
computadas são lineares, presumindo um vôo de aeronave policial, com preferência
de rota e altitude (preferência esta representada por um vôo ponto a ponto,
emergencial e sem desvios significativos que possam ampliar a distância prevista
na rota previamente selecionada).
Não existe
preferência de atendimento a nenhum dos bairros selecionados.
3 - Fundamentação Teórica
Um aspecto relevante é a
concepção de critérios técnicos para o estabelecimento da base das aeronaves em
relação à sua área de operação, devendo levar em consideração os fatores da sua
destinação. O local mais recomendado deverá ser representado pelo centro geográfico da rede, podendo ser identificado,
mediante estudos específicos de otimização da base de partida e retorno das
aeronaves.
Uma frota de 20 helicópteros de uso constante na bacia de Campos, em 1990, levou a Petrobrás ao uso de sofisticadas ferramentas automatizadas e ao uso de algoritmo heurístico, desenvolvido com objetivo de estabelecer rotas para os helicópteros, com propósito de satisfação da demanda e minimização do custo operacional associado aos vôos (Galvão e Guimarães, 1990). No caso da Petrobrás, um plano de vôo consiste de diversas rotas, com apenas um helicóptero escalado para cada rota. Cada plano de vôo destina-se a um determinado conjunto de escalas específicas, localizadas nas plataformas baseadas em alto-mar.
No caso enfocado neste estudo, o helicóptero cumprirá pontualmente uma única rota a ser determinada pelo atendimento de um chamado emergencial. Desta forma, enquanto o algoritmo usado no problema da Petrobrás aproxima-se do método aplicado no algoritmo do Caixeiro Viajante, a solução do heliponto hipotético considerado em nosso estudo aproximar-se do algoritmo da p-mediana. Essa recomendação justifica-se pela procura da minimização do tempo médio de atendimento da aeronave para missões pontuais realizadas nos bairros selecionados, enquanto que o estudo para a Petrobrás visava uma rota de visitas às plataformas. O tempo total despendido nos vôos é representado pelo somatório dos tempos individuais de vôo entre a localização do heliponto a ser identificado e a localização de cada bairro atendido pelos chamados emergenciais. Existe um bairro que representa a solução para p-mediana de um conjunto de bairros pertencentes ao município, que minimiza a soma das distâncias ponderadas de todos os bairros a este ponto central, e que será eleito como base do helicóptero, conforme considerações anteriores especificadas neste estudo.
Resultados de
Hakimi
Para Santos
(2000), o objetivo da solução p-mediana é identificar p instalações de um conjunto predefinido com N (onde N > p) instalações
candidatas, que deverão atender a um conjunto de demandas, de forma que a soma
total das distâncias percorridas de cada ponto de demanda até a instalação mais
próxima seja a menor possível. As p instalações
que pertencerem a uma solução qualquer são chamadas de medianas. O teorema estabelece
que, ao se escolher um ponto central em uma rede, o candidato a ponto central
deve pertencer à rede. Problema conhecido como problema da p-mediana, a seleção ficará restrita aos bairros
(vértices) selecionados. Assim, no caso da p-mediana, o número de possíveis
alternativas é
4 - Desenvolvimento do estudo
As etapas
abaixo foram seqüenciadas para solução do problema proposto.
4.1 -
Fase-1: Seleção dos bairros no mapa do município (os
vértices da rede).
Vinte e sete bairros
foram identificados, procurando obter-se uma ampla dispersão geográfica no
desenho da rede selecionada. Desta forma, foram eleitos sete bairros na zona
oeste, onze bairros na zona central e nove bairros na zona leste.
4.2 -
Fase-2: Identificação das distâncias lineares entre todos os bairros que
participaram do estudo (os arcos
da rede e a matriz de distâncias).
As
distâncias foram registradas, segundo apresentado na matriz abaixo:
|
|
Utilizando
a ferramenta ER_VIEWER,
processamos as distâncias lineares, bairro a bairro, dentre vinte e sete
selecionados, assumindo serem exatas as suas localizações no mapa, considerando
como aceitável a precisão das medidas obtidas.
4.3 -
Fase-3: Alimentação do programa Siciliano com as variáveis da
hipótese
O programa é
alimentado por duas tabelas: a matriz de distâncias e a tabela de pesos ou
ponderações. A matriz de distâncias, em Excel, é lida pelo programa, que
inicialmente processa a simetria das distâncias na tabela, tomando por base a
diagonal, fornecendo a organização dos dados, conforme apresentados na Figura 2
acima. A tabela de ponderações (Figura 3) é um recurso de grande importância,
com atributos flexíveis que podem alterar completamente os resultados da solução
pesquisada. No caso em questão, considerando as hipóteses formuladas para a
primeira alternativa, os pesos associados terão valores iguais a [1]. Isto
poderá ser interpretado pelo equilíbrio das prioridades relativas no atendimento
da aeronave aos bairros selecionados. Entretanto, poderíamos destinar aos pesos
associados, considerações diversas, tais como indicadores de violência, delitos
localizados, áreas de risco com escala de gravidade, volume de ocorrências
policiais etc. Um exemplo de redes ponderadas foi observado em um modelo de
pesquisa de serviços sociais realizado no México por Zubieta e Coria (2001),
utilizando algoritmo p-mediana (Aplicacion del algoritmo
de la p-mediana a programas de desarrollo social utilizando un simulador de
vuelo tridimensional del territorio nacional como visualizador de los
resultados).
Desta forma, e como
segunda alternativa do estudo, construiríamos cenários distintos, ampliando
possíveis resultados para localização do bairro escolhido para o heliponto, de
acordo com os pesos atribuídos a cada bairro, representando ponderações a serem
consideradas pelo algoritmo da P-Mediana e tratado no programa Siciliano. A
Figura 3 apresenta os dados utilizados pelo modelo de apoio aéreo, segundo a
primeira alternativa do estudo, considerando uma rede de prioridades
niveladas.
|
Figura 3 Tabela parcial de pesos associados |
4.4 -
Fase-4: Processamento da P-Mediana
Cada bairro é
selecionado como possível alternativa para o centro geográfico. Gradualmente, o
programa compara e substitui o total processado pelo menor somatório encontrado,
correspondente à distância do bairro candidato aos demais bairros pertencentes à
rede. Ao final, o programa apresentará a solução ótima:
4.5 - Fase-5: Resultados
O programa indica o vértice 10 (Jacarepaguá) como solução ótima para o cenário proposto. Os resultados, resumidos na Figura 4, exibem os totais computados após o processamento da matriz de distâncias ponderadas. Cada coluna representa um bairro candidato e abaixo o somatório, em quilômetros, correspondente à distância deste bairro aos demais bairros da rede. O bairro de Jacarepaguá oferece a menor soma geral nas distâncias lineares de vôo [611 km], seguindo-se os bairros de Freguesia [620 km] e Gardênia Azul [636 km].
|
Figura 4 – Tabela Parcial das distâncias finais
P-Mediana Computadas |
4.6 - Fase-6: Apresentação do Resultado
|
Figura 5: solução do heliponto para o caso particular
dos 27 bairros |
Considerando o
critério utilizado para seleção dos bairros, o resultado matemático não ofereceu
nenhuma surpresa quanto ao resultado esperado. O bairro de Jacarepaguá
representa uma espécie de centro geográfico da rede projetada. Como decorrência
desta condição particular, o programa confirmou esta localização como possível
bairro para o heliponto temporário, recomendando-o para basear a aeronave
durante o curso da missão policial, objeto deste estudo. Sem qualquer influência
no processamento, mas tornando viável a escolha desenvolvida pela modelagem
matemática, Jacarepaguá já dispõe de aeroporto alternativo, podendo receber
aeronaves de médio porte e dotado de infra-estrutura para basear helicópteros
civis ou policiais.
5 - Uma Visão do Problema com Pesos
Diferenciados
O segundo estudo,
levando em conta a incidência relativa de eventos que podem exigir a
participação de helicópteros, leva em conta os dados expressos nas Tabelas 6,7 e
8. Este ensaio tem como objetivo apresentar uma modelagem alternativa para o
problema, agregando pesos diferenciados (tempo de atendimento do serviço) aos
bairros que integram a rede. Selecionamos para ponderação um indicador
representativo de ocorrências policiais de média e alta gravidade (dados
fictícios, exceto indicadores de população), que poderiam, potencialmente,
mobilizar a aeronave para o apoio tático pretendido no caso de operações de
capturas ou confronto armado.
|
Bairros |
População |
Bairros |
População |
Alto da Boa
Vista |
7602 |
Méier |
51866 |
|
Barra da
Tijuca |
97935 |
Parque Anchieta
|
27566 |
|
Barra de
Guaratiba |
4090 |
Pavuna |
84928 |
|
Brás de Pina |
60093 |
Olaria |
10642 |
|
Caju |
17554 |
Realengo |
178404 |
|
Campo Grande
|
320750 |
Recreio dos
Bandeirantes |
47996 |
|
Cosmos |
70421 |
Rio Comprido
|
31035 |
|
Freguesia
Jacarepaguá |
55600 |
Santa Cruz |
195413 |
|
Galeão |
23522 |
São Conrado
|
9414 |
|
Gardênia
Azul |
23035 |
Senador Camará
|
117697 |
|
Grumari |
142 |
Sepetiba |
40290 |
|
Guaratiba |
102762 |
Vargem
Pequena
|
14585 |
|
Jacarepaguá |
115917 |
Praça Seca |
61964 |
|
Marechal
Hermes |
50557 |
|
|
Figura 6 - População nos bairros selecionados - Fonte: Secretaria
de Segurança Pública, 2002
|
Bairros |
Ocorrências
policiais |
Bairros |
Ocorrências
policiais |
|
Alto da Boa
Vista |
25 |
Méier |
76 |
|
Barra da
Tijuca |
206 |
Parque Anchieta
|
77 |
|
Pedra de
Guaratiba |
13 |
Pavuna |
103 |
|
Brás de
Pina |
104 |
Olaria |
20 |
|
Caju |
171 |
Realengo |
319 |
|
Campo Grande
|
852 |
Recreio dos
Bandeirantes |
76 |
|
Cosmos |
128 |
Rio Comprido
|
47 |
|
Freguesia
Jacarepaguá |
89 |
Santa Cruz |
277 |
|
Galeão |
64 |
São Conrado
|
12 |
|
Gardênia
Azul |
53 |
Senador Camará
|
117 |
|
Grumari |
1 |
Sepetiba |
182 |
|
Guaratiba |
503 |
Vargem
Pequena
|
16 |
|
Jacarepaguá |
329 |
Praça Seca |
388 |
|
Marechal
Hermes |
115 |
|
|
Figura 7 – Ocorrências policiais (dados fictícios,
meramente para cenário do estudo)
|
Bairros |
Ocorrências/ 10 mil ha |
Bairros |
Ocorrências/ 10
mil ha |
|
Alto da Boa
Vista |
33 |
Méier |
15 |
|
Barra da
Tijuca |
21 |
Parque Anchieta
|
28 |
|
Pedra de
Guaratiba |
31 |
Pavuna |
12 |
|
Brás de
Pina |
17 |
Olaria |
19 |
|
Caju |
98 |
Realengo |
18 |
|
Campo Grande
|
27 |
Recreio dos
Bandeirantes |
16 |
|
Cosmos |
18 |
Rio Comprido
|
15 |
|
Freguesia
Jacarepaguá |
16 |
Santa Cruz |
14 |
|
Galeão |
27 |
São Conrado
|
12 |
|
Gardênia
Azul |
23 |
Senador Camará
|
10 |
|
Grumari |
14 |
Sepetiba |
45 |
|
Guaratiba |
49 |
Vargem
Pequena
|
11 |
|
Jacarepaguá |
28 |
Praça Seca |
63 |
|
Marechal
Hermes |
23 |
|
|
Figura 8 – Índice de ocorrências/10 mil habitantes - (dados fictícios, meramente para cenário do estudo)
A Figura 6 apresenta o número de habitantes para cada
bairro selecionado na rede em estudo. A Figura 7 apresenta volumes mensais
(hipotéticos) de delitos de média e alta gravidade, em cada bairro integrante da
rede. A Figura 8 correlaciona as duas tabelas anteriores, apresentando o índice
de ocorrências médias mensais por 10 mil habitantes. Este indicador pondera o
resultado, privilegiando os bairros com maior incidências de delitos, aumentando
a distância dos bairros menos violentos, tal que o somatório seja minimizado, de
acordo com a expressão (1).
|
Figura 9 – Tabela parcial das ponderações | |
|
Figura 10 – Matriz parcial de distâncias ponderadas
entre os bairros selecionados |
|
|
Figura
11 – Tabela Parcial das distâncias finais P-Mediana
Computadas |
Figura 12 – Imagem da tela do programa Sicilano, após o
último ciclo do processamento.
Apresentação do Resultado do Cenário Ponderado
|
Figura 13 - Solução do heliponto para o caso dos 27
bairros com ponderação |
O centro geográfico deste novo cenário deslocou-se na
direção nordeste do município, fixando-se no bairro de Freguesia de Jacarepaguá.
Alguns bairros com grande volume de ocorrências, tais como Pavuna, Méier, Olaria
e Rio Comprido, influenciaram a ponderação, atraindo o centro anterior
localizado em Jacarepaguá para o novo centróide processado.
6 - Conclusões
O problema de
localizar uma instalação ou posto de serviço consiste em escolher uma posição
geográfica para sua operação, tal que seja maximizada uma medida de utilidade,
satisfazendo diversas restrições, em particular, restrições de demanda. No setor
público, procura-se maximizar o benefício oferecido à sociedade ou minimizar os
custos dos serviços oferecidos, citando, por exemplo, a distância média ou o
tempo médio gasto pelos beneficiários do sistema para alcançar o serviço
oferecido (Pizzolato, 2003). Na hipótese estudada neste trabalho,
consideramos o tempo médio para levar o serviço aos beneficiários do sistema, a
exemplo de serviços assistenciais de saúde pública (remoção de acidentados por
ambulâncias) ou emergenciais da Defesa Civil (serviços de bombeiros).
Com auxílio deste recurso matemático poderemos modelar com rapidez cenários que atendam com melhor justiça social e mais eficiência os benefícios esperados pelos serviços ofertados.
Uma variada gama de estudos voltados para os mais diversificados objetivos podem ser encontrados em centros de estudos matemáticos, aplicando o modelo da p-mediana como ferramenta de apoio à pesquisa de soluções de localização de instalações, tanto no setor público como no setor privado.
7
- Bibliografia
Galvão, R.D. e
Guimarães, J. (1990). The control of helicopter operations in the Brazilian oil
industry: Issues in the design and implementation of a computerized
system. European Journal of Operational Research,
49, 266-270.
Galvão, R. D.,
Júlio Francisco Barros Neto, Virgílio J. M. Ferreira Filho & Horácio Brescia
de Sousa Henriques (1997), Roteamento de Veículos com
Base em Sistemas de Informação Geográfica, Gestão e Produção,
Vol. 4, pp. 159-173.
Pizzolato, Nélio;
DEI, PUC-Rio.
Notas de
Aula, 2003
Damasceno Manoel, Cel PM
RR.
O Emprego do Helicóptero
em Missões Táticas.
http://www.brasilseguranca.com.br/index.html;
Consulta em setembro de 2002
Elon Santos Corrêa.
Heurística busca
tabu;
http://www.cpgmne.ufpr.br/dissertacoes/elon.pdf
Consulta em 13 de dezembro de 2003
Judith Zubieta Garcia, Alberto
Alonso y Coria
Aplicacion del algoritmo de la p-mediana a programas de
desarrollo social utilizando un simulador de vuelo tridimensional del territorio
nacional como visualizador de los resultados.
http://www.labvis.unam.mx/elio/zubieta
Consulta em 10 de dezembro de 2003
Martins, Isnard
Projeto de programação Siciliano; DEI, PUC-Rio.
Versão 2/b.
Consulta em novembro de 2003.
Álbum do Rio - Município do Rio de Janeiro, visão Satélite Íconos,
Secretaria de Segurança Pública, 2003.
InfoStrata, Cia Vale do Rio Doce.
Consulta em novembro de 2003