Departamento de Engenharia Industrial

Página | 1

APLICAÇÃO DE UM ALGORITMO GRASP REATIVO PARA

PROBLEMAS DE SEQUENCIAMENTO NO CONTEXTO DE

LOGÍSTICA HUMANITÁRIA

Aluno: Jéssica Kexin Sun

Orientador: Luciana Pessôa

1. Introdução

Desastres naturais, como inundações e terremotos, ameaçam a vida de milhões de

pessoas por ano. Por isso, com o intuito de reduzir o tempo gasto no resgate para atender de

forma mais eficiente um número de incidentes e ter como consequência mais vidas salvas e

menos perdas econômicas, faz-se necessário um estudo do gerenciamento de desastres naturais.

Este trabalho amplia o projeto de iniciação científica iniciado em 2016, visando o estudo de

regras de prioridade e heurísticas para problemas de sequenciamento, e considera um problema

de sequenciamento no contexto de logística humanitária para alocação de unidades de resgate

no atendimento de incidentes com diferentes prioridades de acordo com sua severidade. Em

nosso trabalho, aprimoramos o algoritmo GRASP (Greedy Randomized Adaptive Search

Procedures) proposto por Wex et al. [1] e consideramos dados do desastre natural ocorrido em

2011 na Região Serrana do Rio de Janeiro [2]. O algoritmo foi implementado em linguagem

C++ e os resultados computacionais desta pesquisa deram origem a um artigo completo que

será apresentado em agosto/2018 no 50º Simpósio Brasileiro de Pesquisa Operacional, na PUC-

Rio.

2. Objetivos

Nesta pesquisa um problema de alocação e sequenciamento de unidades de resgate

(Rescue Unit Assignment and Scheduling Problem - RUASP) para o atendimento de incidentes

causados por desastres naturais é abordado através da implementação de regras de

sequenciamento e métodos heurísticos para sua resolução. A justificativa para utilização de

métodos heurísticos consiste na sua capacidade de encontrar soluções de boa qualidade

utilizando um tempo de processamento computacional adequado às necessidades da aplicação.

Os métodos heurísticos são classificados entre métodos construtivos, buscas locais e

metaheurísticas. Estas combinam os procedimentos construtivos e de busca local visando

encontrar soluções melhores do que aquelas que seriam obtidas com a aplicação isolada de cada

método [3]. No caso dos desastres naturais, quanto menor o tempo para tomada de decisão sobre

a alocação dos recursos de atendimento, mais vidas são salvas. Neste sentido, algoritmos

capazes de implementar métodos heurísticos devem ser desenvolvidos e validados através de

experimentos computacionais.

3. Descrição do Problema

Os desastres naturais têm ocorrido mais frequentemente no Brasil ao longo dos últimos

anos. A ocorrência e a intensidade destes desastres naturais estão diretamente ligadas com o

grau de vulnerabilidade das comunidades afetadas e não somente dependem da magnitude dos

eventos adversos. Eventos extremos ocorridos nos últimos cinco anos geraram recordes de

Departamento de Engenharia Industrial

Página | 2

impactos sobre a população, desabrigando milhares e levando a óbito centenas, mobilizando

diversos segmentos sociais, acadêmicos e governamentais (BERTONE e MARINHO, 2013).

Os eventos com maior recorrência registrados no país são os que ocorrem devido a

inundações, enxurradas, deslizamentos de encostas, estiagens, secas e vendavais (MMA,2007).

Conforme indicado na Figura 1, nos ambientes urbanos, que abrigam a grande maioria

da população brasileira, as inundações e as enxurradas são os eventos que ocorrem com maior

frequência no país.

Figura 1 - Principais desastres naturais no Brasil (2000-2007). Fonte: [8]

Na Figura 2 são apresentadas as taxas de morte por tipo de evento, indicando que

inundações são os eventos que mais provocam impactos na sociedade, dado que este evento

apresenta maior percentual de óbitos.

