Uso de SAS/OR® para diminuir o tempo de resposta com um melhor
posicionamento de ambulâncias.
Fábio França1,
1
Logical Optimization – Rua Tanhaçu número 405,
CEP 05679-040 São Paulo, Brasil
[email protected]
Resumo. Usando o módulo de pesquisa operacional do SAS®, o Departamento de Bombeiros de
São Francisco analisou operações de resposta a emergências para otimizar o posicionamento de
ambulâncias e criar procedimentos de despacho para reduzir o tempo de resposta. Um primeiro
modelo foi criado como um modelo de planejamento para o posicionamento inicial de
ambulâncias na cidade de São Francisco. Um segundo modelo foi criado para determinar como
posicionar da melhor forma as ambulâncias restantes quando certo número de unidades está
atendendo uma emergência. Este modelo pode ser extendido para quaisquer recursos móveis
utilizados no atendimento de emergências, daí a relevância para a Copa do Mundo e Olimpíadas.
1. Introdução
Na cidade de São Francisco, as ambulâncias são posicionadas nas diversas unidades do corpo de
bombeiros. Existem 19 ambulâncias que podem ser alocadas às 41 unidades do corpo de
bombeiros. Quando existe uma emergência, a unidade mais próxima é enviada para atender o
chamado. Redução no tempo de resposta é chave para salvar vidas e melhorar resultados. O foco
deste projeto foi reduzir o tempo de resposta.
A redução no tempo de resposta pode ser alcançada de diversas maneiras. Como um problema
de otimização, nós focamos em minimizar a distância entre as unidades disponíveis e chamadas
de emergência. A ideia geral é que uma redução na distância produzirá uma redução no tempo
de resposta. Isso requer uma definição quantitativa da distância entre chamados e unidades.
Idealmente, pode-se considerar a distância entre um chamado e um atendimento, calculando-se
as distâncias entre todos os possíveis locais de chamados e locais em que unidades de
atendimento se encontram. Infelizmente isto não é factível, já que os chamados podem vir,
literalmente, de qualquer lugar da cidade. Ao invés disso, a cidade foi dividida em 174 áreas que
têm aproximadamente a mesma população e número de chamados. Desta maneira, algumas
áreas são muito pequenas geograficamente e outras muito maiores. Por exemplo, a área que
cobre o parque de Golden Gate é, geograficamente, muito maior que a área de uma pequena
seção do centro da cidade. Distância entre dois pontos é medida em termos do tempo médio
gasto para ir do centro da área até uma unidade do corpo de bombeiros. Esta definição de
distância não nos permite modelar diferenças de tráfego devido à hora do dia, mas mantém
nosso modelo suficientemente simples para um tempo de resposta muito rápido.
Agora que o problema das distâncias está bem definido, precisamos qual o caminho para
resolver nosso problema. Na teoria de pesquisa operacional, este problema é conhecido como
um problema de Localização de Instalações. Um problema de Localização de Instalações
consiste em determinar a localização de p instalações e atribuir clientes às mesmas de maneira a
minimizar a distância máxima entre um cliente e a instalação a qual ele foi alocado. Em nosso
caso, estamos alocando área da cidade a ambulâncias de maneira a minimizar a distância entre
chamados de emergência e ambulâncias. Isso requer que aloquemos, também, ambulâncias a
unidades do corpo de bombeiros, mas nós simplesmente alocamo-las àqueles que estão
provendo cobertura. Para minimizar a distância, você pode minimizar a distância total, distância
média, ou simplesmente minimizar a distância máxima. Nós escolhemos minimizar a distância
máxima. Esta abordagem assegura que todas as distâncias serão iguais ou menores a uma
distância máxima específica, o que está alinhado com o objetivo de tempo de reposta abaixo de
um limite. O restante do artigo discutirá a formulação do problema, solução e desafios de
implementação.
2. O Problema de Planejamento
Nós chamamos a formulação do problema inicial de problema de planejamento. A formulação
do problema foi desenhada para responder à questão: “Em um determinado momento com
nenhum chamado, quais são as unidades do corpo de bombeiros nas quais as ambulâncias
devem ser posicionadas para minimizar a distância entre as 174 áreas da cidade e as 19
ambulâncias?”. Este problema endereça onde o corpo de bombeiros deve posicionar
inicialmente suas ambulâncias.
2.1 Formulação do Problema
Esta seção descreve a formulação do problema de pesquisa operacional. Incluímos equações e
descrições textuais. De maneira a formular uma base teórica para a solução, devemos definir
formalmente o que conhecemos e o que esperamos determinar. Sabemos a localização das
unidades do corpo de bombeiros onde as ambulâncias podem estacionar e esperar chamados e
tempo de jornada entre qualquer unidade e área da cidade. Nós estamos procurando uma
maneira de alocar áreas da cidade a unidades do corpo de bombeiros e ambulâncias à unidades.
Vamos definir os seguintes índices para os conjuntos que usaremos:
Tabela 1. Índices
Índice
Conjunto
Descrição
i
I
Conjunto locais de unidades do
corpo de bombeiros
j
J
Conjunto de áreas da cidade
m
Im
Conjunto de locais que devem ter
uma ambulância {i ∈ Im } ⊆ I
Usaremos os seguintes nomes e índices para descrever os dados que serão usados pelo
sistema.
Tabela 2. Parâmetros
Parâmetro
Descrição do Parâmetro
LocaisAbertos
Número de ambulâncias disponíveis
Si
Oferta de atendimentos no local i
DISij
Distância do local i até a área j
defaultAberto
Lista de locais que devem ser abertos (m ∈ Im)
Isso descreve o que já conhecemos. Agora precisamos definir termos que descrevam o que
queremos resolver. Esses termos são comumente conhecidos como variáveis de decisão.
Tabela 3. Variáveis
Variável
Descrição da variável
Xij
= 1 se o local i cobre a área j, 0 se não.
Abertoi
= 1 se o local i tem ambulância, 0 se não.
DistMax
Distância máxima entre um local e áreas de
cobertura.
A função objetivo define o objetivo do modelo de otimização. Em nosso caso: Minimizar a
distância máxima entre locais e áreas. Em nossa notação:
Min DistMax
Restrições
O problema de otimização possui as seguintes restrições.
Definição de Distância Máxima:
(1) DistMax ≥ DISijXij para todos i em I, j em J
Restrição de Disponibilidade: O número total de locais abertos deve ser igual ao número de
locais disponíveis para abertura.
(2) ∑i∈I Abertoi = LocaisAbertos
Restrição de Serviço: locais que cobrem uma área devem estar abertos.
(3) Xij ≤Abertoi para todo i em I, j em J
Restrição de Cobertura: A soma da cobertura deve atender à demanda. Demanda aqui
significa que toda área requer atendimento. Ou seja, toda área deve ser coberta por uma
ambulância, e qualquer solução deve prover cobertura para a cidade inteira.
(4) ∑i∈I Xij = Dj para todo j em J
Restrição de Oferta: a soma da cobertura não pode exceder a oferta. Oferta aqui significa
que cada local pode fornecer cobertura a certo número de áreas e a cobertura ocorre apenas
quando o local possuir uma ambulância.
(5) ∑j∈JXij ≤ SiAbertoi para todo i em I
Restrição de Abertura Default: força os locais em I m serem abertos. Esta restrição não está
sendo usada correntemente, mas provê meios de forçar certos locais a abrigar uma ambulância.
(6) Abertoi = 1 para todos i em I m
3. O Problema Real
O problema de planejamento esconde uma das realidades que o corpo de bombeiros de São
Francisco se depara. Apenas em raras ocasiões todas as ambulâncias estão disponíveis
esperando por chamados. Na maior parte do tempo, pelo menos uma ambulância está fora em
algum atendimento. Portanto, uma questão mais relevante seria: “Se certo número de
ambulâncias está fora em atendimento, como se deve reposicionar as ambulâncias restantes de
modo a minimizar a distância entre chamados e ambulâncias?” Nós chamamos este de problema
de tempo real. A formulação do problema de tempo real é a mesma do problema de
planejamento com o acréscimo de alguns conjuntos e uma restrição.
Nós definimos um novo índice f e um novo conjunto: I f. If é o conjunto de locais abertos que
não estão em I m, isto é, estão abertos, mas podem ser fechados. Vamos criar uma restrição que
obrigue o modelo a reposicionar no máximo k ambulâncias.
Restrição de Local Fixo: requer que todas ambulâncias menos k permaneçam onde estão
(7) ∑i∈If Abertoi + k ≤ LocaisAbertos - ∑i∈Im Abertoi
Pode-se perguntar por que não, simplesmente, rodamos o problema com um número de
ambulâncias reduzido. A razão é inteiramente prática. Não é razoável pedir que as ambulâncias
movam-se constantemente. Mantê-las estacionadas tanto quanto possível permite que as equipes
possam comer e descansar apropriadamente, o que, claramente, é fundamental para o bom
desempenho de suas funções.
4. Busca por soluções
Sendo este um problema de programação inteira, precisamos de um solver de programação
inteira. O solver do SAS utilizado foi o MILP – Mixed Integer Linear Programming. O tempo
de solução para este problema é muito alto para ser resolvido de maneira direta. Outros solvers
testados pelo corpo de bombeiros de São Francisco demoraram mais de vinte horas para
encontrar a melhor solução. A solução deste problema não é viável se não for muito rápida de
maneira a ser passada rapidamente para os despachadores.
Com uma estratégia simples de busca binária passamos de horas para segundos no tempo de
solução. A chave para se entender o funcionamento é lembrar que queremos minimizar a
distância máxima entre o chamado (área da cidade) e uma ambulância. Portanto, a solução para
o nosso problema encontra-se em algum lugar na lista de distâncias e nós precisamos apenas
encontrá-la.
O seguinte algoritmo descreve nossa busca pela mínima distância máxima e utilizamos o
MILP para nos ajudar.
(1) Fixe um limite mínimo para a variável DistMax como a maior distância mínima entre uma
unidade e uma área
(2) Crie uma função objetivo dummy (exemplo: min 0)
(3) Resolva uma série de problemas de viabilidade. Já que a solução deste problema é igual a
uma das distâncias DIS[i,j]; ordene estas distâncias e faça uma busca binária, resolvendo um
problema de viabilidade a cada passo nos quais arcos com distâncias maiores são abandonados.
Siga os passos:
a. Crie uma lista ordenada das distâncias.
b. Escolha a distância do meio da lista (chame de m).
c. Crie uma restrição que força X ij=0 para todas as distâncias maiores que m.
d. Se uma solução viável existir, então o valor de DistMax mínimo deve ser menor ou
igual a m. Vá ao passo b. e repita o processo até não encontrar uma solução viável, encontrando,
assim, o menor valor de m.
Já que podem existir várias soluções com este valor de DistMax, rodamos o problema
completo para minimizar a distância total com a restrição de DistMax= m.
Usando este método para resolver o problema conseguimos uma solução abaixo de um
minuto.
5. Implementando a Solução
O resultado do modelo deve ser comunicado aos despachadores. O corpo de bombeiros de São
Francisco usa um sistema de despacho computadorizado que rastreia visualmente o movimento
das ambulâncias usando GPS. O sistema não controla o movimento das ambulâncias;
despachadores avisam as ambulâncias quando estas devem se sair de uma unidade. Conquanto
uma variedade de dados possa ser lida da solução do modelo, os despachadores necessitam de
uma informação muito limitada. Eles precisam da informação apenas da seguinte forma: “Mova
a ambulância x da unidade 1 para a unidade 2”.
De fato, na implementação proposta, recebem a sugestão de onde posicionar as ambulâncias
restantes. Eles podem desprezar a solução se acharem que têm uma solução melhor devido a sua
experiência com padrões de tráfego e tipos de chamadas. Devido aos chamados constantes por
atendimentos, o despachador precisa de uma solução consistentemente atualizada. Esta é a
motivação para encontrar uma solução muito rápida abaixo de um minuto.
6. Conclusão
O tipo de problema apresentado aqui, problema de Localização de Instalações, é um problema
muito estudado pela área de pesquisa operacional, sendo o primeiro em 1826 por Von Thüen.
Vários modelos foram desenvolvidos em diversas áreas de aplicação: localização agrícola,
localização industrial, planejamento de cidades, estudos ambientais, marketing, logística e,
finalmente, serviços de emergência.
O caso apresentado mostra que, apesar de todo este estudo acumulado e do poder
computacional disponível, cada problema particular possui características únicas que precisam
ser tratadas individualmente. Isto dificulta o uso de pacotes e propicia o desenvolvimento de
projetos específicos.
Penso que a relevância do caso apresentado, mostrando tanto ferramentas disponíveis quanto
problemas reais, para a Copa do Mundo e Olimpíadas do Brasil, é bastante clara para o
atendimento de emergências durante estes eventos.
Podemos extender o caso apresentado não só para emergências (ambulâncias, guinchos,
viaturas, etc.) como, também, para outras classes de problemas de localização tais como
localização de postos de informação, de serviços de transportes, atrações turísticas entre outros.
Referências
Gomes, C. F. S., Ribeiro, P. C. C. (2004) “Gestão da Cadeia de Suprimentos Integrada à
Tecnologia
da
Informação”, Técnicas
de
Localização
[Em
linha].
<http://books.google.pt/books?id=B06QoZ8jB8IC&printsec=frontcover#PRA1-PA55,M1>
Almeida, L. M. W. (2009) “Problemas de localização [Em linha]”. Disponível em WWW:
<URL: http://www.eps.ufsc.br/teses99/werle/cap3.html>
William Storti, Jodi Blomberg (2008) “Using SAS/OR® to Improve Emergency Response
Timeswith Better Ambulance Placement”.
http://support.sas.com/resources/papers/sgf2008/sasOR.pdf