ads:
FUNDAÇÃO EDSON QUEIROZ
UNIVERSIDADE DE FORTALEZA
CENTRO DE CIÊNCIAS TECNOLÓGICAS
MESTRADO EM INFORMÁTICA APLICADA
Napoleão Vieira Nepomuceno
COMBINAÇÃO DE METAHEURÍSTICAS E PROGRAMAÇÃO
LINEAR INTEIRA: UMA METODOLOGIA HÍBRIDA APLICADA AO
PROBLEMA DE CARREGAMENTO DE CONTÊINER
Fortaleza
2006
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
FUNDAÇÃO EDSON QUEIROZ
UNIVERSIDADE DE FORTALEZA
CENTRO DE CIÊNCIAS TECNOLÓGICAS
MESTRADO EM INFORMÁTICA APLICADA
Napoleão Vieira Nepomuceno
COMBINAÇÃO DE METAHEURÍSTICAS E PROGRAMAÇÃO
LINEAR INTEIRA: UMA METODOLOGIA HÍBRIDA APLICADA AO
PROBLEMA DE CARREGAMENTO DE CONTÊINER
Dissertação apresentada ao Curso de
Mestrado em Informática Aplicada da
Universidade de Fortaleza como requisito
parcial para obtenção do Título de Mestre
em Informática.
Orientador: Prof. Dr. Plácido Rogério Pinheiro
Fortaleza
2006
ads:
iii
Napoleão Vieira Nepomuceno
COMBINAÇÃO DE METAHEURÍSTICAS E PROGRAMAÇÃO
LINEAR INTEIRA: UMA METODOLOGIA HÍBRIDA APLICADA AO
PROBLEMA DE CARREGAMENTO DE CONTÊINER
Data de Aprovação: ____/____/______
Banca Examinadora:
________________________________________________________
Prof. Plácido Rogério Pinheiro, D. Sc.
(Prof. Orientador – UNIFOR)
________________________________________________________
Prof. André Luís Vasconcelos Coelho, D. Sc
(Prof. Co-orientador – UNIFOR)
________________________________________________________
Prof. Dario José Aloise, D. Sc.
(Membro da Banca Examinadora – UFRN)
________________________________________________________
Prof. Antônio Clécio Fontelles Thomaz, D. Sc.
(Membro da Banca Examinadora – UECE)
iv
NEPOMUCENO, NAPOLEÃO VIEIRA
Combinação de Metaheurísticas e Programação Linear
Inteira: uma Metodologia Híbrida Aplicada ao Problema
de Carregamento de Contêiner [Fortaleza] 2006
58, p. 29,7 cm (INFORMÁTICA / UNIFOR,
Dissertação de Mestrado, 2006)
1. Corte e Empacotamento
2. Carregamento de Contêiner
3. Metaheurísticas
4. Programação Inteira
5. Algoritmos Híbridos
I. INFORMÁTICA / UNIFOR II. Título(Série)
v
Aos meus pais,
Ernandes e Afonsina,
amores da minha vida.
vi
AGRADECIMENTOS
Gostaria de agradecer a todos que de alguma forma contribuíram para a realização deste
trabalho e, em especial, àqueles que foram fundamentais ao longo desta jornada.
Ao professor Plácido Rogério Pinheiro, pelos ensinamentos em minha vida acadêmica e
pelo apoio incondicional ao longo de todo o curso. Sem a sua orientação e o seu incentivo,
este trabalho jamais teria sido concretizado.
Ao professor André Luís Vasconcelos Coelho, pelas considerações que só vieram a
engrandecer este trabalho. Suas acertadas e construtivas críticas foram de extrema
importância para este trabalho e, mais do que isso, para minha formação.
Aos professores Dario José Aloise e Antônio Clécio Fontelles Thomaz, nossos efusivos
agradecimentos pela participação nesta banca de mestrado, o que certamente tornará o
trabalho mais rico e conceituado.
Aos meus pais, Ernandes e Afonsina, que me ensinaram a não temer desafios e a
superar os obstáculos com humildade e determinação.
Aos meus irmãos, Leonardo, Carolina e Marina, que sempre estiveram ao meu lado.
Aos meus colegas, pelo convívio e companheirismo durante a realização do curso.
vii
Resumo da dissertação apresentada ao Corpo Docente do Curso de Mestrado em
Informática Aplicada da Universidade de Fortaleza, como parte dos requisitos necessários
para a obtenção do grau de Mestre em Informática.
COMBINAÇÃO DE METAHEURÍSTICAS E PROGRAMAÇÃO
LINEAR INTEIRA: UMA METODOLOGIA HÍBRIDA APLICADA AO
PROBLEMA DE CARREGAMENTO DE CONTÊINER
Autor: Napoleão Vieira Nepomuceno
Orientador: Plácido Rogério Pinheiro, D.Sc.
Este trabalho apresenta uma metodologia híbrida, combinando Metaheurística e
Programação Linear Inteira, para resolver Problemas de Corte e Empacotamento. No
algoritmo específico proposto para o Problema de Carregamento de Contêiner, um algoritmo
genético atua como um gerador de instâncias reduzidas do problema original, descritas em
Programação Matemática. As instâncias geradas são resolvidas no LINGO, fornecendo os
valores de aptidão para o algoritmo genético e direcionando seu processo evolutivo. Testes
computacionais são realizados em uma biblioteca de exemplos conhecida na literatura, e os
resultados são comparados com os de outros autores. Um estudo de caso, envolvendo
problemas reais de carregamento de contêineres em uma indústria metalúrgica, também foi
considerado para fins de avaliação da proposta. Considerações finais e sugestões de trabalhos
futuros são apresentadas ao final do trabalho.
Palavras-chave: Corte e Empacotamento, Carregamento de Contêiner, Metaheurísticas,
Algoritmos Genéticos, Programação Inteira, Algoritmos Híbridos.
viii
Abstract of the dissertation presented to the board of faculties of the Master Program in
Applied Informatics at the University of Fortaleza, as partial fulfillment of the requirements
for the Master’s degree in Computer Science.
COMBINATION OF METAHEURISTICS AND LINEAR INTEGER
PROGRAMMINIG: A HYBRID METODOLOGY APPLIED TO THE
CONTAINER LOADING PROBLEM
Author: Napoleão Vieira Nepomuceno
Advisor: Plácido Rogério Pinheiro, D.Sc.
This work presents a hybrid methodology, combining Metaheuristics and Integer Linear
Programming, for solving Cutting and Packing Problems. In the particular algorithm proposed
to the Container Loading Problem, a Genetic Algorithm works as a generator of reduced
instances of the original problem, formulated in a Mathematical Programming perspective.
The generated instances are solved using LINGO, and the performance measures
accomplished by the respective models behave as fitness values to the Genetic Algorithm,
thus guiding the evolutionary process. Computational tests are performed over standard
benchmark problems, and the results are compared to those achieved by other authors. As
well, a study over a real case problem was conducted to assess the potentialities of the
approach. Final considerations and suggestions of future work are presented at the end of this
work.
Keywords: Cutting and Packing, Container Loading, Metaheuristics, Genetic Algorithms,
Integer Programming, Hybrid Algorithms.
ix
SUMÁRIO
LISTA DE FIGURAS ...............................................................................................................X
INTRODUÇÃO........................................................................................................................12
1. CONCEITOS FUNDAMENTAIS ...................................................................................14
1.1. Programação Linear Inteira ......................................................................................14
1.1.1 Otimalidade, Relaxação e Limitante ................................................................15
1.1.2 Branch-and-Bound............................................................................................16
1.2. Metaheurísticas.........................................................................................................18
1.2.1 Metaheurísticas de Trajetória ...........................................................................18
1.2.2 Metaheurísticas Populacionais .........................................................................19
1.2.3 Algoritmos Genéticos.......................................................................................20
1.3. Conclusão .................................................................................................................23
2. ABORDAGENS PARA O PROBLEMA DE CARREGAMENTO DE CONTÊINER..24
2.1. Abordagens Usando Programação Matemática........................................................25
2.2. Abordagens Usando Heurísticas e Metaheurísticas..................................................30
2.3. Abordagens Híbridas................................................................................................32
2.4. Conclusão .................................................................................................................34
3. METODOLOGIA HÍBRIDA PROPOSTA .....................................................................35
3.1. Etapas Fundamentais................................................................................................36
3.2. Formulação Matemática do Problema......................................................................38
3.3. Estruturas Redutíveis do Modelo .............................................................................40
3.4. Gerador de Instâncias Reduzidas..............................................................................40
3.5. Heurística de Construção de Camadas .....................................................................42
3.6. Conclusão .................................................................................................................42
4. EXPERIMENTOS COMPUTACIONAIS.......................................................................43
4.1. Experimentos Teóricos.............................................................................................43
4.2. Estudo de Caso .........................................................................................................46
4.3. Conclusão .................................................................................................................48
CONSIDERAÇÕES FINAIS ...................................................................................................49
BIBLIOGRAFIA......................................................................................................................51
APÊNDICE I – MODELAGEM DO PROBLEMA.................................................................55
APÊNDICE II – ARQUIVOS DE ENTRADA........................................................................57
x
LISTA DE FIGURAS
Figura 1: Árvore de Branch-and-Bound...................................................................................17
Figura 2: Operador de cruzamento...........................................................................................21
Figura 3: Operador de mutação. ...............................................................................................22
Figura 4: Estrutura de um algoritmo genético típico................................................................22
Figura 5: Representação espacial da caixa dentro do contêiner...............................................28
Figura 6: Representação bidimensional de interposição espacial entre caixas. .......................28
Figura 7: Definição pictórica do valor J
i
. .................................................................................29
Figura 8: Camada ao longo da largura do contêiner.................................................................30
Figura 9: Seqüência de cortes e padrão de carregamento correspondente. ..............................32
Figura 10: Metodologia híbrida proposta.................................................................................35
Figura 11: Diferentes modos de um tipo de caixa....................................................................38
Figura 12: Representação do cromossomo...............................................................................41
Figura 13: Distribuição dos subproblemas do espaço de busca da metaheurística. .................41
Figura 14: Padrão de carregamento AH. ..................................................................................44
Figura 15: Padrão de carregamento do MaxLoad Pro..............................................................47
Figura 16: Padrão de carregamento MH...................................................................................48
xi
LISTA DE TABELAS
Tabela 1: Resultados comparativos para exemplos de pior caso de B/R. ................................44
Tabela 2: Resultados comparativos para exemplos de melhor caso de B/R. ...........................44
Tabela 3: Resultados obtidos para os 50 primeiros exemplos do grupo thpack1.....................45
Tabela 4: Dados dos casos abordados. .....................................................................................46
Tabela 5: Resultados obtidos para os casos práticos abordados...............................................47
INTRODUÇÃO
O tema principal abordado nesta dissertação é um caso particular dos Problemas de
Corte e Empacotamento (PCEs), denominado Problema de Carregamento de Contêiner
(PCC). Basicamente, este problema consiste em acomodar caixas retangulares de diversos
tamanhos dentro de um contêiner. Dadas as dimensões do contêiner e das caixas a carregar, a
questão é encontrar a melhor disposição das caixas em função de um determinado objetivo –
em geral, o melhor aproveitamento do espaço do contêiner. Este problema, situado na
fronteira do conhecimento em Otimização Combinatória, é facilmente enunciado e
compreendido, “vestindo-se” de uma simplicidade contrastante com sua real complexidade.
Na Ciência da Computação, a importância dos PCEs é reconhecida em áreas essenciais
como Análise de Algoritmos e Otimização Combinatória. Além disso, ao se estudar
problemas específicos de Corte e Empacotamento, são dadas contribuições relevantes para a
melhoria das atividades das empresas, com especial destaque nas atividades industriais e de
logística. Diante da dificuldade inerente e da grande importância prática dos PCEs, um grande
esforço para se obter soluções mais sofisticadas para estes problemas vem sendo realizado.
Diversas formulações matemáticas para o PCC são encontradas na literatura. Entretanto,
em virtude do rápido crescimento do número de restrições e de variáveis do problema, a
abordagem exata só se mostra diretamente aplicável a problemas de tamanho limitado, não
sendo interessante sua utilização na grande maioria dos casos práticos. Diante da dificuldade
de se resolver o problema por meio de métodos exatos, que garantem a obtenção de uma
solução ótima para cada instância do problema, o uso de métodos aproximativos e de
heurísticas está presente em boa parte dos trabalhos que enfocam o PCC. Desta forma,
13
sacrifica-se a garantia de obtenção de soluções ótimas para se encontrar soluções satisfatórias
em um tempo de execução razoável.
Tanto a abordagem exata quanto a abordagem heurística apresentam vantagens e
desvantagens particulares e, de uma maneira geral, podem ser consideradas complementares.
Sendo assim, parece natural combinar as duas técnicas para se construir ferramentas mais
poderosas de resolução de problemas, quer seja para se obter uma solução ótima com melhor
tempo de resposta, quer seja para se alcançar melhores soluções heurísticas. Recentemente, a
abordagem híbrida tem ganhado bastante destaque, combinando algoritmos exatos e
metaheurísticas para resolver problemas difíceis de natureza combinatória.
Este trabalho tem como principal objetivo apresentar uma metodologia híbrida,
combinando Metaheurística e Programação Linear Inteira, que pode servir de framework para
solução de diversos PCEs. A metodologia proposta é particularmente aplicada ao Problema de
Carregamento de Contêiner, e os resultados obtidos são comparados com os de outros autores.
Para isso, são utilizados exemplos encontrados na literatura, em especial, uma biblioteca de
testes largamente utilizada para validação de diversos trabalhos sobre PCEs. Além disso, um
estudo de caso, envolvendo problemas reais de carregamento de contêineres em uma indústria
metalúrgica, também foi considerado para fins de avaliação da proposta.
Para um melhor entendimento, o trabalho está estruturado em capítulos. No Capítulo 1,
é feita uma breve introdução sobre os principais conceitos por trás das técnicas de
Programação Linear Inteira e de Metaheurísticas, assuntos de fundamental importância para
compreensão do trabalho. No Capítulo 2, apresenta-se o estado da arte sobre o Problema de
Carregamento de Contêiner com as diferentes abordagens propostas para resolvê-lo. No
Capítulo 3, é proposta uma metodologia híbrida para resolver Problemas de Corte e
Empacotamento. Em especial, é feita uma aplicação da metodologia ao Problema do
Carregamento de Contêineres usando um algoritmo genético. No Capítulo 4, são apresentados
os resultados computacionais obtidos com a aplicação da metodologia híbrida, que acenam
com a qualidade da proposta, tanto em testes teóricos quanto em um estudo prático. Por fim,
são feitas considerações finais sobre o trabalho.
1. CONCEITOS FUNDAMENTAIS
Neste capítulo, são discutidos os principais fundamentos por trás das técnicas de
Programação Linear Inteira e de Metaheurísticas. Os temas são abordados apenas de forma
introdutória, com o intuito de apresentar os conceitos necessários para uma melhor
compreensão deste trabalho. Para um aprofundamento nesses assuntos, é aconselhável
consultar as obras referenciadas no decorrer deste capítulo. O conteúdo de Programação
Linear Inteira, em particular, está baseado no livro de Wolsey (1998). Um survey recente
sobre Metaheurísticas pode ser encontrado em (BLUM e ROLI, 2003).
1.1. PROGRAMAÇÃO LINEAR INTEIRA
A Programação Linear Inteira (PLI) pode ser utilizada para formular e resolver muitos
problemas práticos de Otimização Combinatória. Muitas das idéias de PLI são baseadas nos
conceitos de Programação Linear (PL), em que um problema é expresso em termos de
variáveis contínuas e um conjunto de restrições lineares sobre essas variáveis. Um problema
em PL pode ser formulado como:
max
{}
,0,: ≥
≤
xbAxcx
onde c é um vetor linha n-dimensional – que define os coeficientes da função-objetivo –, x é
um vetor coluna n-dimensional – que representa as variáveis –, A é uma matriz m x n e b é um
vetor coluna m-dimensional – que definem as restrições do problema. Uma solução (x
1
, x
2
, ...,
x
n
) é dita viável se satisfizer todas as restrições do problema. Uma solução viável que forneça
o maior valor à função-objetivo é chamada solução ótima.
15
Entretanto, é muito comum que as variáveis precisem assumir valores inteiros, e não
contínuos. Se for adicionada a restrição de que todas as variáveis têm que apresentar valores
inteiros, tem-se então um problema em PLI, definido como:
max
{}
.inteiro e 0,: ≥
≤
xbAxcx
E, se todas as variáveis forem restritas a possuir valores 0-1, tem-se um problema em
Programação Linear Inteira 0-1, que pode ser formulado como:
{}
{
}
.1,0,:
n
xbAxcx ∈≤max
Quando se impõe que as variáveis devem assumir valores inteiros, o problema pode
ficar muito mais difícil. E a idéia natural de simplesmente arredondar os valores da solução
ótima encontrada para o problema relaxado em PL é freqüentemente insuficiente para
determinar uma solução ótima, ou mesmo uma solução viável, do problema original.
1.1.1 OTIMALIDADE, RELAXAÇÃO E LIMITANTE
Dado um problema em PLI
{
}
,:max
n
ZXxcxz
deseja-se provar que uma determinada solução x* é ótima. Para isso, é necessário encontrar
um limitante inferior z
l
≤ z e um limitante superior z
u
≥ z, de forma que z
l
= z
u
= z. Na prática,
um algoritmo deve encontrar uma seqüência crescente
⊆∈=
ltll
<
z zzz
de limitantes inferiores, e uma seqüência decrescente
<
<< ...
21
usuu
>>>> ...
21
z zzz
de limitantes superiores, até que
z ,
ε
≤−
ltus
z
onde ε é um valor não-negativo considerado pequeno.
16
Cada solução viável x ∈ X provê um limitante inferior z
l
= c(x) ≤ z. Este é o modo
essencial de se obter limitantes inferiores para problemas de maximização. Para alguns
problemas de PLI, encontrar soluções viáveis é bastante fácil; a dificuldade é encontrar boas
soluções. Entretanto, para outros problemas de PLI, encontrar uma solução viável pode ser tão
difícil quanto resolver o problema em si.
Encontrar limitantes superiores para problemas de maximização apresenta-se como um
desafio diferente. A técnica mais utilizada para se obter estes limitantes é chamada de
relaxação. A idéia consiste em substituir o problema original de PLI por um problema de
otimização mais simples, cujo valor da solução ótima seja, pelo menos, tão grande quanto z.
Para que o problema relaxado tenha esta propriedade, existem duas possibilidades óbvias:
aumentar o conjunto de soluções viáveis ou substituir a função-objetivo por outra que
apresente um valor igual ou maior para qualquer solução do problema original.
A relaxação linear está entre as relaxações mais largamente utilizadas. Dado um
problema em PLI formulado como:
{
}
{
}
,: onde ,:
max
a relaxação linear deste problema pode ser formulada como:
bAxRxPZPxcx
nn
≤∈=∩∈
+
LP
∈=
{}
.:max Pxcxz
A questão que se segue é como construir relaxações interessantes, que forneçam
limitantes mais precisos. A definição de formulações melhores de relaxação está intimamente
relacionada à relaxação linear. Entre outras técnicas encontram-se a relaxação combinatória e
a relaxação lagrangeana.
1.1.2 BRANCH-AND-BOUND
Branch-and-Bound é um dos principais métodos utilizados para resolver problemas de
PLI. A idéia principal do algoritmo é gerar uma árvore de subproblemas obtidos pela
decomposição sucessiva do espaço de soluções do problema original, resolver os
subproblemas usando alguma técnica de relaxação e, a partir dos limitantes superiores e
inferiores obtidos para os subproblemas, ramificar a árvore de forma eficiente até determinar
a solução do problema original.
17
Considerando que S = S
1
∪ ... ∪ S
K
seja uma decomposição de S em subconjuntos
menores, z
k
= max {cx : x ∈ S
k
} para k = 1, ..., K, z
uk
seja um limitante superior em z
k
e z
lk
seja
um limitante inferior em z
k
, então z
u
= max
k
z
uk
é um limitante superior em z e z
l
= max
k
z
lk
é
um limitante inferior em z. Baseando-se nesta proposição, as informações dos limitantes de
subproblemas podem ser utilizadas para eliminar determinadas ramificações da árvore do
método de Branch-and-Bound, enumerando um grande número de soluções implicitamente.
Existem três situações básicas em que se pode podar a árvore de Branch-and-Bound:
quando um subproblema é resolvido de forma ótima, quando um subproblema apresenta um
limitante superior local menor ou igual ao limitante inferior global, ou quando o subproblema
não possui solução viável. Estas condições são formalmente expressas a seguir:
3
A Figura 1, extraída de (WOLSEY, 1998), ilustra cada uma destas situações. O
subproblema S
12
está resolvido de forma ótima – limitante superior é igual ao limitante
inferior (z
u12
= z
l12
= 7) – e, portanto, não deve ser mais decomposto. O subproblema S
11
apresenta limitante superior (z
u11
= 6) menor do que o limitante inferior global (z
l
= z
l12
= 7) e
deve ser eliminado da árvore de Branch-and-Bound. E, por fim, o subproblema S
2
não
apresenta solução viável e também não deve ser ramificado.
{}
.S .
ou ;z .2
resolvido; está :maxz .1
φ
=
≤
∈=
t
lut
tt
z
Sxcx
Figura 1: Árvore de Branch-and-Bound (WOLSEY, 1998).
18
Como o espaço de soluções do problema original foi implicitamente explorado por
completo pela árvore de Branch-and-Bound – já que não existe nenhum subproblema a ser
decomposto –, a solução encontrada para o subproblema S
12
é a solução ótima do problema S.
1.2. METAHEURÍSTICAS
De acordo com Osman e Laporte (1996), uma metaheurística é formalmente definida
como um processo de geração iterativo que guia uma heurística subordinada, combinando os
conceitos de diversificação e intensificação do espaço de busca, para encontrar boas soluções.
O termo “diversificação” refere-se à exploração do espaço de busca, enquanto o termo
“intensificação” refere-se à utilização da experiência acumulada durante este processo.
Esta abordagem, comparada a técnicas clássicas de otimização, apresenta como uma
importante característica a utilização de estratégias para escapar de ótimos locais e propõe
uma heurística geral que independe da natureza do problema específico a ser tratado. Essas
técnicas conseguem evitar ótimos locais por geralmente realizarem a procura da solução
ótima global em diversas regiões do espaço de busca, utilizando uma certa aleatoriedade
direcionada pela heurística codificada.
Existem diferentes maneiras de se classificar as metaheurísticas, cada uma de acordo
com um ponto de vista (BLUM e ROLI, 2003). Uma dessas importantes classificações
considera o número de soluções utilizadas ao mesmo tempo em cada iteração, dividindo as
metaheurísticas em dois grupos: baseadas em trajetórias e baseadas em populações.
As metaheurísticas de trajetória partem de uma solução inicial e descrevem uma
trajetória no espaço de soluções, sempre trabalhando com apenas uma solução a cada iteração
do método. Entre as principais metaheurísticas de trajetória, encontram-se a Têmpera
Simulada e a Busca-Tabu. Por outro lado, as metaheurísticas populacionais trabalham com
um conjunto de soluções a cada iteração do procedimento. Colônia de Formigas e Algoritmos
Genéticos estão entre os métodos mais representativos das metaheurísticas populacionais.
1.2.1 METAHEURÍSTICAS DE TRAJETÓRIA
A Têmpera Simulada é reconhecida como a primeira metaheurística e certamente é um
dos primeiros algoritmos a explicitar uma estratégia de escapar de pontos ótimos locais
19
(BLUM e ROLI, 2003). A Têmpera Simulada faz analogia a um processo de termodinâmica e
foi apresentada como um algoritmo de busca por Kirkpatrick et al. (1983).
A idéia fundamental da Têmpera Simulada é permitir que soluções piores façam parte
da trajetória de busca, evitando o término prematuro do algoritmo em pontos ótimos locais. O
algoritmo começa de uma solução inicial qualquer e utiliza um parâmetro de temperatura T.
Uma nova solução é gerada a partir de uma perturbação da solução inicial. Caso esta nova
solução seja melhor, há a substituição da solução corrente. Entretanto, mesmo que a nova
solução apresente um valor de função-objetivo pior, esta pode substituir a solução corrente
com uma probabilidade dada em função de T. Este parâmetro deve decrescer gradualmente ao
longo do procedimento de busca até que se convirja para um método de busca local.
Outra técnica, a Busca-Tabu, está entre as metaheurísticas mais utilizadas para resolver
problemas de Otimização Combinatória (BLUM e ROLI, 2003), e suas idéias básicas foram
introduzidas por Glover (1986). Este método utiliza explicitamente o histórico do processo de
busca, tanto para tentar escapar de pontos ótimos locais quanto para implementar uma
estratégia de exploração do espaço de soluções.
Basicamente o algoritmo de Busca-Tabu faz uso de um procedimento adaptativo que
possui uma estrutura de memória como guia – chamada de lista tabu –, utilizada para
armazenar os últimos movimentos realizados durante o processo de busca. Isto evita que o
algoritmo retorne a soluções visitadas mais recentemente, prevenindo uma busca em ciclos e
forçando a exploração do espaço de soluções mesmo na existência de ótimos locais.
1.2.2 METAHEURÍSTICAS POPULACIONAIS
Colônia de Formigas é uma metaheurística proposta por Dorigo (1992). Este método é
baseado no comportamento das formigas, que parecem possuir uma estratégia interessante de
percorrer seu ambiente em busca de comida. Enquanto realizam seu percurso, as formigas
deixam um rastro de uma substância: o feromônio. Os caminhos que apresentam maior
concentração desta substância são escolhidos com maior probabilidade.
Os algoritmos de Colônia de Formigas são baseados em um modelo probabilístico
parametrizado que é utilizado para simular os rastros químicos de feromônio. As formigas
artificiais constroem as soluções de forma incremental, adicionando oportunamente
componentes definidos para a solução parcial em consideração (BLUM e ROLI, 2003).
20
Já os Algoritmos Genéticos foram introduzidos por Holland (1975) e popularizados por
Goldberg (1989). Estes algoritmos seguem o princípio da seleção natural e sobrevivência do
mais apto, sendo que a qualidade das características de uma possível solução é medida por
uma função de aptidão. Geralmente, o algoritmo genético começa com uma população
aleatória de cromossomos. Essas estruturas são avaliadas e associadas a uma probabilidade de
reprodução. Para constituir uma nova geração, operações de cruzamento, mutação e seleção
são utilizadas.
Os Algoritmos Genéticos estão entre as metaheurísticas mais utilizadas. Isto se deve
principalmente à sua flexibilidade e robustez. Entretanto, outras características essenciais,
como capacidade de larga exploração do espaço de soluções e facilidade de programação,
corroboram para a aplicação de Algoritmos Genéticos a diversos problemas de Otimização
Combinatória. Em virtude da aplicação proposta neste trabalho, um estudo mais aprofundado
sobre Algoritmos Genéticos, baseado no capítulo de Lacerda e Carvalho (1999, In: GALVÃO
e VALENÇA, 1999, p. 99), será apresentado a seguir.
1.2.3 ALGORITMOS GENÉTICOS
O primeiro passo de um algoritmo genético típico é a geração de uma população inicial
de cromossomos, que representam possíveis soluções do problema a ser resolvido. Durante o
processo evolutivo, esta população é avaliada e cada cromossomo recebe um valor de aptidão,
refletindo a qualidade da solução que ele representa. Em geral, os cromossomos mais aptos
têm mais chance de serem selecionados, enquanto os menos aptos são descartados. Os
cromossomos selecionados podem sofrer modificações em suas características fundamentais
por meio dos operadores de cruzamento e mutação, gerando descendentes para a nova
geração. Este processo é continuado até que um determinado critério seja alcançado.
Representação
Um cromossomo é uma estrutura de dados, normalmente uma cadeia de bits, que
representa uma possível solução para o problema considerado. Em geral, para problemas de
otimização, um cromossomo representa um conjunto de parâmetros da função-objetivo que
deve ser otimizada. O conjunto de todas as configurações que o cromossomo pode assumir
forma o seu espaço de busca.
21
Seleção
Inspirado no processo de seleção natural dos seres vivos, um algoritmo genético escolhe
os melhores cromossomos da população inicial para gerar cromossomos-filhos. Uma
população intermediária é utilizada para alocar os cromossomos-pais, que são geralmente
selecionados com probabilidade proporcional ao seu valor de aptidão.
Cruzamento
O cruzamento é aplicado com uma dada probabilidade, determinada pela taxa de
cruzamento, a um par de cromossomos retirados da população intermediária, gerando dois
cromossomos-filhos. Cada um dos cromossomos-pais tem sua cadeia de bits cortada em uma
posição aleatória, produzindo duas cabeças e duas caldas. As caldas são trocadas, gerando
dois novos cromossomos. Não ocorrendo o cruzamento, os cromossomos-filhos serão
exatamente iguais aos cromossomos-pais. A Figura 2, apresentada a seguir, ilustra o
comportamento do operador de cruzamento.
Figura 2: Operador de cruzamento (GALVÃO e VALENÇA, 1999).
Mutação
Após a operação de cruzamento, o operador de mutação é aplicado em cada bit dos dois
cromossomos-filhos com uma determinada probabilidade, definida pela taxa de mutação,
invertendo os valores dos bits. A mutação aumenta a diversidade dos cromossomos na
população. A Figura 3, apresentada em seguida, demonstra o comportamento desta operação.
22
Figura 3: Operador de mutação (GALVÃO e VALENÇA, 1999).
Critérios de parada
Após a definição da primeira população, o procedimento deve se repetir até que um
determinado critério seja atendido – normalmente, um número estipulado de gerações. Outros
critérios podem ser utilizados, como convergência ou limite de tempo de execução.
Convergência se refere a duas situações distintas. Em uma delas, considera-se que o algoritmo
genético convergiu quando o valor da melhor solução encontrada não se modifica após um
certo número de gerações sucessivas. Outra situação de convergência é quando a população
apresenta os mesmos genes para um percentual considerado alto de cromossomos. A partir
destas considerações, um algoritmo genético típico pode ser definido de acordo com o
esquema da Figura 4:
Figura 4: Estrutura de um algoritmo genético típico.
23
1.3. CONCLUSÃO
Neste capítulo, foi feita uma breve introdução sobre as técnicas de Programação Linear
Inteira e de Metaheurísticas, apresentando-se os conceitos necessários para a compreensão
deste trabalho. Nos capítulos que se seguem, as definições aqui discutidas serão utilizadas
sem maiores considerações.
2. ABORDAGENS PARA O PROBLEMA DE
CARREGAMENTO DE CONTÊINER
O Problema de Carregamento de Contêiner é um caso particular dos Problemas de Corte
e Empacotamento. Como muitos outros problemas de Otimização Combinatória, os PCEs
podem ser facilmente formulados e compreendidos, “vestindo-se” de uma simplicidade
contrastante com sua real complexidade. Basicamente, os Problemas de Corte consistem na
determinação de padrões de corte de unidades de material (objetos), de maneira a produzir um
conjunto de unidades menores (itens), satisfazendo determinadas restrições. Similarmente aos
Problemas de Corte, os Problemas de Empacotamento consistem na determinação da melhor
forma de arranjar um conjunto de itens dentro de objetos.
Os PCEs estão fortemente relacionados com aplicações da área industrial. Variantes
desta classe de problemas aparecem constantemente, dificultando o desenvolvimento de um
único algoritmo que resolva de forma eficiente e eficaz todas elas. Mais ainda, há fortes
indícios teóricos que apontam para a inexistência de tal solução. Assim, na maioria das vezes,
as abordagens de resolução destes problemas se baseiam em um conhecimento específico
explorado no estudo de cada caso. Isso justifica a grande quantidade de métodos heurísticos
propostos na literatura. Muitos autores têm apresentado diferentes abordagens para resolver os
PCEs, entretanto poucos se preocuparam com os casos tridimensionais.
O Problema de Carregamento de Contêiner, um caso tridimensional dos PCEs, consiste
em arranjar caixas retangulares de diversos tamanhos dentro de um único contêiner. Dadas as
dimensões do contêiner e das caixas a carregar, a questão é encontrar a melhor disposição das
caixas em função de um determinado objetivo – em geral, o melhor aproveitamento do espaço
do contêiner. Além das restrições geométricas inerentes ao problema, ou seja, o carregamento
25
deve estar totalmente compreendido no espaço interno do contêiner e não deve haver
interposição do espaço ocupado pelas caixas, outras restrições podem ser eventualmente
consideradas, tais como fragilidade e estabilidade da carga, limite e distribuição de peso do
carregamento e orientação das caixas dentro do contêiner.
Bischoff e Marriot (1990) classificaram dois casos básicos para o PCC. No primeiro,
uma combinação de contêineres deve ser escolhida para transportar, por completo, uma dada
carga. No segundo, o maior volume de uma determinada carga deve ser alocado em um único
contêiner. O problema particular abordado neste trabalho pertence ao segundo caso e pode ser
visto como um caso especial dos PCEs, classificado como 3/B/O/, conforme a taxonomia
proposta por Dyckhoff (1990). Esse problema, apresentando-se como uma generalização do
problema unidimensional de Knapsack Packing, pertence à classe NP-Hard.
Diversas formulações para o PCC são encontradas na literatura. Entretanto, em virtude
do rápido crescimento do número de restrições e de variáveis do problema, a abordagem exata
só se mostra diretamente aplicável a problemas de tamanho limitado, não sendo interessante
sua utilização para situações práticas. Diante da dificuldade de se resolver o problema por
meio da aplicação de métodos exatos, a grande maioria das abordagens de resolução do PCC
faz uso de métodos aproximativos e de heurísticas.
2.1. ABORDAGENS USANDO PROGRAMAÇÃO MATEMÁTICA
Um problema clássico de Otimização Combinatória é denominado de Knapsack. Este
problema considera um conjunto de m itens, sendo que, para cada item j (j = 1, ..., m), tem-se
associado um peso w
j
e um valor v
j
. O objetivo é determinar a coleção de itens de maior valor
possível, respeitando-se a restrição de peso máximo permitido b. O problema de Knapsack
pode ser formulado como um problema em Programação Linear Inteira da forma:
contrário. caso ,0
adeterminad coleção à pertence item o se ,1 onde
, ..
max
1
1
=
=
≤
∑
∑
=
=
j
j
m
j
jj
m
j
jj
x
jx
bxwas
xv
26
Trazendo para o caso tridimensional do Problema de Carregamento de Contêiner, o
Knapsack tem por objetivo determinar um arranjo das caixas dentro de um único contêiner,
respeitando-se as restrições espaciais do problema, de forma a maximizar o volume utilizado
do contêiner. Contudo, deve-se enfatizar que existe uma diferença fundamental entre o
problema clássico de Knapsack apresentado acima e o PCC abordado neste trabalho, visto que
neste último há a necessidade de se considerar a natureza espacial do problema.
Gilmore e Gomory (1963) trataram um problema de corte unidimensional, caracterizado
por um conjunto de objetos de comprimento L e uma demanda d
i
de itens menores de
comprimento l
i
(i = 1, ..., m). O problema consiste em cortar os objetos para obtenção dos
itens demandados, de maneira a utilizar uma quantidade mínima destes objetos. Cada maneira
de se cortar os objetos caracteriza um padrão de corte a
j
= (a
1j
, a
2j
, ..., a
mj
), com j = (1, ..., n),
onde a
ij
é a quantidade de itens do tipo i cortados segundo o padrão de corte a
j
. O problema
pode ser formulado em Programação Linear Inteira da forma:
A exigência de integralidade sobre as variáveis x
j
, que representa o número de objetos
cortados de acordo com o padrão de corte a
j
, torna o problema difícil de ser resolvido. Além
disso, o número de padrões de corte cresce consideravelmente em situações práticas,
inviabilizando a resolução direta do problema. Para superar essas dificuldades, a condição de
integralidade é relaxada e um método eficiente de geração de colunas é utilizado para obter
soluções aproximadas. Entretanto, como a solução deve ser inteira, diversas heurísticas têm
sido desenvolvidas para encontrar uma solução viável a partir da solução aproximada já
encontrada para o problema.
O Problema de Carregamento de Contêiner encontra-se formulado como um modelo em
Programação Linear Inteira 0-1 em (MORABITO e ARENALES, 1997), em que fica
estendido o modelo bidimensional apresentado por Beasley (1985). O problema considera um
conjunto de caixas agrupadas em m tipos. Para cada tipo i, caracterizado pelo comprimento,
largura e altura dados pela tríade (l
i
, w
i
, h
i
), com volume associado v
i
, tem-se uma quantidade
.,...,1 inteiro, e 0 onde
,,...,1, ..
min
1
1
njx
midxaas
x
j
n
j
ijij
n
j
j
=≥
=≥
∑
∑
=
=
27
b
i de caixas. Considera também um contêiner caracterizado pelas dimensões (L, W, H). As
caixas devem ser carregadas ortogonalmente dentro do contêiner. Além disso, por
simplicidade e sem perda de generalidade, as caixas devem ser carregadas com orientação
pré-fixada, com l
i
, w
i
e h
i
paralelos a L, W e H, respectivamente.
Cada variável 0-1 do programa representa a decisão de colocar ou não uma caixa do
tipo i na coordenada (x, y, z) dentro do contêiner. Como enunciado no teorema sobre
canonical dissections (HERZ, 1972), pode-se assumir que, sem perda de generalidade, x, y e z
pertencem respectivamente aos conjuntos de discretização:
A restrição x ≤ L - l
o
determina que a folga para completar a dimensão de comprimento
do contêiner seja maior ou igual ao tamanho da menor caixa, considerando-se sua dimensão
de comprimento. De forma análoga, pode-se entender as restrições apresentadas para as
dimensões de largura e de altura do contêiner.
Considere x
j
o j-ésimo elemento do conjunto X, y
k
o k-ésimo elemento do conjunto Y e z
l
o l-ésimo elemento do conjunto Z, determinados a priori. Conforme ilustrado na Figura 5, se
uma caixa do tipo i for colocada na posição (x
j
, y
k
, z
l
), então não se pode colocar outra caixa
em qualquer posição (x
p
, y
q
, z
r
), com p = 1, ... , |X|, q = 1, ..., |Y| e r = 1, ..., |Z|, tal que:
{}
.,...,1,min onde
,inteiro ,0,,
1
mill
lLxlxxX
io
io
m
i
ii
==
⎭
⎬
⎫
⎩
⎨
⎧
≥−≤==
∑
=
αα
{}
.,...,1,min onde
,inteiro ,0,,
1
miww
wWywyyY
io
io
m
i
ii
==
⎭
⎬
⎫
⎩
⎨
⎧
≥−≤==
∑
=
ββ
{}
.,...,1,min onde
,inteiro ,0,,
1
mihh
hHzhzzZ
io
io
m
i
ii
==
⎭
⎬
⎫
⎩
⎨
⎧
≥−≤==
∑
=
γγ
⎪
⎨
⎩
⎪
⎧
−+≤≤
−+≤≤
−+≤≤
.1
,1
1
h z z z
w y y y
, l x x x
ilrl
ikqk
ijpj
28
z
l
y
k
x
j
Altura
Comprimento
Largura
Caixa do tipo i.
Figura 5: Representação espacial da caixa dentro do contêiner.
Para evitar a interposição de caixas, define-se a matriz de incidência g
ijklpqr
:
⎪
⎪
⎩
⎪
⎪
⎨
⎧
−+≤≤
−+≤≤
−+≤≤
=
contrário. caso ,0
.1
,1
,1 se ,1
ilrl
ikqk
ijpj
ijklpqr
hzzz
wyyy
lxxx
g
que deve ser computada a priori para cada tipo de caixa i (i = 1, ..., m), para cada
posição (x
j
, y
k
, z
l
), com j = 1, ..., |X|, k = 1, ..., |Y| e l = 1, ..., |Z|, e para cada posição (x
p
, y
q
, z
r
),
com p = 1, ..., |
X|, q = 1, ..., |Y| e r = 1, ..., |Z|. A Figura 6 ilustra o comportamento da matriz
de incidência proposta acima, reduzida para duas dimensões para simplificar o entendimento.
x
j
x
p
x
j
+ l
i
y
k
y
q
y
k
+ w
i
Largura
Comprimento
Figura 6: Representação bidimensional de interposição espacial entre caixas.
29
Mais algumas considerações são necessárias para que se possa formular o PCC:
{
}
{}
{}
()
.,...,1 e ,...,1,,...,1,,...,1
Uma definição pictórica do valor J
i
é apresentada na Figura 7. De forma semelhante,
pode-se entender o significado dos valores K
i
e L
i
para as dimensões de largura e de altura.
Figura 7: Definição pictórica do valor J
i
.
Então, o Problema de Carregamento de Contêiner pode ser formulado como:
com
contrário. caso ,0
.,, posição na colocadafor tipodo caixa uma se ,1
:como definidas decisão de variáveisas e
,max
,max
,max
ZlYkXjmi
zyxi
a
a
hHzlL
wWykK
lLxjJ
lkj
ijkl
ijkl
ili
iki
iji
====
⎩
⎨
⎧
=
−≤=
−≤=
−≤=
Sejam
x
Ji
Elementos do conjunto X
O
L-l
i
comprimento L
l
i
Caixa do tipo i
{}
1,0 com
,...,1,
,...,1,,...,1,,...,1,1 ..
max
i
J
1j1k1l
1111
1111
∈
=≤
===≤
∑∑∑
∑∑∑∑
∑∑∑∑
===
====
====
ijkl
i
KL
ijkl
m
i
J
j
K
k
L
l
ijklijklpqr
m
i
J
j
K
k
L
l
ijkli
a
miba
ZrYqXpagas
av
ii
iii
iii
30
Este modelo contém O(m |
X| |Y| |Z|) variáveis e O(|X| |Y| |Z|) restrições. Se uma
orientação não for fixada para carregar as caixas dentro do contêiner, o modelo acima pode
ser estendido com um número ainda maior de variáveis e restrições. Nos casos práticos, estes
números chegam facilmente à ordem de milhões, o que desestimula o emprego das técnicas
usuais de Programação Linear Inteira ao problema (MORABITO e ARENALES, 1997).
Outros modelos em Programação Matemática para o PCC podem ser encontrados em
(TSAI et al., 1993), (CHEN et al., 1995) e (MARTINS, 2003).
2.2. ABORDAGENS USANDO HEURÍSTICAS E METAHEURÍSTICAS
Em um dos primeiros trabalhos que enfocam o PCC sob uma abordagem heurística,
George e Robinson (1980) descreveram uma estratégia de alocação das caixas baseada na
construção de camadas ao longo do comprimento do contêiner. O carregamento é feito do
fundo para a entrada do contêiner, procurando sempre manter uma superfície plana na
fronteira da última camada alocada, como ilustrado na Figura 8.
Figura 8: Camada ao longo da largura do contêiner.
Em cada camada, o método realiza o carregamento de pilhas compostas de caixas do
mesmo tipo. Caso não seja possível utilizar completamente o espaço da camada, outros tipos
de caixa são considerados para tentar preenchê-lo. A ordem de alocação das caixas é ditada
por uma lista de prioridades que privilegia, nesta ordem, os tipos de caixa já utilizados no
carregamento, o tipo com a maior das menores dimensões, o tipo com a maior quantidade
disponível e o tipo com a maior dimensão. Esta lista de prioridades é de fundamental
31
importância para a heurística, pois, além de especificar a ordem de alocação das caixas,
determina o tamanho de cada camada, que depende do comprimento da caixa que a inicia.
Gehring et al. (1990) propuseram um procedimento semelhante que carrega
seqüencialmente uma lista de caixas ordenadas de acordo com o seu volume, em que caixas
de maior volume devem ser alocadas primeiramente no contêiner. Além disso, as caixas são
arranjadas em pilhas independentes, que podem ser deslocadas na superfície do contêiner.
Estas pilhas são alocadas em camadas construídas ao longo do comprimento do contêiner e
cuja profundidade é determinada pela dimensão da caixa que a origina.
Em (BISCHOFF e MARRIOT, 1990), encontra-se uma avaliação comparativa de
quatorze heurísticas propostas para o PCC, que são examinadas em termos de eficiência
diante de problemas com diferentes números de tipos de caixas a serem consideradas no
carregamento. O objetivo considerado é minimizar o tamanho do comprimento do contêiner
necessário para carregar todas as caixas disponíveis. Este critério é especialmente relevante
em casos nos quais existem diversos grupos de itens que devem ser descarregados em
diferentes destinos. Da mesma forma que o método apresentado por George e Robinson
(1980), estes procedimentos preenchem o contêiner em estágios, construindo camadas ao
longo do comprimento do contêiner. A diferença fundamental é que são consideradas
diferentes listas de prioridade, uma para cada heurística apresentada.
Haessler e Talbot (1990) apresentaram um procedimento heurístico para determinar
padrões de carregamento e dimensionar pedidos de acordo com estes padrões. A heurística
desenvolve um plano de carregamento on-line que especifica de forma exata qual item e como
este item deve ser carregado dentro do contêiner. O primeiro passo é estimar quantas caixas,
arrumadas em pilhas, devem fazer parte do carregamento. O pedido é então ajustado,
adicionando-se ou excluindo-se itens, e, depois, um processo iterativo aloca as pilhas de
caixas sobre a superfície do contêiner.
Em (MORABITO e ARENALES, 1994), pode-se encontrar um método baseado em
grafos E/OU para resolver o PCC, em que cada ramo completo do grafo representa um padrão
de carregamento guilhotinado. Sendo assim, este procedimento descarta possíveis soluções
ótimas que porventura sejam obtidas a partir de um padrão de carregamento não-guilhotinado.
A Figura 9 (MORABITO e ARENALES, 1994) mostra um grafo E/OU e uma solução
possível encontrada por este método.
32
Figura 9: Seqüência de cortes e padrão de carregamento correspondente.
Gehring e Bortfeldt (2001) propuseram uma solução para o PCC utilizando um método
guloso para formação de pilhas independentes de caixas – sendo que nenhuma caixa pode
pertencer a mais de uma torre – e um algoritmo genético que procura alocar estas pilhas de
caixas sobre a superfície do contêiner. As caixas devem ser posicionadas de forma que
estejam completamente apoiadas, ou seja, com a base totalmente encostada no chão do
contêiner ou na superfície da pilha que a sustenta. Além disso, nenhuma caixa mais pesada
pode ser posicionada sobre uma caixa mais leve, e o carregamento não deve ultrapassar o
limite de peso tolerado pelo contêiner.
Em (GEHRING et al., 2004), é apresentado um algoritmo paralelo para resolver o PCC,
combinando Têmpera Simulada e Busca Tabu. Nessa proposta, o algoritmo de Têmpera
Simulada é primeiramente executado para determinar uma boa solução inicial. A partir desta
solução, o algoritmo de Busca Tabu realiza uma ou mais iterações de forma a examinar
intensivamente a vizinhança da solução obtida pelo algoritmo de Têmpera Simulada.
Diferentes instâncias deste procedimento são executadas em paralelo.
2.3. ABORDAGENS HÍBRIDAS
Algoritmos Exatos e Metaheurísticas são vistos como duas abordagens gerais, embora
distintas, para resolver problemas de Otimização Combinatória de forma eficiente, cada uma
apresentando vantagens e desvantagens (DUMITRESCU e STÜTZLE, 2003). Apenas
recentemente algoritmos híbridos que buscam unir as vantagens dos Métodos Exatos e das
Metaheurísticas foram propostos na literatura. Grosso modo, alguns destes algoritmos
33
híbridos objetivam obter soluções ótimas com tempos de execução menores, enquanto outros
buscam obter melhores soluções heurísticas.
Puchinger e Raidl (2005) apresentaram uma classificação geral das metodologias
híbridas, distinguindo duas categorias principais: combinações colaborativas e combinações
integrativas. Por colaboração, entende-se que os algoritmos trocam informações, mas nenhum
é parte do outro. Os algoritmos devem ser executados seqüencialmente, de forma intercalada
ou, ainda, em paralelo. Por integração, entende-se que uma das técnicas é um componente
subordinado à outra técnica. Assim, tem-se a distinção entre o algoritmo mestre – que pode
ser tanto o algoritmo exato quanto a heurística – e o algoritmo escravo.
Poucas aplicações de algoritmos híbridos foram feitas aos PCEs. Em um desses
trabalhos, Plateau et al. (2002) combinaram algoritmos de Pontos Interiores e Metaheurísticas
para resolver o problema unidimensional de Knapsack. Em um primeiro momento, o método
de Pontos Interiores é executado com terminação precoce para se obter uma solução inicial.
Aplicando-se diferentes modificações heurísticas, diversas soluções viáveis são obtidas a
partir daquela solução para gerar uma população inicial e, então, um algoritmo evolutivo é
aplicado. Este é um caso típico de colaboração seqüencial.
Puchinger et al. (2004) descreveram um método combinado de Algoritmo Genético e
Branch-and-Bound para resolver um Problema de Corte bidimensional. O algoritmo genético
proposto nesse trabalho utiliza uma representação baseada em ordem, que é decodificada
usando uma heurística gulosa. Eventualmente, de acordo com uma probabilidade
determinada, o algoritmo exato é aplicado dentro da heurística gulosa para encontrar soluções
ótimas locais de padrões de corte. Nesse caso, faz-se uso de combinação integrativa, em que o
algoritmo exato incorporado à metaheurística funciona como um procedimento escravo.
Terno et al. (2000) uniram um método exato e uma heurística gulosa, propondo um
método híbrido eficiente para o Problema de Carregamento de Contêineres tridimensional.
Em um primeiro momento, uma solução viável é obtida por uma heurística gulosa. O
algoritmo de Branch-and-Bound é depois aplicado para melhorar esta solução. Um limite de
tempo é determinado para evitar que o algoritmo exato execute indefinidamente. Nessa
abordagem, técnicas de busca local são incorporadas ao algoritmo de Branch-and-Bound, que
atua como algoritmo mestre do mecanismo híbrido.
34
2.4. CONCLUSÃO
Neste capítulo, foram apresentadas diferentes abordagens utilizadas para resolver o
Problema de Carregamento de Contêiner, desde a programação matemática, passando pela
abordagem heurística, até a concepção dos algoritmos híbridos. No capítulo seguinte, uma
metodologia híbrida, seguindo esta recente linha de pesquisa, é proposta de forma detalhada
como uma alternativa de solução para o PCC.
3. METODOLOGIA HÍBRIDA PROPOSTA
Existem diversas formulações matemáticas para os Problemas de Corte e
Empacotamento. Entretanto, conforme discutido anteriormente, a abordagem exata só pode
ser diretamente aplicada para resolver instâncias de tamanho limitado. Considerando este fato
e buscando obter melhores soluções heurísticas, a metodologia híbrida proposta sugere a
integração de um método exato a uma metaheurística geradora de instâncias reduzidas do
problema abordado, conforme a Figura 10. Grosso modo, o mecanismo híbrido tem o
propósito de determinar um subproblema que possa ser resolvido de forma exata e apresente
uma boa solução para o problema original.
Problema
Original
Gerador de Instâncias Reduzidas
(Metaheurística – Algoritmo Mestre)
Decodificador de Instâncias Reduzidas
(Método Exato – Algoritmo Escravo)
Integração dos Componentes
Dados Gerais
Solu
ç
ão Geral
i
n
s
t
â
n
c
i
a
a
p
t
i
d
ã
o
Figura 10: Metodologia híbrida proposta.
As reduções realizadas ao problema buscam limitar o número de padrões de corte e
empacotamento possíveis, sempre respeitando todas as restrições impostas ao problema
original. Deste modo, a solução ótima encontrada para cada instância gerada é também uma
36
solução viável para o problema que se deseja resolver. Além disso, o valor da função-objetivo
referente à solução ótima de cada subproblema, obtida pelo Decodificador de Instâncias
Reduzidas (DIR), define a qualidade da instância gerada. Esta informação, por sua vez, pode
ser utilizada para guiar o processo de busca do Gerador de Instâncias Reduzidas (GIR).
Seguindo a classificação proposta por Puchinger e Raidl (2005), a metodologia híbrida
sugerida enquadra-se na categoria de combinações integrativas. As soluções das instâncias
geradas pela metaheurística são determinadas quando os subproblemas são resolvidos por um
solucionador exato, que funciona como um decodificador. A melhor solução obtida ao longo
de todo o processo da metaheurística é a solução encontrada para o problema original.
3.1. ETAPAS FUNDAMENTAIS
Basicamente, a metodologia híbrida proposta é composta de uma seqüência de etapas
fundamentais a serem seguidas: a formulação matemática do problema; a identificação das
estruturas redutíveis do modelo; e a definição da metaheurística geradora de subproblemas.
Formulação Matemática do Problema
O primeiro passo para a resolução de um problema em Pesquisa Operacional é a
modelagem, que consiste em traduzir a realidade empírica para sentenças lógicas e dados
objetivos, resultando na formulação matemática do problema (HILLIER e LIEBERMAN,
1995). Um modelo matemático de otimização envolve a representação de um problema
através de um conjunto de relações matemáticas tais como: equações, inequações,
dependências lógicas, e funções.
Nesta etapa, deve-se decidir que aspectos do sistema real devem ser incorporados ao
modelo e que suposições podem ser feitas sobre o problema, explicitando os objetivos
almejados, as variáveis de decisão e as restrições consideradas. Uma formulação errada do
problema certamente implicará em soluções ineficazes ou incorretas. Portanto, mesmo que um
modelo seja sempre uma simplificação da realidade, os aspectos considerados na formulação
matemática do problema devem ser suficientes para representar a situação tratada e atingir os
propósitos determinados.
Muitos dos Problemas de Corte e Empacotamento podem ser naturalmente formulados
em Programação Linear Inteira.
37
Identificação das Estruturas Redutíveis do Modelo
Os Problemas de Corte e Empacotamento apresentam essencialmente as mesmas
estruturas lógicas (HARWIG, 2003). Estes problemas requerem a utilização eficiente de
objetos maiores para obtenção de itens menores. De maneira geral, são conhecidas as
dimensões espaciais dos objetos e dos itens. Outras informações específicas podem ser
consideradas, tais como pesos dos objetos e dos itens, valores associados aos objetos e aos
itens, restrições de orientação dos itens.
Em princípio, é possível gerar todos os padrões de corte e empacotamento e, utilizando
um método exato, resolver o problema. Entretanto, como o número de padrões pode chegar
facilmente à ordem de milhões em casos práticos, a utilização do método exato torna-se
inviável. A idéia então é gerar de forma eficiente apenas um subconjunto destes padrões,
reduzindo o tamanho do problema. Dentre as principais entidades que determinam o número
de padrões de corte e empacotamento do problema estão os diferentes tipos de objetos e de
itens, suas dimensões espaciais e restrições de orientação.
Em geral, quanto mais tipos de objetos e de itens forem considerados, maior o tamanho
do problema. Quanto às dimensões, a questão é um pouco mais complexa. A relação se dá
basicamente pelas proporções dos tamanhos dos itens e dos objetos. Se as caixas são muito
pequenas quando comparadas aos objetos, o número de padrões de corte tende a ser mais
elevado. Por outro lado, quanto mais dimensões proporcionais os tipos de itens apresentarem,
menor o número de padrões de corte possíveis. As restrições de orientação, por sua vez,
impactam diretamente no número de tipos de itens considerados no problema. Caso sejam
impostas restrições de rotação das caixas, o número de padrões de corte tende a diminuir.
Determinação da Metaheurística Geradora de Subproblemas
Por fim, deve-se definir a metaheurística do Gerador de Instâncias Reduzidas. Esta
escolha é de fundamental importância porque, juntamente com a identificação das estruturas
redutíveis do modelo, contribui fortemente para a determinação dos subproblemas que serão
executados pelo Decodificador de Instâncias Reduzidas, que se apresenta como o maior
gargalo da metodologia híbrida proposta.
Além disso, esta escolha está diretamente relacionada com a estrutura a ser utilizada
para representar os dados do problema. A adequada definição da estrutura de dados é
extremamente importante, principalmente quando se está trabalhando com estruturas de
38
elevada complexidade computacional. Muitas vezes, torna-se complicado trabalhar com uma
representação natural, ou seja, de posicionamento dos itens por meio de coordenadas.
3.2. FORMULAÇÃO MATEMÁTICA DO PROBLEMA
Para formular o Problema de Carregamento de Contêiner, estendeu-se o modelo em
Programação Linear Inteira 0-1 apresentado em (MORABITO e ARENALES, 1997) e
discutido detalhadamente no Capítulo 2, com o intuito de permitir a rotação das caixas.
Considere um conjunto de caixas agrupadas em m tipos. Para cada tipo de caixa i,
caracterizado pelo comprimento, largura e altura dados pela tríade (l
i
, w
i
, h
i
), tem-se uma
quantidade b
i
de caixas. Além disso, cada tipo i pode apresentar diferentes modos de acordo
com as restrições de rotação das caixas. Considere todos os n modos originados a partir dos m
tipos de caixas. A Figura 11 ilustra os modos originados a partir de um único tipo de caixa.
Figura 11: Diferentes modos de um tipo de caixa.
Cada modo j é caracterizado por comprimento, largura, altura e tipo dados pela 4 - tupla
(l
j
, w
j
, h
j
, t
j
), com volume associado v
j
= l
j
× w
j
× h
j
. Considere também um contêiner
caracterizado pelas dimensões de comprimento, largura e altura dados pela tríade (L, W, H),
com volume associado V = L × W × H. As caixas devem ser carregadas ortogonalmente
dentro do contêiner. Cada variável 0-1 do modelo representa a decisão de colocar ou não uma
caixa do modo j na coordenada (x, y, z). Sem perda de generalidade, pode-se assumir que x, y
e z pertencem aos conjuntos de discretização, definidos como:
39
{}
{}
{}
.,...,1,min
Para evitar a interposição de caixas, define-se a matriz de incidência g
jdefpqr
, dada por:
que deve ser computada a priori para cada modo j (j = 1, ..., n), para cada posição (x
d
, y
e
, z
f
),
com d = 1, ..., |X|, e = 1, ..., |Y| e f = 1, ..., |Z|, e para cada posição (x
p
, y
q
, z
r
), com p = 1, ..., |X|,
q = 1, ..., |Y| e r = 1, ..., |Z|.
onde
,inteiro ,0,,
;,...,1,min
,inteiro ,0,,
;,...,1,min onde
,inteiro ,0,,
1
1
1
njhh
hHzhzz
njww
wWywyyY
njll
lLxlxxX
jo
jo
n
j
jj
jo
jo
n
j
jj
jo
jo
n
j
jj
==
⎪
⎭
⎪
⎬
⎫
⎪
⎩
⎪
⎨
⎧
≥−≤==
==
⎪
⎭
⎪
⎬
⎫
⎪
⎩
⎪
⎨
⎧
≥−≤==
==
⎪
⎭
⎪
⎬
⎫
⎪
⎩
⎪
⎨
⎧
≥−≤==
∑
∑
∑
=
=
=
γγ
ββ
αα
onde
Z
⎪
⎪
⎩
⎪
⎪
⎨
⎧
−+≤≤
−+≤≤
−+≤≤
=
contrário. caso ,0
.1
,1
,1 se ,1
jfrf
jeqe
jdpd
jdefpqr
hzzz
wyyy
lxxx
g
{
}
{}
{}
{}
()
.,...,1 e ,...,1 ,,...,1 ,,...,1 ,,...,1 com
contrário, caso ,0
;,, posição na colocadafor modo do caixa uma se ,1
:como definidas decisão de variáveisas e
max
,max
,max
, ainda
ZfYeXdnjmi
zyxj
a
hHzf
F
wWyeE
lLxdD
itjJ
fed
jdef
jfj
jej
jdj
ji
=====
⎩
⎨
⎧
=
−≤=
−≤=
−≤=
==
Sejam
40
Então, o Problema de Carregamento de Contêiner pode ser formulado como:
()
{}
1,0 com
,...,1,
,...,1,,...,1,,...,1,1 ..
/max
11 1
1111
1111
∈
=≤
===≤
∑∑∑∑
∑∑∑∑
∑∑∑∑
∈===
====
====
jdef
Jj
i
D
d
E
e
F
f
jdef
n
j
D
d
E
e
F
f
jdefjdefpqr
n
j
D
d
E
e
F
f
jdefj
a
miba
ZrYqXpagas
aVv
i
jjj
jjj
jjj
3.3. ESTRUTURAS REDUTÍVEIS DO MODELO
O modelo proposto para o PCC contém O(n |X| |Y| |Z|) variáveis e O(|X| |Y| |Z|)
restrições. O número de padrões de empacotamento deste modelo é definido pela quantidade
de modos das caixas n e pela cardinalidade dos conjuntos de discretização |X|, |Y| e |Z|. As
instâncias reduzidas dos problemas podem ser geradas desconsiderando-se, eventualmente,
alguns dos modos de caixas disponíveis e/ou algumas posições de alocação descritas pelos
conjuntos de discretização do problema original.
3.4. GERADOR DE INSTÂNCIAS REDUZIDAS
Para o Gerador de Instâncias Reduzidas, fez-se uso de um algoritmo genético. Cada
indivíduo é representado por um cromossomo binário, utilizado para codificar os conjuntos de
discretização do modelo, sendo que cada gen expressa um elemento desses conjuntos,
conforme a Figura 12. Um valor 0 (zero) significa que determinado elemento não é utilizado
no problema reduzido. Por outro lado, um valor 1 (um) significa que o elemento faz parte da
instância reduzida a ser resolvida. Cada cromossomo inicial é obtido da seguinte forma: um
modo é escolhido aleatoriamente e somente os elementos dos conjuntos de discretização
proporcionais às dimensões respectivas deste modo são considerados no problema reduzido.
Para a população inicial, são gerados p cromossomos, sendo que p é o tamanho da
população correspondendo a um pequeno subconjunto do espaço total de configurações. Este
parâmetro é importante, pois se p é pequeno o algoritmo converge rapidamente, não obtendo
bons resultados. Se p é grande, pode-se comprometer o tempo de execução do algoritmo ou
impossibilitar sua execução por falta de recursos computacionais.
41
Conjuntos de discretização:
X = {0, 3, 5, 6, 8, 9} Æ
x
1
x
2
x
3
x
4
x
5
x
6
Y = {0, 4, 7, 8} Æ y
1
y
2
y
3
y
4
Z = {0, 2, 4, 6, 7, 8} Æ z
1
z
2
z
3
z
4
z
5
z
6
Cromossomo:
x
1
x
2
x
3
x
4
x
5
x
6
| y
1
y
2
y
3
y
4
| z
1
z
2
z
3
z
4
z
5
z
6
1 0 0 1 0 1 1 1 0 1 1 1 1 0 1 0
Figura 12: Representação do cromossomo.
Cada subproblema gerado deve ser resolvido pelo Decodificador de Instâncias
Reduzidas. O valor da função-objetivo referente à solução ótima encontrada para a instância –
que representa o volume utilizado do contêiner – é atribuído ao valor de aptidão do indivíduo
associado. Nos casos em que não se consegue resolver ou nem mesmo gerar o modelo da
instância reduzida, em virtude da complexidade do subproblema, o indivíduo é descartado e
um outro cromossomo é gerado. A Figura 13, fictícia, exemplifica o espaço de busca da
metaheurística geradora de instâncias reduzidas, como também demonstra a distribuição dos
subproblemas conforme seu tamanho, qualidade da solução e possibilidade de aplicação do
Decodificador de Instâncias Reduzidas. O espaço de soluções da metodologia está reduzido
aos subproblemas aos quais o Decodificador de Instâncias Reduzidas é aplicável.
Figura 13: Distribuição dos subproblemas do espaço de busca da metaheurística.
42
Para obtenção das populações descendentes, são aplicados os operadores genéticos
convencionais de seleção, cruzamento e mutação. Como critérios de parada são utilizados, em
conjunto, um número máximo de gerações ngen, uma geração de convergência c e um limite
de tempo de execução t.
3.5. HEURÍSTICA DE CONSTRUÇÃO DE CAMADAS
Na implementação realizada, um componente heurístico de construção de camadas foi
incorporado à metodologia com o intuito de reduzir o comprimento teórico do contêiner.
Desta forma, cada camada gerada é tratada como uma instância de Problema de Carregamento
de Contêiner que deve ser resolvida pelo mecanismo híbrido, sendo a solução do problema
original construída em etapas seqüenciais.
Duas estratégias foram utilizadas para determinação do comprimento de cada camada:
numa delas, denominada MaxMax, o tamanho é determinado pelo tipo de caixa com a maior
dimensão e, na outra, denominada MaxMin, pelo tipo de caixa com a maior das menores
dimensões. Nos dois casos, são considerados apenas os tipos de caixas ainda disponíveis para
carregamento. A primeira estratégia garante que a camada pode comportar qualquer um dos
modos, enquanto a segunda assegura que qualquer tipo de caixa pode ser alocado. Quando o
comprimento livre do contêiner se torna menor do que o comprimento da camada gerada, o
espaço restante do contêiner é também considerado nesta iteração.
3.6. CONCLUSÃO
Neste capítulo, um framework híbrido para resolução de Problemas de Corte e
Empacotamento foi discutido detalhadamente e instanciado para resolver o Problema de
Carregamento de Contêiner. No capítulo seguinte, são apresentados alguns resultados obtidos
na realização de experimentos teóricos, como também de um estudo prático realizado em uma
grande empresa metalúrgica.
4. EXPERIMENTOS COMPUTACIONAIS
A metaheurística do Gerador de Instâncias Reduzidas foi desenvolvida em linguagem
Delphi e executada em uma máquina Intel Pentium 4, 3.2 GHz, 1GB de memória. Para o
Decodificador de Instâncias Reduzidas, utilizou-se a dll presente no LINGO 8.0 (SCHRAGE,
2000). Como experimentos computacionais, primeiramente foram realizados testes em uma
biblioteca largamente utilizada para validação de diversos trabalhos sobre Problemas de Corte
e Empacotamento. Posteriormente, fez-se uma aplicação da metodologia proposta em uma
grande empresa metalúrgica. Os resultados são apresentados a seguir.
4.1. EXPERIMENTOS TEÓRICOS
A metodologia híbrida foi aplicada a problemas de uma suíte conhecida na literatura –
disponível no repositório OR-Library –, divididos em grupos de acordo com a quantidade de
tipos de caixas. Para cada problema, foram utilizadas as duas estratégias de construção de
camadas – MaxMax e MaxMin –, sendo considerado para efeito de comparação o melhor
resultado obtido. Especificamente, foram considerados os problemas referentes ao pior e ao
melhor caso de cada grupo, obtidos pela heurística combinada B/R proposta por Bischoff e
Ratcliff (1995). Na Tabela 1 e na Tabela 2, são apresentados comparativamente, em termos de
aproveitamento do volume do contêiner, os resultados alcançados para estes problemas com a
heurística B/R e com o Algoritmo Híbrido (AH) proposto.
44
Tabela 1: Resultados comparativos para exemplos de pior caso de B/R.
Grupo Problema B/R (%) AH (%) Estratégia
thpack1 44 73,72 76,01 MaxMin
thpack2 11 73,79 86,19 MaxMax
thpack3 46 75,33 87,88 MaxMax
thpack4 93 78,38 88,10 MaxMin
thpack5 70 78,71 86,94 MaxMin
thpack6 93 75,22 87,60 MaxMin
thpack7 74 75,73 87,89 MaxMin
Tabela 2: Resultados comparativos para exemplos de melhor caso de B/R.
Grupo Problema B/R (%)
AH (%) Estratégia
thpack1 39 94,36 89,15 MaxMax
thpack2 33 93,76 87,47 MaxMin
thpack3 49 92,63 90,54 MaxMin
thpack4 22 90,06 85,26 MaxMin
thpack5 41 90,39 87,18 MaxMin
thpack6 58 89,15 86,15 MaxMax
thpack7 51 88,28 85,11 MaxMin
Nota-se que o Algoritmo Híbrido supera os resultados encontrados por Bischoff e
Ratcliff (1995) para os exemplos de pior caso da heurística B/R. Em contrapartida, a
heurística B/R tem maior aproveitamento do que o algoritmo AH para os exemplos de melhor
caso de Bischoff e Ratcliff (1995). Mas, de maneira geral, a metodologia híbrida se mostra
superior com média de aproveitamento do volume do contêiner de 86,53% contra 83,53% da
heurística combinada B/R. A Figura 14 ilustra um padrão de carregamento obtido por AH.
Figura 14: Padrão de carregamento AH (thpack1 – problema 44).
45
Além disso, foram computados os 50 primeiros problemas do grupo thpack1, que
apresenta três tipos diferentes de caixa. Conforme a Tabela 3, o Algoritmo Híbrido obteve
resultados bastante satisfatórios, com média de aproveitamento do volume do contêiner de
87,47% e desvio-padrão de 3,58, contra média de aproveitamento do contêiner de 85,40% e
desvio-padrão de 4,30 da heurística combinada B/R.
Tabela 3: Resultados obtidos para os 50 primeiros exemplos do grupo thpack1.
Problema AH (%) Estratégia Problema AH (%) Estratégia
01 89,29 MaxMax 26 83,19 MaxMax
02 89,95 MaxMin 27 86,00 MaxMax
03 81,02 MaxMin 28 88,51 MaxMin
04 88,50 MaxMin 29 91,72 MaxMax
05 90,26 MaxMax 30 90,08 MaxMin
06 90,11 MaxMax 31 89,17 MaxMin
07 81,41 MaxMax 32 92,06 MaxMax
08 88,22 MaxMax 33 84,36 MaxMin
09 87,60 MaxMax 34 89,40 MaxMax
10 87,92 MaxMax 35 84,04 MaxMin
11 89,19 MaxMin 36 89,11 MaxMax
12 88,18 MaxMin 37 91,75 MaxMax
13 90,11 MaxMax 38 80,85 MaxMax
14 86,37 MaxMin 39 88,30 MaxMax
15 85,92 MaxMax 40 88,79 MaxMax
16 86,98 MaxMax 41 86,44 MaxMin
17 90,64 MaxMin 42 91,34 MaxMin
18 80,55 MaxMax 43 91,37 MaxMax
19 90,37 MaxMin 44 74,63 MaxMin
20 90,57 MaxMin 45 88,80 MaxMax
21 89,27 MaxMin 46 87,73 MaxMax
22 87,89 MaxMax 47 82,16 MaxMax
23 83,03 MaxMax 48 88,17 MaxMax
24 86,35 MaxMin 49 89,12 MaxMax
25 87,31 MaxMax 50 91,23 MaxMax
Como parâmetros do algoritmo genético para realização dos experimentos teóricos,
depois de alguns testes para calibração, adotou-se tamanho de população de 50 indivíduos,
número máximo de gerações de 50 indivíduos, convergência de 10 iterações e tempo limite de
1 hora para cada camada.
46
4.2. ESTUDO DE CASO
A Esmaltec é uma das maiores empresas do setor metalúrgico do Brasil, atuando com
papel de destaque na produção de fogões, refrigeradores, freezers e bebedouros. Seu parque
fabril ocupa uma área total de 34,7 hectares, sendo um dos mais modernos da América Latina
em termos de equipamentos e tecnologias de produção e gestão. A fábrica possui área
construída de 65 mil m
2
, com capacidade para produzir 300 mil eletrodomésticos por mês.
A Esmaltec comercializa a sua linha de produtos através de uma grande rede de
revendedores no comércio lojista, cobrindo todo o território nacional com mais de 500 postos
de atendimento. A empresa ainda exporta parte de sua produção para os mercados da América
do Sul, América Central, Caribe, Estados Unidos, Oceania e Oriente Médio.
Os processos de logística são fundamentais para as atividades de escoamento de toda
essa produção. A empresa possui um sistema de estocagem vertical totalmente automatizado,
capaz de abrigar até 100 mil produtos. O terminal de transporte de cargas também é bastante
moderno e conta com um sistema de planejamento e de acomodação de carga largamente
conhecido no mercado mundial.
Nesse contexto, fez-se a aplicação da metodologia híbrida com o intuito de aperfeiçoar
o processo de acomodação de cargas em contêineres. Considerando que ganhos relativamente
pequenos em termos percentuais representam enorme economia diante da escala de produção
da empresa, os resultados preliminares obtidos se mostram animadores. Na Tabela 4, são
apresentados os dados dos contêineres e das caixas dos problemas abordados, onde L, W e H
se referem, respectivamente, às dimensões de comprimento, largura e altura do contêiner, e l,
w e h se referem, nesta ordem, às dimensões de comprimento, largura e altura das caixas
(todas expressas em mm), e b indica a quantidade de itens solicitados no pedido.
Tabela 4: Dados dos casos abordados.
Problema L W H l w h b
01 12000 2340 2680 1585 655 580 120
02 12000 2340 2680 1730 650 640 80
03 12000 2340 2680 870 585 525 280
04 12000 2340 2680 870 585 785 180
05 5810 2330 2380 870 585 525 120
06 5810 2330 2380 1585 655 580 50
47
Na Tabela 5, são apresentados os resultados comparativos das soluções encontradas
pelo MaxLoad Pro (ML), sistema atualmente em operação na Esmaltec, e pela metodologia
híbrida proposta (MH), onde X
ML
e V
ML
referem-se respectivamente à quantidade de caixas
alocadas e ao volume utilizado do contêiner pelo sistema utilizado na Esmaltec, enquanto X
MH
e V
MH
referem-se respectivamente à quantidade de caixas alocadas e ao volume utilizado do
contêiner pela metodologia híbrida.
Tabela 5: Resultados obtidos para os casos práticos abordados.
Problema
X
ML
V
ML
(%)
X
MH
V
MH
(%)
01 101 80,8 117 93,2
02 80 76,5 80 76,5
03 264 93,7 272 96,6
04 180 95,6 180 95,6
05 110 91,2 115 95,4
06 45 84,1 47 87,8
Dos seis problemas abordados, a proposta híbrida foi capaz de encontrar melhores
soluções em quatro casos, além de ter igualado o resultado dos outros dois. O resultado mais
expressivo foi obtido no problema 01, no qual a diferença entre as duas soluções, em termos
de volume utilizado do contêiner, foi de 12,4%. A seguir, na Figura 15 e na Figura 16, são
ilustrados os padrões de carregamento encontrados pelas duas abordagens para o problema 06.
Figura 15: Padrão de carregamento do MaxLoad Pro (problema 06).
48
Figura 16: Padrão de carregamento MH (problema 06).
Embora a metodologia híbrida não considerasse explicitamente restrições sobre
estabilidade da carga, foram obtidas soluções que representam carregamentos estáveis para os
problemas estudados.
No estudo de caso realizado, diante da utilização de um único tipo de caixa (o que
representa uma considerável diminuição do número de padrões de corte do problema), a
metodologia híbrida foi aplicada diretamente, ou seja, sem a utilização da heurística de
construção de camadas. Como parâmetros do algoritmo genético, adotou-se tamanho de
população de 50 indivíduos, número máximo de gerações de 50 indivíduos, convergência de
10 iterações e tempo limite de 5 horas.
4.3. CONCLUSÃO
Neste capítulo, foram desenvolvidos experimentos computacionais que comprovam a
eficácia e a eficiência da metodologia híbrida proposta, que se apresenta como principal
objeto de estudo deste trabalho. Foram obtidos resultados satisfatórios tanto nos testes
teóricos como também no estudo de caso realizado.
CONSIDERAÇÕES FINAIS
O desenvolvimento de uma metodologia híbrida para resolver Problemas de Corte e
Empacotamento se constituiu no grande propósito e na principal contribuição deste trabalho.
Além disso, apresentou-se uma extensão de um modelo em Programação Linear Inteira 0-1
para o Problema de Carregamento de Contêiner, modificado para permitir a rotação das
caixas. Um programa em LINGO deste modelo é apresentado no Apêndice I, bem como um
exemplo dos arquivos dos dados de entrada do problema, encontrado no Apêndice II.
Com o emprego combinado de algoritmos exatos e de metaheurísticas, a metodologia
híbrida proposta apresentou boa performance em termos de qualidade da solução gerada. Em
particular, fez-se uma aplicação da metodologia ao Problema de Carregamento de Contêiner,
obtendo-se resultados satisfatórios para instâncias que não poderiam ser resolvidas com a
aplicação direta de técnicas exatas de Otimização Combinatória. Acredita-se fortemente que a
metodologia híbrida proposta também possa ser aplicada com sucesso a outros Problemas de
Corte e Empacotamento unidimensional e bidimensional.
Como experimentos computacionais, foram realizados testes em uma biblioteca
largamente utilizada para validação de diversos trabalhos sobre Problemas de Corte e
Empacotamento. Além disso, fez-se uma aplicação da metodologia proposta em uma grande
empresa metalúrgica. A abordagem híbrida se mostrou superior nos dois contextos analisados,
embora o tempo de processamento ainda seja bastante custoso. Junte-se a isso o fato de que a
metodologia híbrida não considera explicitamente restrições sobre estabilidade da carga e,
portanto, operações de deslocamento sejam eventualmente necessárias.
50
Trabalhos subseqüentes poderão desenvolver diferentes aplicações da metodologia
híbrida proposta considerando características não levantadas do Problema de Carregamento
de Contêiner abordado neste trabalho – como estabilidade da carga e carregamento paralelo
de diversos contêineres –, ou ainda, tratando de outros Problemas de Corte e Empacotamento.
Buscando melhorar ainda mais os resultados aqui obtidos – em termos de qualidade da
solução e/ou tempo de processamento –, também poderão ser estudadas novas heurísticas de
criação da população inicial do algoritmo genético adotado para o Gerador de Instâncias
Reduzidas do problema. Outro importante detalhe técnico a ser considerado é que os
subproblemas teoricamente mais promissores – pois em sua maioria não podem ser resolvidos
por técnicas exatas – são conhecidos a priori. Isto poderia sugerir a substituição da
metaheurística do Gerador de Instâncias Reduzidas. Uma alternativa seria utilizar alguma
metaheurística de trajetória para gerar os subproblemas.
BIBLIOGRAFIA
BEASLEY, J.E. An exact two-dimensional non-guillotine cutting tree search procedure.
Operations Research, v. 33, p. 49-64, 1985.
BISCHOFF, E., MARRIOTT, M. A comparative evaluation of heuristics for container
loading. European Journal of Operational Research, v. 44, p. 267-276, 1990.
BISCHOFF, E., RATCLIFF, M. Issues in the Development of Approaches to Container
Loading. Omega International Journal of Management Science, v. 23, p. 377–390, 1995.
BLUM, C., ROLI, A. Metaheuristics in combinatorial optimization: overview and conceptual
comparison. ACM Computing Surveys, v. 35, p. 268-308, 2003.
CHEN, C. F., LEE, S. M., SHEN, Q.S. An analytical model for the container loading
problem. European Journal of Operational Research, v. 80, p. 68-76, 1995.
DORIGO, M. Optimization, learning and natural algorithms. Milão, ITA, 1992. PhD Thesis,
Politecnico di Milano.
DUMITRESCU, I., STÜTZLE, T. Combinations of local search and exact algorithms.
Lecture Notes in Computer Science, v. 2611, p. 211-223, 2003.
DYCKHOFF, H. A typology of cutting and packing problems. European Journal of
Operational Research, v. 44, p. 145-159, 1990.
GALVÃO, C., VALENÇA, M. Sistemas inteligentes: aplicações a recursos hídricos e
ciências ambientais. Porto Alegre: Ed. Universidade/UFRGS, 1999.
52
GEHRING, H., MENSCHNER, K., MEYER, M. A computer-based heuristic for packing
pooled shipment containers. European Journal of Operational Research, v. 44, p. 277-288,
1990.
GEHRING, H., BORTFELDT, A. A genetic algorithm for solving the container loading
problem. European Journal of Operational Research, v. 131, p. 143-161, 2001.
GEHRING, H., BORTFELDT, A., MACK, D. A parallel hybrid local search algorithm for the
container loading problem. International Transactions in Operations Research, v. 11, p. 511-
525, 2004.
GEORGE, J. A., ROBINSON, D. F. A heuristic for packing boxes into a container.
Computers and Operations Research, v. 7, p. 147-156, 1980.
GILMORE, P., GOMORY, R. A linear programming approach to the cutting stock problem
(part I). Operations Research, v. 9, p. 849-859, 1961.
GILMORE, P., GOMORY, R. A linear programming approach to the cutting stock problem
(part II). Operations Research, v. 11, p. 363-888, 1963.
GLOVER, F. Future paths for integer programming and links to artificial intelligence.
Computers and Operations Research, v. 13, p. 533-549, 1986.
GOLDBERG, D. E. Genetic algorithms in search, optimization and machine learning.
Reading: Addison Wesley, 1989.
HAESSLER, R. W., TALBOT, F. B. Load planning for shipments of low density products.
European Journal of Operational Research, v. 44, p. 289-299, 1990.
HARWIG, J. M. An adaptative tabu search approach to cutting and packing problems.
Austin, EUA, 2003. PhD Thesis, University of Texas.
HERZ, J. C. Recursive computational procedure for two-dimensional stock cutting. IBM
Journal of Research and Development, v. 16, p. 462-469, 1972.
HILLIER, F. S., LIEBERMAN, G. J. Operations Research. New York: McGraw-Hill, 1995.
HOLLAND, J. H. Adaptation in Natural and Artificial Systems. Ann Arbor: MIT Press, 1975.
53
KIRKPATRICK, S., GELATT, C. D., VECCHI, M. P. Optimization by simulated annealing.
Science, v. 220, p. 671-680, 1983.
LIBERALINO, C. H. P. O problema de bin packing tridimensional em contêineres: usando
interação com o usuário. Natal, Brasil, 2005. Dissertação de mestrado. Universidade Federal
do Rio Grande do Norte.
MARTINS, G. H. Packing in two and three dimensions. Monterey, EUA, 2003. PhD Thesis,
Naval Postgraduate School.
MORABITO, R., ARENALES, S. An and/or-graph approach to the container loading
problem. International Transactions in Operations Research, v. 1, p. 59-73, 1994.
MORABITO, R., ARENALES, S. Abordagens para o problema do carregamento de
contêineres. Pesquisa Operacional, v. 17, n. 1, p. 29-56, 1997.
OR-Library, http://people.brunel.ac.uk/~mastjjb/jeb/info.html, 2006. Originally described in
BEASLEY, J. OR-Library: distributing test problems by electronic mail. Journal of the
Operational Research Society, v. 41, p. 1069-1072, 1990.
OSMAN, I. H., LAPORTE, G. Metaheuristics: a bibliography. Operations Research, v. 63, p.
513-623, 1996.
PLATEAU, A., TACHAT, D., TOLLA, P. A hydrid search combining interior point methods
and metaheuristics for 0-1 programming. International Transactions in Operations Research,
v. 9, p. 731-746, 2002.
PUCHINGER, J., RAIDL, G. R., KOLLER, G. Solving a real-world glass cutting problem.
Lecture Notes in Computer Science, v. 3004, p. 162-173, 2004.
PUCHINGER, J., RAIDL, G. R. Combining metaheuristics and exact algorithms in
combinatorial optimization. Lecture Notes in Computer Science, v. 3562, p. 41-53, 2005.
SCHRAGE, L. Optimization Modeling with LINGO. LINDO Systems, Inc, 2000.
TERNO, J., SCHEITHAUER, J. R., SOMMERWEIß, U. An efficient approach for the multi-
pallet loading problem. European Journal of Operational Research, v. 123, p. 372-381, 2000.
TOPS Engineering Corporation. MaxLoad Pro Version 2.7X User's Guide, 2004.
54
TSAI, R. D., MALSTROM, E. M., KUO, W. Three-dimensional palletization of mixed box
sizes. I.I.E. Transactions, v. 25, n. 4, p. 64-75, 1993.
WOLSEY, L. A. Integer Programming. New York: John Wiley & Sons, 1998.
APÊNDICE I – MODELAGEM DO PROBLEMA
!PROBLEMA DO CARREGAMENTO DE CONTÊINER;
MODEL:
! DADOS DO PROBLEMA;
DATA:
QTDE_POSICOES = @FILE('matriz.ldt');
ENDDATA
! VARIÁVEIS DO PROBLEMA;
SETS:
CONTEINER: COMPR, LARGU, ALTUR;
TIPO: B, QTDE_ALOCADA, ID;
MODO: COMP, LARG, ALTR, TIPO_ID;
GRUPO/1..QTDE_POSICOES/;
ABCISSA: X; ORDENADA: Y; COTA: Z;
MATRIZ: MODO_ID, X_ID, Y_ID, Z_ID, GRUPO_ID;
POSICAO(ABCISSA, ORDENADA, COTA);
VARIAVEL(MODO, POSICAO) : A;
ENDSETS
! DADOS DO PROBLEMA;
DATA:
CONTEINER, COMPR, LARGU, ALTUR = @FILE('caixas.ldt');
TIPO, B, ID = @FILE('caixas.ldt');
MODO, COMP, LARG, ALTR, TIPO_ID = @FILE('caixas.ldt');
ABCISSA, X = @FILE('posicoes.ldt');
ORDENADA, Y = @FILE('posicoes.ldt');
COTA, Z = @FILE('posicoes.ldt');
MATRIZ, MODO_ID, X_ID, Y_ID, Z_ID, GRUPO_ID = @FILE('matriz.ldt');
ENDDATA
! TRANSFORMAÇÃO PARA VARIÁVEL BINÁRIA;
@FOR(VARIAVEL(I,J,K,L) : @BIN(A(I,J,K,L)));
! OBJETIVO;
[OBJ] MAX = @SUM(VARIAVEL(I,J,K,L) | (X(J) #LE# COMPR(1)-COMP(I))
#AND# (Y(K) #LE# LARGU(1)-LARG(I)) #AND# (Z(L) #LE#
ALTUR(1)-ALTR(I)) : 100 * A(I,J,K,L) * ((COMP(I) *
LARG(I) * ALTR(I))/(COMPR(1) * LARGU(1) * ALTUR(1))));
56
! RESTRIÇÕES;
@FOR(GRUPO(G) :
@SUM(MATRIZ(M) | G #EQ# GRUPO_ID(M) #AND# (X(X_ID(M)) #LE# COMPR(1)-
COMP(MODO_ID(M))) #AND# (Y(Y_ID(M)) #LE# LARGU(1)-LARG(MODO_ID(M)))
#AND# (Z(Z_ID(M)) #LE# ALTUR(1)- ALTR(MODO_ID(M))) : A(MODO_ID(M),
X_ID(M),Y_ID(M),Z_ID(M))) <= 1);
@FOR(TIPO(TP) :
@SUM(MODO(I) | ID(TP) #EQ# TIPO_ID(I) :
@SUM(POSICAO(J,K,L) | (X(J) #LE# COMPR(1)-COMP(I)) #AND#
(Y(K) #LE# LARGU(1)-LARG(I)) #AND# (Z(L) #LE# ALTUR(1)-ALTR(I)) :
A(I,J,K,L))) <= B(TP));
@FOR(TIPO(TP) :
@SUM(VARIAVEL(I,J,K,L) | ID(TP) #EQ# TIPO_ID(I) #AND# (X(J) #LE#
COMPR(1)-COMP(I)) #AND# (Y(K) #LE# LARGU(1)-LARG(I)) #AND# (Z(L) #LE#
ALTUR(1)-ALTR(I)): A(I,J,K,L)) = QTDE_ALOCADA(TP));
! SAÍDA DO PROBLEMA;
DATA:
@POINTER(1) = @STATUS();
@POINTER(2) = OBJ;
@POINTER(3) = QTDE_ALOCADA;
ENDDATA
END
APÊNDICE II – ARQUIVOS DE ENTRADA
!arquivo caixas.ldt
!DADOS DO CONTÊINER;
1 83 233 220
~
!TIPOS DE CAIXAS;
1 38 2
~
!DADOS DAS CAIXAS;
1 57 118 43 2
2 43 118 57 2
~
!arquivo posicoes.ldt
!ELEMENTOS DE X;
1 0
~
!ELEMENTOS DE Y;
1 0
~
!ELEMENTOS DE Z;
1 0
2 57
3 86
4 100
5 129
6 143
7 172
~
58
!arquivo matriz.ldt
!NÚMERO DE POSIÇÕES;
7
~
!MATRIZ DE INCIDÊNCIA ESPARSA;
1 1 1 1 1 1
2 2 1 1 1 1
3 1 1 1 2 2
4 2 1 1 2 2
5 1 1 1 2 3
6 1 1 1 3 3
7 2 1 1 2 3
8 2 1 1 3 3
9 1 1 1 3 4
10 1 1 1 4 4
11 2 1 1 2 4
12 2 1 1 3 4
13 2 1 1 4 4
14 1 1 1 4 5
15 1 1 1 5 5
16 2 1 1 3 5
17 2 1 1 4 5
18 2 1 1 5 5
19 1 1 1 5 6
20 1 1 1 6 6
21 2 1 1 4 6
22 2 1 1 5 6
23 2 1 1 6 6
24 1 1 1 6 7
25 1 1 1 7 7
26 2 1 1 5 7
27 2 1 1 6 7
28 2 1 1 7 7
~
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