Figura 2 - Mortos por tipo de desastre no Brasil (2000-2007). Fonte: [9]

58%

14%

6%

8%

11%3%

Inundações e Enxurradas Seca Temperatura extrema

Vendavais Deslizamento Epidemia

0,00%

5,00%

10,00%

15,00%

20,00%

25,00%

30,00%

35,00%

40,00%

45,00% 43,19%

20,40%18,63%

10,38%

6,30%

0,65% 0,20% 0,12% 0,12%

Departamento de Engenharia Industrial

Página | 3

Entre os desastres ocorridos no Brasil, o de grande destaque pelo grau de seriedade e

danos causados foi o que ocorreu entre a noite do dia 11 de janeiro de 2011 e a madrugada do

dia 12 em que chuvas extremas atingiram a Região Serrana do Estado do Rio de Janeiro (RSRJ)

gerando enchentes devido ao transbordamento de córregos e rios (PINHEIRO et al., 2011).

A Figura 3 apresenta os 7 municípios da RSRJ que foram afetados pela chuva e que

juntos formam uma área estimada de 2.300 km², onde vivem mais de 713.000 habitantes.

Estas enchentes ocasionaram deslizamentos de terra, fazendo com que bairros inteiros

ficassem cobertos por lama, centenas de casas fossem varridas pela terra e dezenas de pessoas

ficassem soterradas, causando perdas imensas. Foram mais de 900 mortes contabilizadas, cerca

de 350 desaparecidos e milhares de pessoas desabrigadas, além de graves danos à infraestrutura,

à economia e a alteração geográfica da região afetada, fazendo desta tragédia o maior desastre

climático e geotécnico da história do país, classificado pela ONU como o 8º maior deslizamento

ocorrido no mundo nos últimos 100 anos (BUSCH e AMORIM, 2011).

Apesar de possuir condições econômicas favoráveis, como setor industrial bem

desenvolvido e presença de pontos turísticos importantes, a região serrana sempre se

Figura 3 - Mapa de localização dos municípios afetados. Fonte: [2]

Departamento de Engenharia Industrial

Página | 4

caracterizou por uma grande vulnerabilidade natural devido à sua localização na Serra do Mar,

formada por rochas com camada fina de terra e coberta por Mata Atlântica, com alto declínio e

regime de chuvas intensas no verão. Além destas condições naturais, acrescentou-se o fator

humano. Ao longo de muitos anos as encostas e margens dos rios foram desmatadas e ocupadas

irregularmente, agravando a vulnerabilidade dos solos instáveis e propensos a deslizamentos.

Estes fatores contribuíam para a convivência anual da região com enchentes e alguns

deslizamentos, embora nenhuma situação de gravidade semelhante ao desastre ocorrido em

janeiro de 2011 (PINHEIRO et al., 2011).

Conforme as normas gerais de defesa civil, os desafios e as atividades de resposta a um

desastre são classificadas na fase de preparação, período anterior ao desastre, que aborda tarefas

relacionadas ao planejamento, treinamento, alerta antecipado e estabelecimento de serviços de

emergência necessários, e se fragmenta em duas etapas (BUSCH e AMORIM, 2011).

Na primeira etapa, período durante o desastre, o objetivo é controlar imediatamente a

situação e reduzir o sofrimento, por meio de ações de busca e salvamento, do isolamento de

áreas de risco e críticas, da evacuação da população e provimento de abrigos, vestuário,

alimentação, serviços médicos, do controle de vias de transporte e de comunicação e da

manutenção da ordem pública. A segunda etapa, período após o desastre, é a de reabilitação ou

recuperação da região afetada, que inclui respostas emergenciais para restauração da

infraestrutura destruída, e restauração de condições mínimas de sobrevivência e segurança. Em

cada etapa é de extrema importância uma coordenação que defina o que fazer, quem deve fazer

e como fazer para que alcancem seus objetivos com sucesso. Concluída a resposta ao desastre,

