Um algoritmo polinomial para o problema de empacotamento de contêineres com
estabillidade estática da carga
1. Introdução
Problemas de corte e empacotamento têm sido extensivamente tratados na
literatura. Devido à diversidade de casos em que esses problemas podem aparecer
na prática, e a complexidade estrutural dos mesmos (os problemas são em geral
NP-difíceis), faz com que a grande maioria dos trabalhos encontrados na
literatura apresente abordagens heurísticas para a resolução desses. O
principal objetivo deste artigo é o de apresentar uma técnica que encontre boas
soluções para o problema de empacotamento de bins tridimensionais (3D-BPP) com
a restrição adicional que os itens empacotados estejam em equilíbrio dentro dos
bins. Note-se que no corpo do trabalho, os termos bin tridimensional e
container são tratados de maneira não distinta.
O 3D-BPP tem como dados de entrada:
* um conjunto de n itens (caixas retangulares), cada um desses itens sendo
caracterizados pela largura wj, altura hj e comprimento dj, referenciado
por uma tripla ordenada {wj,hj,dj}, ou seja, e.g. {wj,hj,dj} ¹
{hj,wj,dj} (rotações implicam em itens distintos), para todo jÎ J= {1, 2,
..., n};
* os itens não necessitam serem feitos de um mesmo material, muito embora,
supõe-se que todos esses possuam uma mesma densidade, são perfeitamente
rígidos, além de serem homogêneos; e
* um número limitado de bins (contêineres ou caixas retangulares maiores),
onde inicialmente há uma disponibilidade de pelo menos n bins idênticos e
tridimensionais, tendo dimensões, internas, comuns: largura W, altura H e
comprimento D.
Também, supõe-se, sem perda de generalidade, que todos os dados de entrada são
números inteiros positivos, satisfazendo às relações: wj< W, hj < H e dj < D,
para todo jÎ J.
A resolução do 3D-BPP consiste em se empacotar ortogonalmente todos os n itens,
utilizando a menor quantidade possível de bins. É importante notar, uma vez
mais, que na variante do problema aqui abordado, exige-se que o empacotamento
dos itens seja estável e que no melhor do conhecimento dos autores, não há
menção a isto na literatura.
As motivações práticas para o estudo do 3D-BPP vêm da grande quantidade de
aplicações industriais por ele modelados, as quais variam do carregamento de
cargas em aviões ao seqüenciamento (escalonamento) de tarefas em ambientes
multi-processados. Sob o ponto de vista teórico, o problema é uma extensão
natural do bem conhecido e já clássico problema Bin Packing (BPP), cf. Garey
& Johnson (1979) sendo ele também, NP-difícil no sentido forte.
Ressalve-se que, contrariamente ao Bin Packing usual (unidimensional), não se
conhece heurística alguma, s.m.j., para o 3D-BPP com garantia de desempenho, e.
g. para o BPP, a bem conhecida heurística FFD implica em um erro assintótico de
11/9 e um tempo de processamento limitado por O(n.log n).
Verifica-se que o 3D-BPP começa a ser pesquisado, mais intensivamente, há pouco
mais de dez anos. Conforme especificado em Dowsland (1991), há quantidade
restrita de trabalhos publicados relatando tais problemas de empacotamentos
tridimensionais. A primeira heurística apresentada para o 3D-BPP aparece em
Scheithauer (1991).
Chen et al. (1995) desenvolveram um modelo analítico para o problema do
carregamento de contêineres (PCC), no qual se inclui o 3D-BPP de forma
indireta. O modelo consiste em selecionar um número de bins para empacotar um
conjunto dado de itens. Os bins não precisam ser idênticos e os itens não
necessitam serem colocados ortogonalmente. O objetivo principal daquela
abordagem é o de se minimizar o espaço desocupado dentro dos bins, onde alguns
casos especiais do problema também são lá discutidos. O modelo exato é de
programação linear inteira mista zero-um, onde mesmo para problemas pequenos a
resolução prática dos mesmos torna-se computacionalmente inviável, tanto em
termos de tempo de execução quanto em memória.
A formulação matemática para o 3D-BPP, sem levar em conta as condições de
estabilidade estática dos itens dentro dos bins, pôde ser obtida a partir do
modelo de Chen et al. (1995), para o PCC, através de duas modificações no mesmo
que são:
* A substituição da função objetivo do modelo do PCC, que minimiza o espaço
não utilizado nos bins selecionados para o empacotamento de um conjunto
de itens, por minimizar o número de bins utilizados para empacotar todos
os itens dados;
* Atribuição de valores específicos um grupo de variáveis do PCC
(wxi = lzi = hyi = 1 e wyi = wzi= lxi= lyi= hxi= hzi= 0) para evitar que
rotações nos itens sejam permitidas.
Desta forma o 3D-BPP tem a seguinte formulação matemática:
Sujeito à:
onde:
n é a quantidade de itens;
m é o número de bins disponíveis, onde se supõe, sem perda de generalidade que
m=n;
M é um número arbitrário bastante grande;
aji é uma variável binária que é igual a 1 se o item j é colocado no bin i,
caso contrário ela é igual a 0;
hi é uma variável binária que é igual a 1 se o bin i é usado, caso contrário
ela é igual a 0;
(xj,yj,zj) variáveis contínuas (para localização dos itens) tendo como origem
as coordenadas do canto inferior esquerdo do item j;
ajk, bjk, cjk, ejk, fjk, gjk são as variáveis binárias definidas para indicar
a colocação do item j em relação ao item k.
A variável ajk é igual a 1 se o item j é colocado do lado esquerdo do item k.
Similarmente, as variáveis bjk, cjk, ejk, fjk e gjk representam quando o item j
está à direita, atrás, abaixo, acima ou à frente do item k, respectivamente.
Estas variáveis são necessárias e definidas somente quando j<k. Sem perda de
generalidade, supõe-se que cada contêiner é colocado com a sua largura ao longo
do eixo X, sua altura ao longo do eixo Y, enquanto que seu comprimento fica ao
longo do eixo Z, do sistema de coordenadas espaciais, com a origem sendo
definida no canto inferior esquerdo mais ao fundo do bin ou contêiner.
A resolução do modelo fornece uma solução ótima para o 3D-BPP. A função
objetivo deste modelo implica em minimizar o número de bins utilizados para
empacotar todos os n itens dados no problema. As restrições (I.2) à (I.7)
asseguram que os itens não vão ocupar o mesmo espaço dentro de um mesmo bin. A
restrição (I.8) verifica se há sobreposição de itens, e isto é realizado
somente para itens que estão colocados no mesmo bin. A garantia de que cada
item será colocado em exatamente um bin está descrita na restrição (I.9). Um
bin é considerado utilizado quando algum item é a ele alocado, este requisito é
descrito na restrição (I.10). As restrições (I.11) à (I.13) asseguram que todos
os itens colocados dentro de um bin encaixam-se dentro de suas dimensões
físicas.
A resolução do problema utilizando a este modelo pode ser feita através do uso
de pacotes comerciais de programação matemática tais como LINDO, CPLEX e etc.
Todavia, a quantidade de restrições (O(n3)) e variáveis (O(n2)) tornam inviável
sua resolução prática.
Em termos heurísticos, Pisinger et al. (1999) adaptaram para o 3D-BPP uma nova
metodologia de aproximação para problemas da otimização combinatória,
denominada Busca Local Direcionada GLS (Guided Local Search). Das meta-
heurísticas bastante utilizadas para resolver problemas de otimização, e.g.
Busca Tabu, Algoritmos Genéticos (AG) e etc., só há uma aplicação de AG,
Corcoran & Wainwright (1992), mas resolvendo o caso de preenchimento de
itens por intermédio de faixas bi-dimensionais.
Em Martello et al. (2000) tem-se o primeiro algoritmo exato para o problema
(3D-BPP), assim como para o do Carregamento de Contêineres (Container Loading
Problem), para os quais uma abordagem branch-and-bound foi utilizada. Naquele
mesmo artigo, duas heurísticas são propostas (H1 e H2), as quais serão
comentadas com mais detalhes adiante, já que uma delas (H1) é base de
comparação para a heurística aqui sugerida. Em todos esses artigos não há
menção alguma à estabilidade dos itens empacotados dentro dos bins.
O ataque ao 3D-BPP sugerido aqui se baseia em uma abordagem heurística a qual
apresenta bons resultados práticos. Duas versões para a heurística são
propostas, na primeira a estabilidade do empacotamento nos bins não é
considerada, enquanto na segunda versão sim, sendo que as duas versões são
comparadas com a melhor heurística conhecida da literatura.
A organização do trabalho segue: na Seção 2, são apresentadas as idéias básicas
da heurística polinomial. Na Seção 3, os critérios para que o empacotamento dos
itens dentro dos bins seja estável e a incorporação desses à heurística são
descritos; enquanto que na Seção 4 são apresentados os resultados obtidos nos
experimentos computacionais. As conclusões estão na Seção 5.
2. A Heurística Proposta: primeira versão
A primeira versão da heurística para resolver o 3D-BPP, na qual a estabilidade
estática não é considerada, será chamada de Heurística Sem Estabilidade
Estática (HSEE). Por vício de linguagem a palavra versão é omitida, idem para o
caso com estabilidade; reitera-se que a heurística é uma única, mas com duas
versões.
HSEE tem como idéia básica, a política do melhor preenchimento possível de um
único bin. Tal abordagem pode ser considerada como sendo "on line"
nos bins e não nos itens como usual; para o BPP o melhor preenchimento (e
conseqüente "fechamento") de um único bin apresenta bons resultados
práticos, cf. Soma et al. (1999) tendo sido utilizada, também, no 3D-BPP em
Martello et al. (2000).
Para o preenchimento de um bin é necessário que haja uma política que determine
a ocupação do espaço interno dos bins. Neste sentido, assume-se que uma dada
disposição espacial formada por um conjunto de itens já empacotados (E) no bin,
definirá duas regiões no mesmo: uma região chamada de "envelope",
associado ao empacotamento daqueles itens de E, e outra região
"vazia", na qual os itens ainda não alocados (F) podem,
eventualmente, ser fisicamente alocados naquele bin.
Tanto a região "vazia" dentro de um bin, quanto seu complemento,
podem ser determinados como funções de alguns pontos extremos nos quais itens
podem ser inseridos, 3D-Corner, (ponto de canto); sendo esta definição, uma
extensão do caso bi-dimensional, cf. Martello & Vigo (1998). Um ponto de
canto(PC) de um dado bin, seja ele p, indica que nenhum item j Î F poderá ter
alguma interseção à direita de p, ou acima de p, ou defronte a p, em relação ao
conjunto E no bin em questão, caso j houvesse que ser inserido em p. A
representação de p é feita usando-se o sistema de coordenadas cartesianas
(xp, yp, zp), com a origem sendo definida no canto inferior esquerdo mais ao
fundo do bin. Note-se que caso um item j Î F não possa ser alocado fisicamente
em p, pelo menos uma das condições, xp+wj < W ou yp+hj < H, ou zp+dj < D deve
ser violada.
Na Figura_1 tem-se um conjunto de itens já alocados e os respectivos pontos de
cantos (círculos pretos maiores). No processo de determinação dos PC's alguns
pontos de cantos "falsos" (pontos brancos, Figura_1) podem ser
gerados, os quais são facilmente detectados e removidos utilizando-se a
dominância de pontos. Por exemplo, os pontos a e b, representados na mesma
figura e, respectivamente, com coordenadas (xa, ya, za) e (xb, yb, zb) mostram
que somente a é um PC, pois a está "escondido" atrás de b. Note-se
que xa=xb,ya=yb,
zb>za
(critério de dominância).
A heurística HSEE trabalha basicamente com duas listas ordenadas: (F) uma lista
de itens que ainda tem que ser empacotados e a corrente lista de pontos de
cantos (L), sendo que a idéia básica é a de se alocar o primeiro item
disponível em F ao primeiro ponto de canto fisicamente viável de L . Após a
alocação, há uma atualização em F, e assim por diante, até que F =Æ. A lista F
é ordenada obedecendo a cinco regras distintas (associada à variável inteira
OI, com 1 < OI < 5). Ainda, a lista L , também, é ordenada por sete regras
distintas (dada pela variável inteira OCP, com 1 < OCP < 7).
A lista de itens F ordenada conforme OI pode ser vista como uma solução viável
para o 3D-BPP. A seguir descrevemos as regras para cada um dos valores de OI:
A lista dos pontos de cantos é definida por um conjunto de sete regras (OCP),
onde cada um dos valores de OCPinduz uma ordem parcial na correspondente lista
de pontos de cantos, dado por:
O valor da variável OCP determina a forma de preenchimento dos bins pelos
itens. A Figura 2 mostra duas formas de preencher um dado bin, uma onde OCP=1 e
uma outra onde OCP=6, para o mesmo conjunto de itens ordenados por OI=4.
A heurística HSEE determina no máximo 35 soluções viáveis para o problema e
como solução do problema o menor valor dentre essas soluções viáveis é
escolhido. Há ainda, um critério de parada adicional, quando a solução ótima do
problema é encontrada para tanto, utiliza-se um limitante inferior, L2, onde as
idéias gerais de seu desenvolvimento (L0 ® L1 ® L2) são sumarizadas a seguir:
* O limitante inferior contínuo L0: em que as dimensões dos itens não
precisam ser inteiros positivos, i. e., uma fração de um item pode ser
empacotada dentro de um bin;
* O limitante inferior L1: obtido por redução ao BPP usual, onde não se
leva em consideração no empacotamento, os itens, como sendo
tridimensionais;
* O limitante inferior L2: análogo ao limitante inferior L1, entretanto
todas as três dimensões dos itens são consideradas. Em todos os
experimentos aqui apresentados o limitante inferior L2é utilizado, por
ele dominar tanto L0 quanto L1, cf. Martello et al. (2000). Notando
ainda, que L2 é determinado em tempo quadrático, ref. op. cit., na
quantidade de itens.
Na Figura_3 a seguir tem-se a estrutura geral da heurística.
Para o cálculo da complexidade de HSEE, deve-se notar primeiramente que a
quantidade máxima de PC's é linear em n, e identificada recursivamente por:
T0=1;
T1=T0+2=1+2=3;
T2<T1+2=3+2=5;
.....................
Tn<Tn-1+2, ou ainda Tn<2n+1. Isto implica que Tn = O(n), para n > 0.
HSEE é limitada no tempo de processamento por O(5n log n + nO(n2) + 7n O(n)O(n
log n)); onde, a primeira parcela da soma determina o número de vezes que o
conjunto de itens é ordenado, a segunda parcela está associada ao cálculo de L2
e na última, o laço principal de HSEE que usa 5 formas de classificar o
conjunto de itens, com n itens a serem empacotados, e caso todos eles pudessem
ser alocados, ao máximo de (2n+1) = O(n) pontos de cantos. Ainda, que os PC's
são ordenados de 7 formas distintas, conforme definição de OCP, lembrando que a
ordenação de n itens é realizada em O(n log n) cf. Cormen et al.(1990). Logo,
HSEE tem como limite de tempo de processamento O(n3 log n).
3. Estabilidade Estática no Empacotamento
Nesta Seção é mostrado como tratar a estabilidade estática dos itens (caixas)
no empacotamento dentro dos bins, sendo que os estudos estão baseados em Beer
& Johnston (1976) e Meriam & Kraige (1986), que tratam da mecânica dos
corpos rígidos. Os conceitos utilizados para a determinação do equilíbrio
estático de corpos rígidos (itens) baseiam-se nos conceitos bastante conhecidos
de centro de gravidade, resultante de forças e de momentos, mas que serão aqui
re-apresentados no contexto do problema.
Em um item, seja ele j, que foi suposto ser um paralelepípedo rígido e
homogêneo, com seu peso uniformemente distribuído, o centro de gravidade G irá
se localizar na metade de cada uma das suas dimensões. Se j tiver dimensões wj,
hj e dj e estiver alocado em um bin v na posição xj, yj e zj, o centro de
gravidade G do item j no bin v é dado por: Gx = xj + wj/2, Gy = yj + hj/2 e Gz
= zj + dj/2; sendo possível associar em G a força Pj (peso do item).
A Figura_4 ilustra as situações que podem gerar instabilidade estática nos
itens já empacotados quando da inserção de um item adicional, no caso: item 3
(Figura_4a) e item 5 (Figura_4b). Também, foi suposto que os conjuntos de
itens, já empacotados, encontravam-se em equilíbrio antes da inserção desses
novos itens.
Na Figura_(4.a) vê-se que o centro de gravidade G do item a ser empacotado, no
caso item 3, não se encontra "apoiado" (linha de ação da força) sobre
uma superfície em equilíbrio, provocando um desequilíbrio no mesmo. Entretanto,
o item 3 estaria em equilíbrio caso G encontrasse apoiado: sobre o solo do bin;
ou sobre a superfície rígida de algum outro item; ou ainda, indiretamente sobre
as superfícies de alguns itens, conforme apresentado adiante.
Na Figura_(4.b) mostra que o centro de gravidade G do item a ser inserido, no
caso item 5, está apoiado diretamente sobre a superfície do item 3, mas que há
a possibilidade, daquele item, provocar instabilidade estática nas caixas
previamente empacotadas. A inserção do item 5 na posição indicada pela Figura_
(4.b), implicará em um deslocamento dos itens 5, 3 e 4, gerado pela rotação do
item 3. Note-se que isto decorre do fato do momento resultante dos itens
empacotados ser diferente de zero em relação ao centro de gravidade resultante
do empacotamento (Figura_8).
São apresentados, a seguir, a influência das forças e momentos no
empacotamento. Um item estará em equilíbrio estático quando as forças externas
a ele atuantes tiverem uma resultante nula e idem aos momentos. Desta forma,
obtemos as seguintes condições necessárias e suficientes para o equilíbrio de
um item, em relação a um dado ponto O:
onde e 
representam, respectivamente, a força e o vetor posição de
aplicação da força F no item, e <formula/> x [/
img/revistas/pope/v23n1/a07img04.gif] é o produto vetorial.
Decompondo cada força e cada momento em suas componentes retangulares (x, y e
z), encontramos as condições necessárias e suficientes para o equilíbrio de um
item,
As equações (1) expressam o fato de que as componentes das forças externas
devem ser compensadas nas direções x, y e z. As equações (2) expressam o fato
de que os momentos das forças externas, em relação aos eixos x, y e z, se
anulam. O sistema das forças externas, por conseguinte, não irá gerar
movimentos de translação ou de rotação no item considerado.
A Figura_5 mostra o momento, em relação ao ponto O, de um corpo sobre a ação da
intensidade de uma força atuando no ponto A.
Se um corpo puder ser dividido em diversos outros, o seu centro de gravidade G=
(Gx, Gy, Gz) pode ser determinado de acordo com as equações abaixo:
onde x, y e z são as coordenadas do centro de gravidade dos diversos corpos e P
é o módulo da força peso de cada um dos corpos.
Se o corpo é feito de material homogêneo, como adotado por hipótese para o 3D-
BPP, o seu centro de gravidade coincide com o centróide de seu volume e podem
ser utilizadas as seguintes equações:
onde V representa o volume de cada um dos corpos.
Analisando a situação ilustrada pela Figura_(4.a) constata-se que, sendo E o
conjunto dos itens já alocados no referido bin, com estabilidade estática, a
seguinte condição para que o item 3 fique em equilíbrio deve ser satisfeita:
ou
ou
onde Q=(xQ, yQ, zQ) e R=(xR, yR, zR), com xq< xQ<xq + wq , yQ=yq + hq ,
zq<zQ<zq + dq , xr<xR<xr + wr , yR=yr + hr e zr<zR<zr + dr .
A condição (5) indica que o item está localizado no solo do bin. A condição
(6), representada pela Figura_6, descreve o equilíbrio do item 3, quando o seu
centro de gravidade G estiver apoiado diretamente na superfície de cima de
outro item (s).
A condição (7), representada pela Figura_7, especifica que para o item 3 estar
em equilíbrio é necessário que exista um plano contendo o centro de gravidade
G, e os pontos Q e R, onde Q e R estão nas regiões das superfícies de cima dos
itens q e r, respectivamente, que tocam a superfície de baixo daquela caixa.
Pelo menos uma das condições (5), (6) ou (7), deve ser satisfeita a fim de
garantir a estabilidade estática de qualquer item que, porventura, venha a ser
inserido dentro de um bin.
Também, foi analisada a situação ilustrada pela Figura_(4.b) e verifica-se que
para o empacotamento permanecer em equilíbrio estável é necessário que o
momento resultante dos itens empacotados, em relação ao centro de gravidade do
empacotamento, seja igual a zero. Note-se que a resultante das forças no
empacotamento dos itens também será igual a zero. Resta, então, determinar o
valor de <formula/> (momento resultante do
sistema), onde O é o centro de gravidade do empacotamento dos itens, obtido
pelas equações (4), <formula/> é a força peso de
cada item no empacotamento e <formula/> é o vetor
posição de O ao centro de gravidade G de cada item. Assim, se [/img/revistas/
pope/v23n1/a07img07.gif] = <formula/> os itens do
empacotamento estarão em equilíbrio, ou seja, a carga é estável. Caso contrário
(<formula/> ¹[/img/revistas/pope/v23n1/
a07img08.gif]), a carga está instável e não é possível inserir o item 5 naquela
posição dentro do bin, pois ele irá gerar instabilidade no empacotamento. A
Figura_8, mostra o centro de gravidade do empacotamento ilustrado pela Figura_
(4.b).
A Heurística Com Estabilidade Estática (HCEE) segue a mesma estrutura de HSEE,
com a diferença quando da inserção de um item. Mais especificamente, sempre que
há a inserção de um item dentro de um bin com empacotamento estaticamente
estável, prossegue-se da seguinte forma: primeiro é testado se uma das
condições (5), (6) ou (7) é verdadeira, depois é verificado se [/img/revistas/
pope/v23n1/a07img07.gif] = <formula/>. Caso os
resultados dessas operações forem verdadeiros então o referido item é alocado
naquela posição dentro do referido contêiner, desta forma o sistema continuará
em equilíbrio. Caso contrário, tenta-se alocar o referido item em outros pontos
de cantos ou alocar outros itens no referido ponto de canto, e assim por
diante, até que todos os itens estejam alocados com estabilidade. Note-se que a
quantidade de operações necessárias para testar se um item pode ser incluído
(ou não) em um ponto de canto mantendo a estabilidade estática, pode ser
realizada em tempo constante, não alterando a ordem de convergência da
heurística, que a exemplo de HSEE também é limitada, no tempo máximo de
execução, por O(n4). Ainda, que em termos de espaço, as duas versões da
heurística são claramente limitadas por O(n).
4. Experimentos Computacionais
Um grande número de experimentos computacionais foi realizado, para avaliar o
algoritmo proposto. Foram executadas as duas versões da heurística, HSEE e
HCEE, comparando-os com a heurística H1, desenvolvida por Martello et al.
(2000), a qual gera bons resultados práticos.
A heurística H1 aloca itens dentro de um bin de acordo com uma variação do
preenchimento por camadas (prateleiras) sugerido em George & Robinson
(1980); sendo que os pontos de inserção são pontos de cantos bi-dimensionais. O
problema resultante torna-se, então, o BPP o qual é resolvido pela política de
First-Fit. A heurística H2 faz uma enumeração em árvore, onde os vértices são
pontos de cantos tri-dimensionais. A geração da árvore é feita primeiramente em
largura e a busca em profundidade é realizada para o preenchimento de um único
bin. A heurística H2 foi implementada e testada, todavia, devido ao grande
tempo de processamento e de memória utilizados ' notadamente devido à grande
quantidade de nós gerados pela árvore de busca ' não foi possível a execução da
mesma na máquina utilizada, para a quase totalidade dos testes realizados.
Lembrando uma vez mais, que tanto H1 quanto H2 não levam em conta o equilíbrio
da carga, quando do empacotamento dos itens.
As classes de testes são iguais àquelas definidas em Berkey & Wang (1987) e
Martello et al. (2000) e o conjunto de testes pode ser obtido por solicitação
aos autores do presente artigo. As seguintes classes de problemas foram
consideradas com uma quantidade de itens variando de 10 à 90:
Para as classes de 1 à 5 W = H = D = 100; para todas as classes os dados foram
gerados aleatoriamente a partir de funções de distribuição uniformes.
* Classe 1: A maioria dos itens são muitos altos e profundos,wjÎ [1, ½W],
hj Î [<formula/>H, H] e dj Î [[/img/
revistas/pope/v23n1/a07img09.gif]D, D], j Î J.
* Classe 2: A maioria dos itens são muitos largos e profundos,wjÎ [[/img/
revistas/pope/v23n1/a07img09.gif]W, W], hj Î [1, ½H] e dj Î [[/img/
revistas/pope/v23n1/a07img09.gif]D,D], jÎ J.
* Classe 3:A maioria dos itens são muitos altos e largos,wjÎ [[/img/
revistas/pope/v23n1/a07img09.gif]W, W], hj Î [[/img/revistas/pope/v23n1/
a07img09.gif]H, H] e dj Î [1, ½D], jÎ J.
* Classe 4:A maioria dos itens têm grandes dimensões,wjÎ [½W, W], hj Î [½H,
H] e dj Î [½D, D], jÎ J.
* Classe 5:A maioria dos itens têm pequenas dimensões,wjÎ [1, ½W], hj Î [1,
½H] e dj Î [1, ½D], j Î J.
* Classe 6: problemas gerados aleatoriamente em um intervalo pequeno,W = H
= D = 10, wj, hj, dj Î [1, 10].
* Classe 7: problemas gerados aleatoriamente em um intervalo médio,W = H =
D = 40, wj, hj, dj Î [1, 40].
* Classe 8: problemas gerados aleatoriamente em um intervalo grande,W = H =
D = 100, wj, hj, dj Î [1, 100].
* Classe 9: problemas em que os itens são gerados (aleatoriamente) cuja
solução é conhecida (puzzles), o empacotamento obedece a padrões não-
guilhotinados, caso o problema fosse considerado de corte.
A amostra considerada para cada uma das classes tem tamanho 10 (para cada um
dos valores de n). H1, HSEE e HCEE foram executados em um Pentium III (600 MHz
com 128 Mb de RAM) e o código foi implementado em Ansi C.
As Tabelas_1 e 2 apresentam o desvio médio em relação ao limitante inferior L2,
conforme definido em Martello et al. (2000) e as médias dos tempos (segundos)
de CPU. O desvio é definido como (Z ' L2)/L2, onde Z é o número mínimo de bins
encontrado pelos algoritmos para empacotar todos os itens, em cada uma das
instâncias. Já a Tabela_3 apresenta a média do volume do espaço não ocupado dos
bins utilizados para o empacotamento dos itens.
Verifica-se da Tabela_1, que HSEE apresentou os melhores resultados em todas as
classes, alcançando em média 66,5%, 66,8%, 75,7%, 67,9%, 62,6%, 62,6%, 55,7%,
62,3% e 61,9% dos resultados encontrados por H1, para as classes de 1 a 9,
respectivamente. Isto representa um índice médio de desvio de 64,6% dos
resultados alcançados por HSEE em relação a H1, que é indicativo que HSEE
produz soluções melhores que H1.
Comparando HCEE com H1, levando em conta a Tabela_1, verifica-se que HCEE
apresentou melhores resultados que H1 em sete das nove classes, alcançando as
seguintes médias para cada um dos conjuntos de testes: 73,1%, 210,8%, 83,1%,
71,6%, 75,5%, 64,2%, 78,7%, 86,8% e 116,1% daqueles encontrados por H1, para as
classes de 1 a 9, respectivamente. Em termos médios de quantidade de bins
utilizados, HCEE e H1 podem ser consideradas quase equivalentes, i.e. tem-se
4,5% menos bins abertos por HCEE que H1. Todavia, HCEE teria um índice médio de
desvio de 76,1% menor que H1, se não fossem computados as médias das classes 2
(210,8%) e 9 (116,1%). Nessas duas classes HCEE obteve os piores resultados,
quando comparado a H1. Para a Classe 9, uma provável explicação do por quê HCEE
produz piores resultados vem do fato dos itens terem de ser empacotados de
forma "não-guilhotinada", e a colocação de uma peça "no
meio" de um conjunto de itens já empacotados, via de regra, não ocorre,
devido aos encaixes estarem restritos aos pontos de cantos, por exemplo, como
na figura a seguir.
É importante notar ainda, que configurações como a da Figura_10, apresentada a
seguir, embora fisicamente estáveis não podem ser geradas por HCEE. Supondo que
a ordem de empacotamento dos itens, seja: item 1, item 4, item 2 e item 3. O
item 2 não poderia ser inserido no bin em questão, pois o centro de gravidade
do mesmo não está sobre o item 1 e também por que a altura dos itens 1 e 4 não
é igual (h1 > h4).
HCEE gerou em média 9,8%, 215,5%, 9,8%, 5,5%, 20,5%, 2,5%, 41,2%, 39,2% e 87,5%
a mais do que os resultados encontrados por HSEE para as classes de 1 a 9,
respectivamente. Isto dá uma idéia da quantidade de bins usados a mais de uma
solução sem estabilidade para uma solução que leva em conta os critérios de
estabilidade estática. Com base nesses valores, HCEE gerou uma média global de
47,9% mais bins que HSEE. Se as classes 2 e 9 fossem retiradas deste cálculo o
aumento cairia para 18,3%.
Na Figura_11 a seguir, apresenta-se uma solução gerada por H1, onde fica clara
a necessidade da inserção de prateleiras, caso contrário os conjuntos são
claramente instáveis. Note-se que nos bins 3, 4 e 6 o empacotamento é estável.
Alguns itens (nos bins 1, 2 e 5) não foram apresentados para uma melhor
visualização do empacotamento instável.
Na Figura_12 tem-se a representação gráfica do empacotamento do mesmo conjunto
de itens quando da utilização de HCEE. Apenas o item 2 não está apresentado,
por encontrar-se sobre a superfície do solo do bin 1 e atrás do item 10, no bin
1.
As tabelas apresentadas a seguir têm a comparação do tempo de processamento e a
média do volume do espaço não ocupado dos bins de H1, HSEE e HCEE.
Ao se analisar a Tabela_2, constata-se que HCEE, HSEE e H1 são bastante
rápidas. HCEE consumiu mais tempo que HSEE, devido ao tempo que se gasta para
encontrar uma outra solução com estabilidade estática. Mesmo assim, os tempos
obtidos por H1 e as duas versões da heurística podem ser considerados
aceitáveis, pelo menos sob o ponto de vista prático/industrial.
Verifica-se na Tabela_3, com base na coluna Média, que HCEE e H1 não
conseguiram preencher, na média, nem mesmo 50% do volume dos bins utilizados
para empacotar os itens, nas classes 2 e 7, respectivamente. Nas outras classes
a média de ocupação dos bins foi superior a 50%, tanto para H1 quanto para
HCEE. É interessante notar que com a métrica utilizada para a composição desta
tabela, HSEE não deve ser preterida à HCEE, pois para a Classe 9 e n = 10, o
problema foi resolvido de forma exata para todos os casos. Na mesma classe 9,
HSEE teve a melhor média de ocupação, chegando a preencher todos os bins em
mais de 60% na média. Exceto nas classe 2 e 9, HCEE também teve um desempenho
superior a H1.
5. Conclusões
Através dos experimentos computacionais, baseados em problemas da literatura,
há a indicação que a versão em que a estabilidade estática não é considerada
(HSEE) boas soluções são geradas e com tempo compatível com aquela sugerida em
Martelloet al. (2000). Foram introduzidos critérios para que o empacotamento
dos itens nos contêineres formasse um conjunto estaticamente estável, o que no
melhor do conhecimento dos autores é inédito. Mais ainda, que quando da
incorporação desses à heurística proposta, o tempo de processamento continuou
sendo adequado para aplicações industriais.
Estudos preliminares foram realizados para tratar também da estabilidade
dinâmica do empacotamento. Todavia, devido à grande quantidade de fatores a
serem considerados, e.g. coeficiente de atrito das caixas, velocidade e
aceleração dos bins, e etc, não foi possível a padronização desses em um único
estudo. Faz-se notar que em termos práticos, caso os bins não sofram variações
abruptas de velocidade, inclinação e curvatura, o que ocorre por exemplo no
transporte marítimo (contêineres em navios), o problema da estabilidade da
carga no 3D-BPP, resolvido por HCEE, pode ser considerado como melhor
alternativa àquelas sugeridas na literatura.
Um pacote gráfico foi também gerado, onde é possível acompanhar como se dá o
preenchimento dos bins, item a item. Por exemplo, as Figuras_2, 11 e 12 foram
por ele gerada. Os códigos fontes da heurística proposta, versões com e sem
estabilidade, e do pacote gráfico podem ser obtidos por solicitação junto aos
autores do presente artigo.
