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:

 

Figura 2 – Matriz de distâncias entre os bairros selecionados

 

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).


O processamento aproximará o heliponto dos bairros mais violentos, cujo atributo relaciona-se diretamente com as distâncias ponderadas pelos volumes de ocorrências. Os pesos apresentados na Figura 9 correspondem aos indicadores computados, segundo o critério acima estabelecido.

 

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

 

A tabela apresentada na Figura 11 exibe os resultados processados, computados pelas distâncias ponderadas dos índices de ocorrências extraídos de cada bairro da rede.

 

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

 

Pesquisas em  Bases Fotográficas a partir do Retrato Falado

Quem Diria

Uma alternativa premiada