INTRODUCING REDD IN TANZANIA AND UGANDA – CHALLENGES AND OPPORTUNITIES
6. INSTITUTING NATIONAL POLICIES FOR REDD – SOME GENERAL CONSIDERATIONS
6.3 MEASURES INVOLVED
Conhecidas as localizações de bases e a alocação de ambulâncias às bases nos diversos períodos considerados, resultantes da aplicação do método de solução para o subproblema de localização de bases e alocação de ambulâncias em múltiplos períodos (ALGORITMO_ABC), o subproblema de realocação de ambulâncias é então resolvido a fim de encontrar o plano de realocação de menor tempo total de deslocamento, sendo esse plano de realocação caracterizado pelas realocações de veículos entre bases, entre períodos subsequentes.
Este problema pode ser modelado como o tradicional problema do transporte em grafo bipartido, um problema de programação linear clássico da pesquisa operacional (BRADLEY et al., 1977). Considerando a realocação Rt entre um período genérico t e o
período seguinte t+1, a malha do sistema de ambulâncias do período t pode ser considerada como a oferta por veículos, e a malha do sistema do período t+1 pode ser considerada como a demanda por veículos. Dessa forma, a solução para o problema de realocação de veículos de um tipo k, entre os períodos t e t+1, é equivalente à solução de um problema de transporte cujas mercadorias transportadas são os veículos, as fontes (origens) são as bases que dispõem de veículos do tipo k no período t, e os sumidouros (destinos) são as bases que necessitam de veículos do tipo
k no período t+1. Considerando um par de períodos t e t+1, os custos nos arcos para
esse problema de transporte são iguais aos tempos de deslocamento da matriz de distâncias do problema de localização do período t+1, que é período no qual a realocação ocorrerá para esse par de períodos.
Resolvendo o problema para todos os pares de períodos consecutivos e para todos os tipos de veículos, obtém-se o plano de realocação completo para todos os períodos e tipos de veículo.
Um ponto importante é que não é necessário restringir a capacidade das bases que receberão a realocação do período anterior, pois as condições de viabilidade quanto à capacidade das bases já foram garantidas pela solução do problema de localização de bases e alocação de ambulâncias. Além disso, a quantidade de realocações em um determinado período não foi restrita, como no trabalho de Gendreau et al. (2001). A definição tradicional do problema de transporte considera um conjunto de fontes e suas ofertas por um determinado produto e um conjunto de destinos e suas demandas pelo mesmo produto, definindo um grafo bipartido entre pontos de oferta e pontos de demanda. O problema pode ser definido como: dados os custos unitários de transporte em cada arco do grafo, encontrar o plano de transporte (fluxos nos arcos) que minimize o custo total de transporte. A Figura 4.8 ilustra um exemplo de grafo do problema de transporte. O modelo matemático para esse problema é um problema de programação linear e considera: o conjunto de nós de oferta denominado pela letra I e o conjunto de nós de destino denominado pela letra J, cij o
custo unitário de transporte do arco (i,j), ai a oferta do ponto i, bj a demanda do ponto
j e a variável de decisão xij igual a quantidade de produto transportada no arco (i,j).
F1 F3 F2 S1 S3 S2 S3 Destinos Origens Arcos de Transporte
Figura 4.8 – Representação de um grafo genérico do problema de transporte Fonte: Próprio autor
Problema de Transporte
i j ij ij x c [min] (4.9) Sujeito a:
i j ij b j J x , (4.10)∑
∀∈ j i ij a i I x , (4.11) J j I i xij 0, ;∀∈ (4.12)A função objetivo (4.9) corresponde à minimização do custo total de transporte. As restrições (4.10) garantem que toda a demanda de um determinado sumidouro j seja atendida e as restrições (4.11) certificam que toda a oferta de uma fonte i seja enviada para algum sumidouro. A equação (4.12) é a restrição de não negatividade das variáveis de decisão. Nessa formulação assume-se que o problema seja balanceado, ou seja, a soma das demandas é igual à soma das ofertas.
No caso da realocação das viaturas uma restrição adicional é a integralidade dos fluxos nos arcos do problema de transporte. Todavia, dado que a matriz de coeficientes das restrições do modelo matemático do problema é sempre unimodular, é possível demonstrar que no problema de transporte as variáveis de decisão para a solução ótima do problema apresentam sempre valores inteiros, desde que os valores de demanda e oferta também o sejam (BRADLEY et al., 1977). Na realocação de ambulâncias a demanda e a oferta por viaturas correspondem a números inteiros, o que possibilita a relaxação da restrição de integralidade dos fluxos nos arcos do problema de transporte, utilizando a formulação convencional sem nenhuma alteração.
A solução do problema de transporte está associada a um algoritmo específico chamado Método Simplex para o Problema de Transporte (BRADLEY et al., 1977), o qual resolve o problema garantindo a otimalidade da solução encontrada. Para que o algoritmo funcione o problema deve estar balanceado, isto é, a demanda total deve ser igual a oferta total. Porém, visto que o número de viaturas de ambos os tipos é fixo em todos os períodos, o balanceamento do problema é sempre verificado.
Uma descrição detalhada do problema de transporte e do Método Simplex para o Problema de Transporte podem ser encontrados em Bradley et al. (1977).
Para os fins desta dissertação, foi desenvolvido um procedimento para a solução dos problemas de realocação Rt entre períodos consecutivos para cada tipo de veículo que
corresponde a uma implementação própria do Método Simplex para o Problema de Transporte. Esse procedimento recebe o nome de ALGORITMO_TRANSPORTE e seu desenvolvimento foi feito sem o uso de pacotes comerciais de otimização.
Para a solução do problema é necessário determinar uma solução inicial viável, sendo que existem diversos métodos para encontrar essa solução, como por exemplo: método do canto noroeste, método de Vogel e método do mínimo custo. Referências quanto aos métodos de definição de soluções iniciais para o algoritmo de transporte podem ser encontradas em Hillier e Lieberman (2004), Winston e Venkataramanan (2003) e Bradley et al. (1977). No procedimento ALGORITMO_TRANSPORTE, essa solução inicial é determinada pelo método do canto noroeste.
Bradley et al. (1977) argumentam que o método do canto noroeste é o que, em geral, fornece piores soluções iniciais pois ignora quaisquer informações sobre os custos unitários de transporte, contudo, é o mais simples de ser implementado, visando somente a viabilidade da solução. Para o problema tratado nesta dissertação, o número de problemas de transporte que devem ser resolvidos para uma instância com K tipos de veículos e T períodos de análise é igual a (K.T). Como, em geral, os sistemas de ambulâncias são compostos de dois tipos de veículos e o ciclo de operação dos sistemas é em geral diário ou semanal, resulta que o número de vezes que o problema de transporte deverá ser resolvido é pequeno. Esse fato justificaria a construção de um método mais sofisticado de construção de soluções iniciais para o problema de transporte, contudo, pela sua simplicidade de implementação, optou-se por utilizar como método de construção de solução inicial o método do canto noroeste. Maior detalhamento do método do canto noroeste pode ser encontrado em Hillier e Lieberman (2004).
O resultado da aplicação do ALGORITMO_TRANSPORTE para os K tipos de veículos e T períodos resulta em planos de realocação para os diversos períodos. Esses planos são organizados em (K.T) matrizes Rkt={rijkt}NxN, sendo N o número de pontos de demanda
do problema de localização de bases e de alocação de viaturas a essas bases. Para a matriz Rkt, o elemento rijkt representa a quantidade de veículos do tipo k que devem
ser realocadas no período t+1 do ponto i para o ponto j (a aplicação do procedimento
ALGORITMO_ABC, descrito na seção 4.2.8, garante que os pontos i e j contenham
bases). Esse método de solução resolve o problema de realocação e retorna as matrizes de realocação para os diferentes tipos de veículos em todos os períodos Rkt, k={1,2,...,K} e t={1,2,...,T}. Vale ressaltar que a solução de cada subproblema de
realocação Rt consiste nas matrizes de realocação do período t para cada tipo de
veículo k; no caso em que consideram-se dois tipos de veículos, BLS com k=1 e ALS com k=2, a solução de Rt é dada por R1,t (ou RBLS,t) e R2,t (ou RALS,t).
O procedimento ALGORITMO_TRANSPORTE encontra-se descrito na Figura 4.9 e recebe como parâmetro a solução do algoritmo ABC, mais especificamente a melhor abelha abelha_solucao.
0 ALGORITMO_TRANSPORTE (abelha_solucao)
1 cria as matrizes de transporte Rkt para calcular as soluções
2 para cada tT faça
3 fontes de R(BLS)t = bases de abelha_melhor.bi[] 4 fontes de R(ALS)t = bases de abelha_melhor.bi[] 5 destinos de R(BLS)t = bases de abelha_melhor.bi[]
6 destinos de R(ALS)t = bases de abelha_melhor.bi[] 7 oferta de R(BLS)t = abelha_melhor.BLSi[t][]
8 oferta de R(ALS)t = abelha_melhor.ALSi[t][] 9 demanda de R(BLS)t = abelha_melhor.BLSi[t+1][]
10 demanda de R(ALS)t = abelha_melhor.ALSi[t+1][]
11 gera solução inicial pelo método do canto noroeste para R(BLS)
12 resolve o algoritmo de transporte para R(BLS)t
13 gera solução inicial pelo método do canto noroeste para R(ALS)
14 resolve o algoritmo de transporte para R(ALS)t
15 fim
16 retorna as matrizes Rkt
17 fim
Figura 4.9 – Pseudocódigo para o procedimento ALGORITMO_TRANSPORTE Fonte: Próprio autor