parte-se para a etapa de reconstrução, que impõe ações sustentáveis, desenvolvidas no longo

prazo (BUSCH e AMORIM, 2011).

De maneira a enfrentar esta tragédia de elevada proporção, formou-se uma ampla rede

de socorro, composta por agentes governamentais, organizações não governamentais, empresas

privadas e voluntários, cabendo destaque às intervenções feitas pelo governo federal, estadual

e municipal e pela sociedade civil. Entretanto, apesar de sua dimensão, o socorro não atingiu a

efetividade necessária. A forma pela qual as relações entre os diversos atores que atuaram na

resposta foram estabelecidas e o papel efetivamente desempenhado por cada um deles são

fatores que possibilitaram a existência de conflito e falta de colaboração e coordenação,

marcando fortemente este episódio pelo despreparo das autoridades brasileiras para enfrentar

tragédias naturais como esta (BUSCH e AMORIM, 2011).

Dessa forma, fica evidente a maneira que desastres naturais de elevada gravidade, como

o episódio da Região Serrana do Rio de Janeiro, ameaçam a vida de milhões de pessoas por

ano. Por isso, com o intuito de atender à um desastre de forma rápida, ao diminuir o tempo

utilizado para resgate, atendendo um número elevado de incidentes em um curto intervalo de

tempo e controlando a situação o mais imediato possível, é de extrema necessidade um estudo

do gerenciamento de desastres naturais.

4. Modelo de Solução

O estudo feito por Wex et al. [1] sugere um problema de sequenciamento no contexto

de logística humanitária, tratado como um problema de programação de máquinas paralelas

com máquinas não relacionadas com tempos de configuração dependentes de sequência.

Departamento de Engenharia Industrial

Página | 5

Pode-se considerar o sequenciamento de trabalhos em máquinas paralelas como um

processo fragmentado em duas etapas. Primeiramente, é necessário determinar quais trabalhos

devem ser alocados para quais máquinas. Posteriormente, é preciso definir a sequência dos

trabalhos alocados para cada máquina (PINEDO, 2008).

É proposto pelo estudo um modelo de apoio à decisão para centros de operações de

emergência que aloca unidades de resgate disponíveis para atender incidentes emergentes com

diferentes prioridades de acordo com sua severidade. A vantagem de possuir um modelo

automatizado de otimização e suporte à decisão de coordenação centralizada de alocação e

agendamento de unidades de resgate disponível é que o suporte à decisão proposto auxilia em

situações em que há um alto nível de complexidade e alta pressão de tempo, como no caso de

desastres naturais, auxiliando autoridades a enfrentar estas tragédias.

O modelo é formulado como um problema binário de otimização quadrática e este é

referido como Rescue Unit Assignment and Scheduling Problem (RUASP), em que o objetivo

é minimizar a soma dos tempos de conclusão ao atendimento de cada incidente 𝑗 (𝐶𝑗)

ponderados por sua gravidade (𝑤𝑗). A função objetivo proposta pode ser descrita como ∑ 𝑤𝑗𝐶𝑗.

O tamanho do problema RUASP é determinado pelo número de unidades de resgate

disponíveis m e o número de incidentes n que precisa ser processado. Consideramos situações

em que o número de unidades de resgate disponíveis é menor ou igual ao número de incidentes

(m ≤ n), pois esta proporção é característica de desastres naturais. Além disso, consideramos as

seguintes propriedades:

1) Cada incidente pode ser atendido por um subconjunto de unidades de resgate.

Assim, pode acontecer de uma determinada unidade de resgate não ter capacidade

para atender um ou mais incidentes.

2) Os tempos de processamento são variáveis e determinados pela combinação

incidente-unidade de resgate.

3) Diferentes unidades de resgate requerem diferentes tempos de viagem entre as

localidades dos incidentes.

4) O atendimento a um incidente não pode ser interrompido.

