O Problema da mochila compartimentada e aplicações
1. Introdução
Cortar objetos grandes (por exemplo, bobinas, placas, paralelepípedos) para a
produção de itens menores em quantidades bem definidos, ou empacotar itens
pequenos dentro de espaços bem definidos são problemas idênticos, considerando
que um item cortado de uma certa posição pode ser visto como ocupando aquela
posição (daí a referência na literatura a Problemas de Corte e Empacotamento).
O número de combinações possíveis dos itens dentro de um objeto (cada
combinação possível é chamada padrão de corte) é, em geral, muito grande e, a
tentativa de enumerá-las completamente é inviável do ponto de vista prático.
Uma função objetivo pode ser definida medindo, por exemplo, perdas no caso do
problema de corte, ou vazios no caso de empacotamento, ou custos, ou número de
objetos usados, etc. Um problema de corte e empacotamento consiste em
determinar um padrão de corte que minimize a função objetivo.
Dentro desta categoria de problemas estão vários clássicos da literatura de
pesquisa operacional, tais como os problemas da mochila, bin-packing, dentre
outros, os quais são, em geral, NP-completo (Garey & Johnson, 1979).
Vários trabalhos de revisão nos problemas de corte e empacotamento têm sido
publicados nas últimas duas décadas, como Hinxman (1980), Dyckhoff et al.
(1985), Dyckhoff (1990), Martello & Toth (1990), Dowsland & Dowsland
(1992), Dyckhoff & Finke (1992), Sweeney & Parternoster (1992), Wåscher
& Gau (1996), Dyckhoff et al. (1997), Lodi et al. (2002) e revistas de
prestígio em Pesquisa Operacional têm publicado edições especiais sobre o tema
tais como Dyckhoff & Wåscher (1990), Bischoff & Wåscher (1995),
Arenales et al. (1999).
Várias técnicas de resolução têm sido desenvolvidas, em geral especializando
procedimentos consagrados da Pesquisa Operacional, tais como: enumeração
implícita, programação dinâmica, relaxação lagrangeana, busca em grafos e
heurísticas.
Há, na literatura, um grande número de problemas de corte e empacotamento e
houve uma tentativa no trabalho de Dyckhoff (1990) de classificá-los conforme
algumas características. Em particular, uma primeira característica consiste
nas dimensões relevantes do processo de corte. Assim, podemos ter os problemas
de corte unidimensionais, com apenas uma dimensão relevante para o processo de
corte, como por exemplo, o corte de bobinas (de papel, aço, tecidos, plásticos,
etc) e barras. O clássico problema da mochila pode ser visto como um problema
de corte unidimensional. Outros problemas bidimensionais, onde duas dimensões
são relevantes, têm aplicações diversas, como por exemplo, o corte de placas de
madeira, chapas de aço, placas de vidro, tecido, etc. O problema de corte
estudado neste artigo é unidimensional.
Uma outra característica dos problemas de corte e empacotamento decorre da
elevada repetição de itens a serem produzidos, de modo que uma solução do
problema exige o corte de vários objetos em estoque com repetição de padrões de
corte (o número de objetos cortados por um mesmo padrão de corte passa a ser
uma variável fundamental na formulação do problema, que é aproximado com
sucesso por um problema de otimização linear). Este problema é conhecido na
literatura como Problema de Corte de Estoque e os trabalhos pioneiros de
Gilmore & Gomory (1961, 1963, 1965) utilizaram a técnica de geração de
colunas e permitiram pela primeira vez que problemas práticos pudessem ser
resolvidos com sucesso. A terminologia de problema de corte de estoque é também
usada para problemas onde a repetição dos padrões de corte é baixa (por
exemplo, apenas um objeto deve ser cortado por um padrão particular), mas há
uma demanda a ser atendida, mesmo que em quantidade pequena (por exemplo, um ou
dois itens). Neste caso, a solução arredondada da relaxação por otimização
linear pode não ser uma boa aproximação. As características destacadas por
Dyckhoff (1990) permitem uma classificação dos problemas de corte e
empacotamento, muito embora haja uma diversidade de problemas abrigados na
mesma categoria.
Técnicas de resolução de problemas de corte de estoque (sejam baseadas na
geração de colunas ou heurísticas gulosas, veja Hinxman, 1980 e Wäscher &
Gau, 1996) dependem fundamentalmente da resolução de um subproblema de corte e
empacotamento para a determinação do melhor padrão de corte para um particular
objeto em estoque. Nesse subproblema de corte não há obrigatoriedade de
satisfazer a demanda (caso a demanda seja baixa, deve-se cuidar para que a
demanda não seja excedida, caso contrário, o padrão de corte gerado não seria
usado uma única vez). O problema objeto deste trabalho consiste na determinação
de um único padrão de corte que, como observado, é um problema fundamental na
resolução de problemas mais gerais.
O Problema da Mochila Compartimentada modela a situação hipotética descrita no
resumo deste trabalho com importantes aplicações práticas. Uma aplicação
industrial surge no corte de bobinas de aço, sujeitas à laminação, que será
mais bem explicado em apêndice.
Alguns poucos pesquisadores estudaram o problema de corte de bobinas de aço,
onde ocorre o processo de laminação, porém o problema da mochila
compartimentada foi evitado com auxílio de heurísticas simples. Por exemplo,
Carvalho & Rodrigues (1994) utilizam a técnica de geração de colunas, mas
para a determinação dos padrões de corte (onde surge o problema da mochila
compartimentada) reduzem a busca a soluções homogêneas para cada compartimento.
Em Ferreira et al. (1990) uma heurística gulosa é utilizada na geração de um
conjunto de padrões de corte, sem a restrição de compartimentação, para então
descartar aqueles que não podem ser compartimentados através de regras
heurísticas simples. Em Pereira (1993) encontra-se uma boa descrição do
problema, considerando o processo de laminação e uma modelagem matemática que o
autor concluiu ser ineficiente na resolução de problemas práticos. Hoto (1996,
2001) e Marques (2000) focalizaram seus estudos no problema da mochila
compartimentada. Em particular, Hoto (1996) fornece os primeiros passos para
uma modelagem e métodos heurísticos e, mais tarde Hoto (2001), apresenta
métodos exatos e heurísticos para a mochila compartimentada, que difere do
presente trabalho por não incluir a limitação da quantidade de itens no padrão
de corte (na literatura de corte e empacotamento é chamado de problema
irrestrito). Mais recentemente, Zak (2002) estudou um problema relacionado com
o problema da mochila compartimentada, onde uma seqüência de estágios no
processo de corte obriga que bobinas intermediárias sejam produzidas antes dos
itens finais, definindo uma espécie de compartimentos. Porém, os itens podem
ser acomodados livremente dentro de cada compartimento, isto é, não há uma
partição dos itens em agrupamentos (medicamentos, alimentos, etc.), como
suposto no problema da mochila compartimentada a ser estudado neste trabalho.
Uma variedade de problemas da mochila vem sendo estudada há várias décadas pela
comunidade de Pesquisa Operacional e revisados, por exemplo, nos trabalhos de
Martelo & Toth (1990) e Lin (1998). Porém o problema da mochila
compartimentada não foi estudado.
Na seção 2 definimos e modelamos o problema da mochila compartimentada. Na
seção 3 propomos três métodos heurísticos e seus desempenhos computacionais são
apresentados na seção 4. Por fim, em apêndice, mostramos uma aplicação prática
de relevância que aparece no corte de bobinas de aço, sujeito à laminação.
2. O Problema da Mochila Compartimentada
Nesta seção formalizamos o problema da mochila compartimentada e apresentamos
um modelo matemático de otimização não linear inteiro. Métodos heurísticos são
apresentados na seção 3.
2.1 Definição do Problema
Um alpinista deve carregar sua mochila com mpossíveis itens de sua utilidade. A
cada item i,o alpinista atribui umvalor de utilidadevi e seu peso li.O máximo
peso que o alpinista suporta em sua jornada é de L. Até este ponto, o problema
coincide com a formulação clássica do Problema da Mochila. Porém, os itens são
de agrupamentosdistintos (por exemplo: agrupamento 1: alimentos, agrupamento 2:
utensílios, agrupamento 3: roupas, agrupamento 4: calçados, etc.) e devem estar
em compartimentos separados dentro da mochila (isto é, cada compartimento
contém somente itens de um mesmo agrupamento). Os compartimentos da mochila são
flexíveis, permitindo que o alpinista carregue maior peso em alimentos do que
em roupas, bem como reservar vários compartimentos para alimentos. As
capacidades dos compartimentos (incógnitas) são limitadas inferior e
superiormente (de acordo com os agrupamentos), caso estes sejam criados,
digamos por: e 
(isto é, a soma dos pesos li dos itens alocados no compartimento
deve ser superior ou igual a <formula/> e inferior ou
igual a <formula/>). A cada compartimento é associado
um custo ck, caso este seja preenchido com itens do agrupamento k e, além
disso, cada compartimento incluído na mochila produzirá uma perda da capacidade
da mesma, digamos, S (isto é, se, por exemplo, três compartimentos forem
utilizados, então a capacidade disponível na mochila será de L-3S, ao invés de
L).
O Problema da Mochila Compartimentada consiste em determinar as capacidades
adequadas de cada compartimento e como estes devem ser carregados de modo que o
valor de utilidade total (soma dos valores de utilidade de todos os itens
selecionados) seja máximo, descontando-se os custos dos compartimentos, os
quais dependem dos agrupamentos com que foram preenchidos (ck).
2.2 Um Modelo Matemático para o Problema da Mochila Compartimentada
Nesta seção propomos uma modelagem matemática para oProblema da Mochila
Compartimentada. Observe que a cada compartimento da mochila, tem-se associado
um único agrupamento k de itens, ou seja, não se admite itens de agrupamentos
distintos no mesmo compartimento.
Dados_do_problema:
* M = {1,...,m}: conjunto dos tipos de itens;
* li: peso (Kg) do item i(li>0), i=1,...,m;
* vi: valor de utilidade do item i(vi
³
0), i=1,...,m;
* di: limite máximo de itens i na mochila,i=1,...,m;
* K: número total de agrupamentos distintos;
* Ak: agrupamento k, k=1,...,K, (M = A1
È
A2...ÈAK , Ai
Ç
Aj =Æ, com i¹j);
* Nk: número total de possíveis compartimentos para o agrupamento k(por
exemplo: A1={1,2}, então L11 = 2l1+l2 , L21 = l1+2l2 , L31 = 2l1+2l2 ,
etc., são duas possíveis capacidades de compartimentos para o agrupamento
1. Ljk referencia o j-ésimo compartimento associado ao agrupamento k. O
número Nk depende essencialmente dos itens do agrupamento k);
* ck: custo de um compartimento de itens do agrupamento k, onde ck³0,
k=1,...,K;
* L: capacidade (Kg) da mochila;
* <formula/>: capacidade mínima (Kg) de cada
compartimento associado ao agrupamento Ak;
* <formula/>: capacidade máxima (Kg) de cada
compartimento associado ao agrupamento Ak ([/img/fbpe/pope/v22n3/
a01img01.gif]
<
<formula/>);
* S: perda (Kg) decorrente da inclusão de um novo compartimento na mochila.
Variáveis:
* - ijk: número de itens do tipo i, do agrupamento k, no compartimento do
tipo j, i=1,...,m, k=1,...,K e j=1,...,Nk;
* -jk: número de vezes que o compartimento (padrão) do tipo jalocado com o
agrupamento k é repetido na mochila, k=1,...,Kej=1,...,Nk.
Assim, o j-ésimo compartimento com itens do agrupamento k tem:
* A capacidade ocupada dada por:
* O valor de utilidade dado por:
Um modelo matemático para o problema da mochila compartimentada pode ser
escrito por:
A função objetivo (3.1), a ser maximizada, fornece o valor total de utilidade,
descontado o custo de alocar os compartimentos; as restrições (3.2) e (3.3)
fornecem, respectivamente, o valor de utilidade e a capacidade de cada
compartimento (obviamente, estas restrições podem ser eliminadas, substituindo-
as nas demais restrições); as restrições (3.4) impõem limites físicos aos
compartimentos, onde uma perda S deve ser considerada; as restrições (3.5)
limitam o número de itens na mochila (esta restrição é importante quando um
número excessivo de itens deve ser evitado, embora introduza não-linearidade
nas restrições) e, por fim, a restrição (3.6) correspondente aos limites
físicos da mochila. Observe que o problema (3.1-3.8) é um problema de
otimização não linear inteiro.
O modelo (3.1-3.8) permite considerar um agrupamento especial de itens,
chamados "itens livres", os quais podem ser incluídos na mochila sem
necessidade de compartimentação. Nas heurísticas a seguir, denominamos o
agrupamento K como o agrupamento de itens livres. Assim, para k=K, a restrição
(3.4) é desnecessária (ou, <formula/>=0 e[/img/fbpe/
pope/v22n3/a01img02.gif]= L de modo que é redundante) e cK=0. Na aplicação em
interesse, isto é, no corte de bobinas de aço sujeito à laminação, os
limitantes dos compartimentos são idênticos: [/img/fbpe/pope/v22n3/
a01img01.gif]=Lmin e <formula/>=Lmax, exceto para o
compartimento dos itens livres. Nas heurísticas propostas na próxima seção
usamos esta característica, embora seja facilmente implementável quando os
limitantes para os compartimentos dependem dos agrupamentos.
3. Heurísticas para o Problema da Mochila Compartimentada
Três heurísticas "gulosas" são propostas para a resolução do Problema
da Mochila Compartimentada, considerando uma quantidade máxima de itens a serem
alocados na mochila (di, para i=1,...,m). As heurísticas apostam que o alto
custo de incluir um novo compartimento sugere que, quando criado, seja o maior
possível (no caso do corte de bobinas de aço, apêndice A, este custo
corresponde à laminação que é um processo caro e demorado, justificando a
aposta). A seguir, fazemos uma exposição das heurísticas propostas e na seção 4
analisamos seus desempenhos computacionais.
3.1 Heurística de Decomposição
Esta heurística consiste de duas fases: Na primeira fase são resolvidos (K'1)
Problemas da Mochila de capacidade Lmax, um para cada agrupamento (exceto o
agrupamento Kdos itens livres), resultando nos melhores compartimentos
associados aos agrupamentos. Na segunda fase, um problema da mochila clássico é
resolvido, considerando os compartimentos obtidos na primeira fase como
superitens (na verdade, uma combinação de itens) juntamente com os itens
livres, para o carregamento da mochila.
Uma solução particular para (3.1-3.8) é construída com as seguintes
características:
* Com o intuito de maximizar a função objetivo (3.1) é conveniente a
construção de Vjk grande e, portanto, para cada agrupamento k,
construímos apenas o melhor compartimento (Nk = 1, de modo que j pode ser
suprimido) maximizando (3.2) restrito a (3.3), (3.4) e (3.7) (veja
problema (4.1-4.3)). O valor deaik (j suprimido) é determinado, isto é,
para cada agrupamento k, temos um compartimento;
* Com Nk = 1 (apenas um compartimento por agrupamento) eaik já determinado:
determina-se Lk (tamanho do compartimento k, veja (3.3), com o índice j
suprimido). O valor deak é determinado de modo a otimizar (3.1), sujeito
às demais restrições do problema (3.1-3.8) (veja problema (5.1-5.5)).
O algoritmo para a resolução desta heurística é apresentado a seguir.
Algoritmo:
Passo 1:Selecionar o melhor compartimento para o agrupamento k, k=1, , K'1,
resolvendo o seguinte Problema da Mochila, de capacidade Lmax:
Seja <formula/>: tamanho do compartimento k.
(note queaik são fixados neste passo).
Passo 2:Resolver o seguinte problema da mochila envolvendo os compartimentos
determinados no passo 1 e os itens livres:
* bké o número de vezes que o compartimento associado ao agrupamento k é
repetido na mochila,
* gké o número de vezes que o item livre k é repetido na mochila.
3.2Heurística do Melhor Compartimento
Nesta heurística, como na anterior, o melhor compartimento para cada um dos
agrupamentos de itens é determinado. Temos definido, então:
Em seguida, escolhe-se, o compartimento de maior valor por unidade ([/img/fbpe/
pope/v22n3/a01img04.gif]), sendo então, alocado na mochila. Atualizam-se os
dados e repete-se o processo até que um padrão seja gerado. Com isto é evitado
o problema (5.1-5.5) do procedimento anterior. Porém, apesar de apenas um
compartimento ser gerado por agrupamento, a cada passo, é possível ter
diferentes compartimentos com o mesmo agrupamento, algo excluído na heurística
anterior, onde era permitida apenas a repetição do melhor compartimento. O
algoritmo é apresentado passo a passo a seguir.
Algoritmo:
Passo 1:lutil¬L; "lutilguarda a capacidade disponível na mochila a
cada iteração"
Passo 2:Para k = 1 a K'1, faça:
2.1 Se (lutil³Lmax)
então L_compartimento =Lmax
senão Se (lutil < Lmin)
então L_compartimento=lutil e considera-se apenas os itens
livres em (7.1-7.3),
senão (Lmin£lutil < Lmax) L_compartimento = lutil
Observação: seL_compartimento < Lminou sedi = 0,"i Í Ak,
entãoVk = 0,k=1,...,K'1, restando apenas os itens livres para serem alocados.
Selecionar o melhor compartimento para o agrupamento k resolvendo o seguinte
Problema da Mochila de capacidade L_compartimento:
Passo 3:
3.1 Escolha k* tal que: Max <formula/>
3.2 Atualização:
Se k* em (3.1) corresponder a um compartimento
então lutil¬lutil ' Lk* "alocar um compartimento"
di¬ di 'ik*
senão lutil¬lutil ' Lk*"alocar um item livre"
di¬di ' 1
3.3 Se lutil³Min{Min{Lk, k=1,...,K-1},Min{li," iÍAK}}, volte ao Passo 2.
3.3 Heurística dos "z" Melhores Compartimentos
Esta heurística consiste basicamente na determinação dos "z" melhores
compartimentos associados a cada agrupamento, ou seja, nas "z"
melhores soluções dos Problemas da Mochila para cada agrupamento. A resolução
de um problema de programação linear inteira considerando estes compartimentos
como superitens, juntamente com os itens livres, determina um padrão de corte
para a mochila compartimentada. O algoritmo é apresentado a seguir.
Algoritmo:
Passo 1:Selecionar os "z" melhores compartimentos para o agrupamento
k determinando as "z" melhores soluções para o seguinte Problema da
Mochila de capacidade Lmax, sendo V1k
³
V2k
³
...³Vzkos "z" melhores valores de (8.1) e suas respectivas soluções-
ijk.
Para k=1,...,K-1 e j=1,...,z, resolva:
Passo 2:Resolver o seguinte problema de programação inteira envolvendo os (
(K'1)*z) compartimentos selecionados e os |AK| itens livres:
* bjk é o número de vezes que o compartimento j para o agrupamento k é
repetido na mochila,
* gk é o número de vezes que o item livre k é repetido na mochila.
Nota: Embora a Heurística de Decomposição seja um caso particular da Heurística
dos "z" Melhores Compartimentos, com z = 1, destacamo-la por resolver
uma seqüência de problemas da mochila. O problema (9.1-9.5) é um problema
otimização inteira com várias restrições, ao contrário de (5.1-5.5) que é um
problema da mochila restrito. Para resolver os problemas que surgem nas
heurísticas, propusemos algumas modificações para o método de enumeração
implícita proposto por Gilmore & Gomory (1963), as quais são resumidamente
apresentadas na próxima seção.
3.4 Resolução das Mochilas dentro das Heurísticas
O método de enumeração implícita proposto por Gilmore & Gomory (1963)
resolve eficientemente o problema da mochila irrestrito, nos tamanhos que
ocorrem no contexto dos problemas de corte, isto é, com algumas dezenas de
itens. A implementação usa a estratégia backtracking de modo que o espaço de
soluções é percorrido de maneira bem simples, usando basicamente um vetor
soluçãoa = (a1 a2 ak 0 0), o qual tem o número de coordenadas igual ao número
de itens da mochila, sendoai o número de itens do tipo i, e k o último item
incluído na mochila (ak>0). O vetor solução é suficiente para caracterizar um
nó na árvore de busca, de modo que o nó anterior é caracterizado pora' =
(a1 a2 ak-1 0 0). Regras simples para incluir novos itens na mochila
(portanto, novas soluções ou novos nós na árvore de busca) são facilmente
derivadas, dada a simplicidade das restrições da mochila, bem como limitantes
superiores. Sempre que uma solução mais valiosa é identificada, seu valor é
armazenado, descartando-se a anterior. Entretanto, os problemas da mochila que
necessitamos resolver dentro de cada heurística apresentam características
adicionais que podem ser incluídas no processo de busca, são elas: i) a
limitação do número de itens na mochila, ii) a determinação das
"z"melhores soluções e, iii) restrições adicionais dadas por (9.3). A
inclusão de restrições adicionais no processo de busca no método de enumeração
implícita de Gilmore e Gomory é bastante utilizada, porém nem sempre publicada.
Por exemplo, os autores do método em seu artigo de 1963 sugeriram que
restrições simples, do tipo limitação do número de facas, podem ser incluídas
no processo de busca. Morabito & Garcia (1998) também incluíram restrições
adicionais no processo de busca quando estudaram um problema prático de corte
(originário de uma indústria de madeira reconstituída) onde surgiam restrições
difíceis de serem descritas, mas razoavelmente simples de serem incluídas no
processo de busca e anunciaram excelentes resultados. A seguir, damos uma breve
descrição de como incluímos as características dos problemas da mochila que
ocorrem dentro das heurísticas (seções 3.1 ' 3.3).
3.4.1 O Problema Restrito
Os problemas de mochilas restritas que ocorrem em (4.1-4.3), (5.1-5.5) e (7.1-
7.3) foram resolvidos por uma modificação simples no algoritmo de enumeração
implícita de Gilmore & Gomory (1963). As variáveis devem obedecer à
limitação na quantidade de cada item dentro da mochila. Para isto, o valor
atribuído à variável associada ao item i (que consiste numa busca em
profundidade na árvore de decisões) é calculado por:
onde <formula/> é a capacidade ociosa na mochila
atualizada a cada nó percorrido na árvore de busca.
O cálculo do limitante superior, importante para a eficiência do método de
enumeração implícita sofre também ligeira modificação, devido à canalização das
variáveis.
3.4.2 As "z" Melhores Soluções
Os problemas (8.1-8.3) consistem nas "z" melhoressoluções de um
problema da mochila. Para determinar tais soluções, basta armazenar no processo
de busca as"z" melhoressoluções, ao invés de armazenar apenas a
melhor, como é feito no algoritmo de Gilmore & Gomory (1963). Assim, sempre
que uma nova solução é determinada, o correspondente valor da função objetivo,
digamos V, é comparado com os "z" valores previamente armazenados
(por facilidade estão ordenados, por exemplo: V1
³
V2³ ³Vz), sendo rejeitado caso V £ Vz, ou Vz é descartado e o valor de V
armazenado ordenadamente. Observe que a nova solução gerada difere das
anteriores, pois o processo de busca do algoritmo de Gilmore e Gomory evita
repetições de soluções. Um método alternativo pseudo-polinomial para o cálculo
das melhores soluções do problema da mochila pode ser encontrado em Yanasse et
al.(2000).
3.4.3 O Problema (9.1-9.5)
Dentre os subproblemas que surgem nas heurísticas, o problema (9.1-9.5) é o
mais complexo, pois várias restrições (9.3) são adicionadas à restrição da
mochila (9.2). Procedemos analogamente ao caso restrito, introduzindo uma
modificação no processo de busca do método de enumeração implícita de Gilmore
& Gomory (1963), de modo a garantir a satisfação das restrições (9.3) e
(9.4). Como estamos tratando com superitens (isto é, compartimentos que
armazenam itens de um mesmo agrupamento) e considerando que temos "z"
superitens associados a um mesmo agrupamento, surge a necessidade de um maior
cuidado durante a busca para que as quantidades máximas di, i=1,...,m, não
sejam violadas (veja restrições (9.3)). Para evitar tal violação é necessário
primeiramente limitar a inclusão do superitem (j, k), j = 1, ,z e k = 1, ,K'1
(j-ésimocompartimento associado ao agrupamentok obtido pelo problema (8.1-8.3))
por:
Isto reduz ao caso restrito já discutido, mas não é suficiente. Por exemplo,
seb1k>0 eb2k>0 (isto é, o primeiro e segundo compartimentos associados ao
agrupamento k são carregados na mochila) e, além disso,ai1k>0 eai2k>0 (isto é,
o item i aparece nos compartimentos 1 e 2) então o total de itens do tipo i já
incluídos na mochila é dado por:ai1k b1k + ai2k b2k(veja restrição (9.3)).
Portanto, a quantidade de superitem do tipo 3, por exemplo, é limitada por:
onde <formula/> = di -ai1kb1k -ai2kb2ké a folga da
restrição (9.3). A busca é similar ao caso anterior, porém considerando tais
limitações para o número de compartimentos.
4. Resultados Computacionais
As heurísticas apresentadas na seção 3 foram testadas para uma série de
exemplos gerados aleatoriamente, classificados de acordo com as seguintes 4
características:
i)número de itens livres;
ii)comprimentos dos itens;
iii)limites sobre o número de itens dos agrupamentos e,
iv)limites sobre o número de itens livres.
Tais características tentam simular situações observadas com dados reais. A
seguir apresentaremos as características que foram consideradas para cada
conjunto de dados. Alguns parâmetros foram fixados para todos os exemplos,
representando dados reais. Ao invés de peso, como temos utilizado até agora,
usamos comprimentos da bobina e itens.
·Parâmetros fixados:
1. Capacidade da Mochila: L = 1200 mm;
2. Capacidades mínima e máxima para os compartimentos: Lmin = 154 mm e
Lmax = 456 mm.
3. Perda devido à inclusão de compartimento (imperfeições nas bordas): S =
12 mm.
4. Número de agrupamentos gerados aleatoriamente: KÎ [3, 8].
5. Número de itens por agrupamento gerado aleatoriamente: |Ak|Î[2, 6].
6. vi= li +a,-Î[1,100] (Obs: Na geração de colunas, cada mochila
compartimentada, quando a função objetivo é minimizar a perda, terá os
valores de utilidade neste formato, onde-é o multiplicador simplex).
7. ckÎ[1,100].
· Parâmetros variados: (para cada parâmetro, consideramos duas possibilidades)
i) Número de Itens Livres:
1: número pequeno de itens livres: |AK|Î[1, 3]
2: número grande de itens livres: |AK|Î[4, 10]
ii) Comprimentos dos Itens:
3: Itens pequenos: liÎ[36 mm, 105 mm].
4: Itens grandes e pequenos: liÎ[36 mm, 444 mm].
(Obs: na indústria, os comprimentos dos itens variam bastante de modo que
a situação 4 melhor representa a realidade; a situação 3 explora o pior
caso).
iii) Limites sobre o Número de Itens dos Agrupamentos:
5: limitante baixo: diÎ[1, 3], iÎAk,k =1, ,K'1.
6: limitante alto: diÎ[4, 15],iÎAk,k =1, ,K'1.
iV) Limites sobre o Número de Itens Livres:
7: limitante baixo: diÎ[1, 3],iÎAK.
8: limitante alto: diÎ[4, 15],iÎAK.
Na prática das indústrias metalúrgicas, onde surge o Problema da Mochila
Compartimentada, o percentual de itens livres é bastante variado pode ser da
ordem de 60% (itens livres correspondem a itens que não passam pela laminação).
Embora as heurísticas descritas na seção 3 sejam projetadas para uma única
mochila, devem ser executadas em outras ocasiões onde as várias situações acima
podem ocorrer (por exemplo, na técnica de geração de colunas, uma mochila
compartimentada deve ser resolvida a cada iteração do método simplex ou como
geradora de padrões eficientes na heurística de exaustão Hinxman, 1980), de
modo que observar seus desempenhos nas características acima.
A seguir, é feito um resumo dos resultados obtidos para vários exemplos
gerados. Para cada situação combinada 20 exemplos foram gerados aleatoriamente
e executados para as 3 heurísticas (Decomposição, Melhor Compartimento e
"z" Melhores Compartimentos com z = 2).
4.1 Resultados Obtidos
A seguir será apresentada uma tabela que mostra os valores médios obtidos para
a função objetivo nos 20 exemplos executados para cada conjunto de dados.
Baseado nesta tabela, o gráfico a seguir foi construído. Neste gráfico,
traçamos um comparativo entre os valores médios obtidos para a função objetivo
(vistos na tabela_1) considerando as heurísticas executadas. Para tal,
consideramos como base os valores médios obtidos para a heurística dos
"z" Melhores Compartimentos (correspondendo a 100%) e de acordo com
os valores obtidos nas outras heurísticas, verificamos se eles estão acima ou
abaixo dos valores base. O gráfico_1 ilustra esta comparação.
4.2Análise dos Resultados Obtidos
A execução de vários exemplos permitiu-nos fazer uma comparação entre as três
heurísticas apresentadas. Embora, de modo geral, a Heurística dos "z"
Melhores Compartimentos tenha se destacado em relação às demais, a Heurística
do Melhor Compartimento apresentou resultados melhores em alguns casos
específicos (conjuntos C, D, G, H). Tal situação pode ser explicada analisando
as características presentes nos conjuntos de dados onde essa melhora ocorreu.
Devido à possibilidade de calcular, em seguidas iterações, compartimentos com
capacidades diferentes e reduzidas, a Heurística do Melhor Compartimento não é
tão dependente de muitos itens livres para gerar bons padrões de corte (exceto
quando o espaço restante na mochila é inferior à capacidade mínima permitida
para os compartimentos ' Lmin). Em outro aspecto, a presença de um número
considerável de itens nos agrupamentos faz melhorar os valores dos
compartimentos (superitens).
A Heurística dos "z" Melhores Compartimentos teve um desempenho
superior na maioria dos casos, pois tal heurística permite um número maior de
combinações para o preenchimento da mochila (maior número de compartimentos são
gerados para cada agrupamento).
Quanto à Heurística de Decomposição, por se tratar de um caso particular da
Heurística dos "z" Melhores Compartimentos (onde z = 1), já era
esperado que não obtivesse resultados tão destacados. Porém, ainda assim, esta
heurística não perdeu tanto em desempenho para as demais, sendo, inclusive,
melhor que a Heurística do Melhor Compartimento quando consideramos todos os
exemplos executados para todas as combinações.
Em relação ao tempo de execução, os resultados têm mostrado que as heurísticas
rodam utilizando, em média, frações de segundo e, nos piores casos, em torno de
1 segundo. Tal característica torna-se importante se desejarmos usar estas
heurísticas na geração de colunas para um problema de corte de estoque (onde
demandas devem ser satisfeitas).
5. Conclusões e Perspectivas Futuras
Este trabalho abordou o Problema da Mochila Compartimentada, um problema de
otimização combinatória, que é uma variação do clássico Problema da Mochila
(porém, sua formulação matemática sofre profundas mudanças) e de importantes
aplicações práticas, como no corte de bobinas de aço na indústria metalúrgica.
Um modelo matemático de otimização não linear inteiro foi proposto e nos
permitiu definir um conjunto de métodos heurísticos para a sua resolução. Uma
nova heurística está em desenvolvimento considerando-se a possibilidade de
gerar, para cada agrupamento, "w" compartimentos distintos (i.e.,
distintas capacidades para os compartimentos, ao invés de fixar em Lmax), o que
melhoraria o poder combinatório para o preenchimento da mochila. Além disso, um
método de geração de colunas para o problema de corte de estoque, onde demandas
dos itens devem ser satisfeitas e os padrões de corte são mochilas
compartimentadas vem sendo desenvolvido.
Uma outra continuação deste trabalho consiste em estender o problema aqui
estudado para o caso de diversos tipos de mochilas com características
diferentes (como, por exemplo, capacidades variadas). Isto levaria a considerar
custos (ck) diferenciados de cada agrupamento a cada tipo de mochila.
Por fim, poderíamos estudar o Problema da Mochila Compartimentada para casos
bidimensionais envolvendo situações encontradas na prática como, por exemplo, o
problema de corte de placas de circuitos impressos (os compartimentos são sub-
retângulos menores da placa original, sobre os quais incidem os mesmos
processos); problemas tridimensionais, como no caso de empacotamento de caixas
que devem estar agrupadas (compartimentadas) por cliente.
