MOTIVATIONAL ASPECTS

Uma vez definida a estrutura de dados, o passo seguinte consiste em definir os procedimentos de construção de soluções iniciais, correspondentes ao comportamento das abelhas exploradoras. Esses procedimentos têm por finalidade

encontrar soluções iniciais viáveis, sendo cada uma delas representada por um conjunto de localizações de bases e alocações de ambulâncias nos períodos de tempo atendendo às condições de viabilidade. Antes de qualquer alocação de viaturas, as bases precisam ser localizadas. Além disso, como a realocação de bases é fisicamente impossível, uma solução contida numa determinada abelha no seu vetor bi conterá um conjunto de bases comum para os períodos de análise, bases estas que serão ocupadas por um número variável de viaturas nos diversos períodos. Ou seja, a localização das bases, para uma solução contida numa determinada abelha, precisa ser definida apenas uma vez, dado que é fixa ao longo dos períodos de análise. Contudo, certo conjunto de bases pode ser inviável, por impossibilitar o atendimento de todos os pontos nos raios mínimos de cobertura; neste caso, o conjunto de bases precisa ser redefinido.

O procedimento de localização de bases utiliza um mecanismo aleatório, na medida em que é arbitrado um percentual, p_aleatorio, do número total de bases que são randomicamente localizadas, sendo idênticas as probabilidades de sorteio de cada ponto candidato. Isso significa que as primeiras (p_aleatorio.pz) bases são localizadas

em locais candidatos randomicamente sorteados, resultando numa possibilidade de diversidade de soluções. Essa característica é necessária para o funcionamento de qualquer algoritmo populacional como o algoritmo ABC.

As outras bases são localizadas através de uma lógica que procura o ponto candidato ainda sem nenhuma base posicionada, tal que o menor tempo de deslocamento entre ele e uma base já localizada é máximo. O processo, também chamado de método

minmax, é repetido até que (1-p_aleatorio).pz bases tenham sido localizadas. Esse

método guloso garante que as bases não aleatórias estejam bem distribuídas na malha de pontos, o que por sua vez facilita a construção de soluções viáveis, pois, com um conjunto de bases bem distribuídas, a cobertura de todos os pontos por ambulâncias alocadas a essas bases é facilitada. Além disso, nos casos em que a demanda se encontra distribuída de modo aproximadamente uniforme pelo grafo, sem a existência de pontos com demanda excessivamente maior que os demais, essa distribuição de bases pelo grafo, em geral, favorece a construção de soluções com bons valores de cobertura esperada.

Para a localização das bases, visto que os tempos de deslocamento entre os diversos pontos do grafo são diferentes para cada período, foi considerada no procedimento uma matriz de tempos (t_medios) de deslocamento, sendo que o tempo médio de deslocamento entre o ponto i e o ponto j é igual a média dos tempos de deslocamento entre os pontos i e j em todos os períodos considerados. Essa é uma aproximação, contudo, tendo em vista que o algoritmo ABC utiliza uma população de soluções que são frequentemente modificadas e melhoradas e considerando a aleatoriedade do procedimento, julga-se que essa abordagem de utilizar tempos médios é razoável para o procedimento que visa localizar bases. Esse procedimento foi denominado

LOCALIZA_BASES e encontra-se detalhado na Figura 4.2. 0 LOCALIZA_BASES(abelha i)

1 zera bi

2 cria lista de bases localizadas lista_bases[] 3 bases_localizadas = 0

4 enquanto bases_localizadas < (pz.p_aleatorio) faça 5 sorteia número aleatório r entre 1 e N

6 se bi[r] = 0 7 bi[r] = 1 8 lista_bases = lista_bases + {r} 9 bases_localizadas = bases_localizadas + 1 10 fim 11 fim

12 enquanto bases_localizadas < pz faça 13 cont1 = 0

14 max_t_min =  15 nova_base = 

16 t_minimo_candidato =  17 enquanto cont1 < N faça 18 se bi[cont1] = 0 19 cont2 = 0

