( PDF ) Algoritmo genético aplicado à otimização multiobjetivo em redes de distribuição de petróleos e derivados

Download PDF

ads:

UNIVERSIDADE TECNOLÓGICA FEDERAL DO PARANÁ

Programa de Pós-Graduação em Engenharia Elétrica e Informática Industrial

DISSERTAÇÃO

apresentada à UTFPR

para obtenção do grau de

MESTRE EM CIÊNCIAS

por

HENRIQUE WESTPHAL

ALGORITMO GENÉTICO APLICADO À OTIMIZAÇÃO

MULTIOBJETIVO EM REDES DE DISTRIBUIÇÃO DE PETRÓLEOS E

DERIVADOS

Banca Examinadora:

Presidente e Orientador:

Prof

. Dr

. Lúcia Valéria Ramos de Arruda UTFPR

Examinadores:

Prof

. Dr

. Elizabeth Ferreira Gouvêa Goldbarg UFRN

Prof. Dr. Flávio Neves Junior UTFPR

Prof. Dr. Sérgio Leandro Stebel UTFPR

Curitiba, Dezembro de 2006.

ads:

Livros Grátis

http://www.livrosgratis.com.br

Milhares de livros grátis para download.

ads:

HENRIQUE WESTPHAL

ALGORITMO GENÉTICO APLICADO À OTIMIZAÇÃO

MULTIOBJETIVO EM REDES DE DISTRIBUIÇÀO DE PETRÓLEOS E

DERIVADOS

Dissertação apresentada ao Programa de Pós-

Graduação em Engenharia Elétrica e Informática

Industrial da Universidade Tecnológica Federal do

Paraná, como requisito parcial para a obtenção do

grau de “Mestre em Ciências” – Área de

Concentração: Informática Industrial.

Orientador: Profa. Dra. Lúcia Valéria R. de Arruda

Curitiba

2006

iii

AGRADECIMENTOS

Gostaria de agradecer a todos aqueles que de alguma forma contribuíram para que

este trabalho se tornasse possível.

À Prof

. Dr

. Lúcia Valéria Ramos de Arruda pela oportunidade e pela orientação.

A todos os colegas do laboratório LASCA em especial aos colegas Elder Oroski e

Luiz Carlos Felizari.

Agradeço a minha mãe, Maria Terezinha Westphal, que me apoiou em todos os

momentos, e a todos os familiares que de alguma forma contribuíram para o sucesso deste

trabalho.

SUMÁRIO

LISTA DE FIGURAS.......................................................................................................................VII

LISTA DE TABELAS........................................................................................................................IX

NOMENCLATURA...........................................................................................................................XI

RESUMO ..........................................................................................................................................XII

ABSTRACT.....................................................................................................................................XIII

CAPÍTULO 1........................................................................................................................................1

INTRODUÇÃO ....................................................................................................................................1

1.1 COMPUTAÇÃO EVOLUTIVA ...................................................................................................... 1

1.2 MOTIVAÇÃO E OBJETIVO ......................................................................................................... 2

1.3 ORGANIZAÇÃO DA DISSERTAÇÃO ...............................................................................3

CAPÍTULO 2........................................................................................................................................5

2 ESTADO DA ARTE......................................................................................................................5

2.1 INTRODUÇÃO .......................................................................................................................... 5

2.2 DEFINIÇÃO DE SCHEDULING ...................................................................................................6

2.2.1 Scheduling em refinaria ................................................................................................... 7

2.2.2 Benefícios ......................................................................................................................... 9

2.2.3 Complexibilidade do Scheduling.................................................................................... 10

2.2.4 Métodos de Solução para Scheduling ............................................................................ 11

2.2.5 Simulação.......................................................................................................................12

2.2.6 Otimização ..................................................................................................................... 13

2.3 CONSIDERAÇÕES FINAIS ............................................................................................... 19

CAPÍTULO 3......................................................................................................................................21

3 FUNDAMENTAÇÃO TEÓRICA..............................................................................................21

3.1 ALGORITMOS GENÉTICOS ..................................................................................................... 21

3.1.1 Nomenclatura................................................................................................................. 23

3.1.2 Representação ................................................................................................................ 24

3.1.3 Operadores Genéticos.................................................................................................... 25

3.1.4 Processo evolutivo.......................................................................................................... 31

3.2 ALGORITMOS GENÉTICOS APLICADOS À OTIMIZAÇÃO MULTIOBJETIVO............................... 32

3.2.1 Métodos de solução em programação multiobjetivo...................................................... 35

3.2.2 Tratamento das Restrições ............................................................................................. 38

3.3 CONSIDERAÇÕES FINAIS........................................................................................................ 38

CAPÍTULO 4......................................................................................................................................39

4 MODELAGEM............................................................................................................................39

4.1 O PROBLEMA ........................................................................................................................ 39

4.2 MODELO DA REDE DE DISTRIBUIÇÃO DE PETRÓLEO .............................................................. 40

4.2.1 Representação do modelo .............................................................................................. 42

4.2.2 Geração da População Inicial ....................................................................................... 46

4.2.3 Operadores genéticos..................................................................................................... 47

4.3 OTIMIZAÇÃO MULTIOBJETIVO............................................................................................... 50

4.3.1 Restrições ....................................................................................................................... 51

4.3.2 Função objetivo.............................................................................................................. 54

CAPÍTULO 5......................................................................................................................................61

5 RESULTADOS OBTIDOS.........................................................................................................61

5.1 VALIDAÇÃO DO MODELO ......................................................................................................62

5.2 ESTUDOS DE CASOS ............................................................................................................... 70

5.2.1 Estudo de caso 1............................................................................................................. 71

5.2.2 Estudo de caso 2............................................................................................................. 78

5.2.3 Estudo de caso 3............................................................................................................. 85

5.2.4 Estudo de caso 4............................................................................................................. 94

CAPÍTULO 6....................................................................................................................................104

6 CONCLUSÃO............................................................................................................................104

6.1 COMENTÁRIOS FINAIS.................................................................................................104

6.2 TRABALHOS FUTUROS.................................................................................................106

REFERÊNCIAS BIBLIOGRÁFICAS............................................................................................107

vii

LISTA DE FIGURAS

FIGURA 3-1: PROCEDIMENTO BÁSICO PARA UM AG............................................................................................... 22

FIGURA 3-2: RECOMBINAÇÃO PONTO ÚNICO.......................................................................................................... 26

FIGURA 3-3: RECOMBINAÇÃO MULTIPONTO........................................................................................................... 27

FIGURA 3-4: RECOMBINAÇÃO UNIFORME............................................................................................................... 27

FIGURA 3-5: EXEMPLO DE MUTAÇÃO ..................................................................................................................... 28

FIGURA 4-1: REDE DE ESCUROS (FONTE: PETROBRAS) .................................................................................... 39

FIGURA 4-2: REDE PROPOSTA ................................................................................................................................41

FIGURA 4-3: MATRIZ DE CODIFICAÇÃO.................................................................................................................. 43

FIGURA 4-4: VETOR DE CODIFICAÇÃO.................................................................................................................... 43

FIGURA 4-5: SOLUÇÃO CODIFICADA....................................................................................................................... 45

FIGURA 4-6: SOLUÇÃO DECODIFICADA .................................................................................................................. 45

FIGURA 4-7: ALGORITMO PARA GERAÇÃO DA POPULAÇÃO INICIAL ....................................................................... 46

FIGURA 4-8: ALGORITMO PARA RECOMBINAÇÃO PONTO ÚNICO............................................................................. 47

FIGURA 4-9: ALGORITMO PARA MUTAÇÃO............................................................................................................. 48

FIGURA 4-10: CONSTRUÇÃO DAS CASTAS (SWIECH,2005)................................................................................... 49

FIGURA 4-11: EXEMPLO DE REPARAÇÃO PARA RESTRIÇÃO R4............................................................................... 53

FIGURA 4-12: REPARAÇÃO DA DISTÂNCIA. (A) ANTES DA REPARAÇÃO, (B) DEPOIS DA REPARAÇÃO...................... 54

FIGURA 4-13: DIAGRAMA DO ALGORITMO PARA OTIMIZAÇÃO MULTIOBJETIVO..................................................... 60

FIGURA 5-1: DISTRIBUIÇÃO DOS PRODUTOS DO MELHOR INDIVÍDUO AO LONGO DAS CONEXÕES ........................... 65

FIGURA 5-2: EVOLUÇÃO DO FITNESS DO MELHOR INDIVÍDUO ................................................................................. 67

FIGURA 5-3: EVOLUÇÃO DO DESEMPENHO DO CRITÉRIO DE DEMANDA DE RECEBIMENTO...................................... 67

FIGURA 5-4: EVOLUÇÃO DO DESEMPENHO DO CRITÉRIO DE DEMANDA DE FORNECIMENTO ................................... 68

FIGURA 5-5: EVOLUÇÃO DO DESEMPENHO DO CRITÉRIO DE MINIMIZAÇÃO DO TEMPO ........................................... 68

FIGURA 5-6: EVOLUÇÃO DO DESEMPENHO DO CRITÉRIO DE MINIMIZAÇÃO DA FRAGMENTAÇÃO............................ 68

FIGURA 5-7: SOLUÇÃO DE PARETO PARA O INDIVÍDUO 7 ....................................................................................... 70

FIGURA 5-8: DISTRIBUIÇÃO DOS PRODUTOS DO MELHOR INDIVÍDUO AO LONGO DAS CONEXÕES ........................... 74

FIGURA 5-9: EVOLUÇÃO DO FITNESS DO MELHOR INDIVÍDUO ................................................................................. 76

FIGURA 5-10: EVOLUÇÃO DO DESEMPENHO DO CRITÉRIO DE DEMANDA DE RECEBIMENTO.................................... 76

FIGURA 5-11: EVOLUÇÃO DO DESEMPENHO DO CRITÉRIO DE DEMANDA DE FORNECIMENTO ................................. 77

FIGURA 5-12: EVOLUÇÃO DO DESEMPENHO DO CRITÉRIO DE MINIMIZAÇÃO DO TEMPO ......................................... 77

FIGURA 5-13: EVOLUÇÃO DO DESEMPENHO DO CRITÉRIO DE MINIMIZAÇÃO DA FRAGMENTAÇÃO.......................... 77

FIGURA 5-14: DISTRIBUIÇÃO DOS PRODUTOS DO MELHOR INDIVÍDUO AO LOGO DAS CONEXÕES............................ 80

FIGURA 5-15: EVOLUÇÃO DO FITNESS DO MELHOR INDIVÍDUO............................................................................... 82

FIGURA 5-16: EVOLUÇÃO DO DESEMPENHO DO CRITÉRIO DE DEMANDA DE RECEBIMENTO.................................... 83

FIGURA 5-17: EVOLUÇÃO DO DESEMPENHO DO CRITÉRIO DE DEMANDA DE FORNECIMENTO ................................. 83

FIGURA 5-18: EVOLUÇÃO DO DESEMPENHO DO CRITÉRIO DE MINIMIZAÇÃO DO TEMPO ......................................... 83

viii

FIGURA 5-19: EVOLUÇÃO DO DESEMPENHO DO CRITÉRIO DE MINIMIZAÇÃO DA FRAGMENTAÇÃO.......................... 84

FIGURA 5-20: SOLUÇÃO DE PARETO PARA O INDIVÍDUO 16 ................................................................................... 85

FIGURA 5-21: DISTRIBUIÇÃO DOS PRODUTOS DO MELHOR INDIVÍDUO AO LOGO DAS CONEXÕES............................ 89

FIGURA 5-22: EVOLUÇÃO DO FITNESS DO MELHOR INDIVÍDUO............................................................................... 91

FIGURA 5-23: EVOLUÇÃO DO DESEMPENHO DO CRITÉRIO DE DEMANDA DE RECEBIMENTO.................................... 91

FIGURA 5-24: EVOLUÇÃO DO DESEMPENHO DO CRITÉRIO DE DEMANDA DE FORNECIMENTO ................................. 92

FIGURA 5-25: EVOLUÇÃO DO DESEMPENHO DO CRITÉRIO DE MINIMIZAÇÃO DO TEMPO ......................................... 92

FIGURA 5-26: EVOLUÇÃO DO DESEMPENHO DO CRITÉRIO DE MINIMIZAÇÃO DA FRAGMENTAÇÃO.......................... 92

FIGURA 5-27: SOLUÇÃO DE PARETO PARA O INDIVÍDUO 2 ..................................................................................... 94

FIGURA 5-28: DISTRIBUIÇÃO DOS PRODUTOS DO MELHOR INDIVÍDUO AO LOGO DAS CONEXÕES............................ 98

FIGURA 5-29: EVOLUÇÃO DO FITNESS DO MELHOR INDIVÍDUO............................................................................. 100

FIGURA 5-30: EVOLUÇÃO DO DESEMPENHO DO CRITÉRIO DE DEMANDA DE RECEBIMENTO.................................. 101

FIGURA 5-31: EVOLUÇÃO DO DESEMPENHO DO CRITÉRIO DE DEMANDA DE FORNECIMENTO ............................... 101

FIGURA 5-32: EVOLUÇÃO DO DESEMPENHO DO CRITÉRIO DE MINIMIZAÇÃO DO TEMPO ....................................... 101

FIGURA 5-33: EVOLUÇÃO DO DESEMPENHO DO CRITÉRIO DE MINIMIZAÇÃO DA FRAGMENTAÇÃO........................ 102

FIGURA 5-34: SOLUÇÃO DE PARETO PARA O INDIVÍDUO 5 ................................................................................... 103

LISTA DE TABELAS

TABELA 2-1: SITE DAS PRINCIPAIS EMPRESAS NA ÁREA DE SCHEDULING................................................................ 19

TABELA 3-1: REPRESENTAÇÃO BINÁRIA ................................................................................................................25

TABELA 4-1: DISTÂNCIA ENTRE AS CONEXÕES ...................................................................................................... 42

TABELA 4-2: MATRIZ DE DECODIFICAÇÃO ............................................................................................................. 44

TABELA 4-3: MATRIZ DE CONEXÃO ....................................................................................................................... 45

TABELA 4-4: DESCRIÇÃO DOS PARÂMETROS DO MODELO AG ............................................................................... 46

TABELA 4-5: MÁSCARA DE CODIFICAÇÃO DE PRODUTOS ....................................................................................... 46

TABELA 4-6: DISTRIBUIÇÃO DAS CASTAS (SWIECH,2005)................................................................................... 49

TABELA 4-7: RELAÇÃO DE PARÂMETRO PARA OTIMIZAÇÃO DO MODELO............................................................... 51

TABELA 5-1: DISTÂNCIAS EM UNIDADES DE TEMPO DAS CONEXÕES ...................................................................... 61

TABELA 5-2: PARÂMETROS DO AG........................................................................................................................ 62

TABELA 5-3: PRODUTOS PRODUZIDOS ................................................................................................................... 63

TABELA 5-4: DEMANDA DE RECEBIMENTO ............................................................................................................ 63

TABELA 5-5: DEMANDA DE FORNECIMENTO .......................................................................................................... 63

TABELA 5-6: PONDERAÇÃO PARA OS CRITÉRIOS GLOBAIS...................................................................................... 64

TABELA 5-7: ESTADO INICIAL DOS TANQUES .........................................................................................................64

TABELA 5-8: ESTADO FINAL DOS TANQUES............................................................................................................ 65

TABELA 5-9: VALOR GLOBAL DOS OBJETIVOS........................................................................................................ 66

TABELA 5-10: DESEMPENHO DOS OBJETIVOS DAS SOLUÇÕES DE PARETO.............................................................. 69

TABELA 5-11: PRODUTOS PRODUZIDOS ................................................................................................................. 71

TABELA 5-12: DEMANDA DE RECEBIMENTO .......................................................................................................... 72

TABELA 5-13: DEMANDA DE FORNECIMENTO ........................................................................................................ 72

TABELA 5-14: PONDERAÇÃO PARA OS CRITÉRIOS GLOBAIS.................................................................................... 72

TABELA 5-15: PESO ASSOCIADO À MINIMIZAÇÃO DO TEMPO.................................................................................. 73

TABELA 5-16: ESTADO INICIAL DOS TANQUES ....................................................................................................... 73

TABELA 5-17: ESTADO FINAL DOS TANQUES..........................................................................................................74

TABELA 5-18: DESEMPENHO GLOBAL DOS OBJETIVOS ........................................................................................... 75

TABELA 5-19: DESEMPENHO DOS OBJETIVOS PARA A MINIMIZAÇÃO DO TEMPO POR PRODUTO .............................. 75

TABELA 5-20: PRODUTOS PRODUZIDOS ................................................................................................................. 78

TABELA 5-21: DEMANDA DE RECEBIMENTO .......................................................................................................... 78

TABELA 5-22: DEMANDA DE FORNECIMENTO ........................................................................................................ 79

TABELA 5-23: PONDERAÇÃO PARA OS CRITÉRIOS GLOBAIS.................................................................................... 79

TABELA 5-24: PESO ASSOCIADO À DEMANDA DE RECEBIMENTO POR NÓ................................................................ 79

TABELA 5-25: ESTADO INICIAL DOS TANQUES ....................................................................................................... 80

TABELA 5-26: ESTADO FINAL DOS TANQUES..........................................................................................................81

TABELA 5-27: DESEMPENHO GLOBAL DOS OBJETIVOS ........................................................................................... 81

TABELA 5-28: DESEMPENHO DOS OBJETIVOS DE DEMANDA DE RECEBIMENTO POR NÓ .......................................... 82

TABELA 5-29: DESEMPENHO DOS OBJETIVOS GLOBAIS DAS SOLUÇÕES DE PARETO ............................................... 84

TABELA 5-30: DESEMPENHO DOS OBJETIVOS DE DEMANDA DE RECEBIMENTO POR NÓ DAS SOLUÇÕES DE PARETO85

TABELA 5-31: PRODUTOS PRODUZIDOS ................................................................................................................. 86

TABELA 5-32: DEMANDA DE RECEBIMENTO .......................................................................................................... 86

TABELA 5-33: DEMANDA DE FORNECIMENTO ........................................................................................................ 86

TABELA 5-34: PONDERAÇÃO PARA OS CRITÉRIOS GLOBAIS.................................................................................... 87

TABELA 5-35: PESO ASSOCIADO À DEMANDA DE RECEBIMENTO POR PRODUTO .....................................................87

TABELA 5-36: PESO ASSOCIADO À DEMANDA DE RECEBIMENTO POR NÓ................................................................ 88

TABELA 5-37: ESTADO INICIAL DOS TANQUES ....................................................................................................... 88

TABELA 5-38: ESTADO FINAL DOS TANQUES..........................................................................................................89

TABELA 5-39: DESEMPENHO GLOBAL DOS OBJETIVOS ........................................................................................... 90

TABELA 5-40: DESEMPENHO DOS OBJETIVOS PARA DEMANDA DE RECEBIMENTO POR PRODUTO ........................... 90

TABELA 5-41: DESEMPENHO DOS OBJETIVOS PARA DEMANDA DE RECEBIMENTO POR NÓ...................................... 90

TABELA 5-42: DESEMPENHO DOS OBJETIVOS GLOBAIS DAS SOLUÇÕES DE PARETO ............................................... 93

TABELA 5-43: DESEMPENHO DOS OBJETIVOS POR NÓ DAS SOLUÇÕES DE PARETO PARA DEMANDA DE RECEBIMENTO

..................................................................................................................................................................... 93

TABELA 5-44: PRODUTOS PRODUZIDOS ................................................................................................................. 94

TABELA 5-45: DEMANDA DE RECEBIMENTO .......................................................................................................... 95

TABELA 5-46: DEMANDA DE FORNECIMENTO ........................................................................................................ 95

TABELA 5-47: PONDERAÇÃO PARA OS CRITÉRIOS GLOBAIS.................................................................................... 95

TABELA 5-48: PESO ASSOCIADO À DEMANDA DE RECEBIMENTO POR NÓ................................................................ 96

TABELA 5-49: PESO ASSOCIADO À DEMANDA DE RECEBIMENTO POR PRODUTO .....................................................96

TABELA 5-50: PESO ASSOCIADO À MINIMIZAÇÃO DO TEMPO POR PRODUTO........................................................... 97

TABELA 5-51: ESTADO INICIAL DOS TANQUES ....................................................................................................... 97

TABELA 5-52: ESTADO FINAL DOS TANQUES..........................................................................................................98

TABELA 5-53: DESEMPENHO GLOBAL DOS OBJETIVOS ........................................................................................... 99

TABELA 5-54: DESEMPENHO DOS OBJETIVOS DE DEMANDA DE RECEBIMENTO POR NÓ .......................................... 99

TABELA 5-55: DESEMPENHO PARA A DEMANDA DE RECEBIMENTO POR PRODUTO .................................................99

TABELA 5-56: DESEMPENHO PARA A MINIMIZAÇÃO DO TEMPO POR PRODUTO.....................................................100

TABELA 5-57: DESEMPENHO DOS OBJETIVOS GLOBAIS DAS SOLUÇÕES DE PARETO ............................................. 102

NOMENCLATURA

ABREVIAÇÕES:

AG Algoritmo Genético

AGs Algoritmos Genéticos

MILP Programação Linear Inteira Mista

MILNP Programação Não-Linear Inteira Mista

xii

RESUMO

Neste trabalho, um problema de distribuição de derivados de petróleo através de uma

rede de dutos é modelado. A rede estudada é uma simplificação de uma rede real. A

arquitetura adotada é composta por duas fontes, dois nós intermediários que representam

pontos de recebimento ou entrega de produtos e três terminais. Uma conexão bidirecional é

introduzida para conectar os dois nós intermediários. Isso significa que um produto pode fluir

em ambas as direções. Cada fonte comunica-se com os nós intermediários por uma conexão.