5) A cada incidente é atribuído um fator de ponderação, tanto para vítimas quanto

danos instigados ao longo do tempo, sendo este peso denominado nível de

severidade ou fator de destruição. Aborda-se o objetivo de minimizar a soma dos

tempos de conclusão de cada incidente ponderados pela sua severidade.

Wex et al. [1] propõem e comparam computacionalmente várias heurísticas para o

problema de apoio à decisão de coordenação centralizada de alocação e agendamento de

unidades de resgate. Foram utilizadas uma heurística baseada em Monte-Carlo, oito heurísticas

construtivas e 5 heurísticas de melhoria. Além disso, foram incorporadas essas combinações de

heurísticas construtivas e de melhoria em metaheurísticas GRASP. Dessa forma, o estudo além

de contribuir para a área de gerenciamento de desastres, contribui também para a literatura de

otimização em geral.

As heurísticas consistem em métodos capazes de obter soluções para problemas

combinatórios em um tempo computacional razoável, contudo, sem garantia de que estas

soluções sejam ótimas (PEARL, 1984; REEVES, 1993). Os métodos heurísticos são

classificados entre métodos construtivos, buscas locais e metaheurísticas. Estas combinam os

Departamento de Engenharia Industrial

Página | 6

procedimentos construtivos e de busca local visando encontrar soluções melhores do que

aquelas que seriam obtidas com a aplicação isolada de cada método [3]. A utilização desse tipo

de método é de grande importância devido ao fato de que em casos de problemas mais

complexos, e mesmo que com pequenas instâncias, métodos exatos podem não ser eficientes

(PEARL, 1984; REEVES, 1993).

5. Aplicação da Solução

Para tratar o RUASP, foi implementado um algoritmo GRASP reativo em que as fases

construtiva e de busca local foram feitas com base nos melhores métodos propostos por Wex et

al. [1], sendo elas a heurística construtiva Sched 7 e a busca local com a vizinhança 3-nodes

exchange. Os experimentos foram realizados com base em dois conjuntos de instâncias

distintas. O primeiro conjunto é referente ao terremoto ocorrido no Japão em 2011 composto

por 10 instâncias, utilizadas no trabalho de Wex et al. [1]. O segundo conjunto, também

contendo 10 instâncias, foi gerado a partir de dados extraídos sobre o desastre ocorrido em 2011

na Região Serrana do Rio de Janeiro [Banco Mundial, 2012; Xavier et al., 2016, da Costa et al.,

2017]. As instâncias de ambos os conjuntos variam de tamanho, com 𝑚 ∈ {10; 20; 30; 40} e

𝑛 ∈ {10; 20; 30; 40} com 𝑚 ≤ 𝑛.

5.1. Heurística Sched 7

Na heurística Sched 7, a alocação se dá de forma iterativa, selecionando o incidente e a

unidade que irá atendê-lo no mesmo passo. Usando 𝐶𝑘 para definir o instante de conclusão

parcial de uma unidade k, δ𝑘 para armazenar o último incidente atribuído a uma unidade k e

σ𝑘 para representar a sequência programada em cada unidade k, a heurística retorna σ =

(σ1,..., σ𝑚), como uma lista de programações para as m unidades, como descrito no algoritmo

1.

Algorithm 1 Heurística Sched 7 [Wex et al., 2014]

1: Inicializa o instante de conclusão de cada unidade de resgate, as unidades partindo do

depósito e a lista vazia de alocação de cada unidade

𝐶𝑘 ← 0, 𝛿𝑘 ← 0, 𝜎𝑘 ← 0, ∀𝑘 ∈ 𝑀. 2: Inicializa a lista de incidentes não alocados 𝐼 ← {1, … , 𝑛}

3: Define 𝐶 ← {𝐶𝑘+𝑠𝛿𝑘𝑖𝑘+𝑝𝑖𝑘

𝑤𝑖| 𝑖 ∈ 𝑁, 𝑘 ∈ 𝑀} e