20 enquanto cont2 <= bases_alocadas faça 21 t_min_candidato =  22 se t_medios[cont1][lista_bases[cont2]]< t_min_pto 23 t_min_candidato = t_medios[cont1][lista_bases[cont2]] 24 fim 25 fim 26 se t_min_candidato > max_t_min 27 nova_base = cont1 28 max_t_min = t_min_candidato 29 fim 30 fim

31 lista_bases = lista_bases + {nova_base} 32 bases_localizadas = bases_localizadas + 1 33 fim

Figura 4.2 – Pseudocódigo do procedimento LOCALIZA_BASES Fonte: Próprio autor

Uma vez determinadas as localizações das bases, passa-se à alocação das ambulâncias às mesmas. O procedimento desenvolvido para essa finalidade, denominado

ALOCA_AMBULANCIAS, busca primeiramente atender as condições de viabilidade

relativas às coberturas mínimas, e em seguida maximizar a cobertura esperada. É importante frisar que esse procedimento não assegura a viabilidade da alocação, ou seja, ele não garante que em todos os períodos, todos os pontos serão cobertos por ambulâncias de ambos os tipos dentro dos raios de cobertura rA e rB. Para esse

procedimento, no início, são criadas duas listas, lista_BLS e lista_ALS, contendo os pontos que possuem bases. Em seguida essas listas são ordenadas de maneira não crescente, considerando o número de pontos de demanda que podem ser cobertos por essas bases selecionadas, de acordo com os raios de cobertura para BLS e ALS respectivamente. Para cada ponto de demanda as listas ordenadas são percorridas até se encontrar uma base que cobre esse determinado ponto de demanda e tenha capacidade excedente para receber uma viatura. Se essa base ainda não possuir uma ambulância BLS ou ALS, dependendo de qual lista está sendo percorrida, ela recebe uma viatura do respectivo tipo; caso contrário passa-se para o próximo ponto de demanda. Para um determinado ponto de demanda, no caso de não ser possível encontrar nenhuma base que possa cobri-lo dentro dos raios BLS ou ALS, nada é feito e o processo continua normalmente, ou seja, verifica-se que a solução é inviável. O fato de não ser possível cobrir um determinado ponto por algum tipo de veículo indica que o conjunto de bases, utilizado como entrada de ALOCA_AMBULANCIAS, não permite a construção de uma solução viável pelo procedimento e nada pode ser feito, uma vez que ALOCA_AMBULANCIAS busca apenas alocar as viaturas.

O procedimento ALOCA_AMBULANCIAS tenta atender a viabilidade em relação às ambulâncias básicas primeiro, e em seguida em relação às ambulâncias avançadas, ou seja, para cada ponto percorre-se primeiro a lista lista_BLS e em seguida a lista

lista_ALS. A lógica por trás dessas listas ordenadas é tentar atender a viabilidade com

o menor número possível de viaturas de um determinado tipo, buscando alocar primeiro as viaturas nas bases que cobrem maiores quantidades de pontos. As alocações são sempre realizadas respeitando as capacidades das bases relativas às quantidades de veículos.

Em seguida, ainda referindo-se ao procedimento ALOCA_AMBULANCIAS, as duas listas são reordenadas de acordo com a demanda contida na vizinhança de cada ponto da lista em relação à BLS e ALS (a definição das vizinhanças encontra-se no capítulo 3). Essas listas de pontos são percorridas alternadamente alocando-se viaturas BLS e ALS respeitando a capacidade das bases. Destaca-se que esse procedimento de alocação de bases é realizado considerando um determinado período t, o que implica na consideração das vizinhanças e tempos de deslocamento do período t, sendo ele repetido para todos os períodos t_{∈τ. O procedimento ALOCA_AMBULANCIAS é} detalhado na Figura 4.3.

Esses dois procedimentos, LOCALIZA_BASES e ALOCA_AMBULANCIAS, são combinados num outro chamado INICIA_SOLUCOES, que define o comportamento das abelhas exploradoras, ilustrado na Figura 4.4.