Abordagens para o Problema do Carregamento de Contêineres Reinaldo Morabito Universidade Federal de São Carlos Departamento de Engenharia de Produção 13565-905 - São Carlos, São Paulo e-mail:
[email protected] Marcos N. Arenales Universidade de São Paulo Departamento de Ciências de Computação e Estatística Instituto de Ciências Matemáticas de São Carlos 13560-970 - São Carlos, São Paulo e-mail:
[email protected]
Resumo O problema do carregamento de contêineres consiste em arranjar itens (caixas) de diferentes tamanhos dentro de objetos maiores (contêineres), de maneira a otimizar uma função objetivo, p.e., maximizar o volume carregado. Neste artigo estamos interessados no caso especial de arranjar o máximo volume de uma carga, composta de caixas de baixa densidade, dentro de um único contêiner, safistazendo restrições de estabilidade do carregamento. Revemos algumas abordagens conhecidas da literatura, tais como os procedimentos em duas etapas de carregar as caixas em camadas horizontais e em pilhas verticais, a aplicação de técnicas de programação dinâmica e, em particular, métodos de busca baseados na representação do espaço de soluções num grafo-e/ou. Algumas destas abordagens foram implementadas em micromputador para resolver um exemplo real com 784 caixas, e um exemplo pequeno mas difícil, com apenas 17 caixas, cuja solução ótima é do tipo não-guilhotinado. Palavras-chave: carregamento de contêineres, problemas de corte e empacotamento, busca em grafo-e/ou, padrões de corte tridimensionais.
Abstract The container loading problem consists of arranging items (boxes) of different sizes inside large objects (containers), in such a way as optimizing an objective function, e.g., maximizing the volume loaded. In this paper we are interested in the special case of arranging the maximum volume of a cargo, composed of low density boxes, in a single container, satisfying stability constraints for the cargo loading. We review approaches known in the literature, such as the two-phase procedures of loading boxes in either
horizontal layers or vertical stacks, the application of dynamic programming techniques and, in particular, search methods based on an and/or-graph representation of the solution space. Some of them were implemented in a microcomputer to solve a large real-life example of 784 boxes, and a hard small example of only 17 boxes, whose optimal solution is known to be of nonguillotine type. Keywords: container loading, cutting and packing problems, and/or-graph search, three-dimensional cutting patterns
1. Introdução O problema do carregamento de contêineres (container loading problem) consiste em carregar caixas de diversos tamanhos dentro de contêineres, de maneira a otimizar um certo objetivo, por exemplo, maximizar o aproveitamento do espaço disponível. Além das restrições geométricas envolvidas (o carregamento deve caber dentro do contêiner, duas caixas não podem ocupar o mesmo espaço), outras restrições devem ser eventualmente consideradas, como a estabilidade do carregamento. Ao estudar o problema, Bischoff e Marriott (1990) distinguiram casos em que uma grande carga deve ser transportada, combinando-se vários contêineres em função do custo-benefício, e casos em que o máximo possível de uma carga deve ser carregada dentro de um único contêiner. Os autores ainda distinguiram casos em que o peso da carga e sua distribuição dentro do contêiner governam as opções de carregamento e casos em que o objetivo é maximizar a utilização do contêiner em termos do volume e do valor da carga carregada. Aspectos de fragilidade e manuseio da carga também podem vir a ser considerados. Em particular, Gehring et al (1990) abordaram um caso com restrições de balanceamento e localização das caixas dentro do contêiner. Restrições de peso podem ser até certo ponto compensadas pela possibilidade de escolha das dimensões dos contêineres (contêineres menores são escolhidos para cargas mais densas). Uma escolha adequada do tamanho do contêiner em função da densidade da carga permite que sua capacidade volumétrica seja melhor utilizada. Haessler e Talbot (1990) abordaram o problema do carregamento de vagões ferroviários considerando apenas caixas de baixa densidade. Em muitos casos, a capacidade volumétrica limita a quantidade de caixas a ser carregada, antes que as restrições de peso sejam encontradas (George e Robinson, 1980). No presente artigo admitimos que a carga tem baixa densidade. A figura 1a ilustra dois contêineres e três caixas de tamanhos diferentes. Suponha, por exemplo, que dispomos de apenas um contêiner de cada tamanho e de duas caixas do tamanho 1, duas caixas do tamanho 2 e uma caixa do tamanho 3, e que os dois
contêineres juntos sejam suficientes para arranjar todas estas cinco caixas. Considere o seguinte problema de otimização combinatória: Como carregar todas as caixas dentro dos contêineres, tal que o volume total dos contêineres utilizados seja mínimo?
(1)
Um subconjunto de contêineres deve ser escolhido para carregar todas as caixas. A figura 1b ilustra uma solução para este simples exemplo, com todas as cinco caixas arranjadas dentro do contêiner menor. Note que se os contêineres forem idênticos, então o problema (1) consiste em minimizar o número de contêineres utilizados. Suponha agora que dispomos de cinco caixas do tamanho 1, três caixas do tamanho 2 e dez caixas do tamanho 3, e assim, os dois contêineres juntos não são mais suficientes para arranjar todas estas 18 caixas. Considere este segundo problema de otimização combinatória: Como carregar o máximo volume de caixas dentro dos contêineres disponíveis? (2) Um subconjunto de caixas deve ser escolhido e arranjado dentro dos contêineres disponíveis. A figura 1c ilustra uma possível solução, com parte das 18 caixas carregadas nos dois contêineres. Um caso importante do problema (2) é quando temos um único contêiner disponível. Os problemas (1) e (2) podem ser vistos como problemas de corte e empacotamento (PCE) tridimensionais (Dyckhoff, 1990). Há décadas muitos autores têm apresentado diferentes abordagens para resolver os PCE; entretanto, poucos autores se preocuparam com os casos tridimensionais. Para uma lista de referências, veja os exames de Dyckhoff e Finke (1992), Dowsland e Dowsland (1992), Sweeney e Paternoster (1992) e Morábito e Arenales (1992); veja também a edição especial recente dos PCE em EJOR (1995). Para uma discussão da relação entre problemas de carregamento de contêineres e de carregamento de paletes do distribuidor, veja p.e. Bischoff e Ratcliff (1995) e as referências lá citadas. Neste artigo estamos particularmente interessados no problema (2) com um único contêiner disponível. Admitimos que a carga tenha baixa densidade e consideramos restrições espaciais (restrições geométricas das caixas dentro do contêiner) e de estabilidade do carregamento (veja figura 8). Restrições de estabilidade do carregamento são difíceis de serem modeladas (os autores não têm conhecimento de qualquer tentativa na literatura)---na prática, elas são verificadas movimentando-se o carregamento produzido. Apesar de uma definição formal de estabilidade do carregamento estar além do escopo deste trabalho, nas abordagens a serem apresentadas discutiremos brevemente como certas regras podem produzir carregamentos com maior chance de estabilidade, pois permitem um rearranjo de peças sobrepostas de modo que soluções alternativas podem ser submetidas à prática de movimentação do carregamento.
Na seção 2 modelamos (2) como um subproblema de (1) (conforme Gilmore e Gomory, 1965), distinguindo os casos irrestrito e restrito (veja problemas (3)-(4) e (5)(7) na seção 2). Também apresentamos um programa linear 0-1 para estes casos, que é uma extensão do modelo de Beasley (1985b) originalmente proposto para um PCE bidimensional. Para resolver o problema irrestrito, três métodos aproximados são apresentados nas seções 3, 4 e 5, respectivamente. Os dois primeiros são generalizações do método em duas etapas de Gilmore e Gomory (1965): o primeiro arranja as caixas em camadas e o segundo, em pilhas. Ambos os métodos em geral produzem carregamentos estáveis. O terceiro é uma generalização das fórmulas recursivas de programação dinâmica de Beasley (1985a), e não tem garantia de estabilidade do carregamento. Para resolver tanto o problema irrestrito quanto o restrito, apresentamos na seção 6 a abordagem em grafo-E/OU (Morábito e Arenales, 1994), que é um método aproximado que realiza uma busca num grafo-E/OU para tentar encontrar um bom carregamento estável. No final do artigo (seção 7) apresentamos alguns resultados computacionais de um exemplo real e de um exemplo construído, comparando as soluções produzidas pelos métodos (exceto programação dinâmica).
2. Modelagem do problema Considere um conjunto de caixas agrupadas em m tipos. Para cada tipo i, caracterizado pelo comprimento, largura e altura (li, wi, hi), temos uma quantidade bi de caixas. Considere também um conjunto de contêineres agrupados em n tipos. Para cada tipo k, caracterizado pelas dimensões (Lk, Wk, Hk), estão disponíveis Bk contêineres. As caixas devem ser carregadas ortogonalmente dentro dos contêineres. Por simplicidade e sem perda de generalidade, admita que as caixas sejam carregadas com uma orientação fixada, isto é, com li, wi e hi paralelos a Lk, Wk e Hk, respectivamente. Gilmore e Gomory (1963, 1965) apresentaram um método para resolver o problema (1) baseado no método simplex (dado que ele pode ser modelado como um programa linear) e num subproblema que deve ser resolvido em cada iteração do simplex para produzir um padrão de carregamento. Este subproblema é dado por: m
max ∑ vi ai i =1
s.a.: (a1, a2, ..., am) corresponde a um padrão de carregamento tridimensional
(3) (4)
onde ai é uma variável inteira representando o número de caixas do tipo i no padrão, e vi é o multiplicador simplex (ou uma função dele) associado com uma base particular. Seja z denotando o maior inteiro menor ou igual a z. Este método funciona bem quando bi é
consideravelmente maior do que o produto Lk / li Wk / wi H k / hi , que corresponde ao número máximo de caixas do tipo i no contêiner (Lk, Wk, Hk). Considere agora apenas um contêiner de tamanho (L, W, H). Note que se vi em (3) for o volume da caixa do tipo i, então o problema (3)-(4) é o caso particular do problema (2) com um único contêiner disponível. Se a quantidade bi não for suficientemente grande (i.e. bi < Lk / li W / wi H / hi ), então a variável ai deve ser limitada superiormente por bi. Neste caso o problema (3)-(4) é chamado restrito, dado por: m
max ∑ v i a i
(5)
i =1
s.a.: (a1, a2, ..., am) corresponde a um padrão de carregamento tridimensional com: ai ≤ bi, i= 1, ..., m
(6) (7)
A restrição adicional (7) impõe consideráveis dificuldades para resolver o problema acima, em relação ao problema (3)-(4), conforme será visto. Tanto o problema (3)-(4) quanto o problema (5)-(7) podem ser escritos como um programa 0-1, estendendo-se para o caso tridimensional o programa 0-1 proposto originalmente em Beasley (1985b) para o caso bidimensional. 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. Sem perda de generalidade, pode ser mostrado que x, y e z pertencem respectivamente aos conjuntos de discretização (veja seção 6.3.1):
m X= x| x = ∑ α i li , x ≤ L − l0 , α i ≥ 0, i =1
inteiro
(8)
m Y= y| y = ∑ β i wi , y ≤ W − w0 , β i ≥ 0, i =1
inteiro
(9)
m Z= z|z = ∑ γ i hi , z ≤ H − h0 , γ i ≥ 0, i =1
inteiro
(10)
onde l0 = min{li, i = 1, ..., m} (similarmente para w0 e h0). No texto que segue denotamos por |A| o número de elementos do conjunto A. Sejam xj o j-ésimo elemento do conjunto X, yk o k-ésimo elemento do conjunto Y, e zl o l-ésimo elemento do conjunto Z (note que xj, yk e zl não são incógnitas, isto é, são determinados a priori). Se decidirmos colocar uma caixa do tipo i, com o canto conforme a figura 2 na posição (xj, yk, zl), então não podemos colocar outra caixa em qualquer
posição (xp, yq, zr) satisfazendo xj ≤ xp ≤ xj + li - 1, yk ≤ yq ≤ yk + wi - 1 e zl ≤ zr ≤ zl + hi - 1, com p = 1, ... , |X|, q = 1, ..., |Y| e r = 1, ..., |Z| (verifique na figura 2). Para evitar a sobreposição de caixas, definimos a matriz de incidência gijklpqr como:
1 se x j ≤ x p ≤ x j + li − 1, yk ≤ yq ≤ yk + wi − 1, e zl ≤ zr ≤ zl + hi − 1, gijklpqr = 0 caso contrario. que deve ser computada a priori para cada caixa do tipo i (i = 1, ..., m), para cada posição (xj, yk, zl) (j = 1, ..., |X|, k = 1, ..., |Y| e l = 1, ..., |Z|), e para cada posição (xp, yq, zr) (p = 1, ..., |X|, q= 1, ..., |Y| e r= 1, ..., |Z|). Sejam J(i) = arg maxj=1, ..., |X| {xj | xj ≤ L - li }, K(i) = arg maxk=1,...,| Y| { yk | yk ≤ W - wi } e L(i) = arg maxl=1,...,|Z| {zl | zl ≤ H - hi}, e as variáveis de decisão aijkl definidas como: 1 se uma caixa do tipo i e' colocada na posicao ( x j , y k ,z l ) a ijkl = 0 caso contrario. Note que, necessariamente, aijkl = 0 para todo j>J(i), ou k>K(i), ou l>L(i).. O problema pode ser formulado como: m
J(i)
K(i)
L(i)
i =1
j =1
k =1
l =1
m
J(i)
K(i)
L(i)
i =1
j =1
k =1
l =1
∑ ∑ ∑ ∑v a
max
s. a .:
i
∑ ∑ ∑ ∑g
J(i)
K(i)
L(i)
j =1 k =1
l =1
∑∑∑
(11)
ijkl
ijklpqr
a ijkl ≤ 1, p = 1, ..., | X|, q = 1, ..., |Y |, r = 1, ..., | Z| (12)
aijkl ≤ bi , i = 1, ..., m
com: aijkl ∈ {0, 1}, i=1, ..., m, j=1, ..., J(i), k=1, ..., K(i), l=1, ..., L(i)
(13) (14)
O modelo (11)-(14) 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 porém com um número ainda maior de variáveis e restrições. Nos casos práticos estes números chegam facilmente a ordem de milhões, o que desestimula o emprego das técnicas usuais de programação linear inteira. Além disso, a solução do modelo (11)-(14) não tem garantia de produzir um carregamento estável.
Outro modelo 0-1 para os problemas (3)-(4) e (5)-(7) pode ser encontrado em Tsai et al (1993), porém, com número de variáveis e restrições que cresce exponencialmente com o número de caixas a serem carregadas e também sem garantia de produzir um carregamento estável. Estas dificuldades em parte justificam a coleção de métodos heurísticos encontrados na literatura, como por exemplo em George e Robinson (1980), Han et al (1989), Correia et al (1992), Mohanty et al (1994), Morabito e Arenales (1994) e Bischoff et al (1995). Algoritmos de aproximação com limite de desempenho assintótico também são encontrados; veja p.e. Miyazawa (1997) e as referências nele citadas. Os métodos das próximas três seções tratam apenas o problema (3)-(4), enquanto que o método da seção 6 trata ambos os problemas (3)-(4) e (5)-(7). Todos os métodos são heurísticos.
3. Carregamento em camadas A seguir apresentamos um procedimento em duas etapas para se obter padrões de carregamento tridimensional em geral estáveis. Na primeira etapa, camadas horizontais são formadas arranjando-se caixas de mesma altura (i.e. no máximo m problemas bidimensionais são resolvidos) e na segunda etapa, estas camadas são escolhidas para serem empilhadas ao longo da altura do contêiner (i.e. um problema da mochila unidimensional é resolvido). 3.1. Etapa 1
Na primeira etapa, caixas com altura hj são escolhidas e arranjadas para formar camadas de dimensões (L, W, hj) (veja figura 3a). Seja λ ij o número de caixas do tipo i na camada j (i.e. uma camada com dimensões (L, W, hj)) e: Hj = { i | hi = hj, i = 1, ... , m } Se hk = hj, k ≠ j, então a camada k pode ser desconsiderada. Seja Vj definido como: V j = max ∑ vi λ ij
(15)
i ∈H j
s.a.: (λ 1j,λ 2j ,..., λ mj ) corresponde a um padrão de carregamento bidimensional, onde retângulos (li, wi), i ∈ Hj são escolhidos e arranjados em (L, W)
(16)
3.2. Etapa 2
Na segunda etapa, camadas j com valor Vj são escolhidas e empilhadas ao longo da altura H do contêiner (figura 3b). Seja µ j o número de vezes que a camada j é utilizada. O seguinte problema da mochila deve ser resolvido: m
max
∑V µ j
j
(17)
j =1 m
∑
hj µj ≤ H
(18)
com: µ j ≥ 0 e int eiro, j = 1, ..., m
(19)
s.a .:
j =1
O valor da variável ai em (3)-(4) é finalmente obtido por: m
ai = ∑ λ ij µ j , i = 1, ..., m j =1
Este procedimento generaliza o método de Gilmore e Gomory (1965) proposto para problemas bidimensionais com padrões de corte em 2-estágios. Cada problema bidimensional (15)-(16) da primeira etapa ainda pode ser resolvido heuristicamente por meio da solução de um conjunto de problemas da mochila (Gilmore e Gomory, 1965), e assim, as duas etapas envolvem apenas problemas unidimensionais. Na seção a seguir apresentamos uma outra maneira de generalizar o método de Gilmore e Gomory.
4. Carregamento em pilhas Outro procedimento em duas etapas, similar ao procedimento da seção 3, pode ser definido para resolver (3)-(4). Na primeira etapa, pilhas com altura máxima H do contêiner são formadas empilhando-se caixas, uma sobre a outra (i.e. vários problemas da mochila unidimensionais são resolvidos) e na segunda etapa, estas pilhas são escolhidas para serem arranjadas sobre a base (L,W) do contêiner (i.e. um problema de carregamento bidimensional é resolvido). Os padrões de carregamento obtidos em geral são estáveis. 4.1. Etapa 1
Admita sem perda de generalidade que l1 ≤ l2 ≤ ... ≤ lm. Na primeira etapa, pilhas de dimensões (lj, wk,, H) são formadas com caixas (li, wi, hi), i ∈ LWjk, empilhadas uma sobre a outra, onde: LWjk = { i | li ≤ lj e wi ≤ wk, i = 1, ..., m }, j = 1, ..., m, k = 1, ..., j
(20)
Note em (20) que não precisamos considerar LWjk, k>j, uma vez que: (a) as caixas do tipo i, i>j, não cabem na pilha (lj, wk,, H) quando li > lj, e (b) tal pilha não deixa de ser considerada em (20) quando li = lj. No caso de resultarem pilhas com mesmas dimensões, apenas uma pilha é considerada. Por exemplo, se wk = wj, k < j, então a pilha (lj, wk, H) pode ser desconsiderada, uma vez que ela é igual à pilha (lj, wj, H). Se o número de pilhas ainda for muito grande, podemos reduzí-lo, sob pena de perder soluções melhores, ao considerar apenas as m pilhas (lj, wj, H), j = 1, ..., m (conforme figura 4a). Seja λ ijk o número de caixas do tipo i na pilha jk (i.e. uma pilha com dimensões (lj, wk, H)). Definimos Vjk como: V jk = max
∑v λ i
ijk
(21)
i∈LWjk
∑hλ
≤H
(22)
com: λ ijk ≥ 0 e int eiro, i = 1,...,m
(23)
s. a.:
i ∈LWjk
i
ijk
4.2. Etapa 2
Na segunda etapa, pilhas jk com valor Vjk são escolhidas e arranjadas sobre a base (L,W) do contêiner (figura 4b). Seja µ jk denotando o número de vezes que a pilha jk é utilizada neste arranjo. O seguinte problema bidimensional deve ser resolvido: m
max
j
∑ ∑V j =1 k =1
s.a.: ( µ jk ,
jk
µ jk
(24)
j=1, ..., m, k=1, ..., j) corresponde a um padrão de
carregamento bidimensional, onde os retângulos (lj, wk), j=1, ..., m, k=1, ..., j são escolhidos e arranjados em (L, W) (25) O valor da variável ai em (3)-(4) é finalmente obtido por: m
j
ai = ∑ ∑ λ ijk µ jk ,i = 1,...,m j =1 k =1
Note que tanto o carregamento em camadas (15)-(19) quanto o carregamento em pilhas (21)-(25) são métodos heurísticos para o problema irrestrito (3)-(4), e que ambos envolvem resolver problemas unidimensionais e bidimensionais. Se os problemas
bidimensionais forem aproximados por um conjunto de problemas unidimensionais (Gilmore e Gomory, 1965), então os dois métodos envolvem resolver apenas problemas da mochila. Convém salientar que, para estender o carregamento em pilhas para resolver o problema restrito (5)-(7), precisamos incorporar no modelo (21)-(25) as restrições nãolineares: m
j
∑∑λ j =1 k =1
ijk
µ jk ≤ bi , i = 1, ..., m
(26)
e isto dificulta significativamente a aplicação do procedimento em duas etapas (similarmente para o carregamento em camadas (15)-(19)).
5. Programação dinâmica Beasley (1985a) propôs uma fórmula recursiva de programação dinâmica para o problema bidimensional com cortes guilhotinados (um corte é guilhotinado se, ao ser realizado sobre um retângulo, produz dois retângulos). Esta fórmula pode ser estendida para resolver o problema (3)-(4) ao impormos artificialmente a restrição de cortes guilhotinados (ao ser produzido sobre o paralelepípedo, o corte guilhotinado produz dois paralelepípedos). A solução obtida não tem garantia de estabilidade (veja p.e. as figuras 8a e 8b). Note também que, mesmo que a solução seja estável, ela não tem garantia de otimalidade, uma vez que o carregamento ótimo para o problema (3)-(4) pode ser não guilhotinado. Seja F(x,y,z) o valor do melhor carregamento tridimensional (guilhotinado) para um paralelepípedo de dimensões (x,y,z), dado por (para maiores detalhes veja Beasley, 1985a): F(x,y,z) = max{H(x,y,z); F(x1,y,z) + F( x − x1 x , y, z), x1 ∈ X, 0 < x1 ≤ x-1;
(27) (28)
F(x,y1,z) + F(x, y − y1 y , z), y1 ∈ Y, 0 < y1 ≤ y-1;
(29)
F(x,y,z1) + F(x,y, z − z1 z , y, z), z1 ∈ Z, 0 < z1 ≤ z-1}
(30)
x ∈ X ∪ {L}, y ∈ Y ∪ {W}, z ∈ Z ∪ {H}
(31)
onde x y z H(x, y,z) = max vi i = 1,...,m li wi hi x x = max{x1 | x1 ≤ x, x1 ∈ X }
(32) (33)
y y
=
z z
= max{z1 | z1 ≤ z, z1 ∈Z }
max{y1 | y1 ≤ y, y1 ∈Y }
(34) (35)
e X, Y e Z são definidos conforme (8)-(10) na seção 2. Note que F(L,W,H) requer memória computacional de O(|X| |Y| |Z|), o que nos casos práticos dificulta sua computação. Uma maneira de reduzir o esforço da computação de F(L,W,H) sob pena de perder a otimalidade é utilizar a heurística H4 descrita na seção 6.4.3, que reduz os conjuntos X, Y e Z. Esta abordagem, no entanto, possui uma deficiência em relação à abordagem da próxima seção, conforme mostrado em Morábito e Arenales (1995). A fórmula recursiva (27)-(31) pode ser estendida para tratar o problema restrito (5)-(7) definindo-se F(x,y,z,c) de maneira similar à F(x,y,z), onde c denota qualquer elemento do conjunto C = {(c1, c2, ..., cm) | 0 ≤ ci ≤ bi e inteiro, i = 1, ..., m} que permita produzir um padrão factível para o paralelepípedo (x,y,z) (veja Christofides e Hadjiconstantinou, 1995). Entretanto, devido ao número exponencial de elementos deste conjunto, o cálculo de F(L,W,H, C) torna-se inviável computacionalmente. A heurística H3 (seção 6.4.3) reduz a busca a um pequeno subconjunto de C.
6. Abordagem em grafo-E/OU Um grafo G = (V, E) consiste de um conjunto finito e não vazio V = {1, 2, ..., r } e um conjunto E = {e1, e2, ..., es} cujos elementos são subconjuntos de V de tamanho 2, isto é, eu = (i, j), onde i, j ∈ V. Os elementos de V são chamados vértices (ou nós), e os elementos de E são chamados arestas (ou arcos). Uma maneira de generalizar um grafo é permitir arcos em E de qualquer tamanho; por exemplo, um arco eu = (i, j, k) onde i, j, k ∈ V. Para esta generalização, G = (V, E) é chamado hipergrafo. Uma outra maneira de generalizar um grafo é definir os arcos como pares eu = (i, Vu), onde i ∈ V e Vu ⊂ V; por exemplo, um arco eu = (i, {j, k}) onde i ∈ V e {j, k} ⊂ V. Se Vu tem cardinalidade maior do que 1, então eu é chamado de arco-E e G de grafo-E/OU (caso especial de um hipergrafo orientado). Note que um arco de um grafo define uma relação entre dois nós, um arco de um hipergrafo define uma relação entre um subconjunto de nós, e um arco de um grafo-E/OU define uma relação entre um nó e um subconjunto de nós. Para maiores detalhes de grafos, hipergrafos, e grafos-E/OU, veja por exemplo Berge (1973) e Pearl (1984). A seguir definimos um grafo-E/OU particular para representar todos os possíveis padrões de carregamento tridimensional guilhotinados. Ambos os casos irrestrito e restrito (seção 2) são abordados.
6.1. Padrão guilhotinado irrestrito
A figura 5a esquematiza uma sequência de cortes guilhotinados feitos sobre o contêiner (L,W,H) (A na figura), para produzir o padrão de carregamento guilhotinado da figura 5b. Primeiro, um corte é feito no comprimento L do contêiner (corte 1 da figura), produzindo duas caixas intermediárias B e C, chamadas sucessoras de A. Em seguida, ambas B e C são cortadas independentemente. A caixa B é cortada na sua altura H (corte 2), produzindo D e E. A caixa C é cortada na sua largura W (corte 3), produzindo F e G. Note neste exemplo que as caixas B e C são caixas intermediárias e não aparecem na figura, enquanto que as D, E, F e G são supostas caixas (li, wi, hi), i=1, ..., m, ou caixas que correspondem a espaço não utilizado no padrão. Definimos o 0-corte como a opção de não cortar uma caixa, ou seja, ao ser aplicado sobre a caixa, deixa-a intacta. Obviamente, outros cortes alternativos poderiam ter sido feitos sobre cada caixa da figura 5, gerando diferentes padrões de carregamento. Se todas estas alternativas de corte fossem consideradas, incluindo o 0-corte, poderíamos ter gerado todos os padrões guilhotinados irrestritos (note que nenhuma consideração foi feita com respeito às quantidades disponíveis bi, i = 1, ..., m). Para cada caixa sucessora, um subproblema similar ao original é obtido (mas com tamanho menor). As caixas e os cortes ilustrados na figura 5a podem ser representados respectivamente como nós e arcos num grafo-E/OU orientado (i.e. uma árvore-E/OU neste exemplo particular). A caixa (L,W,H) corresponde ao nó inicial e as caixas após o 0-corte, aos nós finais. Cada corte guilhotinado feito sobre um nó não final corresponde a um arco-E ligando o nó aos seus dois sucessores. Além disto, cada 0-corte aplicado sobre um nó não final corresponde a um arco ligando o nó e uma réplica de si mesmo. Note que um nó não final (l,w,h) tal que l < l0 ou w < w0 ou h < h0 aceita apenas o 0-corte --- tal nó representa o espaço vazio no padrão de carregamento, onde l0 = min{li , i = 1, ..., m} (similarmente para w0 e h0). Considere agora a seguinte sequência de arcos (ou cortes): A partir do nó inicial, escolhemos um arco-E (corte guilhotinado) ou o 0-corte e, a partir de cada nó sucessor, escolhemos um arco-E ou o 0-corte, e assim por diante, até que todos os nós sejam finais. Esta sequência é chamada caminho completo no grafo-E/OU (note que todos os nós finais do caminho completo são obtidos por 0-cortes). Para cada padrão de carregamento existe pelo menos um caminho completo no grafo-E/OU cuja sequência de arcos (cortes) resulta no padrão de carregamento. Se o nó final corresponde a uma caixa do tipo i (i.e. o nó corresponde a (li, wi, hi)), então o seu valor é vi; caso contrário é nulo. O valor do caminho completo é definido como a soma dos valores dos seus nós finais. Portanto, o melhor padrão guilhotinado irrestrito corresponde ao caminho completo mais valioso do grafo-E/OU descrito.
6.2. Padrão guilhotinado restrito
Se existe um limite bi para o número de caixas do tipo i no padrão e bi < L / li W / wi H / hi , então o problema é restrito (seção 2). Considere um nó N do grafo. Note agora que a decisão de produzir caixas do tipo i a partir de N não é mais independente da decisão de produzir outras caixas do tipo i a partir de outros nós que pertencem ao mesmo caminho que inclue N. Seja
bi (N) o máximo número de caixas do tipo i que podem ser produzidas a
partir de N. Se N for um nó inicial, então bi (N) = bi, i=1, ..., m. Seja (N1, N2) um par de sucessores de N, obtidos por um corte guilhotinado. O seguinte problema deve ser resolvido: max ∑ vi (ai1 + ai2 ) m
i =1 1 1 2 1
s.a.: (a , a21 , ..., am1 ) é um padrão guilhotinado para N1 (a , a22 , ..., am2 ) é um padrão guilhotinado para N2 ( ai1 + ai2 ≤ b i ( N ), i = 1, ..., m )
(37) (38) (39) (40)
Não é uma tarefa trivial resolver este problema. Note que se b i (N), i = 1, ..., m , for grande o suficiente, a restrição (40) será redundante e o problema (37)-(39) pode ser decomposto em dois problemas independentes para N1 e N2, e voltamos ao caso anterior do problema irrestrito. Uma estratégia de busca é uma maneira particular de percorrer o grafo-E/OU (ou enumerar seus nós). Nos casos práticos a enumeração completa dos nós é, em geral, computacionalmente infactível. Uma maneira de reduzir a busca é evitar os padrões equivalentes, isto é, padrões diferentes que resultam no mesmo número de peças do tipo i, i=1, ..., m (figura 6). Na seção 6.3 descrevemos algumas regras para evitá-los e incluímos regras para garantir a estabilidade do carregamento. A busca também pode ser reduzida utilizando limitantes para evitar caminhos ruins ou pouco promissores (método branch-and-bound). Entretanto, mesmo utilizando regras e limitantes, a busca ainda assim pode ser inviável, e heurísticas precisam ser definidas para reduzí-la. Na seção 6.4 apresentamos limitantes, heurísticas e uma estratégia de busca que, combinados, nos permite encontrar soluções boas e computacionalmente factíveis para os problemas guilhotinados irrestrito e restrito.
6.3. Regras para evitar padrões equivalentes e tentar produzir padrões estáveis
Nesta seção apresentamos resumidamente algumas regras para evitar os padrões equivalentes. Para maiores detalhes, veja Herz (1972), Christofides e Whitlock (1977) e Morabito e Arenales (1994). No final da seção incluímos regras para tentar garantir que os padrões sejam estáveis. 6.3.1. Padrões normais
Herz (1972) e depois Christofides e Whitlock (1977) mostraram que, sem perda de generalidade, os cortes guilhotinados podem ser reduzidos às combinações lineares não negativas e inteiras dos tamanhos das caixas. Isto é, podemos reduzir os cortes ao longo do comprimento L, da largura W e da altura H do contêiner pelos elementos contidos nos conjuntos de discretização X, Y e Z em (8)-(10). Os padrões obtidos por cortes contidos nestes conjuntos são chamados padrões normais. 6.3.2. Exclusão
Christofides e Whitlock (1977) também mostraram que, sem perda de generalidade, o conjunto X pode ser reduzido definindo para cada nó N o conjunto X(N), considerando os efeitos de exclusão. Admita que N representa uma caixa de tamanho (x, y, z). Note que se uma caixa (li, wi, hi) é tal que wi > y ou hi > z, então seu comprimento li pode ser desconsiderado ao gerar X(N) (veja na figura 7 um exemplo com hi > z). O conjunto X(N) é definido por:
m X (N) = { x 1 | x 1 = ∑ α i li e ( se wi > y ou i =1
hi > z ⇒ α i = 0 ),
1 ≤ x 1 ≤ x − l0 , 0 ≤ α i ≤ bi e int eiro}
(41)
(similarmente para Y(N) e Z(N)). A fórmula proposta por Christofides e Whitlock (1977) para o problema bidimensional pode ser aqui estendida para gerar os conjuntos X(N), Y(N) e Z(N). Primeiro, os conjuntos são determinados para o nó inicial e depois, são facilmente determinados para cada nó N. Admita que l1 ≤ l2 ≤ ... ≤ lm. Para cada combinação dos comprimentos que somam x1, considere a máxima largura. Seja Fi(x1) a menor entre as
máximas larguras das caixas 1, 2, ..., i cujos comprimentos combinados somam x1. Assim, x Fi(x1)= min{Fi-1(x1); max{wi; min ρ {Fi-1(x1- ρ li), 1 ≤ ρ ≤ min 1 ,bi e ρ inteiro}}}, li li ≤ x1 ≤ L - l0 Fi(x1)= Fi-1(x1), x1 < li
onde F0(x1) = ∞ , x1 = 1, 2, ..., L - l0, e Fi(0) = 0, i = 0, 1, ..., m (similarmente, seja Gi(x1) a menor das máximas alturas das caixas 1, 2, ..., i cujos comprimentos combinados somam x1). Se Fi(x1) < ∞ e Gi(x1) < ∞ , então x1 =
∑
i j =1
α i l j , 0 ≤ α j ≤ b j e inteiro;
consequentemente, x1 ∈ X(N). Uma vez que Fi(x1) é independente do nó, ela pode ser gerada antes do início da busca. Depois disso, o conjunto X(N) pode ser facilmente obtido usando Fm(x1) e Gm(x1): Se Fm(x1) ≤ y e Gm(x1) ≤ z, então x1 ∈ X(N). Podemos reescrever X(N) em (41) como: X(N) = {x1 | Fm(x1) ≤ y
e
Gm(x1) ≤ z, 1 ≤ x1 ≤ x - l0}
(42)
(similarmente para Y(N) e Z(N)). 6.3.3. Simetria e ordenação de cortes
Considere novamente o nó N representando uma caixa de tamanho (x,y,z). Note que para cada corte x1 ∈ X(N), se (x-x1) ∈ X(N) então um deles pode ser desconsiderado, uma vez que ambos, ao serem aplicados sobre (x, y, z), produzem as mesmas caixas (x1, y, z) e (x-x1, y, z). Isto pode ser feito simplesmente substituindo 1 ≤ x1 ≤ x - l0 por 1 ≤ x1 x ≤ em X(N) (42). 2 Considere que a caixa (x, y, z) seja cortada em x1 ∈X(N), produzindo (x1,y,z) e (xx1,y,z). Depois disto, considere que (x-x1, y,z) seja cortado em x2 ∈ X(N), produzindo (x2, y, z) e (x-x1-x2, y, z). Note que estes três nós também poderiam ter sido produzidos cortando (x,y,z) em x2 e depois disto, cortando (x-x2, x, z) em x1. Christofides e Whitlock (1977) observaram que, sem perda de generalidade, esta duplicação pode ser evitada simplesmente introduzindo uma ordem (arbitrária) na sequência dos cortes ao longo de x (similarmente nos cortes ao longo de y e z). Se o problema for irrestrito conforme (3)-(4), então as regras de simetria e ordenação de cortes podem ser aplicadas sem perda de generalidade. Se o problema for
restrito conforme (5)-(7), então estas regras tornam-se heurísticas quando combinadas com a heurística gulosa H3, apresentada na seção 6.4.3 para resolver o problema (37)(40). 6.3.4. Estabilidade do carregamento
Também é necessário considerar a estabilidade das caixas que são empilhadas. A figura 8a ilustra um carregamento instável devido ao espaço vazio debaixo da caixa 3. Note que os métodos apresentados nas seções 3 e 4 em geral produzem carregamentos estáveis, por outro lado, o método na seção 5 pode produzir um carregamento como o da figura 8a. Uma regra heurística adicional pode ser imposta no processo de busca para tentar evitar carregamentos instáveis: (i) Após um corte ao longo da altura, todas as caixas sucessoras só podem ser cortadas ao longo de suas alturas, para garantir que tenhamos camadas (caixas intermediárias) compostas apenas de uma ou várias caixas iguais (veja padrão homogêneo descrito na seção 6.4.1). (ii) Se o carregamento não for estável, permutar estas camadas entre si na tentativa de obter um carregamento estável. A parte (i) da regra acima evita o carregamento instável da figura 8a, uma vez que após o corte zz', a caixa intermediária que resulta abaixo de zz' não pode sofrer o corte xx' (note na figura que esta caixa corresponde à camada composta de caixas diferentes 1 e 2). Por outro lado, apenas a parte (i) da regra não evita o carregamento instável da figura 8b (note o espaço vazio debaixo da camada z2, composta de duas caixas iguais). Ao aplicar a parte (ii), as camadas z1, z2 e z3 são permutadas e obtemos um carregamento equivalente estável (figura 8c). Notamos, entretanto, que apesar da regra proposta acina, carregamentos instáveis podem ainda ocorrer, bem como no método de carregamento em pilhas (seção 4). 6.4. Limitantes, heurísticas e estratégia de busca
Considere o nó N representando uma caixa (x, y, z) e seja M(N) = { i | li ≤ x, wi ≤ y, hi ≤ z, i = 1, ..., m }
o conjunto de tipos de caixas que podem ser carregados na caixa do nó N. 6.4.1. Limitantes inferior e superior
Um simples limitante inferior para o nó N pode ser definido a partir de padrões triviais que utilizam apenas um tipo de caixa (padrões homogêneos):
L(N) =
x y z = max vi min , b i (N) i ∈M(N) li wi hi x y z v j min , b j (N) l j w j h j
(43)
onde b j (N) é definido conforme apresentado na seção 6.2. Note, entretanto, que se b j (N) x y z é muito menor do que o produto , o padrão homogêneo conterá muito l j w j h j espaço vazio. Neste caso outros limitantes inferiores, combinando padrões homogêneos, podem ser descritos (veja Morábito e Arenales, 1994, 1996).
Um simples limitante superior para o nó N usado por outros autores (p.e. Beasley, 1985a) também pode ser aqui utilizado. Considere a relaxação do problema (5)-(7) levando em conta apenas a restrição de volume. Temos o seguinte limitante superior: U(N) = max s. a.:
∑v a
i ∈M(N)
i
i
∑ (l w h )a ≤ xyz
i ∈M(N)
i
i i
i
com: 0 ≤ a i ≤ b i (N) e int eiro, i ∈M (N)
(44) (45) (46)
Relaxando as condições ai ≤ bi (N) e inteiro em (46), obtemos um limitante superior fácil de ser computado: x y z U (N) = max vi , i ∈ M (N) li wi hi Apesar de serem simples, os limitantes L(N) e U(N) são efetivos, conforme resultados computacionais em Morabito e Arenales (1994).
6.4.2. Método branch-and-bound
Os limitantes inferior e superior da seção anterior podem ser usados para enumerar implicitamente os nós do grafo. Seja V(N) o melhor valor atual obtido para o nó N. V(N) é dado por um limitante inferior ou por algum caminho completo conhecido a partir do nó N, e é atualizado assim que uma solução melhor for obtida por meio dos sucessores de N. Por exemplo, se V(N) < L(N1) + L(N2), onde (N1, N2) é um par de sucessores de N, então V(N) é atualizado para L(N1) + L(N2). Além disso, se V(N) ≥ U(N1) + U(N2), então N1 e N2 não precisam ser explicitamente considerados. Note que se V(N) = U(N), então V(N) fornece o melhor
valor para o nó N. Estas observações caracterizam um método branch-and-bound onde a ramificação foi definida nas seções 6.1-6.3. Existem várias estratégias para percorrer o grafo-E/OU, isto é, diferentes maneiras para escolher um nó a ser ramificado. Antes de descrever uma estratégia de busca, discutimos outras heurísticas para descartar caminhos não promissores durante a busca. 6.4.3. Heurísticas
Três heurísticas apresentadas em Morábito e Arenales (1994), além de uma heurística devida a Beasley (1985a), podem ser utilizadas para reduzir o espaço de busca.
Heurística H1
Considere o nó N e um par de sucessores (N1, N2), e seja λ 1 uma fração previamente definida. A heurística H1 pode ser definida como: Se (1 + λ 1 ) V(N) ≥ U(N1) + U(N2) Então: Abandone a ramificação que leva a N1 e N2. Note que se λ 1 = 0, o procedimento acima deixa de ser heurístico. Heurística H2
Seja λ 2 uma outra fração previamente definida. A heurística H2 é definida como: Se λ 2 L(N) ≥ L(N1) + L(N2) Então: Abandone a ramificação que leva a N1 e N2. Note que se λ 2 = 0, o procedimento acima deixa de ser heurístico.
Heurística H3
Esta é uma heurística gulosa para tratar o problema (37)-(40). Inicialmente consideramos o nó N1 com o limite bi (N), i=1, ..., m e, após determinar um padrão de carregamento para a caixa representada por N1, consideramos o nó N2 com o limite bi (N) 1
1
a i , i = 1,...,m, onde a i é a quantidade de caixas do tipo i utilizadas em N1. Observe que as regras de simetria e ordenação de cortes (seção 6.3.3), em conjunto com H3, tornam-se uma nova heurística, dado que a ordem em que os nós são percorridos agora é relevante para se obter uma solução.
Heurística H4
Seja M um limite para o número de elementos a ser considerado do conjunto X em (8). Beasley (1985a) propôs um simples procedimento para garantir que esse número seja menor ou igual a M (similarmente para Y e Z). Este procedimento também pode ser aplicado para o problema restrito determinando X conforme (42). 6.5. Estratégia de busca
Uma estratégia de busca híbrida pode ser utilizada para percorrer o grafo-E/OU, que combina duas estratégias básicas: back-tracking (BT) e hill-climbing (HC) (Morábito et al, 1992; Morábito e Arenales, 1994). Seja DB um inteiro positivo denotando o limite de profundidade para a estratégia BT. Por simplicidade, o algoritmo descrito a seguir foi implementado como uma busca em árvore-E/OU:
Algoritmo BT-HC 1. Defina DB para cada árvore-E/OU a ser gerada. Seja RAIZ uma lista que inicialmente contém apenas o nó inicial. 2. Enquanto RAIZ não for vazia, faça: 3. Seja s o primeiro nó de RAIZ. Gere uma árvore-E/OU a partir do nó raiz s, utilizando a estratégia BT. Retire s de RAIZ. 4. Escolha o caminho mais valioso a partir de s e descarte os demais (estratégia HC). Se houverem nós neste caminho que não sejam finais e cuja profundidade seja DB, então inclua-os em RAIZ. No passo 3 a geração dos sucessores de s deve considerar as regras discutidas na seção 6.3, o método branch-and-bound da seção 6.4.2 e eventualmente as heurísticas discutidas na seção 6.4.3. No passo 4 cada caminho escolhido a partir de s corresponde a um trecho (com profundidade no máximo igual a DB) do caminho completo desde o nó inicial até os nós finais. Observe que a estratégia HC, baseada em otimização local em cada trecho, não garante encontrar o caminho mais valioso (i.e. o padrão de carregamento ótimo para os problemas (3)-(4) ou (5)-(7)). Note que o algoritmo BT-HC não requer grande quantidade de memória computacional, dado que ele armazena apenas o melhor caminho percorrido até então. Por outro lado, abordagens baseadas em programação dinâmica, como a da seção 5, requerem memória computacional de O(|X| |Y| |Z|) (veja também Gilmore e Gomory, 1965).
7. Resultados computacionais Os três métodos descritos nas seções 3 (carregamento em camadas), 4 (carregamento em pilhas) e 6 (abordagem em grafo-E/OU) foram implementados em linguagem Pascal (compilador Turbo-Pascal v5.5) num microcomputador PC-486DX2 (relógio de 66 Mherz, 640 Kbytes RAM, DOS 5.0). Para resolver os problemas unidimensionais (problemas da mochila) e bidimensionais envolvidos nos dois primeiros métodos, utilizamos respectivamente o algoritmo de busca em profundidade primeiro proposto em Gilmore e Gomory (1963) e o algoritmo BT-HC conforme Morábito et al (1992). Outros algoritmos poderiam ter sido escolhidos. A título de ilustração, escolhemos um exemplo real introduzido por George e Robinson (1980) referente ao carregamento de um contêiner numa companhia da Nova Zelândia. A tabela 1 apresenta os dados da carga composta de 784 caixas (com volume 26,325 m3) de m=8 tamanhos diferentes, que deve ser carregada num contêiner de tamanho (L,W,H) = (5793, 2236, 2261) milímetros (com volume 29,287 m3). Por conveniência, consideramos que cada caixa do tipo i, i = 1, ..., m, tem valor vi = (li wi hi)/(L W H). O carregamento deve ser estável e cada caixa pode ser arranjada sobre qualquer uma de suas seis faces dentro do contêiner (i.e. nenhuma orientação é fixada).
i 1 2 3 4 5 6 7 8
li 785 901 901 1477 614 400 264 385
wi 139 185 195 135 480 400 400 365
hi 273 195 265 195 185 135 400 290
bi 400 160 40 40 8 16 80 40 784 caixas
Tabela 1 - Dados do exemplo de George e Robinson (1980) A melhor solução obtida pela heurística proposta por George e Robinson (1980) carregou 783 caixas (com valor 0,8974 e volume 26,283 m3), deixando apenas uma caixa do tipo 7 para fora do contêiner (i.e. 0,0422 m3). Ao relaxarmos as quantidades disponíveis bi da tabela 1, obtemos um problema irrestrito. Resolvendo-se este problema por meio dos métodos de carregamento em camadas ou carregamento em pilhas, as soluções obtidas não satisfazem as restrições ai ≤ bi, i = 1 , ..., m, e portanto, são infactíveis para o problema original. Por exemplo, ao fixarmos uma orientação para as caixas, o valor da solução do modelo (15)-(19) (carregamento em camadas) é 0,9597 (obtido em menos de 1 segundo), e do modelo (21)(25) (carregamento em pilhas) é 0,9655 (obtido em 96 segundos). Entretanto, estas
soluções são infactíveis pois, envolvem mais de 40 caixas do tipo 8 (e portanto violam as restrições (26)). Fixando uma orientação para carregar as caixas
Mesmo fixando uma orientação para as caixas, os conjuntos de discretização X, Y e Z em (8)-(10) resultam extremamente grandes (i.e., |X| = 2655, |Y| = 1316 e |Z| = 1128, incluindo o elemento 0). Isto desencoraja qualquer tentativa de resolver otimamente o modelo (11)-(14), com ordem de bilhões de variáveis. Uma alternativa então é utilizar a abordagem em grafo-E/OU para o caso restrito (algoritmo BT-HC da seção 6), com a regra de estabilidade do carregamento da seção 6.3.4. A tabela 2 apresenta as soluções obtidas para diferentes valores de M (heurística H4) e do limite de profundidade DB (veja algoritmo BT-HC). Conforme indicam as colunas da tabela 2, estas soluções foram obtidas aplicando-se a heurística gulosa H3, porém desconsiderando as heurísticas H1 (i.e., λ 1 = 0), H2 ( λ 2 =0), e as regras de simetria e ordenação de cortes (seção 6.3.3).
M
DB
10 20 50 20 20
3 3 3 2 4
Heur. H3 Sim Sim Sim Sim Sim
λ1 λ 2
0 0 0 0 0
0 0 0 0 0
Simetria e ordenação Não Não Não Não Não
Valor da Solução 0,8097 0,8907 0,8840 0,8533 0,8927
Número de caixas 709 778 776 748 778
Tempo (seg) 1 23 733 2 299
Número de nós 4.065 85.277 2.736.123 6.471 1.260.813
Tabela 2 - Soluções do exemplo de George e Robinson (1980) com orientação fixada Note que ao fixarmos a orientação das caixas, nenhuma solução foi superior à solução obtida por George e Robinson (1980). Note também que, a medida que aumentamos os valores de M e DB, esperamos encontrar uma solução melhor. No entanto, devido à presença das outras heurísticas envolvidas, não temos garantia de que esta solução será de fato melhor (compare p.e. a segunda e terceira linhas da tabela 2, com M=20 e M=50, respectivamente). Carregando as caixas sobre qualquer uma de suas faces
Ao considerarmos o problema sem nenhuma orientação para carregar as caixas, devemos fazer algumas adaptações nas regras e expressões descritas nas seções anteriores, como por exemplo redefinir os conjuntos X, Y e Z da seção 6.3.2 e os limitantes inferior e superior da seção 6.4.1. A tabela 3 apresenta as soluções obtidas com a abordagem em grafo-E/OU ao carregarmos as caixas sobre qualquer uma de suas faces dentro do contêiner.
M 10 20 50 20 20 20 20
DB Heur H3 3 Sim 3 Sim 3 Sim 2 Sim 4 Sim 3 Sim 3 Sim
λ1
λ2
0 0 0 0 0 0,01 0,01
0 0 0 0 0 0,95 0,95
Simetria e ordenação Não Não Não Não Não Não Sim
Valor da Solução 0,8848 0,8989* 0,8989* 0,8859 0,8950 0,8989* 0,8975
Número de caixas 768 784 784 775 781 784 783
Tempo (seg) 8 128 1950 11 790 97 25
Número de nós 20.909 284.193 4.177.223 25.223 2.067.815 190.713 51.087
Tabela 3 - Soluções do exemplo de George e Robinson (1980) sem orientação fixada Note que a abordagem em grafo-E/OU encontra a solução ótima do exemplo de George e Robinson (com valor 0,8989 e volume 26,325 m3), uma vez que todas as 784 caixas foram carregadas no contêiner (veja segunda, terceira e penúltima linhas da tabela 3). Além disso, a abordagem em grafo-E/OU é capaz de encontrar soluções subótimas ainda melhores do que a solução obtida por George e Robinson (1980), num tempo relativamente pequeno. Veja, por exemplo, a solução com valor 0,8975 e volume 26,286 m3 na última linha da tabela, que deixa de fora apenas uma caixa do tipo 4 (i.e., 0,0389 m3). A escolha dos valores dos parâmetros DB, λ 1 e λ 2 baseia-se em trabalhos anteriores (Morábito et al, 1992, e Morábito e Arenales, 1994, 1996). Estes resultados são compatíveis com os publicados em Morábito e Arenales (1994). Mais recentemente, Bischoff e Ratcliff (1995) propuseram um algoritmo heurístico que também foi capaz de encontrar uma solução ótima do exemplo de George e Robinson, carregando todas as 784 caixas. Nossa experiência com a aplicação da abordagem em grafo-E/OU neste e em diversos outros exemplos sugere que ela é capaz de produzir boas soluções. Apesar disto, não é difícil construir um exemplo pequeno cuja solução ótima não possa ser encontrada. Considere o exemplo da tabela 4 com 17 caixas de apenas m=3 tipos diferentes, que devem ser carregadas num contêiner de tamanho (L,W,H)= (75,75,75) (note que o volume das caixas é igual ao volume do contêiner). Por simplicidade, admitimos que vi=(li wi hi)/(LWH). O carregamento deve ser estável e cada caixa pode ser arranjada dentro do contêiner sobre qualquer uma de suas seis faces.
i 1 2 3
li 60 45 15
wi 15 30 15
hi 30 30 15
bi 6 6 5 17 caixas
Tabela 4 - Exemplo com padrão ótimo não-guilhotinado
Note que ao relaxarmos as quantidades bi (problema irrestrito), a solução ótima com valor 1 é trivial (carregar 125 caixas do tipo 3) e é obtida em menos de 1 segundo por qualquer uma das abordagens de carregamento em camadas ou em pilhas. Para obter a solução ótima do problema restrito, estendemos o modelo (11)-(14) da seção 2 para o caso mais geral de nenhuma orientação das caixas ser fixada, e o implementamos na linguagem de modelagem GAMS (versão 2.25), utilizando o solver GAMS/OSL (Brooke et al, 1992). Note que, apesar deste exemplo ser relativamente pequeno (X = Y = Z = {0, 30, 15, 45, 60}), o programa 0-1 resultante envolve mais de 2000 variáveis 0-1 e quase 400 restrições. A solução ótima, obtida em alguns minutos, carrega todas as 17 caixas dentro do contêiner; entretanto, o padrão de carregamento correspondente é não-guilhotinado. Ao aplicarmos a abordagem em grafo-E/OU com os parâmetros M = ∞ , λ 1 = 0 e λ 2 = 0, a melhor solução encontrada coloca apenas 16 caixas (lembre-se que ela é capaz de gerar apenas padrões guilhotinados). Os resultados computacionais com e sem orientação fixada e para diferentes valores de DB estão apresentados na tabela 5. Algumas idéias para estender a abordagem em grafo-E/OU para gerar padrões tridimensionais nãoguilhotinados foram esboçadas em Arenales e Morábito (1995) - estas idéias estão na nossa agenda de pesquisa e deverão ser exploradas num trabalho futuro.
Orientação fixada Sim Sim Não Não Não
DB Heur. H3 3 Sim 6 Sim 3 Sim 6 Sim 9 Sim
Simetria e Valor da ordenação solução Não 0,6160 Não 0,6160 Não 0,9360 Não 0,9360 Não 0,9360
Número de caixas 13 13 16 16 16
Tempo (seg) 1 16 1 30 1100
Número de nós 2.395 159.365 1.979 137.041 4.209.639
Tabela 5 - Soluções do exemplo com padrão ótimo não-guilhotinado
Agradecimentos Os autores agradecem aos dois árbitros anônimos da revista pelos seus comentários pertinentes e úteis. Esta pesquisa contou com o apoio do CNPq (processos 522973/95-7 e 680082/95-6) e FAPESP (processo 1995/9522-0). Referências
(1) Arenales, M. e R. Morabito (1995). An AND/OR-graph approach to the solution of two-dimensional non-guillotine cutting problems. Eur.J.Oper.Res. 84, 599-617. (2) Beasley, J. (1985a). Algorithms for unconstrained two-dimensional guillotine cutting. J.Oper.Res.Soc. 36, 297-306.
(3) Beasley, J. (1985b). An exact two-dimensional non-guillotine cutting tree search procedure. Oper.Res. 33, 49-64. (4) Berge, C. (1973). Graphs and hypergraphs. North-Holland, Amsterdam. (5) Bischoff, E. e M. Marriott (1990). A comparative evaluation of heuristic for container loading. Eur.J.Oper.Res. 44, 267-276. (6) Bischcoff, E. e S. W. Ratcliff (1995). Loading multiple pallets. J.Oper.Res.Soc. 46, 1322-1336. (7) Bischoff, E.; F. Janetz; S. W. Ratcliff (1995). Loading pallets with non-identical items. Eur.J.Oper.Res. 84, 681-692. (8) Brooke, A.; D. Kendrick; A. Meeraus (1992). Release 2.25 GAMS - User's guide. The Scientific Press, San Francisco. (9) Christofides, N. e C. Whitlock (1977). An algorithm for two-dimensional cutting problems. Oper.Res. 25, 30-44. (10) Christofides, N. e E. Hadjiconstantinou (1995). An exact algorithm for orthogonal 2D cutting problems using guillotine cuts. Eur.J.Oper.Res. 83, 21-38. (11) Correia, M. H.; J. F. Oliveira; J. S. Ferreira (1992). Problemas de empacotamento tridimensional. Investigação operacional 12(2), 169-180. (12) Dowsland, K. e W. Dowsland (1992). Packing problems. Eur.J.Oper.Res. 56, 2-14. (13) Dyckhoff, H. (1990). A typology of cutting and packing problems. Eur.J.Oper.Res. 44, 145-159. (14) Dyckhoff, H. e U. Finke (1992). Cutting and packing in production distribution: Typology and bibliography, Springler-Verlag Co, Heildelberg.
and
(15) EJOR (1995). Special issue on cutting and packing problems, Eur.J.Oper.Res. 84. (16) Gehring, H.; K. Menschner; M. Meyer (1990). A computer based heuristic for packing pooled shipment containers. Eur.J.Oper.Res. 44, 277-288. (17) George, J. e D. Robinson (1980). A heuristic for packing boxes into a container. Computers and Oper.Res. 7, 147-156. (18) Gilmore, P. e R. Gomory (1963). A linear programming approach to the cutting stock problem - Part II. Oper.Res. 11, 863-888.
(19) Gilmore, P. e R. Gomory (1965). Multistage cutting stock problems of two and more dimensions. Oper.Res.14, 1045-1074. (20) Haessler, R. e F. Talbot (1990). Load planning for shipments of low density products. Eur.J.Oper.Res. 44, 289-299. (21) Han, C. P.; K. Knott; P. Egbelu (1989). A heuristic approach to the threedimensional cargo loading problem. Int.J.Prod.Res. 27(5), 757-774. (22) Herz, J. (1972). Recursive computational procedure for two-dimensional stock cutting. IBM J.Res.Develop. 16, 462-469. (23) Miyazawa, F. K. (1997). Algoritmos de aproximação para problemas de empacotamento. Tese de doutoramento, IME-USP, São Paulo, SP. (24) Mohanty, B.; K. Mathur; N. Ivancic (1994). Value considerations in threedimensional packing - A heuristic procedure using the fractional knapsack problem. Eur.J.Oper.Res. 74, 143-151. (25) Morabito, R. e M. Arenales (1992). Um exame dos problemas de corte e empacotamento. Pesquisa Operacional 12(1), 1-20. (26) Morabito, R. e M. Arenales (1994). An AND/OR-graph approach to the container loading problem. Int.Trans.Oper.Res. 1(1), 59-73. (27) Morabito, R. e M. Arenales (1995). Performance of two heuristics for solving large scale two-dimensional guillotine cutting problems. INFOR 33(2), 145-155. (28) Morabito, R. e M. Arenales (1996). Staged and constrained two-dimensional guillotine cutting problems: An AND/OR-graph approach. Eur.J.Oper.Res. 94(3), 548-560. (29) Morabito, R.; M. Arenales; V. F. Arcaro (1992). An AND/OR-graph approach for two-dimensional cutting problems. Eur.J.Oper.Res. 58(2), 263-271. (30) Pearl, J. (1984). Heuristics: Intelligent search strategies for computer problem solving. Addison-Wesley Co., Reading, MA. (31) Sweeney, P. e E. Paternoster (1992). Cutting and packing problems: A categorized, application-oriented research bibliography. J.Oper.Res.Soc. 43, 691-706. (32)
Tsai, R.; E. Malstrom; W. Kuo (1993). Three dimensional palletization of mixed box sizes. IIE Trans. 25(4), 64-75.
Figura 2 - Colocação da Caixa tipo i (li, wi, hi) na posição (xj, yk, zl) do contêiner.
Figura 3 - Carregamento de caixas em camadas.
(a) Figura 4 - Carregamento de caixas em pilhas
Figura 5 - Sequência de cortes e correspondente padrão de corte
(b)
Figura 6 - Três Carregamentos Equivalentes
Figura 7 - Regra de Exclusão: x1 ∉ X(N) devido a hi > z.
Figura 8 - Carregamentos: instável (a) (b), e estável (c)