𝑐 ← 𝑚𝑖𝑛𝑖,𝑘

𝐶𝑘+𝑠𝛿𝑘𝑖𝑘+𝑝𝑖𝑘

𝑤𝑖

4: for 𝑙 = 1 to n do

5: Seleciona o incidente 𝑖∗ ∈ 𝐼 e a unidade 𝑘∗ ∈ 𝑀 correspondente a c, onde a relação entre

o instante de conclusão e o nível de criticidade é o menor. Se não existir um mínimo, retorna

como inviável.

6: Atualiza 𝐼 ← 𝐼 \{𝑖∗}, 𝐶𝑘∗ ← 𝐶𝑘

∗ + 𝑠𝛿𝑘∗ 𝑖∗𝑘∗ + 𝑝𝑖∗𝑘∗,

𝛿𝑘∗ ← 𝑖∗ e 𝜎𝑘

∗ ← 𝜎𝑘∗ ∪ {𝑖∗}

7: Atualiza 𝐶 ← {𝐶𝑘+𝑠𝛿𝑘𝑖𝑘+𝑝𝑖𝑘

𝑤𝑖| 𝑖 ∈ 𝑁, 𝑘 ∈ 𝑀} e

𝑐 ← 𝑚𝑖𝑛𝑖,𝑘

𝐶𝑘+𝑠𝛿𝑘𝑖𝑘+𝑝𝑖𝑘

𝑤𝑖

8: end for

9: retorna 𝜎 ← (𝜎1, … , 𝜎𝑚)

Departamento de Engenharia Industrial

Página | 7

5.2 Busca Local com 3-nodes exchange

A busca local com vizinhança 3-nodes exchange consiste na troca de três nós de posição

entre si, afim de evitar que sejam geradas soluções inviáveis para o problema, dadas as

diferentes disponibilidades das unidades de resgate. No caso do problema abordado, os nós são

os incidentes e estes são trocados respeitando a restrição de disponibilidade das unidades de

resgate. Todas as permutações são testadas dado o conjunto de incidentes programados e todas

as soluções dentro da vizinhança são avaliadas, tomando como solução corrente a de menor

custo dentre todas elas. O algoritmo é interrompido quando nenhuma solução vizinha apresenta

custo menor que o da solução corrente.

5.3 GRASP Reativo

A metaheurística GRASP (Greedy Randomized Adaptive Search Procedures)

corresponde a um processo iterativo de duas fases. A primeira fase se caracteriza pela

construção de uma solução viável a partir de um algoritmo guloso aleatorizado. Na segunda

fase, uma busca local é aplicada sobre a solução corrente, gerada pela primeira fase. O algoritmo

retorna a melhor solução encontrada dentre todas as iterações efetuadas. Neste trabalho,

utilizou-se a heurística Sched 7 na fase construtiva do GRASP e a busca local com a vizinhança

3-nodes exchange para melhoria das soluções construídas.

No procedimento de construção de uma solução viável, um elemento que compõe a

solução é escolhido, a cada passo do algoritmo, a partir de uma lista de elementos candidatos.

Cada um desses elementos possui um custo associado à decisão de incluí-lo na solução parcial.

No caso da heurística Sched 7, um elemento da solução corresponde a um par incidente/unidade.

Para definir o elemento, o GRASP, a cada iteração, utiliza um algoritmo guloso aleatorizado,

definindo uma lista restrita de candidatos (LRC) contendo os melhores elementos. A partir do

custo de entrada de cada um dos elementos candidatos, podem ser computados os custos

mínimo (𝐶𝑚í𝑛) e máximo (𝐶𝑚á𝑥). Para que os elementos façam parte da LRC, seu custo de

entrada deve pertencer ao intervalo definido por [𝐶𝑚í𝑛; 𝐶𝑚í𝑛+α(𝐶𝑚á𝑥−𝐶𝑚í𝑛)] condicionado ao

