Tempo x Custo
Admita-se, que para o Caso 2 o empreiteiro optou pela solução ali considerada óptima. Para a mesma altura da obra do caso anterior este tem também, prevista a execução do aterro de uma obra ferroviária durante um período igualmente de 5 meses (100 dias ou 800 horas úteis), com as seguintes características:
- divisão em 6 frentes correspondendo a cada uma delas distinto material e respectivo volume (Quadro 5.7);
- exigência por parte da companhia ferroviária em realizar o aterro por camadas com espessura máxima de 0.30 m, e neste caso com uma energia pesada, para qualquer material.
Para este caso, o rendimento médio no universo de soluções possíveis, considerando uma energia pesada é próximo dos 100 m3/h.m.compactador, prevendo-se um número de compactadores necessários em obra (admitindo valores médios para L e k), determinado através da fórmula (5.14), de 16.
O construtor, não possuindo o número de compactadores necessários (apenas lhe sobram 13 compactadores para 16 necessários) obriga-se a recorrer ao aluguer de máquinas, sendo-lhe proposto um conjunto de 10 máquinas o qual ele poderá alugar parcialmente (Quadro 5.8).
Quadro 5.8 Máquinas disponíveis: (a) próprias; (b) para aluguer; (c) no global
(a) (c)
(b)
Nota: L em metros e Custo em €/hora
Face a este cenário, qual o conjunto de máquinas que minimiza o custo no trabalho de compactação?
Como os preços das máquinas alugadas são competitivos face à eficiência das mesmas (L’s e k’s altos) o técnico responsável pelo planeamento fará a escolha do parque de máquinas considerando o universo de 23 compactadores disponíveis, procurando minimizar o custo da compactação respeitando o prazo estabelecido. Dada a maior eficiência das máquinas a alugar, pensa-se ser possível diminuir a dimensão do parque de compactadores (valores médios de L e k recalculados como 1.97 e 0.68, respectivamente). Através da fórmula (5.14) estimam-se necessários 14 compactadores.
Neste caso a procura cega é incomportável em termos computacionais, pelo que recorreu-se apenas aos algoritmos evolucionários.
Numa primeira fase, através do AG procurou encontrar-se uma solução eficiente para referência no processo de avaliação, pois neste caso não é possível conhecer à partida a solução óptima. Tendo em conta a cardinalidade do problema, assumiu-se uma possibilidade de mutação de 100 %, procurando-se por outro lado encontrar uma dimensão adequada para a população de indivíduos. Testaram-se assim, populações com 100, 200, 500 e 1000 indivíduos, concluindo-se na generalidade que o alargamento da
1 - P2: L=2.00; k=0.70; Custo=15.00 2 - P3: L=2.10; k=0.70; Custo=16.50 3 - SP1: L=2.20; k=0.70; Custo=23.20 4 - SP2: L=2.20; k=0.70; Custo=25.20 5 - V3: L=1.80; k=0.75; Custo=18.90 6 - V4: L=1.80; k=0.75; Custo=20.20 7 - V5: L=1.80; k=0.70; Custo=21.20 8 - VP3: L=2.20; k=0.75; Custo=22.50 9 - VP4: L=2.20; k=0.75; Custo=24.20 10 - VP5: L=2.20; k=0.70; Custo=23.00 1 - P1: L=1.50; k=0.65; Custo=11.80 2 - P2: L=1.80; k=0.65; Custo=12.40 3 - P2: L=2.00; k=0.65; Custo=13.90 4 - P3: L=2.00; k=0.60; Custo=14.70 5 - SP1: L=2.00; k=0.70; Custo=19.30 6 - SP2: L=2.20; k=0.60; Custo=22.60 7 - SP2: L=2.20; k=0.65; Custo=23.00 8 - V2: L=1.50; k=0.65; Custo=15.70 9 - V3: L=1.60; k=0.70; Custo=16.40 10 - V4: L=1.60; k=0.60; Custo=19.30 11 - VP2: L=2.00; k=0.65; Custo=19.40 12 - VP4: L=2.20; k=0.65; Custo=21.50 13 - VP4: L=2.20; k=0.70; Custo=21.90
população não traz benefícios significativos, aumentando por outro lado o esforço computacional.
No Quadro 5.9 mostra-se a melhor solução obtida com o AG, com uma população de 100 indivíduos, ao fim 11 minutos. Esta solução, que por certo não respeita o prazo estabelecido, poderia no entanto ser adoptada sem grandes transtornos recorrendo a 47 horas extraordinárias.
Quadro 5.9 Melhor solução obtida com o AG (solução de referência)
Parque de compactadores* P2 1 (2) P2 2 (3) P3 2 (6) SP2 1 (9) SP2 3 (11) V2 (12) V4 1 (15) V4 2 (16) V5 (17) VP2 (18) VP4 1 (20) VP4 2 (21) VP4 3 (22) VP5 (23) Rendimento global (m3/h)
Tempo de trabalho global (h) Tempo x Custo horário global (€)
* Cada compactador identifica-se pela sua classe, pelo seu índice de repetição, e entre parêntesis pela numeração do Quadro 5.8c 1772.76 846.14 234380.66 R1 3760.60 R1 R3 2583.65 R3 66.48 R1 18414.61 58.06 R3 16081.90 208.26
Tempo x Custo horário sobre os materiais (€)
A1 A2 B6 C2A2
47940.46 44499.78 49756.61 57687.30 1391.78 1440.53 Tempo de trabalho sobre os materiais
(h)
A1 A2 B6 C2A2
173.07 160.65 179.63
Rendimento sobre os materiais (m3/h) A1 A2 B6 C2A2
2022.30 1244.95
A utilização da EE neste caso permitiu obter resultados superiores aos conseguidos com o AG. A melhor solução obtida com a EE (Quadro 5.10) permitiria uma economia de 8.9 % relativamente à melhor solução determinada pelo AG. A EE gera soluções com um desempenho médio superior ao da melhor solução obtida com o AG.
Quadro 5.10 Solução mais económica gerada pela EE
Parque de compactadores* P3 1 (5) P3 2 (6) SP2 1 (9) SP2 2 (10) V2 (12) V3 1 (13) V3 2 (14) V4 1 (15) V4 2 (16) V5 (17) VP4 1 (20) VP4 2 (21) VP4 3 (22) VP5 (23) Rendimento global (m3/h)
Tempo de trabalho global (h) Tempo x Custo horário global (€)
* Cada compactador identifica-se pela sua classe, pelo seu índice de repetição, e entre parêntesis pela numeração do Quadro 5.8c
C2A2 R1 R3
38765.43 37590.49 50133.82 58124.64 16460.64 14137.13 Tempo x Custo horário sobre os
materiais (€)
A1 A2 B6
179.63 208.26 58.98 50.65 2961.35 Tempo de trabalho sobre os materiais
(h) A1 A2 B6 C2A2 R1 R3 138.89 134.68 1945.29 771.09 215212.20
Rendimento sobre os materiais (m3/h) A1 A2 B6 C2A2 R1 R3
2519.90 1484.95 1391.78 1440.53 4238.90
No Quadro 5.11 resumem-se os resultados obtidos com os dois algoritmos evolucionários, em dez experiências para cada. Para o AG admitiu-se uma possibilidade de mutação unitária e uma população de 100 indivíduos evoluindo durante um máximo de 100 gerações. Para a EE adoptou-se um parâmetro com valor igual a 0.005.
Quadro 5.11 Comparação de desempenhos entre AEs
AG EE T*C (€) 245858.61 ± 9453.50 (234380.66) 215641.42 ± 515.00 (215212.20) %REF 104.90 ± 4.03 (100.00) 92.00 ± 0.22 (91.82) T (h) 922.96 ± 40.24 (846.14) 770.95 ± 1.34 (767.99*) TP (s) 881.50 ± 454.56 (113.89*) 148.89 ± 11.60 (133.14*) VCR (€) E (€) -22139.70 ± 9453.50 (-10661.75) 8077.49 ± 515.00 (8506.71) * Obtido para uma solução que não é a melhor determinada pelo algoritmo de procura
** Calculado através da estratégia evolutiva em 10 experiências T*C: Valor da função objectivo (Tempo x Custo)
%REF: Percentagem do (Tempo x Custo) de referência T: Tempo de compactação
TP: Tempo dispendido na procura
VCR: Valor da função objectivo adoptando apenas um critério de Rendimento E: Economia permitida pelo critério de Tempo x Custo
Nesta ocasião, observa-se que o AG verifica dificuldades na convergência, enquanto que a EE encontra sempre uma boa solução (Figura 5.10). No caso do AG, a sua forma de convergir lenta e esporádica dever-se-á sobretudo à necessidade de serem produzidas combinações sem repetições de compactadores na população de indivíduos, o que pode ser mais complicado face a cromossomas de maior tamanho e gerados de um espaço amplo de “alelos”. Por outro lado, para a EE o cromossoma inicial é gerado de forma probabilística, com base nos desempenhos individuais dos compactadores, e com a garantia de não existirem repetições. Como neste caso a função objectivo é cumulativa dos desempenhos individuais dos compactadores, a EE gera soluções (conjuntos de compactadores) com maiores aptidões.
(a) (b)
Figura 5.10 Evolução típica da EE (a) e do AG (b)
5.5 Conclusões
A consideração do critério de minimização de Tempo x Custo permite obter soluções mais económicas do que aquelas obtidas com uma heurística simples baseada no Rendimento. Por outro lado, para o caso em que se utiliza o critério de minimização da diferença Prazo – Tempo interessará obter uma solução, a qual respeitando uma margem de erro relativamente ao prazo pretendido, permita um valor de Tempo x Custo mais reduzido.
A optimização com procura “cega” é feita procurando soluções exaustivamente em todo o universo possível, pelo que é infalível. Esta estratégia será no entanto inviável em problemas de alta cardinalidade, pois os recursos computacionais (memória e tempo de processamento) requeridos são impraticáveis nestes casos. Para estes problemas aparecem como ferramentas privilegiadas os algoritmos evolucionários.
A estratégia evolutiva utilizada, encontrando rapidamente uma solução, pode ser vista como uma máquina de procura a “curto prazo”. Embora não encontrando, por regra, a solução óptima, o binómio de desempenho “tempo de procura aproximação ao valor da função objectivo” introduz esta estratégia de pesquisa como um artefacto para obter uma boa primeira aproximação.
O algoritmo genético revela uma grande flexibilidade, adaptando-se a distintos cenários. Este mostra um elevado desempenho nos casos mais simples, perdendo no entanto eficiência à medida que se introduzem restrições, como se sentiu particularmente nos cenários com frentes simultâneas. Para estes casos as soluções
obtidas não são sequer válidas, pelo que não se mostrou qualquer exemplo. Nestes problemas mais complexos pensa-se, que a solução passará por adoptar uma formulação que lide melhor com as restrições, por exemplo a optimização multi-objectivo.
A avaliação das metodologias de optimização adoptadas no presente contexto passará também pela experimentação com casos reais de obras.
Finalizando, a técnica de optimização, embora desde já há muito tempo utilizada, encontra na computação evolutiva um caminho a percorrer rumo a futuros desenvolvimentos e aplicações.