Os nós intermediários podem comunicar-se com os terminais através de várias conexões.

A principal meta do cenário estudado é satisfazer a demanda de produtos em cada

ponto de destino no devido tempo. Outra importante meta é garantir que uma produção

mínima seja enviada de ambas as fontes. Um conjunto de restrições deve ser levado em

consideração, como a capacidade máxima e mínima de armazenagem dos tanques, evitar

colisões na conexão bidirecional entre outras. Algumas destas restrições são consideradas

como objetivos de otimização caracterizando um problema de otimização multiobjetivo.

Outras restrições são avaliadas através de uma função reparadora, proposta para evitar

soluções infactíveis. Propõe-se a utilização de um modelo baseado em algoritmos genéticos

com elitismo para a solução do problema

Uma das maiores dificuldades em otimização multiobjetivo baseada em AGs é a

busca por boas soluções mas que não são ótimos ao longo de todos os critérios. Neste

trabalho, combinou-se AG como método de solução a uma estratégia de elitismo baseada em

castas em que um grupo das melhores soluções são mantidas geração a geração. Esta

estratégia evita que um bom indivíduo seja perdido em uma operação genética mal sucedida.

Em cada geração, a população é ordenada e os melhores indivíduos são mantidos em um

grupo a parte sem repetições de solução.

O método do critério global é usado para avaliar cada indivíduo. Em uma rede

normalizada, o valor da solução ideal é usado para calcular o desempenho de um indivíduo

para cada critério, e então uma função objetivo única é formulada. Uma aproximação do

método da ponderação de objetivos é usada para gerar prioridades dentre os critérios de

otimização e para gerar um conjunto de soluções não dominadas.

xiii

ABSTRACT

In this paper, a problem of distribution of petroleum products through pipelines

networks is proposed. It considers a simplified model of a real network. The network is

composed by two sources, two intermediate connection that actuate as receiving or delivering

points with storage capacity and three terminals. A bidirectional connection is introduced to

connect the two intermediates nodes; it means that a fluid can flow in both directions. Each

source can achieve the intermediate nodes by one connection. The intermediate nodes can

achieve the terminals by several connections.

The main goal is to satisfy the demanded products at the destination points in due

time, but another important goal is to assure the minimal production delivery from both

sources. Moreover, a number of constraints must be satisfied, as the limit in storage capacity

of the tanks, avoid collisions in the bidirectional connection and so on. Several objective

functions are defined to express these goals. Some constraints are included into the model as

hard objective functions. Other constraints are evaluated through a repairing function,

proposed, to avoid infeasible solutions. This is a combinatorial problem and very suitable to

model by GA.

One of the major difficulties of GA-based search in multiobjective optimization

regards points that are good but not excellent along any criterion. If the rationale of Pareto

optimality is accepted, all locally non-dominated individuals should have the same

reproductive potential. Moreover, niche and speciation methods may be useful for stabilizing

the multiple subpopulations that arise along the Pareto-optimal front, thereby preventing

excessive competition among distant population members. In this work, it was used an elitism

strategy where a group (niche) of the best solutions are kept generation by generation. This

strategy avoids to loose good solutions during the evaluation. Each generation, the population

is ordered by fitness and the best solutions are kept in a group without solutions repetition.

The Global Criterion Method is used to calculate the fitness. In a normalized network,

an ideal solution is used to calculate the fitness of each objective and then a single objective

criterion is formulated. An approaching of Weighing Objectives Method is used to generate a

set of non-dominated solutions.

xiv

CAPÍTULO 1

INTRODUÇÃO

1.1 COMPUTAÇÃO EVOLUTIVA

Atualmente os conceitos de computação evolutiva têm sido empregados em uma

variedade de disciplinas, desde ciências naturais e engenharia até biologia e ciência da

computação. A idéia básica, surgida nos anos 50, é aplicar o processo de evolução natural

como um paradigma de solução de problemas, a partir de sua implementação em computador.

Os problemas de otimização são os que mais tem se beneficiado com o uso de técnicas de

computação evolutiva, razão pela qual serão adotados como exemplos e pontos de partida

para a descrição e formalização dos conceitos e técnicas de computação evolutiva aqui

apresentadas. Além disso, muitos problemas de engenharia podem ser adequadamente

apresentados como problemas de otimização (MICHALEWICZ & FOGEL, 2000), garantindo

que o escopo de abordagem se mantenha muito amplo.

A vantagem mais significativa da computação evolutiva está na possibilidade de

resolver problemas pela simples descrição matemática do que se quer ver presente na solução,

não havendo necessidade de se indicar explicitamente os passos até o resultado, que

certamente seriam específicos para cada caso. É claro que os algoritmos evolutivos

correspondem a uma seqüência de passos até a solução, mas estes passos são os mesmos para

uma ampla gama de problemas, fornecendo robustez e flexibilidade a técnica. Sendo assim, a

computação evolutiva deve ser entendida como um conjunto de técnicas e procedimentos

genéricos e adaptáveis, a serem aplicados na solução de problemas complexos, para os quais

outras técnicas conhecidas são ineficazes ou dificilmente aplicáveis. Trata-se de um novo

paradigma de solução de problemas, pois se abre mão da garantia de obtenção da solução

ótima para se conquistar boas soluções via uma ferramenta de propósito geral e de

complexidade menor. Novos paradigmas afloram sempre que condições propícias para tal

passam a vigorar, e no caso da computação evolutiva a condição primordial é a

disponibilidade de uma grande quantidade de recursos computacionais.

INTRODUÇÃO

1.2 MOTIVAÇÃO E OBJETIVO

O propósito principal da programação da produção em refinarias é coordenar as

operações de uma refinaria com seus objetivos de produção, de modo a otimizar a

lucratividade do sistema de processamento ou a minimizar os seus custos. Vários são os

fatores a serem considerados nas diretrizes de produção: alterações nas demandas,

especificações dos produtos, datas de entrega, qualidade e quantidade das matérias primas,

disponibilidade e desempenho das unidades de processo são alguns deles. Integrada

fortemente a estratégias de planejamento, a atividade de programação da produção deve ser

desenvolvida de maneira otimizada. Neste contexto, os principais fatores associados

envolvem desde o suprimento de matéria prima até os sistemas de informação de mercado de

produtos, passando pela operação da planta e gerenciamento ótimo dos recursos disponíveis.

As atividades e operações associadas a uma refinaria são caracterizadas pela

necessidade de uma quantidade significativa de tomadas de decisão em uma base diária. Estas

atividades tratam normalmente situações que combinam operações contínuas com a

determinação de alocação de recursos (equipamentos, insumos e tempos de processamento)

para as várias tarefas envolvidas na produção (SHAH, PANTELIDES e SARGENT, 1993).

Uma rede de distribuição de petróleo é composta por refinarias, terminais e/ou

parque de armazenagem, interligados por um conjunto de oleodutos, nos quais operam o

transporte de petróleo e derivados entre áreas adjacentes. O transporte destes produtos é

motivado pelo cumprimento de uma demanda de mercado e/ou uma demanda de estoque e/ou

por uma demanda de fornecimento de uma produção mínima ou por qualquer outro motivo

operacional. Para a otimização da operação desta rede será usada uma metodologia de

computação evolutiva conhecida por Algoritmo Genético.

Uma justificativa para a utilização de AG neste tipo de problema é:

• A capacidade do AG em lidar com problemas para os quais não é possível ou é

muito custoso obter uma descrição detalhada, ou ainda junto ao qual não é

possível impor restrições muito fortes, ambas condições necessárias para a

aplicação de ferramentas de solução dedicadas e, portanto, mais eficientes.

INTRODUÇÃO

• A possibilidade de recorrer a técnicas de solução adaptativas, ou seja, capazes de

manter o desempenho mesmo quando o ambiente é não-estacionário, ou seja,

quando o problema está sujeito a pequenas variações em suas especificações: não

é necessário reiniciar todo o processo de busca de uma solução frente a pequenas

mudanças nas especificações do problema, já que refinamentos podem ser

obtidos a partir das soluções atuais;

• A capacidade de gerar soluções suficientemente boas em um tempo

suficientemente rápido junto a problemas de elevada complexidade. Algoritmos

evolutivos são capazes de fornecer boas soluções, não necessariamente ótimas,

requerendo uma quantidade aceitável de recursos computacionais;

1.3 ORGANIZAÇÃO DA DISSERTAÇÃO

Este trabalho aborda o desenvolvimento de técnicas de otimização para problemas de

escalonamento em uma malha de oleodutos. Investiga um modelo simplificado, de uma rede

real de distribuição de petróleo e seus derivados e elabora um método de solução baseado em

algoritmos genéticos, levando em conta restrições e atividades relevantes relacionadas à

transferência de alguns produtos acabados de uma refinaria.

O capítulo 2 apresenta uma revisão da literatura sobre problemas de otimização na

indústria do petróleo. Algumas ferramentas comerciais para tal fim são apresentadas.

No capítulo 3 descreve-se a fundamentação teórica para o desenvolvimento da

solução proposta. Os principais aspectos da teoria que envolve algoritmos genéticos e

otimização multiobjetivo são apresentados.

No capítulo 4 é apresentada a formulação do modelo desenvolvido, onde são

discutidos os algoritmos e estratégias de implementação para aplicação de AGs e as equações

para a modelagem do problema de otimização multiobjetivo.

INTRODUÇÃO

No capítulo 5 é apresentado um estudo de caso simples com o intuito de validar o

modelo desenvolvido e são mostrados estudos de casos baseados em simulação de situações

comuns na indústria do petróleo.

No capítulo 6 são apresentadas as conclusões do trabalho e propostas para trabalhos

futuros.

INTRODUÇÃO

CAPÍTULO 2

2 ESTADO DA ARTE

2.1 INTRODUÇÃO

Nos últimos anos é evidente o interesse por parte das Indústrias de Processos

Químicos no planejamento e programação da produção. O interesse se deve ao impacto

econômico que essas atividades possuem (PINTO, 2000). Por exemplo, companhias de

petróleo estão sujeitas a variações de parâmetros econômicos de decisões diárias entre

produzir ou comprar determinados produtos para atender a demanda de um ou mais clientes.

Neste contexto, as indústrias têm procurado melhorar o desempenho da cadeia de produção

em que estão inseridas, desde o pedido do cliente até a entrega do produto. Considerando que

este é um fator essencial para manter uma vantagem sobre a concorrência.

Tanto na otimização da programação quanto na programação da produção têm-se

dois termos comumente usados no meio industrial e acadêmico oriundos da língua inglesa; os

termos planning e scheduling. Na Indústria do Petróleo, tanto planning como scheduling

referem-se os procedimentos de alocação de recursos por um determinado tempo para

executar uma determinada tarefa (PEKNY e ZENTNER, 1994). Plannnig e scheduling

possuem diferentes visões de operação no tempo. Enquanto planning tem uma visão de longo

prazo considerando uma quantidade de operações realizadas como se todas as operações

ocorressem ao mesmo tempo, scheduling objetiva a previsão dos tempos dos movimentos

capturando a dinâmica do sistema no curto prazo.

As atividades e operações associadas a uma refinaria são caracterizadas pela

necessidade de uma quantidade significativa de tomadas de decisão em uma base diária. Estas

atividades tratam normalmente situações que combinam operações contínuas com a

determinação de alocação de recursos (equipamentos, insumos e tempos de processamento)

para as várias tarefas envolvidas na produção (SHAH, PANTELIDES e SARGENT, 1993).

ESTADO DA ARTE

Assim o problema de programação da produção e alocação de tarefas pode ser

considerado um problema de scheduling.

2.2 DEFINIÇÃO DE SCHEDULING

Segundo BODINGTON e SHOBRYS (1995), o scheduling é a determinação,

podendo ser revisada diariamente ou semanalmente, do que cada estágio da produção deve

fazer em um determinado horizonte de tempo, que pode variar entre um turno de trabalho e

algumas semanas, definindo (ou prevendo) todas as entradas e saídas de cada operação de

produção.

No desenvolvimento da atividade de scheduling, o tempo e as operações movem-se

continuamente, do início para o fim do período considerado, com as revisões levando em

conta o que está atualmente acontecendo. O objetivo da atividade de scheduling é, portanto, a

implementação do que foi determinado pelo planning, sujeito a uma série de variações como

alterações no suprimento de matéria-prima, instabilidades no processo de produção, mudanças

dos requisitos dos clientes ou problemas com a distribuição dos produtos. Desta forma, os

programadores de produção devem realizar correções no sentido de buscar os objetivos

determinados pela atividade de planning.

Em outras palavras, a programação da produção visa coordenar as operações de uma

refinaria com seus objetivos de produção, de modo a otimizar a lucratividade do sistema de

processamento ou a minimizar os custos do mesmo. Vários são os fatores a serem

considerados nas diretrizes de produção: alterações nas demandas, especificações dos

produtos, datas de entrega, qualidade e quantidade das matérias primas, disponibilidade e

desempenho das unidades de processo são alguns deles. Integrada fortemente a estratégias de

planejamento, a atividade de programação da produção deve ser desenvolvida de maneira

otimizada. Os principais fatores associados envolvem desde o suprimento de matéria prima

até os sistemas de informação de mercado de produtos, passando pela operação da planta e

gerenciamento ótimo dos recursos disponíveis.

Na sua forma mais conceitual um problema de scheduling consiste de uma estratégia

operacional; de um conjunto de equipamentos da planta; de um conjunto de recursos:

ESTADO DA ARTE

humanos, de utilidades e de materiais; de um conjunto de receitas de produtos e sua relação de

precedência na produção; uma demanda de produtos e uma otimização de um ou mais

critérios da planta (REKLAITIS, 1991).

Os modelos de scheduling podem ser classificados em duas categorias (PEKNY et al,

1990), generalistas e específicos:

1. A elaboração de modelos de scheduling generalistas, através da manipulação

adequada do conjunto de restrições contidas no modelo inicialmente proposto.

Estes modelos são baseados em programação inteira mista (linear ou não linear).

Os trabalhos nesta área foram inicialmente apresentados por KONDILI et al

(1993) com as representações em Rede Estado Tarefa, para descrever processos

químicos complexos. Esta representação na forma de grafo é composta por dois

tipos de nós: os nós Estado e os nós Tarefa, os primeiros representam a matéria

prima, os produtos finais e os intermediários, e os segundos representam as

operações de processamento.

2. Desenvolvimento de algoritmos específicos para cenários de problemas

particulares. Alguns destes cenários incluem estágios múltiplos de

processamento, equipamentos com várias condições de estocagem de

intermediários. Os trabalhos nesse sentido vêm sendo largamente difundidos, por

utilizarem algoritmos específicos de cada processo (GRAU et al.,1996;

KONDILI et al.,1993; PINTO e GROSSMANN, 1995; KUDVA et al.,1994).

2.2.1 SCHEDULING EM REFINARIA

A atividade de scheduling em uma refinaria é denotada pela necessidade de uma

quantidade significativa de tomadas de decisão em uma base diária, lidando com situações

que combinam operações contínuas e por bateladas (BODINGTON e SHOBRYS, 1995).

Assim Scheduling envolve uma interação dinâmica envolvendo negócios (variações do

mercado e clientes) e o processo de produção e distribuição de petróleo e seus derivados.

Tais decisões, como por exemplo, a escolha do tanque que receberá um determinado

tipo de petróleo, parecem triviais, mas podem gerar conseqüências importantes dias depois.

ESTADO DA ARTE

Além disso, há um alcance amplo de atividades diferentes que precisam ser programadas

quase ao mesmo tempo e um grande número de influências externas que devem ser levadas

em consideração para a tomada de decisões.

O scheduling de uma refinaria deve ser factível, ou seja, as atividades devem ser

possíveis de serem realizadas. Elas devem também serem capazes de integrar uma variedade

de informações provenientes de diferentes fontes. É necessário saber o inventário e a

qualidade dos produtos disponíveis, nível de produção, disponibilidade de equipamentos, de

que forma diferentes unidades de processo interagem, tempo de processo, tamanho possível

das bateladas e assim por diante.

Em uma refinaria, as atividades envolvidas para a programação de produção incluem

(CASTRO, 2001):

• o recebimento e mistura de petróleos: o programador deve definir a seqüência de

recebimento do petróleo disponível e a forma de processamento destas misturas,

visando seu máximo aproveitamento.

• modos de operação das unidades de processo: é de responsabilidade do

programador de produção a definição do tipo de carga a ser processada e quais os

produtos que devem ser produzidos em um determinado momento e qual o seu

destino.

• utilização da tancagem de componentes intermediários: o programador de

produção deve avaliar a adequação dos estoques de matéria-prima para as

unidades de processo. Produtos finais e intermediários devem ser apropriados

para operações em unidades de processo e mistura.

• realização de misturas de produtos: em função das solicitações dos clientes e das

características dos componentes disponíveis, o programador de produção define

como, quando e qual o tipo de produto a ser preparado.

ESTADO DA ARTE

A programação da produção de uma refinaria está subordinada a interferências

externas. Existem aquelas originadas na própria refinaria, como por exemplo, problemas

operacionais nas unidades de processo e as que ocorrem fora da refinaria, como alterações na

chegada de matéria prima e entrega de produtos.

Outra característica é a ordem de importância dos tipos de problemas de

programação de produção para cada refinaria. Para refinarias sujeitas a variação nos tipos de

petróleos recebidos, a programação da seqüência deste recebimento e a preparação das cargas

das unidades são o problema mais crítico em termos de scheduling. Por outro lado, em

refinarias que dispõe de diferentes tipos de modais de transporte para escoamento de sua

produção, a programação das retiradas de produtos pode se tornar bastante complexa

(CASTRO, 2001).

Normalmente, o programador de produção não tem muito tempo para tomar decisões

e raramente, há a possibilidade de se avaliar mais detalhadamente as conseqüências de uma

determinada decisão no futuro. Muitas das decisões são baseadas na experiência do operador

e por isso não se pode afirmar que tais decisões levam a uma programação ótima.

2.2.2 BENEFÍCIOS

Num ambiente competitivo, caracterizado por baixas margens de refino e alta

volatilidade dos preços, a lucratividade de uma refinaria deve ser alcançada por uma

programação ótima de alocação de recursos de acordo com a previsão de produção

estabelecida. O sucesso dessa operação está intimamente ligado à atividade de scheduling.

Existem muitas razões de ordem técnica e financeira que justificam o

desenvolvimento e a implantação de ferramentas computacionais direcionadas ao scheduling

de refinarias de petróleo, conforme MAGALHÃES et al. (1998):

• a seleção de misturas ótimas de óleo cru e produtos intermediários auxilia na

obtenção de produtos finais, com parâmetros dentro de uma faixa estreita e

estável de especificação;

ESTADO DA ARTE

• a utilização otimizada do parque de armazenagem reduz as perdas em tancagem.

Estas perdas podem ocorrer em função do tempo que o produto fica depositado

no tanque, contribuindo para a formação de emulsões (dispersão de gotículas de

um líquido em outro imiscível);

• expansão da capacidade de monitoramento/tomada de decisão no processo como

um todo, bem como em situações de instabilidade. Como exemplo desta situação

pode-se citar uma oscilação no processo de refino, tirando de especificação

alguns produtos finais ou intermediários;

• ganho de flexibilidade ao fornecimento de produtos requeridos em situações

especiais;

• possibilidade teórica de obtenção de qualidade assegurada ao produto que sai do

processo, o que pode conduzir ao fornecimento direto às distribuidoras;

• possibilidade de adoção de uma política just-in-time indo ao encontro das

necessidades das distribuidoras;

• redução da necessidade de inventários.

2.2.3 COMPLEXIBILIDADE DO SCHEDULING

O principal fator de dificuldade para a escolha de um método de solução definitivo

para o problema de scheduling é a inexistência de uma técnica de programação matemática

apropriada às características de problema combinado a uma razoável complexidade do

problema. Isto porque, o problema de scheduling tem elementos discretos na chegada de

petróleo, armazenamento, mistura e expedição de produtos e elementos contínuos na operação

das unidades de processo (PELHAM e PHARRIS, 1996).

Em vista da não disponibilidade de sistemas desenvolvidos comercialmente para

utilização pela indústria do refino em geral (CUTTING e HAVERLY, 1995), a maioria dos

ESTADO DA ARTE

programadores de produção de refinarias de petróleo utiliza métodos manuais auxiliados por

planilhas, para realização de cálculos específicos. Tentativas de utilização de sistemas de

scheduling desenvolvidos para outras indústrias, onde os processos por bateladas

predominam, não tiveram sucesso. Na falta de ferramentas adequadas para as refinarias, os

programadores de produção têm as suas atividades limitadas à determinação de uma

seqüência de operações factível, restando pouco ou nenhum tempo para encontrar a seqüência

ótima de operação.

2.2.4 MÉTODOS DE SOLUÇÃO PARA SCHEDULING

Alguns pesquisadores têm buscado novas técnicas nos campos da Inteligência

Artificial e na Pesquisa Operacional para a solução de problemas de scheduling de refinarias,

produzindo resultados aproximados para uma classe geral de problemas ou soluções exatas

para problemas específicos (ALMEIDA, 2000; STEBEL, 2001; MORO, 2000).

A importância da modelagem matemática na abordagem de problemas de otimização

em refinarias de petróleo fica evidente devido à complexidade das atividades relacionadas.

Estas se tornaram um vasto campo para a criação e a aplicação de modelos matemáticos

visando melhorias no planejamento operacional. Como exemplo, a otimização de operações

de transferência e estocagem numa refinaria de petróleo tem por objetivo alcançar melhores

condições de operação, segundo determinados critérios, sem alterar a malha disponível de

válvulas, bombas e dutos, usando um melhor caminho para a transferência de produtos de um

tanque a outro (MORO, 2000). A principal função destes modelos é fazer com que o dado

sistema torne-se o mais eficiente possível em termos econômicos e como conseqüência, um