parâmetro α ∈ [0;1]. Ao passo que um novo elemento é incluído na solução parcial, o custo de

cada um dos elementos restantes deve ser recalculado. Após a construção da solução completa,

é aplicada uma busca local com o intuito de melhorar a solução construída, uma vez que essas

soluções podem não ser ótimos locais.

Para lidar com os diferentes portes de instâncias do RUASP, é utilizado uma abordagem

reativa para atualização do valor de α. Dessa forma, define-se um conjunto discreto, com r

elementos, de valores possíveis para α ∈ {𝛼1; 𝛼2;...; 𝛼𝑟}, com probabilidade 𝑝𝑖,i = 1,...,r

associadas a cada elemento do conjunto. A princípio, definem-se probabilidades iguais para

todos os elementos, com 𝑝𝑖,= 1/r. Conforme o algoritmo é executado, as probabilidades de

escolha de cada valor de α são atualizadas com base na qualidade das soluções desenvolvidas

para cada valor de α no momento da avaliação. O valor da melhor solução encontrada entre

todas as iterações do método, até o momento da avaliação, é definido como 𝑓∗ e o valor médio

das soluções encontradas para α𝑖 é definido como µ𝑖. Desta forma, as probabilidades da escolha

de cada valor de α são atualizadas de acordo com as Equações 1 e 2.

𝑝𝑖 = 𝑞𝑖

∑ 𝑞𝑗𝑟𝑗=1

⁄ , 𝑖 = 1, … , 𝑟 (1)

Departamento de Engenharia Industrial

Página | 8

𝑞𝑖 = (𝑓∗

𝜇𝑖)

𝛿

, 𝑖 = 1, … , 𝑟 (2)

6. Resultados e Discussão

O algoritmo foi aplicado ao primeiro conjunto de instâncias (Inst), referentes ao

terremoto no Japão em 2011 [1]. Os resultados adquiridos, com 30 minutos de execução, são

apresentados na Tabela 1 abaixo em termos do número de unidades (m), número de incidentes

(n), resultados obtidos pela aplicação da heurística Sched 7 junto à busca local com 3-nodes

exchange (Sched 7 + BL), das melhores soluções conhecidas (Best Known Solutions - BKS)

para essas instâncias até então, presentes no trabalho desenvolvido por Wex et al. [1], e do

GRASP reativo subdividido em: Mínimo, Média, Máximo, Desvio Padrão (DP) e os desvios

percentuais, tanto com relação às melhores soluções (∆BKS) quanto com relação às soluções da

heurística com busca local (∆S7).

Tabela 1: Resultados do GRASP reativo com 30 minutos de execução para as instâncias do terremoto no Japão de 2011.

Inst m n Sched 7

+ BL

BKS GRASP Reativo

[Wex et

al., 2014] Mínimo Média Máximo DP ∆BKS ∆S7

1 10 10 276,67 276,67 269,08 269,08 269,08 0,00 -2,74% -2,74%

2 10 20 868,03 834,41 821,15 825,7 826,65 2,04 -1,04% -4,88%

3 10 30 2130,71 2069,54 2022,94 2023,55 2024,97 0,98 -2,22% -5,03%

4 10 40 2582,09 2471,92 2452,52 2459,88 2464,74 4,36 -0,49% -4,73%

5 20 20 482,90 481,02 465,80 466,23 466,86 0,54 -3,07% -3,45%

6 20 30 661,95 645,16 633,06 635,46 637,67 2,08 -1,50% -4,00%

7 20 40 1098,58 1076,03 1059,58 1068,31 1075,81 4,19 -0,72% -2,76%

8 20 30 520,79 484,94 477,79 477,88 478,70 0,29 -1,46% -8,24%

9 30 40 850,55 779,50 789,92 794,37 801,58 3,36 1,91% -6,60%

10 40 40 822,01 684,10 680,65 687,53 694,36 5,17 0,50% -16,36%

