Pesquisa Operacional e o Desenvolvimento Sustentável
27 a 30/09/05, Gramado, RS
DISTRIBUIÇÃO DE CABINES DE SEGURANÇA EM PARTE DO BAIRRO
DO LEBLON NA CIDADE DO RIO DE JANEIRO
Roberta Almeida Pereira
Leonardo Claro Garcia
Valdir Agustinho de Melo
Paulo Jorge Magalhães Teixeira
Paulo Oswaldo Boaventura Netto
Samuel Jurkiewicz
Área de Pesquisa Operacional, Programa de Engenharia de Produção, COPPE/UFRJ, Centro de
Tecnologia, Bl. F, Cidade Universitária, Ilha do Fundão, Rio de Janeiro, Brasil.
Tels. (0xx21) 2562-7047, 2280-7438, 2562-8289.
E-mails: [email protected], [email protected], [email protected], [email protected],
[email protected], [email protected].
Resumo
Este trabalho propõe uma solução para o posicionamento de cabines de segurança em parte do bairro do Leblon
na cidade do Rio de Janeiro, utilizando a metodologia associada ao problema de p-centros. O objetivo é obter a
localização de até 3 (três) cabines, de forma que o deslocamento do policial ao local da chamada de emergência
obedeça a percursos globalmente otimizados, respeitando o sentido do deslocamento de veículos em vias
públicas.
Palavras chave: Grafos, alocação, segurança urbana.
Abstract
This work contains a proposition concerning the allocation of police cabins within the Leblon suburb in the city
of Rio de Janeiro, using the p-center graph-theoretical methodology. The objective is to find optimal locations
for at most three cabins in a way that, when attending emergency calls, the policemen follow globally optimized
paths respecting the driving direction along the streets.
Keywords: Graphs, allocation, urban security.
1. Introdução
A literatura especializada atual contempla de forma bastante ampla a discussão de diferentes
aplicações de problemas de localização de serviços urbanos emergenciais, tais como os de
postos de serviço para ambulâncias, bombeiros e polícias, em vista da grande importância que
o rápido atendimento a tais chamadas pode representar, de modo a salvar vidas, preservar o
patrimônio público e/ou privado e prevenir a criminalidade, segundo Takeda (2000) e Oliveira
(2003). Com o crescimento muitas vezes desordenado das cidades, aumenta a necessidade de
investimentos nas áreas sociais, visando proporcionar bem estar para a população. Nesta
perspectiva, estudos vêm sendo realizados com a finalidade de otimizar o uso dos recursos
destinados ao atendimento da demanda de novos postos de serviço e assim melhorar a oferta
desses serviços, podendo-se desta forma proporcionar melhor atendimento aos interessados. A
variedade de situações envolvida tem estimulado pesquisadores a aprofundados estudos nesta
área de aplicação.
Pesquisa Operacional e o Desenvolvimento Sustentável
27 a 30/09/05, Gramado, RS
Nos últimos tempos, com a preocupação de reorganizar os serviços urbanos emergenciais,
pesquisadores têm voltado certa atenção para este foco, como pode ser visto nos trabalhos de
Fujimara et al (1987), Trudeau et al(1989) e Golberg et al (1990). Brandeau e Larson (1986)
fizeram um estudo da localização das ambulâncias em Boston. Chelst e Barlach (1981)
calcularam o envio de duas patrulhas para cada ocorrência, devido a vários exemplos dos
departamentos de polícia.
O objetivo deste trabalho é a alocação de cabines de segurança: postos, ou guaritas, que
possuam condições e equipamentos que permitam um atendimento eficiente à população em
casos de ocorrência de situações que exijam a presença policial. Trata-se de um estudo piloto
que abrange parte do bairro Leblon, localizado na cidade do Rio de Janeiro. Foi considerado
que cada cabine de segurança disporá, ao menos, de uma unidade de veículo de transporte
pronta a atender à necessidade de locomoção de policiais ali alocados, sempre que solicitados,
ou que assim considerarem necessário. Neste trabalho analisa-se a possibilidade de instalação
de até 3 (três) dessas cabines.
2. Como o problema tem sido abordado
A alocação de pontos de segurança no Rio de Janeiro tem sido feita em parte por critérios da
Polícia Militar do Rio de Janeiro e em parte atendendo a demandas de setores da sociedade
que identificam as necessidades, definem ou sugerem a localização e coletam recursos para
sua efetiva implantação. Não há estudos de caráter mais amplo que identifiquem a melhor
localização para um dado número desses pontos, em relação à sua capacidade de intervenção.
Segundo Takeda (2000), serviços emergenciais são de responsabilidade do poder público que,
em muitas situações, não apresenta planejamento adequado para a realidade envolvida. Na
grande maioria dos casos, não existem avaliações periódicas para avaliar as condições
operacionais do sistema e definir indicadores de desempenho que revelem o nível de serviço
oferecido.
3. Objetivos do trabalho
Para serviços de emergência o critério de definição da localização das cabines deve, em
princípio, basear-se na otimização, a priori, da maior distância associada ao deslocamento
entre a cabine de segurança localizada mais próxima da ocorrência e o local desta ocorrência.
Por se tratar de um bairro de alto poder aquisitivo foi adotado, como hipótese de trabalho, que
os policiais receberiam chamadas sempre por telefone, dado o percentual elevado de telefones
fixos e celulares entre a população. Portanto, não foi considerada a situação na qual uma
pessoa tivesse que se deslocar a pé, de algum ponto do bairro, até uma cabine.
A quantidade de cabines a serem alocadas, neste trabalho, é um dado do problema. Foi
considerado que os pontos onde se daria um atendimento policial correspondam a esquinas, o
que é uma aproximação razoável, tendo em vista que o atendimento seria por viatura e a
inexistência de trechos de rua de comprimento não compatível com essa hipótese (por
exemplo, superior a 300 metros). Os melhores itinerários a serem percorridos e a
determinação das distâncias mínimas de deslocamento dos policiais até o cidadão foram
considerados no sentido cabine-ponto de atendimento, respeitando-se o sentido do trânsito em
vias públicas dentro do objeto em estudo.
4. Dados, conceitos teóricos e considerações sobre o modelo adotado
O modelo de grafo associou cada interseção de ruas (esquina) a até quatro vértices e cada
trecho de rua a um arco, sempre que o sentido do tráfego o permita. Os pesos atribuídos aos
2354
Pesquisa Operacional e o Desenvolvimento Sustentável
27 a 30/09/05, Gramado, RS
arcos são as distâncias entre os vértices adjacentes. A ordem de rotulação dos vértices seguiu
os sentidos Leste-Oeste e Sul-Norte.
Resumidamente, as noções teóricas utilizadas são as seguintes:
O afastamento e(x) de um vértice x ∈ X em um grafo G=(X,U) é a maior distância do vértice
a algum y∈X. Num grafo orientado, consideram-se o afastamento exterior e+(x) e o seu dual
direcional, o afastamento interior e-(x). Apenas o primeiro foi aqui considerado. O raio ρ(x) é
o menor dos afastamentos existentes num grafo. O centro num grafo é um vértice de
afastamento mínimo. A noção de centro pode ser generalizada para um conjunto de vértices,
definindo-se um p-centro, Christofides (1975) como um conjunto de p vértices tal que a
distância de todo vértice externo a algum dos seus vértices seja mínima.
A fonte para consulta foi o mapa digital vetorial do bairro do Leblon, adquirido junto ao
IPLAN-RIO (Instituto Municipal de Urbanismo Pereira Passos). O mapa possui uma escala
de 1 : 10.000, com um erro máximo de um ponto de + 13 metros e 90% desses pontos
apresentam erros inferiores a + 8 metros. Um mapa simplificado da região está representado
no Anexo A, e o grafo que modela a área em estudo está representado no Anexo B.
A modelagem deste problema por grafos envolve a determinação de um p-centro (exterior) do
grafo. No caso de uma só cabine, o problema é de centro simples e foi resolvido utilizando-se
o algorítmo de Floyd-Warshall, Boaventura (2003). Os casos de dois e de três centros foram
resolvidos por enumeração, dadas as pequenas dimensões do problema e o pequeno número
de centros.
Para a determinação da localização de apenas uma cabine de segurança foi utilizada a idéia de
minimizar a maior distância. Sendo assim, uma única cabine de segurança deve ser localizada
em um 1-centro exterior, visto que o importante nesta situação reside no fato de que o serviço
policial chegue rapidamente ao local onde é necessário, Boaventura (2003). No caso de mais
de uma cabine, foi introduzido um caso para análise comparativa (Situação 2) no qual se
considera uma distância mínima a ser observada entre as cabines, de modo a que se obtenha
uma melhor distribuição da presença policial.
5. O problema de p-centros
O objetivo do problema de p-centro é instalar um determinado número de facilidade para
servir diversas comunidades, sendo que as mesmas devem ser instaladas nas comunidades.
Assim, pretende-se minimizar a distância entre a unidade de serviço e a comunidade mais
distante, isto é, otimizar o pior caso.
O problema de p-centros aplicado ao objeto de estudo é o de localizar dois e três centros no
grafo do bairro do Leblon, os quais minimizam a distância entre as cabines policiais e a
comunidade, ou seja, quer se determinar os p vértices (Xp) do grafo que minimizam a
“distância” entre os vértices dos grafo (Xi) e os Xp.
Christofides e Viola (1971) apresentam um algoritmo para resolver problemas de localização
de serviços emergenciais como localização de bombeiros, hospitais, polícia, ambulância e
outros O algoritmo proposto é uma forma iterativa de resolver problemas do ponto central.
5.1 O caso p = 1
Na busca de um centro único foi utilizado o algoritmo de Floyd-Warshall, pela sua excelente
performance, aliada a sua grande simplicidade. O resultado é imediato.
5.2 O caso p > 1
2355
Pesquisa Operacional e o Desenvolvimento Sustentável
27 a 30/09/05, Gramado, RS
Como foi colocado, o problema foi resolvido por enumeração visto que sua ordem de
grandeza, bem como o número de centros a serem considerados, permitia um processamento
bastante rápido.
Seja Dk,l = max { d(Xi,Xk), d(Xi,Xl) } a maior das distâncias entre todos os outros vértices Xi
(Xi ≠ Xk, Xi ≠ Xl) do grafo aos vértices Xk e Xl, onde (Xk, Xl) é uma dentre quaisquer das
combinações dois a dois dos vértices do grafo.
De posse de todos os Dk,l, tomaremos min { Dk,l }. O par Xk, Xl que possuir o valor mínimo
será o par de centros Xp, isto é, a localização dos 2-centros.
De forma análoga, o procedimento se repete para o caso 3-centros.
Na situação em que se procurou evitar a possível alocação de cabines muito próximas uma da
outra, excluíram-se as soluções que apresentassem:
-
no caso de 2 cabines, uma distância entre cabines menor que 2/3 do raio do grafo;
-
no caso de 3 cabines, uma distância entre cabines que permitisse inscrever 3
vizinhanças circulares de diâmetro igual à distância mínima, em uma circunferência de
raio igual ao raio do grafo.
6. Resolvendo o problema de p-centros
As restrições do algoritmo para a busca de dois e de três centros foram baseadas no resultado
obtido para o caso de um centro (vértice 43). O algoritmo encontrou um raio de 1227 metros.
O caso p = 2
Situação 1: Não foi considerada restrição de distância mínima entre o par de vértices
tomados como centros.
Situação 2: Foi considerada uma restrição de distância mínima entre o par de vértices
tomados como centros, correspondente a 2/3 do raio determinado no caso de um centro. O
desenho a seguir (Fig. 1) ilustra a situação considerada.
Figura 1: Distância mínima entre centros
•
•
O caso p = 3
Foram adotadas condições análogas às do caso de dois centros.
Situação 1: Não foi considerada restrição de distância mínima entre os vértices tomados
como centros.
Situação 2: Foi considerada uma restrição de distância mínima entre o trio de vértices
tomados como candidatos a centros (Fig. 2).
O desenho a seguir ilustra a situação. Observa-se que o raio (que seria o do grafo, por
analogia com uma circunferência) é igual a 2/3 da altura do triângulo, somado à metade da
distância mínima entre os centros.
2356
Pesquisa Operacional e o Desenvolvimento Sustentável
27 a 30/09/05, Gramado, RS
Figura 2: Cálculo do valor de 92,8% da medida do raio
(distância mínima)
r = 2/3 altura do triângulo eqüilátero + d/2
•
•
•
r = 2/3 d 3 + d
2
2
•
r=d 2 3 +3
6
⇒ dmin = 0,928 r
7. Implementação e resultados computacionais
A implementação do algoritmo base para a execução deste trabalho foi realizada utilizando-se
a linguagem Borland Turbo C++, Versão 3.0 em microcomputador AMD Athlon XP 2.4 com
256Mb de RAM. Os resultados obtidos estão indicados na Tabela 1.
Dist.
Dist. efetiva entre centros Maior percurso pelo usuário
mínima
Problema Situação Vértices entre
Vértice Vértice Dist. máx. Vértice Vértice Dist. máx.
centro
centros origem destino
(m)
origem destino
(m)
1-centro
43
----43
97
1227
2-centro
1
13,71
----71
105
958
2
13,71
806
13
71
1107
71
105
958
3-centro
1
38,48,92
----48
28
698
2
20,50,103 1138
20
50
1167
20
90
764
Tabela 1: Localização de centros e resultados numéricos correspondentes
De uma forma geral, entre os casos estudados é claro que a melhor solução para o bairro é a
localização de 3 cabines (ou até mais) pois ela minimiza a distância máxima até o usuário. Se
o custo for alto ou se a política de alocação for de no máximo 2 cabines, seria suficiente
localizar essas duas cabines levando em consideração o resultado obtido para três, pois esta
solução apresenta um vértice em uma esquina muito próxima ao batalhão da PM do bairro,
que faria assim parte do problema. Os maiores percursos a serem percorridos pelos usuários,
identificados na Tabela 1, estão ilustrados no anexo B.
8. Análise dos resultados
8.1 Caso de um centro
O algoritmo encontra o vértice 43 como o centro do grafo (esquina da Rua João Lira com a
Avenida Ataulfo de Paiva). A distância máxima (deste vértice ao vértice 97) é de 1227
metros. Logo, a instalação de uma única cabine na área considerada não atende de modo
eficiente às necessidades do cidadão.
8.2 Caso de dois centros
2357
Pesquisa Operacional e o Desenvolvimento Sustentável
27 a 30/09/05, Gramado, RS
Situação 1: os vértices 13 e 71 foram determinados como centros. A distância máxima (do
vértice 71 ao vértice 105) é de 958 metros. Muito embora tais vértices tenham suas
localizações situadas em locais estratégicos do grafo, se considerarmos as orientações dos
fluxos dos veículos, a distância é ainda maior que a considerada satisfatória, e assim, fica
claro que a instalação de duas cabines, na área considerada, ainda não atende de modo
satisfatório e eficiente às necessidades do cidadão.
Situação 2: os mesmos vértices da situação anterior foram determinados como centros. A
distância efetiva entre esses vértices é de 1007 metros e, portanto, a restrição de distância
mínima de 806 m entre eles é satisfeita.
8.3 Caso de três centros
Situação 1: os vértices 38, 48 e 92 foram determinados como centros. A distância máxima de
um vértice do grafo até um centro (do vértice 48 até o vértice 28) é de 698 metros. Para uma
solução com 3 centros essa distância é bastante alta, pois representa mais da metade da
distância para o caso de um centro.
Situação 2: os vértices 20, 50 e 103 foram determinados como centros. Em relação à situação
anterior, estes vértices estão ligeiramente afastados entre si (a maior das distancias ocorre
entre os vértices 20 e 50 e é de 1167 metros). A restrição de distância mínima entre os pontos
provocou, de fato, um acréscimo na distância máxima a ser percorrida pelo usuário, passando
para 764 metros. Portanto, estamos diante de uma solução viável (porém não a melhor) do
problema em estudo.
9. Conclusões
A possibilidade de instalação de uma única cabine, em quaisquer das duas simulações
efetuadas, mostra claramente as dificuldades que causará aos usuários em virtude da
necessidade de serem percorridas distâncias muito maiores que aquelas julgadas satisfatórias
para um atendimento mais eficaz, em alguns casos superiores a um quilômetro.
Considerando-se a possibilidade de instalação de duas cabines, a solução que apresenta a
maior relação localização/distância máxima ao usuário é aquela que contempla os vértices 13
e 71, porém a distância de 958 metros ainda tem valor bastante elevado.
Considerando-se a possibilidade de instalação de três cabines, a solução que apresenta a maior
relação localização/distância máxima ao usuário é aquela que contempla os vértices 38, 48 e
92, pois estão bem localizados em relação aos demais e minimizam a distância máxima até o
usuário, que é de 698 metros.
De um modo geral, dentre as simulações feitas, aquela que apresentou o melhor resultado é
quando se considera a possibilidade de instalação de três cabines, pois minimiza a distância
máxima até o usuário de forma considerável e satisfatória.
Se o custo de instalação de três cabines for considerado fora do orçamento projetado para tal,
e for possível a instalação de até duas cabines, pode-se considerar os resultados obtidos para a
simulação de instalação de três cabines, pois um dos vértices que compõem a solução está
localizado numa esquina muito próxima ao Batalhão.
12. Referências
Boaventura Netto, P. O., Grafos - Teoria, Modelos, Algoritmos, 3a ed., São Paulo, E. Blucher,
2003, 314 p.
2358
Pesquisa Operacional e o Desenvolvimento Sustentável
27 a 30/09/05, Gramado, RS
Brandeau, M.; Larson, R.C. (1986). Extending and applying the hypercube queuing model to
deploy ambulances in Boston. In: Swersey, A.J. and Ingall, E.J., (eds) Delivery of Urban
Services. TIMS studies in the Management Science v.22, Elsevier, 121-153.
Chelst, K.R.; Barlach, Z. (1981). Multiple unit dispatches in emergency services: Models to
estimate system performance. Management Science. v.27, n.12, 1390-1409.
Christofides, N. (1975). Graph theory: an algorithmic approach. Academic Press.
Christofides, N.; Viola, P. (1971). The Optimum Location of Multi-centers on a Graph.
Operational Research Quarterly. v.22, n.2, 145-154.
Fujimara, O.; Makjamroen, T.; Gupta, K.K. (1987) Ambulance deployment analysis: A case
study of Bangkok. European Journal Operational Research. v.31, 9-18.
Golberg, J.; Dietrich, R.; Chen, J.; Mitwasi, M.; Valenzuela, T.; Criss, E. (1990) Validating
and applying a model for locating emergency medical vehicles in Tucson, AZ. European
Journal Operational Research v.49, 308-324.
Oliveira, L. K. (2003). Uma aplicação do modelo hipercubo de filas para avaliação do centro
de emergência da Polícia militar de Santa Catarina. Dissertação de Mestrado, Programa de
Pós-Graduação em Engenharia de Produção, Universidade Federal de Santa Catarina (UFSC).
Takeda, R. A. (2000) Uma contribuição para avaliar o desempenho de sistemas de
transportes de saúde. Tese de Doutorado, Departamento de Engenharia de Transportes,
Escola de Engenharia de São Carlos, USP.
Trudeau, P.; Rousseau, J.; Ferland, J. A.; Choquette, J. (1989). An operations research
approach for the planning and operation of an ambulance service. INFOR. v.27, n.1, p.95113.
Agradecimento
Este trabalho teve o apoio do CNPq, através de bolsa de pesquisador e “grant” associado.
Anexos A e B
Anexo A: corresponde ao mapa do bairro, adicionado da rotulação que associa esquinas a
vértices do grafo utilizado como modelo.
Anexo B: corresponde ao grafo. Nele, estão indicados os percursos correspondentes às
distâncias máximas contidas na Tabela 1.
2359
Pesquisa Operacional e o Desenvolvimento Sustentável
27 a 30/09/05, Gramado, RS
Anexo A
2360