novo ponto operacional pode ser encontrado.

Entre os tipos de metodologias computacionais mais freqüentemente utilizadas na

tentativa de resolver os problemas de scheduling na indústria de petróleo, pode-se citar a

simulação, otimização e/ou programação matemática e inteligência artificial (BARBOZA,

2005).

ESTADO DA ARTE

2.2.5 SIMULAÇÃO

Simulação pode ser definida como sendo "o desenvolvimento de um modelo lógico

que reproduz a realidade a fim de avaliar o comportamento e o desempenho de sistemas sob

as mais variadas condições" (PEGDEN et al, 1990).

Simulação é uma das abordagens mais comuns para resolução do problema de

scheduling, em função da sua ênfase na consistência da solução encontrada, permitindo

identificar as conseqüências de uma programação escolhida (BODINGTON e

SHOBRYS,1995).

A técnica de simulação para problemas de scheduling mostra o que poderia acontecer

com um sistema se ele fosse ajustado para uma configuração particular. Esta configuração

inclui a programação das entradas do sistema, a disposição dos recursos, as regras para o

fluxo de roteamento, e as paradas e turnos esperados. Podem ser incluídas regras no

roteamento para permitir que o trabalho com maior prioridade seja processado primeiro ou

preemptar outras ordens. Os arquivos de saída podem mostrar o início e o fim esperados para

cada tarefa. Assim, a simulação pode realizar algumas funções de programação da produção,

uma vez que os dados básicos das tarefas se encontram no modelo. De fato, programações de

produção alternativas podem ser consideradas facilmente no modelo através de planilhas, e

podem ser rodados cenários com cada uma destas programações alternativas. Os resultados

para cada cenário podem ser vistos simultaneamente para que a melhor programação possa ser

escolhida.

De uma forma geral, os algoritmos de simulação podem ajudar a determinar a

seqüência de operações, mas normalmente não levam em conta os direcionadores

econômicos. Caso não se utilize nenhuma outra forma de inteligência computacional, a

solução do problema de scheduling através de simulação reduz-se a um processo de tentativa

e erro (BODINGTON e SHOBRYS, 1995).

ESTADO DA ARTE

2.2.6 OTIMIZAÇÃO

Problemas de scheduling pertencem a uma das mais difíceis categorias de problemas

de otimização (KALLRATH e WILSON, 1997). O problema de scheduling pode ser

modelado como um de Programação Linear Inteira Mista (MILP) ou Programação Não-

Linear Inteira Mista (MILNP). Isto permite utilizar variáveis inteiras para decisão para tratar

com questões de seqüenciamento, quantidades mínimas de produtos e outros tipos de decisões

do tipo sim/não.

Algumas limitações do uso de técnicas de programação matemática na solução de problemas

de scheduling são (BODINGTON e SHOBRYS, 1995):

• Tempo de solução elevado

• Controle do processo de solução

• Dificuldade na interpretação da modelagem

2.2.6.1 Programação Matemática

Os modelos MILP e MILNP tendem a tornarem-se muito grandes com o aumento do

número de variáveis, aumentando significativamente o tempo necessário para encontrar uma

solução, mesmo utilizando-se linguagens e computadores modernos. Dessa maneira é difícil

abstrair o entendimento de como tal solução foi obtida ou de que forma um dado de entrada

afetaria a busca da solução ótima.

Em BALLINTIJN (1993), destaca-se o emprego de modelos matemáticos de

otimização em refinarias com o propósito de encontrar alguma seqüência de operações diária

em suas unidades de produção. O autor ressalta ainda a importância de modelos de

programação linear inteira mista (MILP) para o estudo de tomadas de decisão envolvendo a

operação de uma refinaria. O modelo proposto caracteriza uma planta de processamento onde

os custos e demandas típicas variam de forma determinística de período a período. O objetivo

é fazer com que a operação seja realizada a custos mínimos, atendendo-se a demanda de

determinados produtos.

ESTADO DA ARTE

JOLY e PINTO (1999) criaram um modelo para a produção de óleo combustível e

asfalto na REVAP, que é responsável por oitenta por cento da produção de óleo combustível

produzido no Brasil. O modelo gera um acompanhamento ótimo da produção sob restrições

de demanda dos produtos e operacionais, com o objetivo de minimizar os custos envolvidos

na refinaria citada. Foram propostas e comparadas duas formulações MILP e MINLP quanto

ao tempo computacional requerido e à qualidade das soluções geradas.

Outro trabalho pode ser encontrado em MAGATÃO (2001) que aborda a otimização

no transporte de derivados de petróleo através de um duto. O objetivo principal é o

desenvolvimento de modelos de auxílio ao gerenciamento das operações de um poliduto. O

poliduto em estudo conecta uma refinaria a um terminal portuário. Os modelos de otimização

foram elaborados em MILP, com discretização uniforme dos intervalos de tempo. Destaca-se

a utilização de estratégias de subdivisão do problema para contornar a dificuldade de

resolução computacional. Os modelos propostos foram capazes de gerar novos pontos de

operação para o sistema de bombeio, proporcionando ganhos operacionais significativos.

STEBEL (2001) propõe em seu trabalho dois modelos para as operações de

transferência e estocagem de GLP (Gás Liquefeito de Petróleo). O cenário é composto por um

conjunto de esferas de estocagem e dutos de recebimento e envio. O primeiro modelo é

baseado em redes de Petri e permite acompanhar o comportamento de cenários do processo. A

simulação com redes de Petri permite um diagnóstico de pontos críticos do problema e a

experimentação de diferentes abordagens para sua solução. O segundo modelo, proposto em

MILP com representação discreta do horizonte de scheduling, realiza a otimização do sistema.

Nesse caso, o modelo tem como objetivo a minimização dos custos operacionais. As

restrições físicas e operacionais assim como as de demanda são consideradas em ambas as

abordagens, sendo possível uma visualização dos estados nos quais se encontram as esferas.

2.2.6.2 Inteligência Artificial

As pesquisas sobre modelos computacionais inteligentes têm nos últimos anos, se

caracterizado pela inspiração na natureza. Para os pesquisadores, muitas das soluções

promovidas pela ação natural são complexos problemas de adaptação que fornecem modelos

ESTADO DA ARTE

interessantes. Embora não se possa afirmar que tais soluções sejam ótimas, não há a menor

dúvida de que os processos naturais são bem concebidos e adequados ao nosso mundo.

Considerando as características da atividade de scheduling de uma refinaria de

petróleo, verifica-se que seu desenvolvimento depende muito do conhecimento e habilidades

do programador de produção que a executa. Desta forma, verifica-se que há um grande

potencial na utilização de técnicas de inteligência artificial para a resolução de problemas de

scheduling (CASTRO, 2001).

Nos últimos anos, diversos trabalhos têm sido desenvolvidos, procurando utilizar

técnicas de inteligência artificial (AI) em problemas de scheduling. Estes trabalhos procuram

demonstrar que apesar das diversas alternativas disponíveis para execução do scheduling, é

possível identificar padrões, acrescentar parâmetros difusos à avaliação, aplicar modelos de

tomada de decisão e acoplar sistemas especialistas ou algoritmos otimizadores, separadamente

ou conjuntamente, a fim de se obter um sistema autônomo de determinação de scheduling

(LOUREIRO, 1997).

A Heurística definida como a utilização de um procedimento de busca inteligente

para obtenção da solução de um problema, é um método bastante atrativo para os

programadores de produção, ao emular o processo de pensamento dos mesmos. Além disso, a

Heurística tem a característica desejável de poder ser estruturada para fazer um número

limitado de alterações de seqüência de programação ao mesmo tempo (BODINGTON e

SHOBRYS, 1995).

Heurísticas podem ser construídas a partir de algoritmos matemáticos, ou conjuntos

de regras de sistemas especialistas, visando estabelecer um método de busca de solução

inteligente. Como exemplo, pode-se citar a tentativa de encontrar a seqüência de operações de

produção que reduz os custos de transição. Alternativamente, uma técnica de otimização pode

ser aplicada para resolver um aspecto particular do scheduling, como o balanço de estoques

ou capacidades ou a sincronização das atividades de produção ao longo dos estágios do

processo produtivo (BODINGTON e SHOBRYS, 1995).

ESTADO DA ARTE

CASTRO (2001) estudou o problema da programação de produção em refinarias de

petróleo (scheduling), utilizando Algoritmos Genéticos como base de um aplicativo para

computador que pudesse resolver um problema de programação de produção de uma refinaria,

uma vez que esta técnica é bastante adequada para a otimização de problemas não lineares

que envolvem variáveis discretas e contínuas, como é o caso do problema de scheduling.

Assim, desenvolveu-se um modelo de solução para o Sistema de Produção e Armazenamento

do Gás Liqüefeito de Petróleo da Refinaria Henrique Lage.

ALMEIDA (2001) desenvolveu um método que aplica Algoritmos Genéticos para

solucionar problemas de scheduling combinando com sistemas baseados em regras.

Algoritmos Genéticos são aplicados para encontrar e otimizar soluções geradas por problemas

de scheduling de óleos combustíveis e asfalto na REVAP (Refinaria do Vale do Paraíba).

Sistemas baseados em regras são aplicados na escolha de vários tanques de armazenagem do

produto final recebido da produção que servirá para atender a demanda de vários centros

consumidores.

No trabalho de CRUZ et al (2003) é mostrada a modelagem de um problema de

distribuição de derivados de petróleo e posterior otimização utilizando técnicas heurísticas

(Algoritmos Genéticos). Nesse trabalho, muitas funções objetivo são consideradas, restrições

são inclusas como parte da função objetivo. Prioridades e penalidades são impostas às funções

objetivo.

Uma abordagem híbrida pode ser encontrada em GARCIA (2004). O trabalho pode

ser considerado uma evolução de CRUZ et al (2003), onde foi resolvido um problema de

distribuição de derivados de petróleo em uma rede de oleodutos. O problema foi modelado e

solucionado utilizando duas técnicas: Método Heurístico através de um algoritmo

multiobjetivo evolucionário e Programação Matemática. O trabalho comparou soluções

obtidas através do método Híbrido, MILP e Computação Evolucionária onde concluiu que

métodos híbridos podem obter soluções ótimas em intervalos de tempo de execução menor.

COELLO e CHRISTIANSEN (1995) apresentam uma técnica que combina

algoritmos genéticos e método do critério global para encontrar o valor ótimo para um

ESTADO DA ARTE

problema de otimização multiobjetivo com múltiplas restrições. Nesse trabalho, uma

interessante aproximação é utilizada onde se mescla o método da ponderação com o método

do critério global. A metodologia usada é simples e fácil de ser implementada e como

resultado fornece um conjunto de soluções Pareto-ótima.

GOLDBARG et al (2004) aplicaram um algoritmo Transgenético para um problema

de rede de dutos de Gás. A seleção de tipos de tubos é considerada como um problema de

otimização com restrições e normalmente é abordado como um problema de custo mínimo,

tendo como variáveis de decisão o diâmetro dos tubos.

Uma abordagem combinando métodos de simulação e técnicas da computação

evolucionária tais que Algoritmos Genéticos e Algoritmos Transgenéticos é desenvolvida em

BARBOZA (2005) e aplicada ao problema de estocagem e distribuição de óleo diesel em uma

refinaria. Os resultados apresentados reforçam a idéia de que métodos baseados em

inteligência artificial podem substituir métodos baseados em MILP, achando soluções

factíveis em um menor tempo computacional.

2.2.6.3 Aplicativos comerciais

O mercado do petróleo e gás é extremamente rentável visto que nossas fontes de

energia são dependentes da queima de produtos oriundos do craqueamento do petróleo. Por

isso existe uma quantidade enorme de empresas fornecedoras de serviços para esse tipo de

indústria. Na tentativa de aumentar a rentabilidade, muitas soluções são propostas. Desde a

modernização da estrutura e maquinários à melhor utilização dos recursos disponíveis na

indústria. A tendência de hoje é tentar melhorar o rendimento da estrutura instalada através da

otimização da rede e para isto várias empresas oferecem pacotes computacionais para os

problemas de planning e scheduling em indústrias.

Dentre muitas empresas no ramo de aplicativos para a indústria do petróleo,

destacam-se as seguintes:

1. Haverly Systems Inc: A Haverly oferece para o escalonamento de fornecimento

de crus, operações na refinaria, mistura de produtos e distribuição de produtos

finais a ferramenta H/SCHED. Os modelos gerados são otimizados a partir da

ESTADO DA ARTE

Programação Linear, incluindo a técnica de programação inteira mista. O

H/SCHED possui geração automática de escalonamento proprietária. Interfaces

gráficas para melhor visualização ao usuário estão incluídas. Desta maneira o

programador tem controle total dos detalhes finais da programação (HAVERLY,

2005).

2. AspenTech: A AspenTech apresenta o aplicativo Aspen Distribution Scheduler

para o escalonamento da movimentação de produtos entre plantas, distribuição,

manutenção da rede de inventários e otimização dos custos da distribuição. A

otimização dar-se-á através das técnicas de Heurísticas, Programação Linear e

Programação Inteira Mista gerando uma distribuição ótima (ASPENTECH,

2005).

3. Ingenious Inc: A Ingenious Inc. oferece para problemas de otimização a

ferramenta ProSched que tem como características uma interface de simulação

para a evolução de escalonamentos e otimizações factíveis. A modelagem é feita

através do Visual Basic que está integrado ao software. Para minimização e

maximização são utilizados algoritmos genéticos (INGENIOUS, 2005).

4. Palisade: RISKOptimizer é um dos aplicativos disponíveis para problemas de

otimização fornecidos pela Palisade. O RISKOptimizer combina duas