Média -1,08% -5,88%

A partir dos resultados obtidos, é possível notar que com o GRASP reativo houve uma

redução de custo em oito (1-8) de 10 instâncias com relação as melhores soluções conhecidas

até então para o problema, apresentando um ganho médio de 1,08% dentre todas as instâncias,

chegando a 3,07% na instância 5. Vale ressaltar também que mesmo as soluções máximas

obtidas pelo método foram menores do que as BKS para essas mesmas instâncias (1-8), porém

nas duas instancias de maior porte (9 e 10), o método não conseguiu melhorar as soluções

obtidas por Wex et al. [1]. No comparativo com a heurística Sched 7 com busca local, o

algoritmo mostrou um ganho ainda maior de 5,88% na média, chegando a 16,36% na instância

10, indicando que os ganhos com o uso desse método em um caso real de desastre natural podem

resultar em um atendimento mais eficiente dos incidentes, evitando assim maiores desastres.

Comprovando a capacidade do GRASP reativo em gerar boas soluções para o RUASP,

o algoritmo foi aplicado ao segundo conjunto de instâncias (Inst) referentes ao desastre de 2011

na Região Serrana do Rio de Janeiro. São apresentados os resultados adquiridos, com 30

minutos de execução, na Tabela 2 abaixo em termos do número de unidades (m), número de

incidentes (n), resultados obtidos pela aplicação da heurística Sched 7 junto à busca local com

3-nodes exchange (Sched 7 +BL) e dos resultados do GRASP reativo, subdivididos em:

Departamento de Engenharia Industrial

Página | 9

Mínimo, Média, Máximo, Desvio Padrão (DP) e os desvios percentuais com relação as soluções

da heurística com busca local (∆S7).

Tabela 2: Resultados do GRASP reativo com 30 minutos de execução para as instâncias do desastre de 2011 na Região Serrana do Rio de Janeiro.

Inst m n Sched 7 +

BL

GRASP Reativo

Mínimo Média Máximo DP ∆S7

1 10 10 10220,2 9911,51 9911,51 9911,51 0,00 -3,02%

2 10 20 27865,8 27050,6 27050,6 27050,6 0,00 -2,93%

3 10 30 54062,6 53328 53328,1 53328,1 0,05 -1,36%

4 10 40 79345,5 77951,6 78191,5 78342 110,26 -1,45%

5 20 20 16941,3 16641 16641 16641 0,00 -1,77%

6 20 30 40330,3 39611,5 39641,7 39762,3 63,58 -1,71%

7 20 40 52350,7 51305,4 51428,5 51568,5 114,70 -1,76%

8 20 30 24979,4 24490,5 24490,5 24490,5 0,00 -1,96%

9 30 40 38759,3 37615,8 37773,4 37976,7 106,58 -2,54%

10 40 40 31229,5 30742,9 30930,1 31051,1 82,11 -0,96%

Média -1,95%

Para esse conjunto de instâncias, a heurística Sched 7 apresentou bom desempenho, com

um desvio médio de apenas 1,95 % em relação ao GRASP e com um desvio máximo de 3,02%

para a instância 1. Apesar de equiparado com o GRASP reativo, qualquer solução que possa

melhorar a programação das unidades de resgate, por menor que seja, pode ser muito

significativa para o tipo de problema abordado.

7. Conclusão

O estudo permitiu um maior conhecimento sobre regras de sequenciamento e métodos

heurísticos, evidenciando a importância de aplicá-los nestes problemas, pois possibilitam obter

soluções boas e em alguns casos com resultados apenas um pouco mais elevados do que os

valores ótimos, em um tempo computacional razoável, enquanto que métodos exatos não são

capazes de solucioná-los. Proporcionou também a experiência de participação do Simpósio

Brasileiro de Pesquisa Operacional.

Através dos resultados obtidos pela implementação do algoritmo GRASP reativo,