tecnologias, a de simulação (@RISK's Monte Carlo) e a de algoritmos genéticos

(EvolverTM) que permitem a otimização através de modelos gerados em

planilhas do Excel. Uma característica é a habilidade de lidar com incertezas,

podendo ser adicionada funções de distribuição de probabilidade (PALISADE,

2005).

5. Critical Control: O foco da empresa é fornecer ferramentas para escalonamentos

por bateladas e detecção de vazamentos. Para isso, a Critical Control lançou o

software PipeWorks. O produto consiste em um Escalonador e Planejador de

Bateladas Futuras (Future Batch Planner) para assistir na operação de dutos e

escalonamento da movimentação dos produtos especificados para um duto.

ESTADO DA ARTE

Future Batch Planner (FBP) utiliza técnicas de inteligência artificial para prover o

escalonamento automático do duto. FBP recebe a configuração do duto, regras de

escalonamentos, funções objetivas e gera várias soluções de escalonamento.

Depois seleciona o melhor resultado. O resultado apresentado poderá ser ajustado

de acordo com os critérios do usuário através de uma ferramenta interativa

(CRITICAL CONTROL, 2005).

A Tabela 2-1 relaciona a corporação pesquisada e sua respectiva localização na

internet.

Tabela 2-1: Site das principais empresas na área de scheduling

Corporação Webpage

Haverly Systems Inc http://www. haverly.com

AspenTech http://www.aspentech.com

Ingenious Inc. http://www.ingenious.cc

Palisade http://www.palisade.com

Critical Control http://www.criticalcontrol.com

De maneira geral, boas soluções são propostas. As soluções abrangem metodologias

desde Programação Linear até Algoritmos Genéticos. Os softwares comerciais são bem

vindos para a resolução de problemas mais genéricos. A partir do momento em que o

problema começa a ter muitos detalhes, a ferramenta deixa de ser flexível e rápida na busca de

soluções. Isto ocorre pelo fato de que quando o problema é abrangente, a ferramenta deve se

adequar ao problema. Mas muitos problemas são peculiares à própria companhia e por isso a

ferramenta perde sua capacidade de adequar-se ao problema, levando a ocorrência do oposto,

ou seja, o problema é que acaba tendo que se adequar à ferramenta devido à limitação de

recursos do aplicativo. Neste momento individualiza-se a utilização do aplicativo.

2.3 CONSIDERAÇÕES FINAIS

A programação da produção e alocação de tarefas continua sendo um problema atual

visto que a produção acadêmica no desenvolvimento de metodologias de otimização continua

ESTADO DA ARTE

crescendo. Existe uma procura das corporações junto às universidades e entidades comerciais

na busca de soluções para problemas cada vez mais complexos e individuais.

Em um mercado dinâmico, em que a tomada de decisão precisa ser rápida, boas

soluções devem ser encontradas em um curto espaço de tempo. Neste contexto, AG vem se

tornando uma metodologia bastante pesquisada devido a menor complexidade na

implementação entre outras vantagens que serão apresentadas no próximo capítulo.

FUNDAMENTAÇÃO TEÓRICA

CAPÍTULO 3

3 FUNDAMENTAÇÃO TEÓRICA

3.1 ALGORITMOS GENÉTICOS

As pesquisas sobre modelos computacionais inteligentes têm se caracterizado pela

tendência em buscar inspiração na natureza. Para cientistas da computação, matemáticos e

engenheiros, muitas soluções que a natureza encontrou para complexos problemas de

adaptação fornecem modelos interessantes. Embora não se possa afirmar que tais modelos

forneçam soluções ótimas. A idéia básica é aplicar o processo de evolução natural como um

paradigma de solução de problemas, a partir de sua implementação em computador.

A computação evolutiva engloba um número crescente de métodos onde Algoritmos

Genéticos têm sido a mais difundida e estudada técnica (TANOMARU,1995).

Algoritmo Genético (AG) é um método computacional de busca baseado em

mecanismos da evolução natural e na genética. Em AG, uma população de possíveis soluções

evolui de acordo com operadores probabilísticos concebidos a partir de metáforas biológicas,

de tal modo que exista uma tendência de que, na média, os indivíduos representem soluções

cada vez melhores, a medida que o processo evolutivo continue. Ou seja, o AG realiza uma

simulação de evolução biológica por meio de uma busca multidirecional no espaço de

soluções potenciais do problema. A cada geração, a população é modificada de maneira que

as boas soluções permaneçam e possam reproduzir-se, e as ruins sejam descartadas. Os

princípios básicos de AGs foram estabelecidos em HOLLAND (1975).

Os AGs possuem as seguintes características que diferem de métodos convencionais

de busca e otimização (GOLDBERG, 1989):

1. AGs trabalham com uma população (conjunto) de soluções candidatas

simultaneamente e não com uma única solução.

2. AGs operam num espaço de soluções codificadas, e não num espaço de busca

direta.

FUNDAMENTAÇÃO TEÓRICA

3. AGs necessitam somente de informações sobre o valor de uma função objetivo

para cada membro da população e não requerem derivadas ou qualquer outro tipo

de conhecimento.

4. AGs utilizam regras de transição probabilísticas e não determinísticas.

De maneira simplificada um AG consiste de (COLEY,1999):

• Uma população de soluções potenciais.

• Uma maneira de quantificar e qualificar uma solução.

• Um método para compor novas soluções a partir de parte das melhores soluções.

• Um operador de mutação para manter a diversidade na população.

O procedimento básico para um AG pode ser visto na Figura 3-1. Um conjunto de

soluções codificadas corresponde a uma população de indivíduos, P(0). AGs são algoritmos

iterativos, e cada iteração corresponde a uma geração. Cada geração é designada pelo

parâmetro “t” e tem sua população modificada por recombinações (crossover) e mutações.

Figura 3-1: Procedimento básico para um AG

Uma população é iniciada aleatoriamente gerando soluções potenciais. Essas

soluções representam pontos espalhados no espaço de busca. Inicializações aleatórios geram

FUNDAMENTAÇÃO TEÓRICA

populações com soluções, em sua maioria, ruins. Métodos heurísticos podem ser utilizados

para a produção de boas soluções para a população inicial.

Um AG típico utiliza três operadores, seleção, recombinação e mutação, para

conduzir a população na direção de convergência para o ponto ótimo global. Após a aplicação

desses 3 operadores, o processo se repete até que uma condição de parada seja atingida ou

quando se atingir um determinado número de gerações desejado.

Algumas vantagens podem ser citadas na utilização de AGs como método de

otimização (LEMONGE,1999):

• Otimizam quantidades maiores de variáveis;

• Realizam buscas simultâneas em vários pontos do espaço de busca;

• Fornecem um conjunto de soluções e não uma única solução;

• Flexibilidade no tratamento de restrições;

• Permite otimizar múltiplas funções com objetivos conflitantes;

• Podem ser associados a outras técnicas de otimização (algoritmos híbridos);

• Podem ser implementados facilmente em computadores;

• Não exige conhecimento aprofundado do problema.

3.1.1 NOMENCLATURA

Sendo o AG um método inspirado na evolução natural, muito dos termos

encontrados são originados da Biologia.

• Gene: é a unidade básica que controla uma determinada propriedade de um

indivíduo. Representa parte de uma característica da solução.

FUNDAMENTAÇÃO TEÓRICA

• Indivíduo ou Cromossomo: é a representação da solução do modelo sendo

formado por conjunto de genes.

• População: conjunto de indivíduos que representam o atual espaço de busca do

problema.

• Geração: identifica a evolução de uma população, ou seja, número da iteração que

o algoritmo genético executa.

• Função de Avaliação: é a função que se quer otimizar. Representa as

características do problema e é usada para avaliar o nível de aptidão dos

cromossomos.

• Fitness: valor que mede o grau de aptidão de um cromossomo. Identifica se uma

solução é boa ou ruim.

• Recombinação: consiste na troca (evento aleatório) de informações entre dois

cromossomos.

• Mutação: consiste na troca (evento aleatório) da característica de um gene

(variável) em determinado cromossomo.

3.1.2 REPRESENTAÇÃO

Um passo fundamental para aplicação de algoritmos genéticos é representar cada

possível solução como uma seqüência de símbolos gerados a partir de um dado alfabeto.

Uma solução típica de um AG é composta por um vetor, onde cada posição do vetor

representa um gene. Um gene pode assumir qualquer valor contando que obedeça ao alfabeto

escolhido. Alfabetos binários normalmente são utilizados para representação de números. A

Tabela 3.1 ilustra a representação binária para um vetor solução de tamanho 2.

FUNDAMENTAÇÃO TEÓRICA

Tabela 3-1: Representação binária

Representação binária Valor numérico

00 0

01 1

10 2

11 3

Para casos mais simples a representação binária é suficiente, mas a representação a

ser utilizada depende de cada problema. Em alguns casos, um vetor solução pode representar

uma seqüência de eventos onde uma letra especifica o evento ocorrido. Por exemplo, para o

alfabeto A = {A, B, C, D} e um vetor solução de tamanho 3, uma possível solução S seria; S

= AAB ou S = BCD. Sendo S a representação de uma seqüência de eventos ocorrida.

A escolha da codificação dos cromossomos a ser adotada é uma etapa bastante

importante na construção do algoritmo genético, já que deve permitir a representação da

solução completa do problema, sem dificultar a medida da função de fitness ou a aplicação

dos operadores genéticos. Na versão clássica do algoritmo, os indivíduos são representados

através de vetores binários de tamanho fixo (HOLLAND, 1975).

3.1.3 OPERADORES GENÉTICOS

Os Algoritmos Genéticos baseiam-se nos operadores genéticos para seleção,

recombinação, mutação e substituição da população (CHAMBERS, CORCORAN &

WAINWRIGHT, 1995).

Os operadores genéticos são aplicados aos cromossomos da população com o

objetivo de reproduzir novos e melhores indivíduos a partir dos já existentes. As operações

são necessárias para permitir a diversidade dos indivíduos, bem como explorar outras regiões

do espaço de busca. Os principais operadores são recombinação e mutação.

FUNDAMENTAÇÃO TEÓRICA

3.1.3.1 Recombinação

O operador de recombinação cria novos cromossomos através da combinação de dois

ou mais indivíduos selecionados aleatoriamente. O objetivo desta aplicação é a troca de

informação entre diferentes soluções candidatas (MICHALEWICZ, 1996) (GOLDBERG,

1989).

A recombinação ocorre com uma probabilidade P

a ser definida no projeto. Altas

taxas de recombinação reduzem as chances de convergência para um máximo local, mas

acabam por resultar em maiores perdas computacionais devido à exploração de regiões não

promissoras dentro do espaço de busca. Existem grandes quantidades de operadores de

recombinação propostos na literatura, com aplicação direcionada a diferentes tipos de

codificações e problemas. Os mais comuns são recombinação ponto único, recombinação

multiponto e recombinação uniforme (CASTILHO, 2003).

Recombinação ponto único

Um ponto de cruzamento é escolhido e a partir deste ponto as informações genéticas

são trocadas conforme ilustrado na Figura 3-2.

Figura 3-2: Recombinação ponto único

Recombinação multiponto

Análogo a recombinação ponto único com a diferença que vários pontos de

cruzamentos podem ser utilizados conforme mostrado na Figura 3-3.

FUNDAMENTAÇÃO TEÓRICA

Figura 3-3: Recombinação multiponto

Recombinação uniforme

Não utiliza pontos de cruzamentos. A recombinação é determinada por uma máscara

de bits aleatórios nas quais os genes de cada pai são herdados por cada filho. Para cada bit 1

da máscara, o gene do pai é copiado para o filho 1, caso contrário o bit da mãe é copiado. Para

o segundo filho o processo é invertido. Para cada bit 0, o gene do pai é copiado para o filho 2

e para o bit 1 da máscara o gene da mãe é copiado.

Figura 3-4: Recombinação uniforme

Segundo VON ZUBEN (2000) não se pode afirmar que uma técnica de

recombinação é melhor que outra. Cada técnica pode apresentar desempenho melhor ou pior

dependendo do problema e de que forma ele foi modelado.

3.1.3.2 Mutação

O operador de mutação tem como objetivo manter e propiciar a diversidade genética

da população (MICHALEWICZ, 1996) (GOLDBERG, 1989). Este operador implica na

FUNDAMENTAÇÃO TEÓRICA

alteração aleatória de uma ou mais características de um cromossomo escolhido, propiciando

assim, a introdução de novos elementos na população.

A utilização deste operador visa resgatar material genético perdido e inserir material

não explorado, prevenindo desta maneira a convergência prematura do algoritmo para

soluções sub-ótimas (COELHO & COELHO, 1999) e assegura que a probabilidade de

examinar qualquer ponto do espaço de busca não será zero.

Na maioria das vezes o operador mutação é aplicado aos indivíduos após a

recombinação. O operador mutação é aplicado aos indivíduos com probabilidade P

. Se esta

probabilidade for baixa, pode haver comprometimento na diversidade dos indivíduos.

Contudo se a probabilidade for alta pode haver perturbações aleatórias de tal forma que os

filhos provavelmente perderão suas semelhanças com os pais podendo assim comprometer a

convergência. A Figura 3-5 exemplifica o processo de mutação.

Figura 3-5: Exemplo de mutação

3.1.3.3 Seleção

O processo de seleção ocorre após a avaliação de cada indivíduo pertencente

população, normalmente sendo baseado no princípio da sobrevivência dos melhores

indivíduos. Os cromossomos com melhores níveis de aptidão possuem uma maior

probabilidade de serem mantidos e selecionados para a etapa de reprodução. Da mesma

forma, os cromossomos com baixos níveis de aptidão possuem pouca probabilidade de

permanecer e, conseqüentemente, podem ser eliminados da população. Portanto, o operador

seleção visa escolher os indivíduos que devem continuar o processo evolutivo conforme

estratégia adotada.

FUNDAMENTAÇÃO TEÓRICA

As principais estratégias de seleção de um indivíduo para a próxima geração são:

seleção rank, seleção por roleta, seleção por torneio e técnica elitista.

Seleção Rank

A população é ordenada de acordo com o nível de aptidão de cada indivíduo. Os

melhores indivíduos possuem as melhores posições. Segundo BENNETT (1997), é associado

à posição zero o elemento de melhor desempenho e a posição N

pop

-1 o pior indivíduo, sendo

pop

o tamanho da população. Sendo assim, um indivíduo α com posição r

no rank é

selecionado com probabilidade p

dada pela equação 3.1:

()

−

⋅

poppop

(3.1)

Seleção por Roleta

O algoritmo genético clássico utiliza um esquema de seleção de indivíduos chamado

seleção por roleta (MICHALEWICZ, 1996). Neste método cada indivíduo ocupa, em uma

roleta, uma área proporcional ao seu nível de aptidão. Assim, aos indivíduos com maior

aptidão é associada uma fatia maior da roleta e aos indivíduos com menor aptidão, fatias

menores. Em seguida faz-se a simulação do giro da roleta “n” vezes, selecionando-se os “n”

indivíduos que se manterão na etapa seguinte. Os mais aptos possuem uma probabilidade

maior de serem selecionados, podendo, inclusive, serem selecionados mais de uma vez,

enquanto os menos aptos, com uma probabilidade menor, podem desaparecer logo após as

primeiras gerações.

A probabilidade de seleção p

de um cromossomo com aptidão F

em uma população

de tamanho N

pop

é dada pela equação 3.2.

∑

pop

(3.2)

A partir de p

, calcula-se a probabilidade acumulada q

pela equação 3.3.

FUNDAMENTAÇÃO TEÓRICA

∑

(3.3)

Para o processo de seleção sorteia-se aleatoriamente um número no intervalo r [0,1].

Se r ≤ q

, então o primeiro cromossomo é selecionado, caso contrário, o individuo

selecionado será o i-ésimo tal que q

i-1

< r < q

O método de seleção por roleta é o método mais comumente utilizado, porém, pode

levar o algoritmo a diminuir a diversidade da população, e isto ocasiona, em determinadas

situações, a convergência prematura das soluções (FABRO, 2003). Um outro problema é a

possibilidade de extinguir-se um indivíduo com alto nível de aptidão já que este tipo de

seleção trabalha com probabilidades, e por isso um bom indivíduo pode ser perdido ao longo

das gerações.

Seleção por Torneio

Neste método geram-se grupos aleatórios de indivíduos. O indivíduo com o melhor

nível de aptidão no grupo, é selecionado, enquanto que os demais são descartados. O processo

é repetido até que a população esteja completa. A vantagem deste método é a não

convergência prematura do algoritmo, o que dificulta a estagnação do processo.

Técnica Elitista

A técnica elitista tem como objetivo enviar certo número de melhores indivíduos da

população corrente para a próxima geração, evitando, assim, a possível perda de boas

soluções no processo de seleção. Esta técnica é aplicada em conjunto com algum outro

método de seleção para aumentar a velocidade de convergência do algoritmo e garantir que

bons indivíduos não sejam perdidos nas gerações futuras.

A desvantagem da utilização da técnica elitista é a possibilidade de gerar a

convergência prematura do algoritmo genético. Visto que os melhores indivíduos são

mantidos nas gerações futuras e isso leva uma reprodução maior destes indivíduos durante as

evoluções.

FUNDAMENTAÇÃO TEÓRICA

Segundo SWIECH (2005), existe a solução de manter as cópias dos melhores

indivíduos obtidos durante as evoluções, isolados do corpo principal do programa. Neste caso,

o elitismo mantém determinado número de cópias de bons elementos dentro de uma casta

isolada do programa principal, que não participam do processo de seleção e não sofrem

alterações dos operadores genéticos. Além disto, dentro desta casta não existem soluções

repetidas.

Assim, a casta elitista, além de ser responsável pela garantia de transmissão de bons

indivíduos para a população seguinte, tem a função de preservar o conjunto de melhores

soluções obtidas até o encerramento da rotina. Esta estratégia elitista será utilizada neste

trabalho sendo explicada em detalhes no capítulo 4 que traz a metodologia proposta.

3.1.4 PROCESSO EVOLUTIVO

Para se obter a população da geração t + 1 (população inicial a cada ciclo) a partir da

população da geração “t”, segue-se os seguintes procedimentos:

1. Calcula-se a adequação do indivíduo ao meio ambiente (fitness), e os

cromossomos com maior aptidão terão maior possibilidade de serem selecionados;

2. Selecionam-se os cromossomos para o cruzamento de acordo com a estratégia

adotada;

3. Realiza-se o processo de recombinação para toda a população conforme

probabilidade de ocorrência escolhida;

4. Para os descendentes obtidos, pode-se aplicar a operação de mutação a cada

posição física do cromossomo de acordo com a probabilidade de ocorrência

escolhida.

5. Repete-se o processo de 1 a 4 até que o critério de parada desejado seja atendido.

O processo de busca da solução normalmente tem como critério de parada o número

de gerações, ou seja, o total de ciclos de evolução de um algoritmo genético. Outro critério de

FUNDAMENTAÇÃO TEÓRICA

parada que pode ser utilizado é a melhor solução do problema que não apresenta evolução

após um número pré-determinado de gerações.

As taxas de aplicação de recombinação e de mutação podem variar a cada ciclo, em

função de um melhor desempenho na busca da solução. A taxa de aplicação da recombinação

pode ser maior nas primeiras gerações, quando a população se apresenta dispersa no espaço

de busca. Após várias gerações, os indivíduos tendem a apresentar características similares e

neste momento pode ser interessante aumentar a taxa de mutação para trazer novo material

genético para a formação de melhores indivíduos (ALMEIDA, 2001).

A determinação destas taxas de aplicação é denominada de interpolação de

parâmetros e pode ser linear ou adaptativa. Na interpolação linear, um parâmetro é variado

entre um valor inicial e final, através de ajustes fixos, linearmente a cada conjunto de

gerações. A interpolação adaptativa leva em consideração o desempenho das gerações

antecedentes para alteração na taxa de recombinação. Este desempenho é medido em função

do sucesso da evolução dos indivíduos (CASTRO, 2001).

3.2 ALGORITMOS GENÉTICOS APLICADOS À OTIMIZAÇÃO

MULTIOBJETIVO

A otimização multiobjetivo é o ramo da otimização matemática que busca

desenvolver métodos de resolução para problemas em que se identificam vários e diferentes

objetivos a serem satisfeitos. A motivação para o uso e desenvolvimento desses

procedimentos é o tratamento simultâneo de todos os objetivos identificados no problema

(MOURA, 2002). Em problemas com um único objetivo, a solução ótima é obtida através da

simples maximização (ou minimização) de uma função objetivo de variáveis de decisão

sujeita a uma série de restrições práticas. Diferentemente disso, a análise multiobjetivo

seleciona a solução de melhor compromisso em um cenário em que há múltiplos objetivos.

Aqui, busca-se a otimização do conjunto das funções objetivo, através de critérios e

julgamento das alternativas de solução possíveis.

FUNDAMENTAÇÃO TEÓRICA

As funções objetivo formam a descrição matemática do chamado critério de

desempenho, as quais usualmente são conflitantes. Assim, pode-se dizer que o termo otimizar

significa descobrir uma solução, para a qual os valores de todas as funções objetivo são

considerados aceitáveis pelo projetista ou decisor.

Um problema de otimização multiobjetivo pode ser definido como:

Minimizar ))(),...,(),(()(

xfixfxfxF = , i ≥ 2

(3.4)

Sujeito a:

(x) ≤ 0, j = 1,...,m (3.5)

(x) = 0, k = 1,...,n (3.6)

Onde F(x) é um vetor de funções objetivo, x é um vetor de variáveis de decisão, g

e h

são respectivamente a j-ésima e k-ésima restrições, e i, m e n representam o número total de

funções objetivo, restrições expressas como inequações e restrições expressas como equações

respectivamente.

A otimização multiobjetivo normalmente apresenta objetivos conflitantes, de tal maneira

que o atendimento a cada um dos objetivos pode corresponder a uma solução ótima. Isso faz com

que esses problemas apresentem várias soluções ótimas. Por essa razão, na

análise multiobjetivo

aplica-se o Princípio da Otimalidade de Pareto (DEB, 1999), na qual não é possível que uma

solução seja melhor em todos os critérios, dado um conjunto de soluções. As soluções de

Pareto são as melhores soluções entre as quais não existe um ordenamento (ou seja, não há

como definir, a partir da avaliação das funções objetivo, se uma solução é melhor que a

outra). Dessa maneira, fica evidente que o princípio de otimalidade em otimização

multiobjetivo lida com um conjunto de soluções e não com uma única solução.

Soluções dominadas são aquelas que possuem o desempenho de todos os seus critérios

iguais ou inferiores se comparadas a um conjunto de soluções. Para um problema tendo mais

de um objetivo, f = (f

, f

,…, f

), i = 1,..., M e M ≥ 2, para duas soluções quaisquer x

(1)

e x

(2)

têm-se duas possibilidades – ou uma domina a outra ou ninguém domina ninguém. Diz-se que

FUNDAMENTAÇÃO TEÓRICA

a solução x

(1)

domina x

(2)

se ambas as condições, 3.7 e 3.8 são verdadeiras (DEB, 1999).

Denota-se ‘ f ’para melhor, ‘ p ’ para pior e “!” para negação.

)()!(

xfxf

p ,

para i=1,2,..., M

(3.7)

)()(

xfxf

f ,

para pelo menos um i ∈{1,2,..., M}

(3.8)

Se alguma condição for violada, então x

(1)

não domina x

(2)

Segundo DEB (1999), dado um conjunto de soluções, é possível encontrar as soluções

Pareto-ótimas, aplicando o seguinte algoritmo.

Considerando uma população de N soluções e M ≥ 2 objetivos.

1. Inicia i = 1;

2. Para todo j = 1 e j ≠ i, compare as soluções x

(i)

e x

(j)

para todos os M objetivos

usando as condições das 3.7 e 3.8.

3. Se para algum j, x

(i)

é dominado por x

(j)

, marque x

(i)

como “dominado”.

4. Se i = N, ou seja, todas as soluções foram verificadas então siga para o passo 5.

Caso contrário, incrementar i em uma unidade e volte ao passo 1.

5. Todas as soluções que não estão marcadas como “dominado” são Pareto-ótima.

Algoritmos evolucionários são apropriados para problemas de otimização

multiobjetivo porque lidam simultaneamente com um conjunto de possíveis soluções, na qual

permitem encontrar um conjunto de soluções Pareto-ótima em uma única simulação. O que

não acontece com técnicas tradicionais de programação matemáticas onde cada solução é

obtida e deve ser guardada para compor um conjunto de soluções Pareto-ótima (COELLO,

1999).

FUNDAMENTAÇÃO TEÓRICA

3.2.1 MÉTODOS DE SOLUÇÃO EM PROGRAMAÇÃO MULTIOBJETIVO

Na literatura é possível encontrar uma variedade de métodos como forma de resolver

um problema de otimização multiobjetivo. Estes métodos de resolução de problemas de

otimização multiobjetivo podem ser classificados em dois grupos: (ARRUDA et al, 2006)

• definidas prioridades e/ou pesos entre os vários objetivos de interesse, encontra-se

a solução ótima segundo estas informações fornecidas a priori;

• sem nenhuma informação adicional, encontra-se o conjunto das soluções ótimas de

Pareto para dentre estas, se escolher uma a posteriori.

Exemplos de métodos do primeiro grupo são Programação Objetiva, Método do

Critério Global, Recozimento Simulado e métodos evolucionários em que se combinam as

diversas funções objetivo dentro de uma única função, obtendo como resultado da otimização

uma solução única. Por outro lado, existem outros métodos evolucionários que se enquadram

no segundo grupo calculando um grande número de soluções ótimas de Pareto para uma

escolha pessoal posterior.

O algoritmo genético proposto neste trabalho utiliza uma função objetivo única como

os métodos do primeiro grupo mas calcula através de uma técnica elitista de ranqueamento

por nicho, um conjunto de soluções ótimas das quais são selecionadas as soluções de Pareto,

como os métodos do segundo grupo.

Um método de nicho deve ser capaz de formar e manter diferentes soluções finais,

independente se estas soluções apresentam desempenhos semelhantes ou diferentes. Estas

devem ser mantidas por um período infinito com respeito ao tamanho da população total

(ARRUDA, 2006). Em otimização multiobjetivo, os métodos de nichos são particularmente

interessantes para manter uma série de subpopulações nas regiões Pareto-ótimas, além de

prevenir a competição de indivíduos distantes. O termo distante normalmente está relacionado

às diferenças genotípicas. Neste trabalho, o critério de distância está associado ao

desempenho do indivíduo em relação a cada um dos objetivos considerados. Assim um

FUNDAMENTAÇÃO TEÓRICA

método de nicho modificado é empregado de forma a tornar o processo de competição mais

ameno, além de assegurar a transmissão de bons indivíduos para a população seguinte e ainda

manter um conjunto de soluções com bom nível de adequação desde o início do processo

evolutivo.

Para a construção da função de avaliação do AG foram utilizados os seguintes

métodos de modelagem de problemas de otimização multiobjetivo: o método do critério

global, método das ponderações e método da penalização, os quais são detalhados a seguir.

Método do Critério Global (GUPTA & SIVAKUMAR, 2002)

O método do critério global utiliza o valor ótimo como base de cálculo para definir o

grau de aptidão (fitness) de um indivíduo. Esse método converte a função multiobjetivo em

um único objetivo sendo expresso matematicamente pela função 3.9.

)x(ff

min

∑

⎟

⎠

⎞

⎜

⎝

⎛

−

(3.9)

Onde f* é o valor ótimo, N é a quantidade de objetivos e P um valor de projeto,

normalmente sendo definido como 1 ou 2.

Quando o valor ótimo de cada objetivo é conhecido, a aplicação deste método

mostra-se bastante eficiente já que cada objetivo é normalizado, evitando assim a comparação

de critérios com grandezas diferentes.

Método das Ponderações (COELLO, 1999)

Este método consiste na aplicação de um peso aos critérios da função objetivo. Na

prática, o método é útil na geração de subconjuntos de Pareto caracterizados pelas

preferências impostas pelos pesos utilizados em cada objetivo. Portanto não é viável, a

geração de todo o conjunto de Pareto-ótimo através desse método. Matematicamente o

método é expresso por:

∑

)x(fwmin

(3.10)

FUNDAMENTAÇÃO TEÓRICA

Satisfazendo a seguinte condição.

∑

1, 0 < w

< 1

(3.11)

Onde N é o número de objetivos a ser otimizado.

Método da penalidade (CASTILHO, 2003)

Essa técnica penaliza essencialmente as soluções infactíveis. Isso é feito alterando a

função de aptidão por meio da adição de um termo de penalidade. Portanto, funções de

penalidades funcionam como um guia em direção a soluções factíveis. A maior dificuldade do

método é definir a função de penalidade, cabendo ao projetista essa tarefa. A preocupação é

como determinar a penalidade de tal maneira que se tenha um balanço na direção de aptidão

que a informação seja preservada.

Conforme sugerido por GEN & CHEN (1997), existem dois caminhos para formular a

função de avaliação em conjunto com a penalidade. Uma forma é adicionar um termo de

penalidade à função objetivo, conforme equação 3.12.

F(x) = f(x) + pen(x), (3.12)

Se x é factível, então pen(x) = 0;

Caso contrário, pen(x) > 0.

Onde f(x) é a função objetivo e pen(x) é a função de penalidade.

A outra maneira é multiplicar a função objetivo pela função de penalidade, conforme

mostrado na equação 3.13.

F(x) = f(x) * pen(x), (3.13)

Se x é factível, então pen(x) = 1;

Caso contrário, pen(x) > 1.

A literatura é vasta na utilização de funções de penalidade. Em MICHALEWICZ e

SCHOENAUER (1996) podem ser visto outras formas de aplicar funções de penalidade.

FUNDAMENTAÇÃO TEÓRICA

3.2.2 TRATAMENTO DAS RESTRIÇÕES

Um dos problemas na aplicação de AG em otimização multiobjetivo é de que forma

tratar as restrições. Em muitos casos, restrições podem ser vistas como parte da função

objetivo a ser otimizada.

Quando isso não acontece, as restrições devem ser tratadas no intuito de tentar evitar

soluções infactíveis. Algumas técnicas são apresentadas em GEN & CHENG (1997)

conforme mostrado a seguir.

• Estratégia de penalidade: problemas onde o número de restrições é elevado

resultam em grande quantidade de soluções infactíveis. Portanto, às vezes torna-

se difícil gerar soluções factíveis. A técnica de penalidade é uma estratégia que

lida com soluções infactíveis conforme explicado no tópico anterior.

• Estratégia de reparação: consiste em reparar um individuo transformando-o em

uma solução factível. Para problemas de otimização combinatória a

implementação dessa técnica não oferece dificuldades na maioria dos casos.

• Estratégia da rejeição: descarta indivíduos infactíveis ao longo das gerações.

3.3 CONSIDERAÇÕES FINAIS

Este capítulo apresentou e discutiu os principais conceitos relacionados à otimização

multiobjetivo e a sua solução via Algoritmos Genéticos com o intuito de estabelecer

terminologias e conceitos.

O método proposto neste trabalho é baseado na utilização de Algoritmo Genéticos

com elitismo, técnica de ranqueamento e formação de nicho, o qual garante ao final da

evolução um conjunto de boas soluções em relação aos diferentes objetivos do problema de

otimização. A partir deste conjunto, selecionam-se as soluções ótimas de Pareto, confome será

apresentado a seguir.

CAPÍTULO 4

4 MODELAGEM

4.1 O PROBLEMA

A distribuição de derivados de petróleo é uma atividade importante e complexa. Dada a

elevada taxa de ocupação das redes, é necessária a otimização. Uma melhor eficiência no uso

da rede, quando possível, pode ser uma solução mais barata e mais rápida que investimentos

na ampliação da malha de distribuição.

Um dos fatores críticos para o sucesso da modelagem é o próprio entendimento do

problema a ser resolvido. A Figura 4-1 mostra a rede de escuros (derivados pesados e vários

tipos de petróleo) da PETROBRAS no estado de São Paulo, como exemplo da

complexibilidade de uma rede de polidutos.

Figura 4-1: Rede de escuros (FONTE: PETROBRAS)

Uma rede de distribuição de petróleo é composta por um número de refinarias e

terminais, ou áreas, interligadas por um conjunto de oleodutos, ou trechos de dutos, os quais

MODELAGEM

operam o transporte de um conjunto de produtos (petróleos, derivados de petróleos e produtos

orgânicos) entre áreas adjacentes. O transporte é realizado em sucessivos envios de bateladas.

Uma batelada é a quantidade de um determinado produto transportado por um poliduto.

Geralmente um produto é transportado de refinarias, portos e/ou centro de

armazenagens para pontos de destino. Os dutos são normalmente unidirecionais. Em alguns

casos especiais, os dutos podem ser bidirecionais, como por exemplo, um poliduto

interligando um porto e uma refinaria. Em uma conexão unidirecional, um produto iria fluir

somente do porto para a refinaria ou somente da refinaria para o porto. Já na conexão

bidirecional, um produto poderia fluir tanto do porto para a refinaria quanto da refinaria para

o porto, mas nunca ao mesmo tempo.

Um determinado duto pode ainda vir a apresentar restrições de uso devido a janelas

de tempo, como conseqüência de necessidade de manutenção da linha ou em virtude das

denominadas restrições horosazonais (impedimento de bombeamento em determinadas linhas

em virtude de pico de consumo de energia elétrica).

4.2 MODELO DA REDE DE DISTRIBUIÇÃO DE PETRÓLEO

O modelo tratado neste trabalho é uma simplificação de uma rede real. O modelo é

composto por um conjunto de fontes (refinarias), um conjunto de terminais (pontos de

destino), e um conjunto de tanques intermediários que podem ser receptores ou fornecedores

de produtos (parque de armazenagem).

A rede em discussão pode ser vista na Figura 4-2. As refinarias estão representadas

pelos nós N

e N

. Os nós intermediários N

e N

representam parque de armazenagem de

produtos. Os pontos de destino ou terminais estão representados pelos nós N

, N

e N

MODELAGEM

Figura 4-2: Rede proposta

As linhas que unem os nós representam os polidutos e as flechas representam a

direção que flui o produto transportado. Ambos os nós, N

e N

, fornecem produtos para N

através das conexões D

, D

e D

. Essas conexões são unidirecionais, ou seja, o

produto flui somente na direção da fonte para os nós intermediários. Os nós N

e N

são

conectados através de um poliduto bidirecional D

. As conexões D

e D

conectam os nó

N5 e N

à N

respectivamente. Já as conexões D

e D

conectam os nós N

e N

à N

respectivamente. Os produtos produzidos nas fontes N

e N

estão sendo designados de forma

genérica e nomeados como produto 1, 2, 3 e 4. O produto que cada fonte produz é

configurado conforme desejado. Por exemplo, a fonte N

pode ser configurada para produzir

produtos do tipo 1 e 2 e a fonte N

para produzir produtos do tipo 3 e 4.

Considera-se a tancagem agregada por produto, isto é, cada nó intermediário e/ou

terminal possui a quantidade de tanques necessária para cada produto que ele possa receber.

Ou seja, se em um nó é possível receber 4 tipos de produtos, então assume-se que nesse nó

existam 4 tanques para a armazenagem desses produtos.

MODELAGEM

No modelo está sendo considerado que os produtos são entregues na forma de

bateladas discretas. Uma batelada representa um volume mínimo de um produto a ser

transportado em uma unidade de tempo. Uma batelada unitária é um volume mínimo que

preenche um duto. Cada conexão possui uma distância normalizada em termos de unidades de

tempo necessárias para que uma dada batelada seja transportada de um ponto a outro. O

modelo assume a discretização do tempo. A Tabela 4-1 mostra a distância de cada conexão.

Tabela 4-1: Distância entre as conexões

Conexão Distância

Para a simplificação do problema, cada duto é considerado com o mesmo diâmetro e

mesmas características. Todos os produtos fluem com a mesma velocidade e ocupam o

mesmo volume no duto.

4.2.1 REPRESENTAÇÃO DO MODELO

A solução para o problema é dada por cada tipo de batelada que é enviada em cada

instante de tempo em cada conexão.

Para codificar a solução é possível utilizar uma matriz que represente a solução.

Nesta matriz, as linhas representam as conexões e as colunas o tempo. As conexões

bidirecionais são desdobradas em duas conexões, onde cada conexão representa um possível

caminho. O desdobramento das conexões bidirecionais se deve a necessidade de codificar o

MODELAGEM

caminho de ida e de volta. Cada produto é codificado por um número inteiro. A matriz é

preenchida pelo valor que representa cada produto no devido tempo e conexão. O valor zero

significa que não existe produto alocado na conexão. Neste caso quando existe um produto na

conexão D

não existe produto em D

. Para a codificação é necessário saber o horizonte de

tempo, que é uma definição de projeto. A Figura 4-3 mostra um exemplo de codificação da

rede da Figura 4-2 para 10 instantes de tempo.

Figura 4-3: Matriz de codificação

Por exemplo, no instante 2 não haverá produto alocado na conexão 1, na conexão 2

haverá o produto 4, na conexão 3 não haverá produto, e assim por diante.

Utilizar matriz como forma de representação em AG acaba dificultando a

implementação e com isso aumentando o esforço computacional. Para facilitar a

implementação, a solução será codificada em forma de um vetor, onde cada linha representará

um indivíduo. A solução em forma de matriz pode ser rearranjada em forma vetorial

conforme mostrado na Figura 4-4.

Figura 4-4: Vetor de codificação

A implementação em forma de vetor permite por sua vez que o espaço de busca

tenha uma forma matricial. Neste caso a população pode ser representada como uma matriz,

onde cada linha representa um indivíduo. O vetor solução pode ser visto na terceira linha da

Figura 4-4.

MODELAGEM

4.2.1.1 Condições de contorno

A codificação mostrada pode não contemplar determinadas condições do problema,

como por exemplo, os tipos de produtos produzidos em uma refinaria, que podem ser

diferentes em cada uma. Para aproximar o modelo a uma situação real, a fonte representada

pelo nó N

pode produzir tipos de produtos diferentes de N

. Desta forma, algumas conexões

não podem assumir certos valores. Para lidar com esse tipo de situação, a codificação do valor

em cada conexão admitirá valores na faixa de [0; número de produtos permitidos e/ou

produzidos]. No final do processo, uma matriz é utilizada para decodificar essa representação

no produto correspondente.

Como cada tipo de produto é codificado por um valor inteiro, então assumindo que

produza produtos do tipo 1 e 2 e N

produza produtos do tipo 3 e 4, os valores contidos no

vetor solução seriam os mesmos para a conexão 1 e 2 e para a conexão 3 e 4, cujo intervalo

seria de [0;2]. Os valores contidos neste vetor estão mascarados para efeitos de

implementação, portanto para saber o valor real contido no vetor, uma matriz deve ser usada

para decodificação conforme mostrado na Tabela 4-2, onde cada linha representa a conexão e

cada coluna o produto correspondente para cada valor codificado.

Tabela 4-2: Matriz de decodificação

Valores codificados 0 1 2 3 4

Conexão 1 0 1 2

Conexão 2 0 1 2

Conexão 3 0 3 4

Conexão 4 0 3 4

Conexão 5 0 1 2 3 4

Conexão 6 0 1 2 3 4

Conexão 7 0 1 2 3 4

Conexão 8 0 1 2 3 4

Conexão 9 0 1 2 3 4

Conexão 10 0 1 2 3 4

MODELAGEM

Utilizando a matriz, a solução codificada mostrada na Figura 4-5, ficaria na forma

decodificada conforme mostrado na Figura 4-6. A região hachurada destaca as conexões onde

alguns tipos de produtos não podem existir.

Figura 4-5: Solução codificada

Figura 4-6: Solução decodificada

Considerando o exemplo fornecido, para o instante 1 na conexão 4 o valor contido no

vetor solução é 2 (Figura 4-5). Na matriz de decodificação (Tabela 4-2) o valor 2 representa a

segunda coluna e a conexão 4 a quarta linha, logo o produto correspondente nesta conexão é o

4 (Figura 4-6).

Para associar o nó de origem e destino e a distância normalizada em termos de unidade

de tempo de cada conexão, uma matriz é utilizada e pode ser vista na Tabela 4-3.

Tabela 4-3: Matriz de conexão

Conexão Nó de origem Nó de destino Tempo

1 1 3 1

2 1 4 3

3 2 3 3

4 2 4 2

5 3 4 3

6 3 5 3

7 3 6 4

8 4 3 2

9 4 6 3

10 4 7 2

MODELAGEM

A Tabela 4-4 mostra os parâmetros utilizados na implementação do AG.

Tabela 4-4: Descrição dos parâmetros do modelo AG

Parâmetro Descrição

ind

Quantidade de indivíduos na população

gene

Quantidade de genes no indivíduo

conex

Quantidade de conexões

4.2.2 GERAÇÃO DA POPULAÇÃO INICIAL

A geração de números aleatórios é comumente usada na aplicação de algoritmos

genéticos. Algoritmos genéticos assumem uma população inicial para iniciar o processo de

aplicação dos operadores genéticos bem como a seleção de cada indivíduo da população.

Para a geração da população inicial, um vetor é utilizado como máscara para

codificar em cada tempo o tipo de produto em cada conexão no vetor solução. Na Tabela 4-5

é possível visualizar a máscara, onde cada conexão irá assumir valores inteiros dentro da faixa

[0; quantidade de produtos permitido e/ou produzido].

Tabela 4-5: Máscara de codificação de produtos

Conexão 1 2 3 4 5 6 7 8 9 10

Qtde de produto 2 2 2 2 4 4 4 4 4 4

Para a decodificação basta utilizar a matriz da Tabela 4-2 já apresentada. A geração

da população inicial é feita conforme algoritmo abaixo.

Figura 4-7: Algoritmo para geração da população inicial

MODELAGEM

Onde Population é a matriz de representação da solução de toda a população. Cada

linha dessa matriz representa um indivíduo. Nesta matriz, N

ind

é o número de linhas e N

genes

número de colunas e Mask é o vetor usado para representar a máscara mostrada na Tabela 4-5.

4.2.3 OPERADORES GENÉTICOS

Os operadores genéticos são responsáveis em reproduzir novos e melhores

indivíduos a partir dos já existentes. Os operadores aplicados no modelo são; a recombinação

de ponto único e a mutação.

4.2.3.1 Recombinação de ponto único

A recombinação de ponto único pode ser implementada de acordo com o algoritmo

da Figura 4-8.

Figura 4-8: Algoritmo para recombinação ponto único

4.2.3.2 Mutação

A mutação é um importante operador genético pois é responsável em provocar a

diversidade na população. Altas taxas de probabilidade de mutação podem ocasionar a não

convergência do modelo.

A implementação foi feita conforme algoritmo mostrado na figura abaixo.

MODELAGEM

Figura 4-9: Algoritmo para mutação

4.2.3.3 Seleção

O método de seleção utilizado neste trabalho é baseado na técnica elitista de

ranqueamento e formação de nichos (GOLDBERG, 1989), mas com algumas modificações.

Neste caso, o elitismo mantém determinado número de cópias de bons elementos dentro de

uma casta isolada do programa principal (casta elitista), que não participam do processo de

seleção e não sofrem alterações dos operadores genéticos. Além disto, dentro desta casta não

existem soluções repetidas. O algoritmo de seleção conforme implementado neste trabalho foi

inicialmente proposto em SWIECH (2005).

As operações genéticas ocorrem somente no corpo principal do algoritmo genético,

no qual existem cópias dos elementos guardados na casta elitista. A casta elitista tem também

a função de manter os melhores indivíduos encontrados durante toda a evolução, mesmo no

momento da convergência total de um único elemento nas demais castas do programa.

Para escolha dos indivíduos em cada população foi empregado o método de seleção

por torneio, com elitismo de 10% do tamanho da população. Foram determinadas quatro

castas com distribuição conforme Tabela 4-6. A casta elitista é composta por 10% do tamanho

da população, e abriga os melhores elementos da geração anterior, sem que haja repetição de

uma mesma solução. A casta de reprodução é formada pela reprodução dos 20% melhores

elementos da população corrente, podendo haver repetições. A casta intermediária é formada

pela transmissão direta de 50% da população corrente referente aos indivíduos com nível de

MODELAGEM

aptidão intermediário. A última casta é composta pelas soluções menos adequadas da

população corrente, que sofrem um processo de eliminação e são transmitidas apenas em

parte para a nova geração.

Tabela 4-6: Distribuição das castas (SWIECH,2005)

População Próxima

corrente geração

10% Casta Elitista

20%

→

25% Casta de reprodução

50%

→

50% Casta intermediária

30%

→

15% Casta de eliminação

Casta

→ → → →

Maior nível

de aptidão

A Figura 4.10 apresenta o procedimento utilizado pelo algoritmo genético para a

construção das castas descritas.

20% 50% 30%

10%

50%

25% 15%

casta

elitista reprodução

casta de casta

intermediária eliminação

casta de

Sb1 Sb2 Sb3

PRÓXIMA POPULAÇÃO

POPULAÇÃO CORRENTE

MAIOR NÍVEL DE ADEQUAÇÃO

CORPO PRINCIPAL DO ALGORITMO GENÉTICO

Figura 4-10: Construção das castas (SWIECH,2005)

Primeiramente os indivíduos da população corrente, após avaliados, são ordenados

de acordo com seus níveis de aptidão, e, então, a população é subdividida em três partes

correspondentes a 20, 50 e 30% do tamanho total da população. A seguir, o algoritmo repassa

os indivíduos com melhor nível de aptidão para a casta elitista da população seguinte, até

completar o número de 10% do tamanho da população, sem que haja indivíduos iguais. Como

podem existir indivíduos repetidos dentro da subdivisão Sb1 (20% melhores da população

MODELAGEM

corrente), a casta elitista pode ser formada por elementos das outras subdivisões.

Posteriormente os indivíduos da subdivisão Sb1 são colocados através da atuação da seleção

por torneio formando a casta de reprodução. Os indivíduos da subdivisão Sb2 são repassados

diretamente para a casta intermediária, e, finalmente, alguns indivíduos da subdivisão Sb3

sofrem eliminação, também através da utilização da seleção por torneio novamente, gerando a

casta de eliminação.

Após este procedimento, são utilizados os operadores genéticos de mutação e

recombinação somente no corpo principal do algoritmo genético (Figura 4-10), para a

finalização da construção da nova geração. Após formada, a nova geração tem todos os seus

indivíduos avaliados, ordenados e posteriormente subdivididos nas três partes (Sb1, Sb2 e

Sb3) para a continuação do ciclo de busca.

Com a utilização da metodologia apresentada, ao final da simulação, são disponíveis

na casta elitista, não apenas um, mas vários indivíduos que formam o conjunto das melhores

soluções encontradas pelo algoritmo genético. Portanto, ao visualizar um conjunto de

soluções possíveis, o “decisor” tem flexibilidade e opção de escolha, podendo trabalhar com

uma ou mais soluções de acordo com seu interesse.

Para os algoritmos de recombinação e mutação apresentados neste trabalho, deve-se

iniciar ‘i’ com o valor correspondente a quantidade de indivíduos pertencentes à casta elitista,

dessa maneira garante-se que os melhores indivíduos não sofrerão operações genéticas. A

casta elitista deve ser par para evitar inconsistência na aplicação do operador recombinação

para o algoritmo mostrado nesse capítulo.

4.3 OTIMIZAÇÃO MULTIOBJETIVO

Para o entendimento da otimização multiobjetivo implementada, a Tabela 4-7

esclarece os principais parâmetros utilizados.

MODELAGEM

Tabela 4-7: Relação de parâmetro para otimização do modelo

Parâmetros Descrição

Quantidade de bateladas demandada do produto j pelo destino i

Quantidade de bateladas recebida do produto j no destino i

Quantidade mínima de bateladas do produto j que deve ser enviado pela

fonte i

Quantidade de bateladas do produto j armazenado no tanque i

Quantidade de bateladas do produto j enviado pela fonte i

Frag

Quantidade de fragmentações na conexão i

Tchegada

Tempo de chegada do ultima batelada do produto i no destino j

Tmin

Menor tempo para receber uma batelada no destino i

Tmax Horizonte de tempo do modelo

NC Número de colisões na conexão bidirecional

LCm

Limite inferior da quantidade de bateladas do produto j no nó i

LCM

Limite superior da quantidade de bateladas do produto j no nó i

Quantidade de fontes

Quantidade de destino

Quantidade de tanques no nó i

Quantidade de nós

Quantidade de objetivos

4.3.1 RESTRIÇÕES

O modelo está sujeito as seguintes restrições:

1. R1: Uma mínima quantidade de bateladas de cada produto deve ser enviada. Para

evitar a paralisação da produção em uma refinaria e por não haver recursos

(tanques disponíveis) para armazenagem dos produtos, uma quantidade mínima

de produtos deve ser enviada.

≤ E

para i = 1,...N

para j = 1,...,Nt

(4.1)

MODELAGEM

2. R2: A demanda em cada destino deve ser cumprida e cada destino não deve

receber mais do que o planejado

≤ D

para i = 1,...N

para j = 1,...,Nt

(4.2)

3. R3: Um nó não pode enviar e receber ao mesmo tempo produtos de uma conexão

bidirecional, portanto ou o nó está em um estado de envio ou de recebimento ou

ocioso. Então não podem existir colisões na conexão bidirecional proposta.

NC = 0 (4.3)

4. R4: A capacidade de cada tanque não pode ser violada.

LCm

≤ C

≤ LCM

para i = 1,...N

para j = 1,..., Nt

(4.4)

Para lidar com as restrições, optou-se pela estratégia de reparação que consiste em

reparar um individuo, cuja solução é infactível, transformando-o em uma solução factível. As

restrições R1 e R2 serão tratadas como objetivos e por isso não serão contemplados na

reparação.

A reparação da restrição R3 é feita da seguinte maneira:

Conforme explicado, a conexão bidirecional é desdobrada em duas conexões, uma

representando o envio em um sentido, e outra conexão representando o envio no sentido

oposto. Dessa maneira, toda vez que uma batelada existir na conexão no mesmo tempo, a

batelada que iniciar primeira será mantida, já a outra batelada será retirada. Se as bateladas

iniciaram ao mesmo tempo o envio, então uma delas é retirada aleatoriamente.

Para a reparação da restrição R4 e para eliminar sobre demanda, uma função

recursiva é implementada. Esta função é responsável em fazer a contagem das bateladas e por

MODELAGEM

atualizar o estado de cada tanque. Para cada conexão, e em cada instante de tempo, a função

identifica se está acontecendo um evento de envio ou de recebimento de uma batelada.

Se o evento for um envio, então a única violação passível de ocorrer seria a

superação do limite inferior do tanque de origem. Caso ocorra essa violação, a batelada é

retirada da conexão e adicionada ao tanque de origem.

Caso o evento seja um recebimento de uma batelada, então ocorreria uma violação

no limite superior do tanque de destino. Neste caso, a batelada é retirada da conexão e

decrementada no tanque de destino e adicionada no tanque de origem. Ao adicionar na origem

uma batelada, o estado passado do tanque se altera podendo ocasionar uma nova violação e

por isso a função deve ser recursiva e recomeçar a contar as bateladas novamente após

terminar a verificação em todo o horizonte de tempo. A Figura 4-11 ilustra uma possível

violação para o caso citado.

Figura 4-11: Exemplo de reparação para restrição R4

Considerando que o tanque A (origem) e B (destino) já estão no limite superior, no

instante 7, ocorre um evento de envio, então a batelada do produto 1 é decrementada do

tanque A (origem). No instante 8, ocorre um evento de recebimento e a batelada é adicionada

ao tanque A chegando ao limite superior novamente. No instante 9, ocorre um evento de

recebimento no tanque B e a batelada é adicionada ao tanque. Como o tanque B se encontra

no limite superior, então uma violação do limite superior da capacidade ocorre e a batelada

deve ser retirada da conexão, sendo decrementada no tanque B e adicionada à origem. Mas

como o tanque A, no estado atual, já se encontra no limite superior, então a batelada não pode

ser adicionada novamente, pois isso acarretará numa nova violação no limite superior. Uma

violação em cascata acaba ocorrendo. Neste caso, a batelada é somente retirada da conexão e

depois de terminada a verificação para todo horizonte de tempo, deve-se recomeçar

MODELAGEM

novamente a busca por violações nos limites de capacidade dos tanques em todo horizonte de

tempo.

Como cada conexão possui uma distância normalizada em termos de unidades de

tempo, como já descrito, existe uma reparação para corrigir o tempo de permanência que uma

batelada deve ocupar na conexão. Por exemplo, se a distância tem valor de 3 unidades de

tempo, então durante 3 unidades de tempo consecutivas a representação da batelada deve

aparecer codificada no vetor solução do modelo. A Figura 4-12 ilustra uma dada conexão com

distância de 3 unidades de tempo antes e depois da reparação.

Figura 4-12: Reparação da distância. (a) antes da reparação, (b) depois da reparação

4.3.2 FUNÇÃO OBJETIVO

A metodologia aplicada para calcular o desempenho de um indivíduo é uma

aproximação do método do critério global, onde faz se necessário o conhecimento do valor

ótimo como forma de normalizar a rede. Critérios com grandezas diferentes podem dominar a

avaliação final e com isso prejudicar critérios com magnitudes menores. O método do critério

global é apresentado na equação 4.5.

∑

−

fmaxf

f)x(f

)x(F

(4.5)

Onde F(x) é o resultado da composição de todos os objetivos, fmax

é o pior caso

para o critério i, f

(x) é o resultado do critério i para o indivíduo ‘x’e f

é o valor ideal para o

objetivo i. Ao normalizar a rede, os resultados ficam dentro da faixa [0;1], de tal forma que 0

é o valor ótimo, ou seja, todos os critérios foram cumpridos. F(x) com valor igual a 1 significa

MODELAGEM

que nenhum critério foi atendido. Qualquer valor entre 0 e 1 mostra que o critério foi atendido

parcialmente.

Os objetivos de otimização para o modelo apresentado são:

1. Demanda de fornecimento: Definido como a quantidade mínima de bateladas de

cada produto que deve ser enviada evitando assim a saturação dos tanques de

armazenagem de uma refinaria. Não é desejável paralisar uma produção por falta

de parque de armazenagem.

2. Demanda de recebimento: Definido como a quantidade de bateladas de cada

produto que deve ser entregue aos pontos solicitantes (terminais).

3. Minimização do tempo para atendimento à demanda.

4. Minimização da fragmentação no envio das bateladas: Evitar a alternância no

envio das bateladas dos produtos, ou seja, tentar enviar seqüências de bateladas

do mesmo produto.

A otimização de um critério leva em consideração todo o modelo, ou a otimização de

um critério para um produto para uma determinada situação. A nomenclatura a seguir será

usada para facilitar o entendimento da forma em que se deseja otimizar.

Global – Um valor é associado ao critério, levando em consideração o modelo como

um todo. Por exemplo, para o caso da demanda de recebimento, um valor estará associado a

este critério levando em consideração a demanda atendida de cada produto nos terminais e em

cada terminal.

Local – O desempenho do critério levará em consideração apenas o nó em questão.

Por exemplo, o valor do desempenho da demanda de recebimento de um terminal estará

associado apenas ao cumprimento ou não desta demanda neste terminal.

MODELAGEM

Unitária – O desempenho do critério leva em consideração apenas o produto em

questão, ou seja, o valor de desempenho deste objetivo estará associado ao cumprimento

parcial ou total para o produto em questão.

Desta maneira, o modo de otimizar permite a inserção de prioridades e/ou

preferências para a otimização dos critérios. A forma de otimizar depende da necessidade em

cada caso e poderá ser administrada através da utilização de pesos, onde cada peso poderá ser

associado a um objetivo. O valor zero para um peso significa a não necessidade de otimizar o

objetivo. Sendo assim, a otimização da demanda de fornecimento, por exemplo, poderá ter um

valor associado à otimização global e/ou um valor associado a cada refinaria e/ou um valor

associado a cada produto produzido por refinaria.

4.3.2.1 Demanda de fornecimento

As equações 4.6 e 4.7 apresentam a minimização da produção mínima a ser enviada

por produto e por fonte respectivamente. A equação 4.8 visa minimizar o envio de uma

mínima produção levando em consideração todas as fontes.

⎟

⎠

⎞

⎜

⎝

⎛

≤−

ijij

PE,

min

para i = 1,..., N

para j = 1,..., Nt

(4.6)

⎟

⎠

⎞

⎜

⎝

⎛

⎪

⎭

⎪

⎬

⎫

⎪

⎩

⎪

⎨

⎧

≤−

∑

ijij

PE,

min

para j = 1,..., N

(4.7)

MODELAGEM

⎟

⎠

⎞

⎜

⎝

⎛

⎪

⎭

⎪

⎬

⎫

⎪

⎩

⎪

⎨

⎧

≤−

∑

ijij

PE,

min

(4.8)

4.3.2.2 Demanda de recebimento

As equações 4.9, 4.10 e 4.11 apresentam a minimização do atendimento à demanda

de cada produto, de cada destino e de todos os destinos respectivamente.

)

min(

−1,

para i = 1,..., N

para j = 1,..., Nt

(4.9)

⎟

⎠

⎞

⎜

⎝

⎛

−

∑

min

para j = 1,..., Nd

(4.10)

⎟

⎠

⎞

⎜

⎝

⎛

−

∑

min

(4.11)

4.3.2.3 Minimização do tempo para atendimento à demanda de recebimento

Deve se considerar como Tmim

uma combinação da distância de cada conexão e a

demanda. Para minimizar o tempo, a demanda deve ser levada em consideração, pois se

deseja que a demanda seja cumprida no menor prazo possível. Por isso aplica-se um artifício

que penaliza o resultado quando a demanda não é cumprida. Isso é necessário para evitar uma

avaliação errada quando a demanda não é atendida mas a variável Tchegada

coincide com

MODELAGEM

Tmim

. As equações 4.12, 4.13 e 4.14 minimizam o tempo de atendimento à demanda por

produto, em cada destino e em todos os destinos respectivamente.

⎟

⎠

⎞

⎜

⎝

⎛

+−

−+

−

1)RD(

)RD(

TmimmaxT

TmimTchegada

min

ijij

jij

para i = 1,..., Nt

para j = 1,..., N

(4.12)

⎟

⎠

⎞

⎜

⎝

⎛

+−

−+

−

∑

ijij

jij

)RD(

TmimmaxT

TmimTchegada

min

para j = 1,..., Nd

(4.13)

⎟

⎠

⎞

⎜

⎝

⎛

+−

−+

−

∑

ijij

jij

)RD(

TmimmaxT

TmimTchegada

min

(4.14)

4.3.2.4 Minimização da fragmentação das bateladas nas conexões

A fragmentação de uma batelada ocorre quando em uma seqüência de envios de

bateladas, diferentes produtos são enviados alternadamente ao invés de ocorrer o envio de um

mesmo produto e depois os outros produtos sequencialmente. A alternância no tipo de

produto a ser enviado pode provocar contaminações nas fronteiras do produto enviado e por

isso a fragmentação de bateladas não é desejada. A equação 4.15 e 4.16 minimizam a

fragmentação de envios de bateladas em cada conexão e de todas as conexões do modelo

respectivamente.

MODELAGEM

[

]

[]

)

iMaskFrag,

Frag

)iMask(Frag

min(

⎪

⎭

⎪

⎬

⎫

⎪

⎩

⎪

⎨

⎧

≥

−−

para i = 1,..., N

conex

(4.15)

[

]

[]

⎟

⎠

⎞

⎜

⎝

⎛

⎪

⎭

⎪

⎬

⎫

⎪

⎩

⎪

⎨

⎧

≥

−−

∑

conex

Nconex

iMaskFrag,

Frag

)iMask(Frag

min

(4.16)

A avaliação final de um indivíduo (fitness) dar-se-á pela média da soma de todos os

objetivos levando em consideração seus respectivos pesos, conforme mostrado na equação

4.17.

∑

⋅

fitness

para w

≥ 0

(4.17)

Para priorizar a otimização de um determinado critério, foi aplicada uma

aproximação do critério da ponderação onde um peso é associado a cada objetivo, a diferença

é que a soma dos pesos não precisa ser necessariamente igual a um. O valor de cada peso é

uma decisão de projeto. Uma metodologia semelhante pode ser encontrada em COELLO e

CHRISTIANSEN (1995). A avaliação de um indivíduo pode se tornar bastante complexa

devido a todas as possibilidades de otimização apresentadas, por isso é bastante importante a

escolha do valor de cada peso. Valores de w

igual a zero significam que a avaliação do

critério i não deve ser levada em consideração na avaliação do indivíduo.

A seqüência de ações tomadas pelo algoritmo do modelo é mostrada na Figura 4-13,

e implementada na linguagem C++ utilizando a ferramenta Builder 5.0.

MODELAGEM

Primeiramente uma população é inicializada com valores aleatórios. A população

então fica sujeita a função reparadora que corrige as soluções infactíveis de acordo com a

violação de cada restrição. A população é avaliada e selecionada, de acordo com algoritmo

apresentado neste capítulo, para a aplicação dos operadores genéticos de acordo com as taxas

de recombinação e mutação configuradas. A nova população então é selecionada e fica sujeita

novamente a função reparadora, pois soluções infactíveis podem surgir após as operações

genéticas.

Figura 4-13: Diagrama do algoritmo para otimização multiobjetivo

No capítulo seguinte, a metodologia proposta é aplicada a um conjunto de cenários

da rede apresentada na figura 4-2, para validação e análise de desempenho.

CAPÍTULO 5

5 RESULTADOS OBTIDOS

Neste capítulo serão apresentados os resultados obtidos a partir da modelagem vista

no capítulo 4. Primeiro, uma simulação para validar o modelo será apresentada. Alguns

estudos de casos de situações comuns na indústria do petróleo serão mostrados em seguida.

Em cada caso, será apresentado o estado inicial e final de cada nó, o valor de cada peso para

cada critério além do desempenho do melhor indivíduo da população. Um gráfico de Gantt

será usado para mostrar a distribuição de cada produto nas conexões ao longo do horizonte de

programação.

A distância em termos de unidades de tempos discretos em cada conexão para as

simulações a serem apresentadas é mostrada na tabela abaixo.

Tabela 5-1: Distâncias em unidades de tempo das conexões

Conexão Tempo

1 1

2 3

3 3

4 2

5 3

6 4

7 2

8 3

9 3

10 2

No modelo de rede utilizado, os nós 1 e 2 representam refinarias. Os produtos por

elas produzidos são determinados como parâmetros de entrada do modelo. Os nós 5, 6 e 7

representam terminais ou pontos de entrega. Os nós 3 e 4 são considerados parque de

armazenagem.

RESULTADOS OBTIDOS

O horizonte de programação das simulações a serem apresentadas é de 48 unidades

de tempo, ou seja, o último recebimento de produto possível será na unidade de tempo 48 e

nenhum envio poderá ocorrer após esse tempo.

Os parâmetros de configuração do algoritmo genético são apresentados na Tabela 5-

2. Todas as simulações foram realizadas em um computador HP Intel Pentium Mobile

1600Mhz, 512 MB de memória RAM.

Tabela 5-2: Parâmetros do AG

Parâmetro Valor

Tamanho da população 20

Taxa de mutação 0,1

Taxa de recombinação 0,8

Quantidade de indivíduos para o torneio 2

5.1 VALIDAÇÃO DO MODELO

Para validar o modelo, é proposta uma simulação tendo como objetivo os seguintes

critérios, conforme equações apresentadas no capítulo anterior:

1. Minimizar o tempo de atendimento da demanda de recebimento.

2. Atender a demanda de recebimento no horizonte programado.

3. Atender a demanda de fornecimento de produtos.

4. Minimizar a quantidade de fragmentação no envio das bateladas

A Tabela 5-3 apresenta os produtos fornecidos por cada refinaria.

RESULTADOS OBTIDOS

Tabela 5-3: Produtos produzidos

Nó Produtos

1 1;2

2 3;4

A demanda de recebimento é configurada através da quantidade de bateladas de cada

produto que um terminal deverá receber e é apresentada na Tabela 5-4.

Tabela 5-4: Demanda de recebimento

Produtos

Nó

1 2 3 4

5 3 3 3 3

6 3 3 3 3

7 3 3 3 3

A demanda de fornecimento é configurada através da quantidade mínima de

bateladas de cada produto que deve ser enviada a partir de cada refinaria, e é apresentada na

Tabela 5-5.

Tabela 5-5: Demanda de fornecimento

Produtos

Nó

1 2 3 4

1 5 5 - -

2 - - 5 5

Para a validação do modelo, a otimização dos objetivos levará em consideração

apenas o resultado global de cada objetivo. A Tabela 5-6 apresenta os pesos associados a cada

critério.

RESULTADOS OBTIDOS

Tabela 5-6: Ponderação para os critérios globais

Critério Peso

Demanda de recebimento 3

Demanda de fornecimento 3

Minimização do tempo 3

Minimização da Fragmentação 1

O objetivo de minimização da fragmentação no envio das bateladas é um critério que

pode prejudicar o desempenho de otimização dos outros critérios e por essa razão possui um

peso associado menor. Evitar a fragmentação é muito importante, mas não é a prioridade

nesta simulação. Todos os demais pesos estão configurados com o valor zero. Desta forma

não haverá prioridades para nenhum nó e nenhum produto.

O estado inicial de cada tanque nos nós é apresentado na tabela 5-7 abaixo.

Tabela 5-7: Estado inicial dos tanques

Produtos

1 2 3 4

Nó

Min Atual Max Min Atual Max Min Atual Max Min Atual Max

1 0

10 0

2 0

10 0

3 0

10 0

4 0

10 0

5 0

6 0

7 0

6 0

O critério de parada desta simulação será o número de gerações, que neste caso será

de 5000 gerações.

Para as configurações descritas anteriormente, a Figura 5-1 mostra a distribuição de

cada produto nas conexões do melhor indivíduo ao longo horizonte de programação. O tempo

de execução para achar a solução foi de 30 segundos.

RESULTADOS OBTIDOS

Figura 5-1: Distribuição dos produtos do melhor indivíduo ao longo das conexões

O estado final de cada tanque em cada nó é apresentado na tabela abaixo.

Tabela 5-8: Estado final dos tanques

Produtos

1 2 3 4

Nó

Min Atual Max Min Atual Max Min Atual Max Min Atual Max

1 0

10 0

2 0

10 0

3 0

10 0

4 0

10 0

5 0

6 0

7 0

6 0

RESULTADOS OBTIDOS

A Tabela 5-9 apresenta o desempenho por objetivo do modelo após 5000 gerações.

Onde o valor zero significa que o objetivo foi cumprido, o valor um significa que o objetivo

não foi cumprido e qualquer valor entre zero e um significa que o objetivo foi atendido

parcialmente.

Tabela 5-9: Valor global dos objetivos

Critério Desempenho

Demanda de recebimento 0

Demanda de fornecimento 0

Minimização do tempo 0,35

Minimização da Fragmentação 0,26

Pode se notar que tanto a demanda de recebimento quanto a de fornecimento foram

atendidas totalmente. No gráfico da Figura 5-1 pode ser visto que os envios se concentram ao

lado esquerdo do gráfico, o que significa que houve uma minimização do tempo de

atendimento a demanda. Atingir o valor zero para o objetivo de minimização do tempo não é

possível, pois fisicamente é inviável que todos os produtos de um terminal sejam recebidos ao

mesmo tempo com apenas uma ou duas conexões. A Figura 5-1 mostra também uma

minimização na fragmentação das bateladas nos envios, isso pode mostrado pela pouca

alternância de produtos nas conexões.

A Figura 5-2 mostra a evolução do fitness do melhor indivíduo, sendo zero o melhor

resultado e 1 o pior.

RESULTADOS OBTIDOS

0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000

0.12

0.14

0.16

0.18

0.2

0.22

0.24

0.26

Geração

Figura 5-2: Evolução do fitness do melhor indivíduo

As figuras abaixo mostram a evolução do desempenho do melhor indivíduo nos

seguintes critérios globais; atendimento a demanda de recebimento, demanda de

fornecimento, minimização do tempo e minimização da fragmentação das bateladas

respectivamente.

0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000

0.05

0.1

0.15

0.2

Geração

Figura 5-3: Evolução do desempenho do critério de demanda de recebimento

RESULTADOS OBTIDOS

0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000

-1

-0.5

0.5

Geração

Figura 5-4: Evolução do desempenho do critério de demanda de fornecimento

0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000

0.3

0.35

0.4

0.45

0.5

0.55

0.6

0.65

0.7

Geração

Figura 5-5: Evolução do desempenho do critério de minimização do tempo

0 500 1000 1500 2000 2500 3000 3500 4000 4500 5000

0.25

0.3

0.35

0.4

0.45

0.5

0.55

0.6

Geração

Figura 5-6: Evolução do desempenho do critério de minimização da fragmentação

Para a população final é aplicado o algoritmo apresentado no capítulo 3 para a

identificação das soluções de Pareto. Para uma população de 20 indivíduos, foram obtidas 3

RESULTADOS OBTIDOS

soluções consideradas de Pareto. A Tabela 5-10 mostra o indivíduo e o desempenho de cada

objetivo.

Tabela 5-10: Desempenho dos objetivos das soluções de Pareto

Indivíduo Demanda de

recebimento

Demanda de

fornecimento

Tempo Fragmentação

1 0 0 0,35 0,26

7 0,11 0 0,44 0,24

9 0,16 0 0,58 0,18

De acordo com a definição, uma solução de Pareto não pode ser dominada por outras

soluções em um conjunto de soluções. Uma solução domina uma outra se os desempenhos

dos objetivos não forem piores que a outra solução e que pelo menos um objetivo seja melhor.

As 3 soluções apresentadas mostram que não são soluções dominadas por ninguém, já que em

algum objetivo uma solução acaba sendo superada por outra e por isso são consideradas de

Pareto. A figura 5-7 mostra a distribuição das bateladas ao longo do horizonte de

programação como exemplo de solução de Pareto do sétimo indivíduo.

RESULTADOS OBTIDOS

Figura 5-7: Solução de Pareto para o indivíduo 7

As figuras mostram que houve uma rápida convergência. Os resultados encontrados

são bastante satisfatórios e validam o modelo proposto. Os critérios foram atendidos em quase

toda a sua totalidade. AGs mostram que podem ser ferramentas potenciais de otimização. Um

AG não garante um ótimo global, mas boas soluções podem ser encontradas com um esforço

e tempo computacional menor, conforme mostrado. A implementação da estratégia de

formação de casta elitista permitiu se obter 3 soluções de Pareto para o problema em questão.

Apesar da complexibilidade do modelo, a implementação pode ser considerada

simples. O bom desempenho da rede está associado à capacidade de corrigir soluções

infactíveis. As funções reparadoras devem ser tratadas com atenção para evitar

inconsistências nas soluções durante as gerações.

5.2 ESTUDOS DE CASOS

Alguns estudos de caso serão apresentados nesta seção. Estes estudos têm a

finalidade de mostrar o desempenho da rede em problemas reais enfrentados nas operações

diárias de sistemas de distribuição de petróleo.

RESULTADOS OBTIDOS

Todos os estudos de caso terão os seguintes objetivos:

1. Minimizar o tempo de atendimento da demanda de recebimento.

2. Atender a demanda de recebimento no horizonte programado.

3. Atender a demanda de fornecimento de produtos.

4. Minimizar a quantidade de fragmentação no envio das bateladas.

A otimização global, local (por nó), ou unitária (por produto) dependerá dos pesos

associado a cada objetivo.

5.2.1 ESTUDO DE CASO 1

Este estudo de caso apresenta um problema relacionado ao atendimento a demanda

de recebimento em regime de urgência. Este caso pode ser associado a uma situação real

referente ao envio de QAV para atender a demanda de um aeroporto, por exemplo. Na

programação de demanda de recebimento é desejável a priorização do QAV de tal forma que

a demanda deste produto seja primeiramente atendida no menor tempo.

Para simular este caso, em cada terminal haverá a necessidade de receber um produto

no menor tempo possível, ou seja, haverá uma prioridade na minimização do tempo para a

entrega destes produtos nos terminais. Esta prioridade é configurada associando um peso ao

objetivo de minimização do tempo para atender a demanda de recebimento.

Abaixo são apresentados os produtos fornecidos por cada refinaria.

Tabela 5-11: Produtos produzidos

Nó Produtos

1 1;2

2 3;4

A demanda de recebimento é apresentada na Tabela 5-12.

RESULTADOS OBTIDOS

Tabela 5-12: Demanda de recebimento

Produtos

Nó

1 2 3 4

5 3 3 3 3

6 3 3 3 3

7 3 3 3 3

A demanda de fornecimento é apresentada na tabela abaixo.

Tabela 5-13: Demanda de fornecimento

Produtos

Nó

1 2 3 4

1 6 6 - -

2 - - 6 6

Abaixo são mostrados os valores de cada peso associado a cada objetivo global.

Tabela 5-14: Ponderação para os critérios globais

Critério Peso

Demanda de recebimento 3

Demanda de fornecimento 3

Tempo 3

Fragmentação 1

A Tabela 5-15 apresenta os pesos associados a cada produto para a minimização do

tempo de atendimento a demanda de recebimento.

RESULTADOS OBTIDOS

Tabela 5-15: Peso associado à minimização do tempo

Peso

Nó

Produto 1 Produto 2 Produto 3 Produto 4

1 0 0 0 0

2 0 0 0 0

3 0 0 0 0

4 0 0 0 0

5 0 0 3 0

6 0 3 0 0

7 0 0 0 3

Todos os demais pesos estão configurados com o valor zero. O estado inicial de cada

tanque nos nós é apresentado na tabela abaixo.

Tabela 5-16: Estado inicial dos tanques

Produtos

1 2 3 4

Nó

Min Atual Max Min Atual Max Min Atual Max Min Atual Max

1 0

10 0

2 0

10 0

3 0

10 0

4 0

10 0

5 0

6 0

7 0

6 0

O critério de parada desta simulação será o número de gerações, que neste caso será

de 50000 gerações.

Para as configurações descritas anteriormente, a Figura 5-8 mostra a distribuição de

cada produto nas conexões do melhor indivíduo ao longo horizonte de programação. O tempo

de execução para achar a solução foi de 2 minutos aproximadamente.

RESULTADOS OBTIDOS

Figura 5-8: Distribuição dos produtos do melhor indivíduo ao longo das conexões

O estado final de cada tanque em cada nó é apresentado na tabela abaixo.

Tabela 5-17: Estado final dos tanques

Produtos

1 2 3 4

Nó

Min Atual Max Min Atual Max Min Atual Max Min Atual Max

1 0

10 0

2 0

10 0

3 0

10 0

4 0

10 0

5 0

6 0

7 0

6 0

A tabela a seguir apresenta o desempenho de cada objetivo global do modelo.

RESULTADOS OBTIDOS

Tabela 5-18: Desempenho global dos objetivos

Critério Desempenho

Demanda de recebimento 0

Demanda de fornecimento 0

Tempo 0,32

Fragmentação 0,09

A Tabela 5-19 apresenta o desempenho de cada objetivo por produto do modelo para

a minimização do tempo de atendimento a demanda de recebimento.

Tabela 5-19: Desempenho dos objetivos para a minimização do tempo por produto

Desempenho

Nó

Produto 1 Produto 2 Produto 3 Produto 4

1 - - - -

2 - - - -

3 - - - -

4 - - - -

5 - - 0 -

6 - 0 - -

7 - - - 0

Primeiramente é possível perceber que a priorização no atendimento a demanda de

recebimento no menor tempo foi atendida já que os valores desses objetivos alcançaram o

valor zero. Através da Figura 5-8, pode ser visto que o produto 3 (vermelho) que era

prioridade de recebimento no nó 5 foi o primeiro a ser entregue através da conexão 6. Já o

produto 2 (verde), foi o primeiro a ser recebido no nó 6 através das conexões 7 e 9, como era

esperado. O produto 4 (amarelo) que tinha prioridade no recebimento foi o primeiro também a

ser entregue através da conexão 10.

Outro destaque neste resultado foi a minimização da fragmentação do envio que

atingiu o valor de 0,09, ou seja, as bateladas ocorreram quase que sequencialmente evitando

assim a degradação dos produtos nos envios.

RESULTADOS OBTIDOS

A Figura 5-9 mostra a evolução do fitness do melhor indivíduo.

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 10

0.05

0.1

0.15

0.2

0.25

Geração

Figura 5-9: Evolução do fitness do melhor indivíduo

As Figuras 5-10 a 5-13 mostram a evolução do desempenho do melhor indivíduo nos

seguintes critérios globais; atendimento a demanda de recebimento, demanda de

fornecimento, minimização do tempo e minimização da fragmentação das bateladas

respectivamente.

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 10

0.05

0.1

0.15

0.2

0.25

0.3

0.35

Geração

Figura 5-10: Evolução do desempenho do critério de demanda de recebimento

RESULTADOS OBTIDOS

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 10

-0.2

-0.15

-0.1

-0.05

0.05

0.1

0.15

0.2

Geração

Figura 5-11: Evolução do desempenho do critério de demanda de fornecimento

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 10

0.3

0.35

0.4

0.45

0.5

0.55

0.6

0.65

Geração

Figura 5-12: Evolução do desempenho do critério de minimização do tempo

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 10

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5

Geração

Figura 5-13: Evolução do desempenho do critério de minimização da fragmentação

RESULTADOS OBTIDOS

Não houve a ocorrência de soluções de Pareto na população final, ou seja, todas as

outras soluções são dominadas pela solução apresentada.

5.2.2 ESTUDO DE CASO 2

Este estudo de caso apresenta um problema relacionado a estoque meta. É comum

além de atender uma demanda de recebimento, manter um estoque mínimo nos tanques.

Sendo os nós 3 e 4 representativos de um parque de armazenagem, então faz sentido

estes nós possuírem um estoque meta. Para simular este caso, será configurada uma demanda

de recebimento para esses nós. Esse é um caso especial e por isso alguns artifícios devem ser

utilizados. O primeiro artifício como já descrito é configurar uma demanda de recebimento

para esses nós intermediários. O segundo artifício é permitir sobre demanda para esses nós, o

que não é permitido pelo modelo inicial, segundo restrição R2. Ou seja, a função reparadora

não deverá atuar nesses nós para o caso de sobre demanda. Nesta simulação, diferente das

anteriores, o produto 3 pode ser fornecido por ambas as refinarias.

Abaixo são apresentados os produtos fornecidos por cada refinaria.

Tabela 5-20: Produtos produzidos

Nó Produtos

1 1;2,3

2 3;4

A demanda de recebimento é apresentada na Tabela 5-21.

Tabela 5-21: Demanda de recebimento

Produtos

Nó

1 2 3 4

3 0 2 6 0

4 0 0 6 4

5 3 3 3 3

6 3 3 3 3

7 3 3 3 3

RESULTADOS OBTIDOS

A demanda de fornecimento é apresentada na tabela abaixo.

Tabela 5-22: Demanda de fornecimento

Produtos

Nó

1 2 3 4

1 6 6 6 -

2 - - 6 6

Abaixo são mostrados os valores de cada peso associado a cada objetivo global.

Tabela 5-23: Ponderação para os critérios globais

Critério Peso

Demanda de recebimento 3

Demanda de fornecimento 3

Minimização do tempo 3

Minimização da fragmentação 1

Para garantir que as demandas de recebimento nos terminais sejam atendidas, então

alguns pesos são associados a esses objetivos conforme mostrado na tabela abaixo.

Tabela 5-24: Peso associado à demanda de recebimento por nó

Nó Peso

1 0

2 0

3 0

4 0

5 3

6 3

7 3

Todos os demais pesos estão configurados com o valor zero.

O estado inicial de cada tanque nos nós é apresentado na tabela abaixo.

RESULTADOS OBTIDOS

Tabela 5-25: Estado inicial dos tanques

Produtos

1 2 3 4

Nó

Min Atual Max Min Atual Max Min Atual Max Min Atual Max

1 0

20 0

2 0

20 0

3 0

10 0

4 0

10 0

5 0

6 0

7 0

6 0

O critério de parada desta simulação será o número de gerações, que neste caso será

de 50000 gerações.

A Figura 5-14 mostra a distribuição de cada produto nas conexões do melhor

indivíduo ao longo horizonte de programação. O tempo de execução foi de 2 minutos

aproximadamente.

Figura 5-14: Distribuição dos produtos do melhor indivíduo ao logo das conexões

RESULTADOS OBTIDOS

O estado final de cada tanque em cada nó é apresentado na tabela abaixo.

Tabela 5-26: Estado final dos tanques

Produtos

1 2 3 4

Nó

Min Atual Max Min Atual Max Min Atual Max Min Atual Max

1 0

20 0

2 0

20 0

3 0

10 0

4 0

10 0

5 0

6 0

7 0

6 0

A tabela abaixo apresenta o desempenho dos objetivos globais do modelo após

50000 gerações.

Tabela 5-27: Desempenho global dos objetivos

Critério Desempenho

Demanda de recebimento 0

Demanda de fornecimento 0

Tempo 0,38

Fragmentação 0,35

A Tabela 5-28 apresenta o desempenho de cada objetivo por produto para a

minimização do tempo de atendimento a demanda de recebimento.

RESULTADOS OBTIDOS

Tabela 5-28: Desempenho dos objetivos de demanda de recebimento por nó

Nó Desempenho

1 -

2 -

3 -

4 -

5 0

6 0

7 0

A Figura 5-15 mostra a evolução do fitness do melhor indivíduo.

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 10

0.06

0.08

0.1

0.12

0.14

0.16

0.18

0.2

0.22

Geração

Figura 5-15: Evolução do fitness do melhor indivíduo

As figuras abaixo mostram a evolução do desempenho do melhor indivíduo nos

seguintes critérios globais; atendimento a demanda de recebimento, demanda de

fornecimento, minimização do tempo e minimização da fragmentação das bateladas

respectivamente.

RESULTADOS OBTIDOS

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 10

0.05

0.1

0.15

0.2

0.25

Geração

Figura 5-16: Evolução do desempenho do critério de demanda de recebimento

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 10

-0.2

-0.15

-0.1

-0.05

0.05

0.1

0.15

0.2

Geração

Figura 5-17: Evolução do desempenho do critério de demanda de fornecimento

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 10

0.3

0.35

0.4

0.45

0.5

0.55

0.6

Geração

Figura 5-18: Evolução do desempenho do critério de minimização do tempo

RESULTADOS OBTIDOS

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 10

0.35

0.4

0.45

0.5

Geração

Figura 5-19: Evolução do desempenho do critério de minimização da fragmentação

O resultado obtido é bastante satisfatório principalmente porque a quantidade de

produtos disponíveis era igual à soma de toda a demanda de recebimento, o que acaba

dificultando, em alguns casos, o atendimento total deste objetivo. O estoque meta foi atingido

com sucesso sem prejudicar a demanda de cada terminal.

Foram obtidas 5 soluções consideradas de Pareto na população final. As tabelas 5-29

e 5-30 abaixo mostram a identificação do indivíduo e o desempenho dos seus objetivos

globais e por nó respectivamente.

Tabela 5-29: Desempenho dos objetivos globais das soluções de Pareto

Indivíduo Demanda de

recebimento

Demanda de

fornecimento

Tempo Fragmentação

1 0 0 0,35 0,35

6 0,21 0 0,64 0,25

7 0,2 0 0,64 0,34

15 0,23 0 0,59 0,32

16 0,26 0 0,58 0,34

RESULTADOS OBTIDOS

Tabela 5-30: Desempenho dos objetivos de demanda de recebimento por nó das soluções de Pareto

Indivíduo Nó 1 Nó 2 Nó 3 Nó 4 Nó 5 Nó 6 Nó 7

1 - - - - 0 0 0

6 - - - - 0,08 0,16 0,16

7 - - - - 0,25 0 0,25

15 - - - - 0,41 0 0,16

16 - - - - 0,16 0 0,16

A solução do indivíduo 16 é mostrada como exemplo na Figura 5-20.

Figura 5-20: Solução de Pareto para o indivíduo 16

As Tabelas 5-29 e 5-30 mostram que não existe dominância entre as soluções

apresentadas e por isso são consideradas soluções de Pareto.

5.2.3 ESTUDO DE CASO 3

Este caso visa apresentar um problema de desabastecimento de um determinado

produto. Um desabastecimento pode ocorrer pelo aumento de demanda não previsto, por um

RESULTADOS OBTIDOS

problema na produção ou por qualquer outro fator. Quando a demanda se torna maior que a

produção, então deve se priorizar o atendimento desta demanda. A priorização da demanda é

uma decisão estratégica nesse cenário e é decidida de acordo com os interesses da corporação.

Para simular este caso, será configurada uma quantidade de produtos disponíveis

menor que a demanda, e neste caso haverá uma priorização de atendimento a demanda do

produto faltante em um determinado terminal.

Abaixo são apresentados os produtos fornecidos por cada refinaria.

Tabela 5-31: Produtos produzidos

Nó Produtos

1 1;2

2 3;4

A demanda de recebimento apresentada na Tabela 5-32.

Tabela 5-32: Demanda de recebimento

Produtos

Nó

1 2 3 4

5 3 3 3 3

6 3 3 3 3

7 3 3 3 3

A demanda de fornecimento é apresentada na tabela abaixo.

Tabela 5-33: Demanda de fornecimento

Produtos

Nó

1 2 3 4

1 6 6 - -

2 - - 6 6

Abaixo são mostrados os valores de cada peso associado a cada objetivo global.

RESULTADOS OBTIDOS

Tabela 5-34: Ponderação para os critérios globais

Critério Peso

Demanda de recebimento 3

Demanda de fornecimento 3

Minimização do tempo 3

Minimização da fragmentação 1

A Tabela 5-35 apresenta os pesos associados a cada produto para o atendimento a

demanda de recebimento. O desabastecimento acontecerá para o produto 1 e por isso terá um

peso associado ao objetivo de atendimento a demanda.

Tabela 5-35: Peso associado à demanda de recebimento por produto

Peso

Nó

Produto 1 Produto 2 Produto 3 Produto 4

1 0 0 0 0

2 0 0 0 0

3 0 0 0 0

4 0 0 0 0

5 0 0 0 0

6 0 0 0 0

7 5 0 0 0

Além de priorizar a entrega do produto 1 no nó 7, haverá uma priorização também

para atender toda demanda de recebimento deste nó conforme mostrado na Tabela 5-36. Nesta

tabela, todos os demais pesos estão configurados com o valor zero

RESULTADOS OBTIDOS

Tabela 5-36: Peso associado à demanda de recebimento por nó

Nó Peso

1 0

2 0

3 0

4 0

5 0

6 0

7 3

O estado inicial de cada tanque nos nós é apresentado na tabela abaixo.

O critério de parada desta simulação será o número de gerações, que neste caso será

de 50000 gerações.

Tabela 5-37: Estado inicial dos tanques

Produtos

1 2 3 4

Nó

Min Atual Max Min Atual Max Min Atual Max Min Atual Max

1 0

10 0

2 0

10 0

3 0

10 0

4 0

10 0

5 0

6 0

7 0

6 0

A figura a seguir mostra a distribuição de cada produto nas conexões do melhor

indivíduo ao longo horizonte de programação. O tempo de execução foi de 2 minutos

aproximadamente.

RESULTADOS OBTIDOS

Figura 5-21: Distribuição dos produtos do melhor indivíduo ao logo das conexões

O estado final de cada tanque em cada nó é apresentado na tabela abaixo.

Tabela 5-38: Estado final dos tanques

Produtos

1 2 3 4

Nó

Min Atual Max Min Atual Max Min Atual Max Min Atual Max

1 0

20 0

2 0

20 0

3 0

10 0

4 0

10 0

5 0

6 0

7 0

6 0

A tabela abaixo apresenta o desempenho de cada objetivo global do modelo após

50000 gerações.

RESULTADOS OBTIDOS

Tabela 5-39: Desempenho global dos objetivos

Critério Desempenho

Demanda de recebimento 0,05

Demanda de fornecimento 0

Tempo 0,32

Fragmentação 0

As tabelas abaixo apresentam os desempenhos dos objetivos de atendimento à

demanda de recebimento por produto e por nó.

Tabela 5-40: Desempenho dos objetivos para demanda de recebimento por produto

Desempenho

Nó

Produto 1 Produto 2 Produto 3 Produto 4

1 - - - -

2 - - - -

3 - - - -

4 - - - -

5 - - - -

6 - - - -

7 0 - - -

Tabela 5-41: Desempenho dos objetivos para demanda de recebimento por nó

Nó Desempenho

1 -

2 -

3 -

4 -

5 -

6 -

7 0

RESULTADOS OBTIDOS

As figuras abaixo mostram a evolução do desempenho do melhor indivíduo do

fitness e dos seguintes critérios globais; atendimento a demanda de recebimento, demanda de

fornecimento, minimização do tempo e minimização da fragmentação das bateladas

respectivamente.

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 10

0.06

0.08

0.1

0.12

0.14

0.16

0.18

Geração

Figura 5-22: Evolução do fitness do melhor indivíduo

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 10

0.05

0.1

0.15

0.2

0.25

Geração

Figura 5-23: Evolução do desempenho do critério de demanda de recebimento

RESULTADOS OBTIDOS

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 10

-0.2

-0.15

-0.1

-0.05

0.05

0.1

0.15

0.2

Geração

Figura 5-24: Evolução do desempenho do critério de demanda de fornecimento

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 10

0.3

0.35

0.4

0.45

0.5

0.55

0.6

0.65

0.7

Geração

Figura 5-25: Evolução do desempenho do critério de minimização do tempo

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 10

0.05

0.1

0.15

0.2

0.25

0.3

0.35

0.4

Geração

Figura 5-26: Evolução do desempenho do critério de minimização da fragmentação

RESULTADOS OBTIDOS

O modelo desenvolvido e o método de otimização implementado mostram-se

bastante consistentes já que mais uma vez os objetivos foram atingidos em sua maioria.

Apenas a minimização do tempo não foi plenamente atendida sendo a razão já explicada no

tópico sobre a validação do modelo. Devido à escassez do produto 1, a demanda de

recebimento do nó 5 não pode ser totalmente atendida. Como pode ser visto, o fitness do

melhor indivíduo ficou muito próximo de zero com o valor de 0,06. Isso mostra estar muito

próximo ao valor ótimo para o modelo, como pode ser visto na Figura 5-22.

Nessa simulação foram obtidas duas soluções consideradas de Pareto na população

final sendo mostrado a identificação do indivíduo e o valor dos seus objetivos globais e por nó

respectivamente.

Tabela 5-42: Desempenho dos objetivos globais das soluções de Pareto

Indivíduo Demanda de

recebimento

Demanda de

fornecimento

Tempo Fragmentação

1 0,05 0 0,33 0

2 0,05 0 0,32 0,02

Tabela 5-43: Desempenho dos objetivos por nó das soluções de Pareto para demanda de recebimento

Indivíduo Nó 1 Nó 2 Nó 3 Nó 4 Nó 5 Nó 6 Nó 7

1 - - - - - - 0

2 - - - - - - 0

Ambas as soluções de Pareto obtiveram o valor zero para o objetivo de atendimento

a demanda de recebimento para o produto 1 no nó 7, mas a Tabela 5-42 mostra que não existe

dominância entre as soluções já que uma delas apresentou melhor desempenho na

minimização do tempo e a outra na minimização da fragmentação. A solução do indivíduo 2 é

mostrada na figura a seguir.

RESULTADOS OBTIDOS

Figura 5-27: Solução de Pareto para o indivíduo 2

Esta solução é muito próxima da melhor solução havendo apenas uma pequena

melhora na minimização do tempo.

5.2.4 ESTUDO DE CASO 4

Este estudo de caso tem por objetivo mesclar as necessidades de cada estudo

apresentado para mostrar a robustez do modelo. Mesmo em situações adversas ainda é

possível encontrar boas soluções.

Abaixo são apresentados os produtos fornecidos por cada refinaria.

Tabela 5-44: Produtos produzidos

Nó Produtos

1 1;2,3

2 3;4

A demanda de recebimento é apresentada na tabela 5-45.

RESULTADOS OBTIDOS

Tabela 5-45: Demanda de recebimento

Produtos

Nó

1 2 3 4

3 0 2 6 0

4 0 0 6 4

5 3 3 3 3

6 3 3 3 3

7 3 3 3 3

A demanda de fornecimento é apresentada na tabela abaixo.

Tabela 5-46: Demanda de fornecimento

Produtos

Nó

1 2 3 4

1 6 6 6 -

2 - - 6 6

Abaixo são mostrados os valores de cada peso associado a cada objetivo global.

Tabela 5-47: Ponderação para os critérios globais

Critério Peso

Demanda de recebimento 3

Demanda de fornecimento 3

Tempo 3

Fragmentação 1

Para garantir que as demandas de recebimento nos terminais sejam atendidas, então

alguns pesos são associados aos objetivos de atendimento à demanda nos terminais conforme

mostrado na tabela a seguir.

RESULTADOS OBTIDOS

Tabela 5-48: Peso associado à demanda de recebimento por nó

Nó Peso

1 0

2 0

3 0

4 0

5 0

6 0

7 3

A Tabela 5-49 apresenta os pesos associados a cada produto para a demanda de

recebimento.

Tabela 5-49: Peso associado à demanda de recebimento por produto

Peso

Nó

Produto 1 Produto 2 Produto 3 Produto 4

1 0 0 0 0

2 0 0 0 0

3 0 0 0 0

4 0 0 0 0

5 0 0 0 0

6 0 0 0 0

7 5 0 0 0

A Tabela 5-50 apresenta os pesos associados a cada produto para a minimização do

tempo de atendimento a demanda de recebimento.

RESULTADOS OBTIDOS

Tabela 5-50: Peso associado à minimização do tempo por produto

Peso

Nó

Produto 1 Produto 2 Produto 3 Produto 4

1 0 0 0 0

2 0 0 0 0

3 0 0 0 0

4 0 0 0 0

5 0 0 3 0

6 0 3 0 0

7 0 0 0 3

Todos os demais pesos estão configurados com o valor zero.

O estado inicial de cada tanque nos nós é apresentado na tabela abaixo.

Tabela 5-51: Estado inicial dos tanques

Produtos

1 2 3 4

Nó

Min Atual Max Min Atual Max Min Atual Max Min Atual Max

1 0

20 0

2 0

20 0

3 0

10 0

4 0

10 0

5 0

6 0

7 0

6 0

O critério de parada desta simulação será o número de gerações, que neste caso será

de 50000 gerações. O resultado da simulação é apresentado na Figura 5-28.

RESULTADOS OBTIDOS

Figura 5-28: Distribuição dos produtos do melhor indivíduo ao logo das conexões

O estado final de cada tanque em cada nó é apresentado na tabela abaixo.

Tabela 5-52: Estado final dos tanques

Produtos

1 2 3 4

Nó

Min Atual Max Min Atual Max Min Atual Max Min Atual Max

1 0

20 0

2 0

20 0

3 0

10 0

4 0

10 0

5 0

6 0

7 0

6 0

A tabela abaixo apresenta os valores de cada objetivo global do modelo após 50000

gerações.

RESULTADOS OBTIDOS

Tabela 5-53: Desempenho global dos objetivos

Critério Desempenho

Demanda de recebimento 0,03

Demanda de fornecimento 0

Tempo 0,32

Fragmentação 0,15

A Tabela 5-54 apresenta os valores de cada objetivo por produto do modelo para a

minimização do tempo de atendimento a demanda de recebimento.

Tabela 5-54: Desempenho dos objetivos de demanda de recebimento por nó

Nó Desempenho

1 -

2 -

3 -

4 -

5 -

6 -

7 0

São apresentados os valores de cada objetivo por produto do modelo para o

atendimento à demanda de recebimento e minimização do tempo respectivamente.

Tabela 5-55: Desempenho para a demanda de recebimento por produto

Desempenho

Nó

Produto 1 Produto 2 Produto 3 Produto 4

1 - - - -

2 - - - -

3 - - - -

4 - - - -

5 - - - -

6 - - - -

7 0 - - -

RESULTADOS OBTIDOS

100

Tabela 5-56: Desempenho para a minimização do tempo por produto

Desempenho

Nó

Produto 1 Produto 2 Produto 3 Produto 4

1 - - - -

2 - - - -

3 - - - -

4 - - - -

5 - - 0 -

6 - 0 - -

7 - - - 0

As figuras abaixo mostram a evolução do desempenho do melhor indivíduo do

fitness e dos seguintes critérios globais; atendimento a demanda de recebimento, demanda de

fornecimento, minimização do tempo e minimização da fragmentação das bateladas

respectivamente.

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 10

0.04

0.06

0.08

0.1

0.12

0.14

0.16

0.18

0.2

Geração

Figura 5-29: Evolução do fitness do melhor indivíduo

RESULTADOS OBTIDOS

101

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 10

0.05

0.1

0.15

0.2

0.25

0.3

0.35

Geração

Figura 5-30: Evolução do desempenho do critério de demanda de recebimento

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 10

-0.2

-0.15

-0.1

-0.05

0.05

0.1

0.15

0.2

Geração

Figura 5-31: Evolução do desempenho do critério de demanda de fornecimento

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 10

0.3

0.35

0.4

0.45

0.5

0.55

0.6

0.65

0.7

Geração

Figura 5-32: Evolução do desempenho do critério de minimização do tempo

RESULTADOS OBTIDOS

102

0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5

x 10

0.15

0.2

0.25

0.3

0.35

0.4

0.45

0.5

Geração

Figura 5-33: Evolução do desempenho do critério de minimização da fragmentação

A demanda de recebimento do produto 1 no nó 5 não foi atendida pelo fato de estar

sendo simulado um desabastecimento. O estoque meta bem como a prioridade na

minimização do tempo de envio dos produtos foram atendidos. Os resultados da simulação

mostram que o modelo é robusto de tal maneira a encontrar uma solução muito próxima da

ótima, já que o valor do fitness do melhor indivíduo foi de 0,045. A evolução do fitness pode

ser vista na Figura 5-29.

Nesta simulação foram obtidas 2 soluções consideradas de Pareto na população final,

sendo mostrado a identificação do indivíduo e o desempenho dos seus objetivos globais na

Tabela 5-57.

Tabela 5-57: Desempenho dos objetivos globais das soluções de Pareto

Indivíduo Demanda de

recebimento

Demanda de

fornecimento

Tempo Fragmentação

1 0,03 0 0,32 0,15

5 0,125 0 0,44 0,13

Apenas com os resultados do desempenho dos objetivos globais já é possível

comprovar que as soluções podem ser consideradas de Pareto já que não existe dominância

entre elas. Em quanto o indivíduo 1 tem melhores resultados para a demanda de recebimento

RESULTADOS OBTIDOS

103

e minimização do tempo, o indivíduo 5 possui melhor resultado para a minimização da

fragmentação das bateladas.

A solução do indivíduo 5 é apresentada na figura abaixo.

Figura 5-34: Solução de Pareto para o indivíduo 5

CAPÍTULO 6

6 CONCLUSÃO

6.1 COMENTÁRIOS FINAIS

A programação da produção e alocação de tarefas continua sendo um problema atual,

e sendo um mercado dinâmico em que a tomada de decisão precisa ser rápida, boas soluções

devem ser encontradas em um curto espaço de tempo. A busca pela solução ótima demanda

elevado esforço computacional e conseqüentemente tempo. AGs vêm de encontro a esse

problema já que é capaz de fornecer boas solução em tempo hábil. Muitos objetivos devem

ser satisfeitos dentro da programação da produção e por isso faz-se necessário o uso da

otimização multiobjetivo. A vantagem para o uso e desenvolvimento desse procedimento é o

tratamento simultâneo de todos os objetivos identificados no problema buscando a solução de

melhor compromisso neste cenário.

Esta dissertação apresentou uma modelagem de um problema de distribuição de

derivados de petróleo através de uma rede de dutos. A rede proposta é uma simplificação de

uma rede real. O método proposto foi baseado na utilização de Algoritmo Genéticos com

elitismo, técnica de ranqueamento e formação de nicho, o qual garante ao final da evolução

um conjunto de boas soluções em relação aos diferentes objetivos do problema de otimização.

Ao término das gerações, selecionam-se as soluções ótimas de Pareto por serem consideradas

as melhores soluções. O método do critério global foi utilizado, pois através dele uma função

objetivo única é formulada, facilitando a busca pelas soluções “ótimas”. O método das

ponderações permitiu a elaboração de um método sistemático para a inserção de prioridades

no modelo. O uso de penalidades mostrou-se uma boa estratégia para evitar inconsistências no

cálculo do desempenho dos objetivos conforme foi mostrado nos casos de minimização do

tempo. Para estes casos, o não cumprimento da demanda pode mascarar o resultado do

desempenho, visto que a normalização do tempo leva em conta a ultima batelada recebida, ou

seja, o não cumprimento de uma demanda pode levar a um bom desempenho na minimização

do tempo. Sendo assim, corre-se o risco de prejudicar a convergência do modelo.

RESULTADOS OBTIDOS

105

O tratamento das restrições via função reparadora foi uma contribuição essencial

para evitar soluções infactíveis. Através do método recursivo proposto nesta dissertação,

restrições deixaram de serem vista como objetivo e puderam ser corrigidas dinamicamente

sem depender da evolução do modelo. Restrições que tornam uma resposta infactível devem

ser corrigidas no momento em que é detectada, pois se tratadas como objetivo corre-se o risco

de inviabilizar a busca por uma solução ótima. Por exemplo, o não cumprimento de uma

demanda torna a resposta infactível do ponto de vista dos objetivos, mas um tanque contendo

produto acima da capacidade torna-se irreal e não aplicável.

Os resultados apresentados no capítulo 5 mostram que em um curto espaço de tempo

o modelo é capaz de convergir e boas soluções são obtidas. A conexão 6 neste trabalho

representou uma conexão crítica visto que devido a sua extensão, representada por uma

elevada distância em unidades de tempo, era necessário que ela estivesse 100% do tempo

ocupada para o atendimento da demanda dentro do horizonte de tempo programado. Mesmo

assim, as demandas de recebimento foram atendidas. Para a otimização global, tendo como

prioridade a minimização do tempo não foi possível atingir desempenho próximo a zero, pois

a situação considerada ótima para o menor tempo é o atendimento da demanda de

recebimento de um produto. Como em cada terminal, sempre existia demanda de recebimento

para mais de um produto então não foi possível atingir o valor ótimo. Isso não significa que o

tempo não foi minimizado, os resultados mostram o contrário.

Como contribuição final, o trabalho confirmou resultados da literatura, que

estabelecem que algoritmos genéticos podem e devem ser aplicados na resolução de

problemas complexos como a distribuição de petróleo e derivados. A utilização dessa

metodologia não demanda cálculos complexos e por isso proporciona relativa rapidez na

obtenção de boas soluções, o que é primordial em operação de plantas reais como uma malha

de dutos.

Quando não existe a utilização de bibliotecas com algoritmos já implementados,

como é o caso desse trabalho, então a disciplina da boa programação é essencial para deixar o

código rápido e enxuto. O conhecimento detalhado do problema a ser modelado, neste caso

RESULTADOS OBTIDOS

106

permite a escolha de estruturas cromossômicas que facilitem a implementação e a busca das

soluções como é o caso das estruturas de máscaras utilizadas nesta dissertação.

6.2 TRABALHOS FUTUROS

Conforme já explicado nos capítulos 4 e 5, as soluções de Pareto são consideradas as

melhores segundo cada um dos critérios que formam o problema de otimização multi-

objetivo. Neste trabalho, a otimalidade de Pareto não foi utilizada na evolução do conjunto

final de soluções. Apenas, a população da casta elitista é submetida a uma seleção de Pareto.

Com isto, uma continuação natural deste trabalho seria a utilização de uma abordagem

baseada em soluções de Pareto para a seleção dos indivíduos juntamente com as técnicas de

elitismo, ranqueamento e formação de nicho, propostas nesta dissertação.

Também a modelagem proposta não contemplou o uso inteligente das conexões

bidirecionais e com isso não proporcionou um ganho real ao modelo, no que se refere à

utilização deste tipo de conexão. O uso racional dessas conexões é importante, uma vez que

elas são o gargalo de muitas operações em redes reais. Assim sugere-se uma modelagem mais

detalhada deste tipo de conexão, que permitam um uso eficaz e racional dessas conexões

bidirecionais no modelo desenvolvido.

REFERÊNCIAS BIBLIOGRÁFICAS

ALMEIDA, M. R. Programação Automática da Produção em Refinarias de Petróleo

utilizando Algoritmos Genéticos Rio de Janeiro, 2001. Dissertação de Mestrado Pontifícia

Universidade Católica do Rio de Janeiro.

ALMEIDA, M. R., HAMACHER & PACHECO M. A. C. Algoritmos Genéticos para

Programação Automática da Produção em Refinarias de Petróleo. Artigo não publicado.

Pontifícia Universidade Católica do Rio de Janeiro, 2000, 15 p.

ARRUDA, L. V. R.; SWIECH, M. C. S.; NEVES – JR, F. & DELGADO, M. R., Um Método

evolucionário para sintonia de controladores PID em processos multivariáveis, artigo

submetido para publicação, Universidade Tecnológica Federal do Paraná, 2006.

ASPENTECH. http://www.aspentech.com. Página visitada em Dez/2005

BALLINTIJN, K. Optimization in Refinery Scheduling: Modeling and Solution. In

Optimization in Industry. Mathematical Programming and Modeling Techniques in Practice,

v. 1, p. 191–199. John Wiley & Sons, Chichester, England, 1993.

BARBOZA, A. O., Simulação e técnicas da computação evolucionária aplicadas a problemas

de programação linear inteira mista. Tese de doutorado. Universidade Tecnológica Federal do

Paraná, 2005.

BENNETT, A. P. Finite population effects for ranking and tournament selection. Complex

Systems, v11, p.1-24, 1997.

BODINGTON, C. E. & SHOBRYS, D. E. Planning, Scheduling and Control Integration in

the Process Industries 1a Edição, McGraw-Hill, New York, NY, EUA, 414 p, 1995.

REFERÊNCIAS BIBLIOGRÁFICAS

108

CASTILHO, V. C. Otimização de componente de Concreto Pré-moldado Protendidos

Mediante Algoritmos Genéticos. Tese de doutorado. Escola de Engenharia de São Carlos, São

Paulo, 2003.

CASTRO, H. P., Utilização de Algoritmos Genéticos para Solução de Problema de

Programação de Produção de uma Refinaria de Petróleo. Dissertação de mestrado.

Universidade Federal de Santa Catarina, 2001.

CHAMBERS, Lance. Practical Handbook of Genetic Algorithms - Applications Volume I 1a

Edição, CRC Press, Boca Raton, FL, EUA, 555p, 1995.

COELLO, C. A. C. An Updated Survey of Evolutionary Multiobjective Optimization

Techniques: State of the Art and Future Trends”, Proceedings of 1999 Congress on

Evolutionary Computation, Washington D.C., IEEE Press, p. 3-13, 1999.

COELLO, C. A. & CHRISTIANSEN, A. D. “An Approach to Multiobjective Optimization

Using Genetic Algorithms”, In Dagli, C. H., Akay, M., Chen, C. L. P., Fernández, B. R., and

Ghosh, J. (editors), Intelligent Engineering Systems Through Artificial Neural Networks, V.

5, p. 411-416, ASME Press, St. Louis Missouri, USA, November, 1995.

COELHO, L. S. & COELHO, A. A. R. Algoritmos evolutivos em identificação e controle de

processos: uma visão integrada e perspectivas. SBA Controle & Automação, v. 10, n. 01,

1999.

COLEY, D. A. An introduction to genetic algorithms for scientists and engineers. Singapore,

World Scientific, 1999.

CRITICAL CONTROL. http://www.criticalcontrol.com. Página visitada em Nov/2005

CUTTING, G.A.G & HAVERLY, C.A. A System for Optimizing the Scheduling and

Blending of Crudes 1995 NPRA Computer Conference Annual Meeting. San Francisco,

California, National Petroleum Refiners Association 1995, 7 p.

REFERÊNCIAS BIBLIOGRÁFICAS

109

CRUZ, J.M., ANDRÉS-TORO, B., HERRÁN, A., BESADA, E. P. & BLANCO, P. F.

Multiobjective optimization of the transport in oil pipeline networks. IEEE International

Conference on Emerging Technologies and Factory Automation, 1:566-573, 2003.

DEB, K. Evolutionary Algorithms for Multi-Criterion Optimiza-tion in Engineering Design.

In Proceedings of Evolutionary Algorithmsin Engineering and Computer Science

(EUROGEN’99), 1999

FABRO, J. A. Uma abordagem neuro-nebulosa para controle preditivo de processos multi-

estágios. Tese de doutorado, Centro Federal de Educação Tecnologia do Paraná, Curitiba,

2003.

GARCIA, J.M.C., MARTIN, J.L.R.,GONZALES, A.H. & BLANCO, P.F. Hybrid heuristic

and mathematical programming in oil pipelines networks. IEEE Congress on Evolutionary

Computation, Vol.2, pp 1479 - 1486, 2004.

GEN, M. & CHENG, R. Genetic algorithms and engineering design. New York, John Wiley,

1997.

GOLDBARG, E. F. G; CASTRO, M. P. & GOLDBARG, M. C. A., A Transgenetic algorithm

for the gas network pipe sizing problem. Proceedings of International Conference on

Computational Methods, pp 80 – 84, 2004.

GOLDBERG, D. E. Genetic algorithm in search, optimization and machine learning.

Reading, USA, Addison-Wesley Publishing, 1989.

GRAU, R.; GRAELLS, J.; COROMINAS, A.; ESPUÑA, A. & PUIGJANER, L. Global

Strategy for Energy and Waste Analysis in Scheduling and Planning of Multiproduct Batch

Chemical Processes. Computer and Chemical Engineering, V.20, p.853-868, 1996.

REFERÊNCIAS BIBLIOGRÁFICAS

110

GUPTA, A.K. & SIVAKUMAR, A.I. Simulation based multiobjective schedule optimization

in semiconductor manufacturing. Proceed. of the 2002 Winter Simulation Conference, 2002.

HAVERLY. http://www.haverly.com. Página visitada em Dez/2005.

HOLLAND, J. H. Adaptation in natural and artificial systems. AnnArbor, University of

Michigan Press, 1975.

INGENIOUS. http://www.ingenious.cc. Página visitada em Nov/2005

JOLY, M. & PINTO, J. M. Scheduling Optimization of Fuel Oil and Asphalt Production. 2nd

European Congress on Chemical Engineering, Montepellier, França, 1999.

KALLRATH, J. & WILSON, J. M., Business Optimisation Using Mathematical

Programming. 1st Edition ed. Macmillian Press, 1997.

KONDILI, E.; PANTELIDES, C.C. & SARGENT, R.W.H. A General Algorithm for Short

term Scheduling of Batch Operations - I. MILP Formulation. Computer and Chemical

Engineering, v.17, p.211-227, 1993.

KUDVA, G.; ELKAMEL, A.; PEKNY, J.F. & REKLAITIS, G.V. Heuristic Algorithm for

Scheduling Batch and Semi-Continuous Plants with Productions Deadlines, Intermediate

Storage Limitations and Equipment Changeover Costs. Computer and Chemical Engineering,

v.18, n.9, p.859-875, 1994.

LEMONGE, A.C. C. Aplicação de algoritmos genéticos em otimização estrutural. Tese de

Doutorado, Universidade Federal do Rio de Janeiro, 1999.

LOUREIRO, F. M., Desenvolvimento de um Gerador de "Scheduling" para uma Indústria de

Produção sob Encomenda: Uma Abordagem Baseada no Uso de Controladores Difusos e

Algoritmos Genéticos. Dissertação de Mestrado, Universidade Federal de Santa Catarina,

Florianópolis, 1997.

REFERÊNCIAS BIBLIOGRÁFICAS

111

MAGALHÃES, M.V.O.; MORO, L.F.L.; SMANIA, P.; HASSIMOTO, M.K.; PINTO, J.M.;

& ABADIA, G.J. SIPP - A Solution for Refinery Scheduling. NPRA Computer Conference,

San Antonio (EUA), 1998.

MAGATÃO, L. Programação Matemática Aplicada à Otimização das Operações de um

Poliduto. Dissertação de Mestrado - Centro Federal de Educação Tecnologia do Paraná, 2001.

MICHALEWICZ, Z. Genetic algorithms + data structures = evolution programs. 3. ed.

Springer-Verlag, New York, 1996.

MICHALEWICZ, Z. & FOGEL D.B., “How to Solve It: Modern Heuristics” Springer-

Verlag, 467 pp, 2000.

MICHALEWICZ, Z. & SCHOENAUER, M. Evolutionary Algorithms for Constrained

Parameter Optimization Problems. Evolutionary Computation, 4(1): p.1-32, 1996.

MORO, L.F.L. Técnicas de Otimização Mista-Inteira para o Planejamento e Programação de

Produção em Refinarias de Petróleo. Tese de Doutorado. Escola Politécnica da Universidade

de São Paulo, SP, Brasil, 2000.

MOURA, L. Um Algoritmo Genético para Otimização Multiobjetivo Fuzzy. Dissertação de

mestrado. Universidade Estadual de Campinas, São Paulo, 2002.

PALISADE. http://www.palisade.com. Página visitada em Nov/2005

PEGDEN,C.D., SHANON, R.E. & SADOWSY4 R. Introduction to Simulation Using

SIMAN McGraw-Hilt New Jersey, 1990.

PENKNY, J.F. & ZENTNER, M. G.; Learning to solve process scheduling problems: the role

of rigorous knowledge acquisition frameworks. In Foundation of Computer Aided Process

Operations; Rippin, D.W.T., Hale J.C., Davis, J.F, Eds; CACHE, Austin (TX), pp 275-309,

1994

REFERÊNCIAS BIBLIOGRÁFICAS

112

PEKNY, J.F.; MILLER, D.L. & MCRAE, G.J. An Exact Parallel Algorithm for Scheduling

when Production Costs Depend on Consecutive System States. and Chemical

Engineering,v.14, n.9, p.1009-1023, 1990.

PELHAM, R. & PHARRIS, C., Refinery Operations and Control – A Future Vision 1996

NPRA Computer Conference Annual Meeting. San Antonio, Texas, NPRA 1996, 16 p.

PINTO, J. M. Planejamento e programação de operações de produção e distribuição em

refinarias de petróleo. Tese de livre docência, Escola Politécnica da Universidade de São

Paulo, SP, Brasil, 2000.

PINTO, J.M. & GROSSMANN, I.E. A Continuous Time Mixed Integer Linear Programming

Model for Short Term Scheduling of Multistage Batch Plants. Industrial & Engineering

Chemistry Research. v.34, p.3037-3051, 1995.

REKLAITIS, G. V., Overview of Scheduling and Planning of Batch Process Operations.

Fourth International Symposium on Process System Engineering, Montebello, Quebec,

Canada, 1991.

SHAH, N.; PANTELIDES, C.C. & SARGENT, R.W.H. A General Algorithm for Short Term

Scheduling of Batch Operations – II Computational Issues. Computer and Chemical

Engineering v.17, n.2, p.229-244, 1993.

STEBEL, S. L. Modelagem da Estocagem e Distribuição de GLP de uma Refinaria de

Petróleo. Dissertação de Mestrado. Centro Federal de Educação Tecnologia do Paraná, 2001.

SWIECH, M. C. S. Algoritmos Genéticos para sintonia simultânea de Múltiplos controladores

em processos de refino. Dissertação de mestrado. Centro Federal de Educação Tecnológica do

Paraná, Curitiba, 2005.

REFERÊNCIAS BIBLIOGRÁFICAS

113

TANOMARU, J. Motivação, Fundamentos e Aplicações de Algoritmos Genéticos. II

Congresso Brasileiro de Redes Neurais, Curitiba, PR, Brasil, p. 373-403, 1995.

VON ZUBEN, F. J. Computação evolutiva: uma abordagem pragmática. I Jornada de Estudos

em Computação de Piracicaba e Região, v. 1, pp. 25-45, Piracicaba, 2000.

Livros Grátis
( http://www.livrosgratis.com.br )
 
Milhares de Livros para Download:
 
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas

Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
 
 