evidenciou-se, para o primeiro conjunto de instâncias, referentes ao terremoto no Japão em

2011, uma redução de custo de 1,08% em média do que as melhores soluções obtidas na

literatura para o problema, chegando a uma redução máxima de 3,07% em uma das instâncias

propostas. Para o segundo conjunto de instâncias, referentes ao desastre ocorrido em 2011 na

Região Serrana do Rio de Janeiro, o GRASP reativo foi comparado com a aplicação de métodos

heurísticos definidos na literatura como eficientes para o RUASP, tendo um ganho médio de

1,95% chegando a um ganho máximo de 3,02% em uma das instâncias avaliadas desse

conjunto.

Daremos continuidade ao projeto implementando no GRASP reativo outras heurísticas

construtivas e de busca local, além de gerar mais instâncias de teste a partir dos dados dos

incidentes da região serrana.

Departamento de Engenharia Industrial

Página | 10

8. Referências

1 - WEX, Felix et al. Emergency response in natural disaster management: Allocation and

scheduling of rescue units. European Journal of Operational Research, v. 235, n. 3, p. 697-

708, 2014.

2 - PINHEIRO, Henri; ANDRADE, Kelen; MOURA, Carlos. A maior catástrofe climática do

Brasil sob a visão operacional do CPTEC/INPE. In: Simpósio Internacional de Climatologia,

2011, João Pessoa-PB. Anais… São Paulo-SP: CPTEC/INPE, 2011.

3 - GENDREAU, Michel; POTVIN, Jean-Yves. Handbook of metaheuristics. Volume 2. New

York: Springer, 2010.

4 - PEARL, J. Heuristics: intelligent search strategies for computer problem solving.

Boston: Addison-Wesley, 1984. 382p.

5 - REEVES, C. R. Modern heuristic techniques for combinatorial problems. Nova York:

John Wiley & Sons, Inc., 1993.

6 – BUSCH, Amirilis; AMORIM, Sonia. A tragédia da região serrana do Rio de Janeiro em

2011: procurando respostas. ENAP Casoteca de Gestão Pública, Brasília, 2011. Disponível

em: <http://repositorio.enap.gov.br/handle/1/328>. Acesso em: 18 jul. 2017.

7 – BERTONE, Pedro; MARINHO, Clarice. Gestão de riscos e resposta a desastres naturais: A

visão do planejamento. In: Congresso CONSAD de Gestão Pública, 6, 2013, Brasília. Anais...

Brasília: CONSAD, 2013.

8 - BRASIL. Ministério do Meio Ambiente. Vulnerabilidade ambiental: Desastres naturais

ou fenômenos induzidos. Brasília: MMA, 2007.

9 - Atlas Brasileiro de Desastres Naturais 1991-2010. Volume Brasil. CEPED/UFSC.

Florianópolis, 2012.

10 – PINEDO, Michel. Scheduling: Theory, Algorithms and Systems. 3. ed. New York:

Springer, 2008.

11 - MUNDIAL, Banco. Avaliação de perdas e danos: inundações e deslizamentos na Região

Serrana do Rio de Janeiro - Janeiro de 2011. Relatório elaborado pelo Banco Mundial com

apoio do Governo do Estado do Rio de Janeiro. Brasília, 2012.

12- XAVIER, Iran Rosa; DE MELLO BANDEIRA, Renata Albergaria; BANDEIRA, Adriano

de Paula Fontainhas. Análise do emprego de helicópteros para transporte aéreo logístico

em resposta a desastres naturais. 2016. Tese (Mestrado em Engenharia de Transportes) –

Instituto Militar de Engenharia, Rio de Janeiro.

13- DA COSTA, Natália de Brito Oliveira Luiz; FONTAINHA, Tharcisio Cotta; LEIRAS,

Adriana. Brazilian Air Force operations in disaster response–a process analysis. Disaster

Prevention and Management: An International Journal, v. 26, n. 4, p. 479-498, 2017.