BrBRCEEn0101-74382003000200007

Uma heurística de busca tabu simples para o problema de carregamento de paletes do produtor

1. Introdução O problema de carregamento de paletes (pallet loading problem) consiste em carregar produtos (embalados em caixas) sobre um palete retangular, de maneira a otimizar o aproveitamento do mesmo. Supõe-se que as caixas, disponíveis em grandes quantidades, devam ser arranjadas ortogonalmente, isto é, devem ter seus lados posicionados paralelamente aos lados do palete. O problema de carregamento de paletes aparece com freqüência nas atividades de armazenagem, movimentação e transporte de produtos. Devido à escala de certos sistemas logísticos, um pequeno aumento do número de produtos carregados sobre cada palete pode resultar numa economia global significativa.

Hodgson (1982), ao estudar o problema, dividiu-o em dois possíveis casos: o problema de carregamento de paletes do produtor (manufacturer's pallet loading problem) e o problema de carregamento de paletes do distribuidor (distributor's pallet loading problem). No primeiro caso, o produtor fabrica um bem que é embalado em caixas iguais de dimensões (l,w,h). Estas caixas devem ser então carregadas em camadas horizontais sobre paletes de dimensões (L,W,H) (onde H é a altura máxima tolerável do carregamento). Em cada camada, uma orientação vertical das caixas é fixada. Se nenhuma orientação for fixada (isto é, as caixas podem ser carregadas sob qualquer uma de suas faces: lw, lh e wh), tais restrições permitem decompor o problema do produtor em dois subproblemas: (i) para cada face das caixas, o problema bidimensional de arranjar ortogonalmente o máximo número de retângulos (i.e., faces das caixas) dentro do retângulo (L,W) (superfície do palete), e (ii) o problema unidimensional de arranjar o máximo número de camadas ao longo da altura H do palete. Note que este último é um problema da mochila (knapsack problem) com capacidade H.

No segundo caso, o distribuidor recebe vários bens de diversos fornecedores, embalados em caixas de diferentes dimensões (li,wi,hi), i=1,..,m. Essas caixas são então carregadas sobre paletes. Note que o problema do distribuidor pode ser visto como um problema de carregamento de contêineres (Bischoff & Ratcliff, 1995; Morabito & Arenales, 1994). Em particular, se uma orientação vertical for fixada, por exemplo, se as caixas devem ser carregadas sob a face liwi, então o problema do distribuidor reduz-se ao problema bidimensional de encontrar o arranjo ortogonal de retângulos (li,wi) e (wi,li), i=1,..,m, dentro do retângulo (L,W) que maximize a utilização de (L,W).

Revisões dos problemas do produtor e distribuidor podem também ser encontrados nos artigos e edições especiais de Dowsland & Dowsland (1992), Sweeney & Parternoster (1992), Dyckhoff & Finke (1992), Balasubramanian (1992), Martello (1994), Bischoff & Waescher (1995), Dyckhoff et al. (1997), Arenales et al.(1999), Wang & Waescher (2002), Hifi (2002) e Martins (2002).

No presente estudo abordamos o problema do produtor, em particular, o problema bidimensional descrito em (i) de arranjar, sem sobreposição, retângulos (l,w) e (w,l) no retângulo (L,W). Este problema também aparece no arranjo físico de paletes sobre carrocerias de caminhões e no projeto de embalagens para formar unidades de carga intermediárias (Morabito, Morales & Widmer, 2000). É importante salientar que, embora existam algoritmos polinomiais para a versão guilhotinada do problema do produtor (Tarnowski et al., 1994), o caso mais geral parece ser de difícil resolução do ponto de vista da teoria de complexidade, embora isso ainda não tenha sido provado (Dowsland, 1987; Nelissen, 1995; Letchford & Amaral, 2001).

O problema do produtor pode ser modelado como um caso particular do modelo de programação linear 0-1 em Beasley (1985) proposto para o problema de corte não- guilhotinado. Outros modelos 0-1 para o problema do produtor podem ser encontrados em Tsai et al. (1993) e Hadjiconstantinou & Christofides (1995) (recentemente Amaral & Letchford (2001) mostraram que esta última formulação não é válida em certos casos). Além dos métodos propostos por estes autores, outros métodos exatos para resolver o problema do produtor são reportados em Dowsland (1987) e Bhattacharya et al. (1998). Entretanto, todas estas abordagens são em geral computacionalmente intratáveis nas situações práticas. Mais recentemente, Lins et al. (2003) apresentaram uma abordagem capaz de resolver problemas considerados de difícil resolução; os autores conjecturam que tal abordagem tenha garantia de otimalidade. Pesquisas com limitantes superiores para o problema também podem ser encontradas em Nelissen (1995), Letchford & Amaral (2001) e Morabito & Farago (2002).

Diversos autores têm tratado com relativo sucesso o problema do produtor com heurísticas de construção conhecidas como heurísticas de blocos,onde são gerados padrões de carregamento compostos por um ou mais blocos, cujas caixas possuem a mesma orientação. Exemplos de heurísticas de blocos são reportados em Steudel (1979), Smith & De Cani (1980), Bischoff & Dowsland (1982), Nelissen (1994, 1995), Scheithauer & Terno (1996) e Morabito & Morales (1998, 1999). Uma característica desses métodos é que os padrões gerados estão limitados aos chamados padrões não-guilhotinados de primeira ordem (definidos na próxima seção). Parte da motivação do presente trabalho é propor uma heurística capaz de resolver problemas desta classe, não resolvidos pelas heurísticas de bloco da literatura, em tempo computacional relativamente pequeno.

Meta-heurísticas são técnicas que, quando aplicadas a métodos de busca local, permitem a superação da otimalidade local com vistas à obtenção de soluções de qualidade superior. Apesar do sucesso que estas técnicas têm alcançado em uma variedade de problemas, no que diz respeito ao problema do produtor, poucas aplicações são reportadas na literatura. Exemplos dessas aplicações são reportados em Dowsland (1993) (simulated annealing), Herbert & Dowsland (1996) (algoritmos genéticos), Dowsland (1996) e Yamassaki & Pureza (2001) (busca tabu). Em particular, os dois últimos trabalhos utilizam uma versão sem memória de busca tabu que parte de uma solução com o número ótimo de caixas e infactível com respeito à sobreposição, e realiza movimentos destas caixas para novas posições com vistas à sobreposição zero (padrão ótimo). Os resultados reportados indicam que estas heurísticas não têm bom desempenho em problemas de tamanho moderado (por exemplo, acima de 40 caixas).

Neste trabalho é apresentada uma abordagem baseada na incorporação de busca tabu simples a heurísticas de bloco. Ao contrário de versões avançadas que também empregam estruturas de memória de longo prazo para aplicação de estratégias de intensificação e diversificação, os elementos restritivos da busca tabu simples restringem-se a estruturas de memória de curto prazo. O papel dessas estruturas é de apenas armazenar e penalizar certas características ou atributos de soluções já visitadas, por um determinado número de iterações. Além do uso de memória, um outro aspecto que distingue a presente abordagem dos trabalhos de Dowsland (1996) e Yamassaki & Pureza (2001) é o fato da busca ocorrer no espaço factível de soluções, o que permite que um padrão esteja disponível em qualquer iteração. Além disso, movimentos ou transições entre soluções são aplicados a blocos ao invés de caixas como nos trabalhos anteriores. E, finalmente, ao contrário das heurísticas de bloco, a abordagem é capaz de tratar situações onde a solução ótima é um padrão não- guilhotinado de ordem superior.

Na próxima seção, definimos os padrões de carregamento e discutimos resumidamente heurísticas de bloco. Na seção 3, descrevemos a abordagem proposta e na seção 4, os experimentos computacionais e os resultados obtidos com a aplicação desta abordagem. As conclusões e próximos passos desta pesquisa são discutidos na seção 5.

2. Heurísticas de bloco Os padrões de carregamento podem ser classificados em guilhotinado, não- guilhotinado de 1ª ordem, e não-guilhotinado de ordem superior (Arenales & Morabito, 1995). Eles são definidos da seguinte maneira: i. padrão guilhotinado: um corte é chamado guilhotinado se, ao ser produzido sobre um retângulo, produz 2 novos retângulos. Um padrão obtido por sucessivos cortes guilhotinados é chamado padrão guilhotinado (Figura_1a).

ii. padrão não-guilhotinado de 1ª ordem: um corte é chamado não- guilhotinado de 1ª ordem se, ao ser produzido sobre um retângulo, produz 5 novos retângulos arranjados de maneira a não formar um padrão guilhotinado (veja corte em negrito da Figura_1b). Um padrão obtido por sucessivos cortes guilhotinados e/ou cortes não- guilhotinados de 1ª ordem é chamado padrão não-guilhotinado de 1ª ordem (Figura_1b). Note que todo padrão guilhotinado também é um padrão não-guilhotinado de 1ª ordem (mas o inverso não é verdadeiro).

iii. padrão não-guilhotinado de ordem superior: é um padrão que não pode ser obtido por sucessivos cortes guilhotinados e/ou cortes não- guilhotinados de 1ª ordem (Figura 1c).

Dado que o problema do produtor não impõe restrições sobre o tipo do padrão, uma simplificação para abordá-lo seria impor artificialmente a restrição de padrões guilhotinados. Entretanto, esta alternativa em geral não resulta em boas soluções. Conforme mencionado na seção 1, devido às dificuldades com a aplicação de métodos exatos, diversas heurísticas têm sido propostas na literatura para resolver o problema do produtor, em especial as chamadas heurísticas de bloco (Nelissen, 1995). Cada bloco é definido como um retângulo contendo caixas arranjadas com a mesma orientação.

Um exemplo de uma heurística de bloco foi proposta em Steudel (1979). O palete é dividido em até 4 blocos e, em cada um deles, as caixas são simplesmente arranjadas conforme uma orientação pré-fixada. As dimensões destes blocos são determinadas num procedimento em dois estágios: no primeiro estágio a utilização do perímetro do palete é maximizada e no segundo, possíveis modificações nestes blocos são exploradas, variando suas dimensões, numa tentativa de preencher o bloco central. O padrão escolhido é aquele que resulta no maior número de caixas dentro dos blocos.

A Figura_2 apresenta padrões obtidos do exemplo de um palete (L,W)=(48,40) com caixas (l,w)=(11,7). A Figura_2a ilustra o padrão obtido no primeiro estágio e a Figura_2b, no segundo estágio. Note que 22 caixas foram arranjadas no palete.

Se o padrão obtido no segundo estágio for composto por exatamente 4 blocos, então temos um padrão não-guilhotinado de 1ª ordem, conforme o ilustrado na Figura_2b (em particular, este padrão também é guilhotinado). Caso contrário, o padrão será apenas guilhotinado.

Outro exemplo de uma heurística de bloco, semelhante à anterior, foi proposta por Smith & De Cani (1980). O palete também é dividido em até 4 blocos, e mais uma vez as caixas são simplesmente arranjadas dentro dos blocos conforme uma orientação pré-fixada. O procedimento examina todas as possíveis modificações nestes blocos, variando suas dimensões (inclusive a possibilidade das dimensões serem nulas), e retorna o padrão que resultar no maior número de caixas dentro dos blocos. A Figura_2c apresenta o padrão obtido ao aplicar este procedimento para o exemplo anterior. Este padrão (com 23 caixas) é melhor do que o padrão obtido com a heurística anterior, com apenas 22 caixas. Note que os padrões das Figuras_2b e 2c são não-guilhotinados de 1ª ordem com 4 blocos, porém apenas o padrão da Figura_2b é também guilhotinado.

Heurísticas de bloco baseadas na divisão do palete em cinco ou mais blocos podem ser encontradas em Bischoff & Dowsland (1982), Nelissen (1994), Scheithauer & Terno (1996) e Morabito & Morales (1998). Esta última gera padrões ótimos em problemas não-guilhotinados de 1ª ordem. Heurísticas recentes baseadas em outras técnicas são encontradas em G & Kang (2001) e Lins et al. (2002). Na grande maioria dos problemas, estas heurísticas encontram o padrão ótimo; nos poucos problemas em que não encontram (considerados difíceis), geram padrões de boa qualidade, em geral, a apenas uma ou duas caixas do número ótimo. Portanto, o desafio ao se propor um novo método é que este deve apresentar um desempenho superior ao resolver os problemas difíceis, em particular, os problemas cujo padrão ótimo é de ordem superior.

3. Abordagem proposta A idéia básica da abordagem é de, partindo de uma solução gerada por uma heurística de blocos arbitrária, realizar iterativamente movimentos de aumento (ou expansão) de blocos selecionados (blocos ativos) em uma determinada direção (para cima, para baixo, para esquerda ou para direita). A cada movimento de expansão, apenas padrões factíveis são gerados.

Como o padrão resultante da aplicação da heurística de blocos em geral é bastante compactado (i.e., a superfície do palete é bem utilizada), o aumento de um dado bloco ativo quase sempre provoca alterações em outros blocos (blocos passivos), a fim de preservar a factibilidade das soluções. A estrutura de vizinhança aqui utilizada prescreve que blocos passivos possam ser diminuídos, eliminados, divididos em um ou mais blocos, ou terem suas orientações originais alteradas. Além do impacto em blocos passivos, um dado movimento de expansão pode também provocar cisões do bloco ativo em dois ou três blocos, conforme discutido a seguir. Desta forma, os padrões resultantes destes movimentos são suficientemente genéricos, incluindo padrões não-guilhotinados de ordem superior não gerados por outras heurísticas de bloco.

3.1 Estrutura de Vizinhança Para qualquer bloco de um padrão, é possível realizar expansões para direita, para esquerda, para cima ou para baixo. A especificação da direção define a face de expansão do bloco, enquanto as demais faces permanecem inalteradas.

A Figura_3 ilustra um bloco com 4 camadas verticais e 4 camadas horizontais de caixas. Uma vez especificada a face de expansão do bloco, ele pode crescer com a inclusão de caixas em uma ou mais camadas (verticais ou horizontais) adjacentes. Um caso especial é o crescimento de todas as camadas de uma face.

No bloco da Figura_4, por exemplo, as possíveis camadas adjacentes em movimentos de expansão para a direita são {1}, {2}, {3}, {4}, {1,2}, {2,3}, {3,4}, {1,2,3}, {2,3,4} e {1,2,3,4} (note que {1,3}, {1,4} e {2,4} não são permitidos, uma vez que não são adjacentes). Uma vez definidas as camadas da face de expansão, o crescimento do bloco é feito adicionando-se um número de caixas a estas camadas, tal que não exceda os limites do palete. A Figura_4 ilustra dois possíveis movimentos de expansão para a direita.

Como blocos são essencialmente estruturas retangulares, na expansão da Figura 4a, o bloco ativo original deve sofrer cisões, no caso, resultando em 3 blocos (camadas {1}, {2,3} e {4}). Na expansão da Figura_4b, o bloco ativo mantém sua integridade, simplesmente agregando uma nova coluna de caixas em sua face direita.

Uma situação especial ocorre quando a heurística de blocos gera um padrão com um único bloco (solução homogênea). Rigorosamente, a busca heurística não pode ser aplicada porque não há movimentos disponíveis para seleção. Na presente abordagem, caso não seja possível garantir a otimalidade do padrão gerado, o bloco é dividido em sub-blocos, e a partir daí prossegue-se com a busca heurística.

O crescimento do bloco ativo superpõe cada bloco passivo em maior ou menor extensão. Foram consideradas 4 circunscrições ou configurações possíveis para a área não superposta de cada bloco passivo. As configurações envolvem a partição desta área em subconjuntos de um total de 8 áreas retangulares possíveis (A, B, C, D, E, F, G e H), conforme ilustrado na Figura_5. Note que um bloco ativo pode superpor vários blocos passivos, e neste caso, cada bloco passivo é tratado separadamente conforme a Figura_5.

Para uma dada configuração e para cada área não superposta dos blocos passivos (que possam conter pelo menos uma caixa), é construído um novo bloco com orientação tal que maximize o número de caixas que nele podem estar contidas.

Cada novo bloco é posicionado de tal forma que sua coordenada superior esquerda corresponde à coordenada superior esquerda da área onde ele foi criado (veja a Figura_10 adiante). A configuração selecionada para uma dada expansão de um bloco ativo é aquela que maximiza o valor da função de avaliação do movimento, definida na seção 3.4. A Figura_5 ilustra as 4 possíveis configurações resultantes de um movimento para direita do bloco ativo i (para as demais direções, rotacionar consecutivamente os desenhos em 90o), afetando o bloco passivo j. Caso haja uma tira de espaço livre entre a face direita do bloco passivo e a face esquerda de um bloco adjacente (ilustrada na Figura_6 entre o bloco passivo j1 e o bloco adjacente j3), a área desta tira é adicionada a área do bloco passivo (para as demais direções, rotacionar consecutivamente o desenho em 90o).

A espessura de uma tira de espaço livre é definida como a menor distância (horizontal para movimentos à direita e à esquerda, e vertical para movimentos acima e abaixo) entre uma face do bloco passivo e blocos adjacentes. No exemplo da Figura_6, a espessura e da tira adicionada ao bloco passivo j1é a distância entre j1 e bloco adjacente j3. Entretanto, se incorporássemos tiras possivelmente distintas às áreas das configurações F e G do bloco j1 (ao invés de uma única tira ao bloco j1), a área F seria acrescida de uma tira com espessura e1 enquanto G incorporaria uma tira correspondente à distância e2  entre o bloco j1 e o bloco j2 , maior do que e1(veja Figura_7). É possível que tal modificação torne o processo de busca mais eficaz já que promove um maior aproveitamento dos espaços vazios do palete. Por razões de simplicidade de implementação, neste trabalho optou-se pela incorporação de tiras ao bloco.

Um movimento de expansão propriamente dito é definido pelos seguintes parâmetros: • Bloco a ser expandido (1, 2, ..., número de blocos no padrão corrente).

• Direção da expansão (direita, esquerda, acima, abaixo).

• Camadas de expansão adjacentes (p.e., para cada face do bloco da Figura_4 têm-se: {1}, {2}, {3}, {4}, {1,2}, {2,3}, {3,4}, {1,2,3}, {2,3,4} e {1,2,3,4}).

• Número de caixas a serem adicionadas nas camadas de expansão (qualquer número de caixas, desde que não ultrapasse os limites do palete).

• Configuração pré-selecionada das áreas remanescentes dos blocos passivos (1, 2, 3 ou 4).

3.2 Deslizamento de Blocos Sempre que um movimento é realizado, é comum o surgimento de espaços não aproveitados entre os blocos. Conforme mencionado na seção 3.1, procura-se incorporar alguns destes espaços na área remanescente dos blocos passivos onde são criados novos blocos (Figuras_6 e 7). Um outro procedimento que otimiza ainda mais o aproveitamento destes espaços é o deslizamento de blocos. Após cada iteração, os blocos são movidos de forma a concentrar os espaços vazios, preferencialmente, em uma única área. Como o padrão corrente geralmente possui um número de caixas já bastante próximo do ótimo (freqüentemente com apenas uma caixa a menos), a soma dessas pequenas áreas livres aumenta a chance de inclusão de uma caixa adicional no padrão.

A estratégia utilizada consiste no deslizamento dos blocos em direção aos quatro cantos do palete. Inicialmente desliza-se os blocos em direção à face vertical (esquerda ou direita) mais próxima do palete. Em seguida desliza-se os blocos em direção à face horizontal (acima ou abaixo) mais próxima do palete. O procedimento é repetido até que nenhum deslizamento nas duas direções seja possível. Desta forma, os espaços vazios tendem a se concentrar no centro do palete (Figura_8). Note que os deslizamentos são restringidos pelas faces de outros blocos e pela face do palete.

3.3 Elementos de restrição Em função da boa qualidade da solução inicial gerada pela heurística de blocos, o padrão obtido é invariavelmente um ótimo local com relação à estrutura de vizinhança proposta. Para que a busca heurística se desenvolva além deste ponto, torna-se necessária a utilização de mecanismos que restrinjam o retorno a padrões previamente obtidos. Para este fim, foram incorporados elementos restritivos de busca tabu com uso de memória de curto prazo (Glover & Laguna, 1997), também conhecida como busca tabu simples. Ao contrário de versões mais avançadas que utilizam estruturas de memória de longo prazo para aplicação de estratégias de intensificação e diversificação, o papel da busca tabu simples é de apenas armazenar e restringir certas características ou atributos de soluções já visitadas por um determinado número de iterações.

Existe, entretanto, uma dificuldade intrínseca em se definir funções de memória para o problema, dado que o número de elementos que se alteram a partir da aplicação da estrutura de vizinhança é bastante variável. Cada movimento é definido por vários parâmetros, os quais podem assumir um amplo espectro de valores, além de envolver a alteração, eliminação e/ou geração de blocos em um número que não pode ser especificado previamente. Por esta razão, definir o que exatamente restringir não é uma tarefa simples.

Várias funções de memória foram investigadas. Em especial, a indexação por coordenadas de bloco apresentou os melhores resultados, sendo utilizada nos experimentos descritos na seção 4. Nesta implementação, utilizou-se períodos tabu fixos através da criação de uma lista circular L de t elementos onde são armazenadas as coordenadas dos blocos envolvidos em cada movimento. A proibição sobre coordenadas tem o propósito de procurar restringir movimentos a partir de regiões do palete mais recentemente modificadas. Em particular, são armazenadas as coordenadas originais do bloco ativo e as novas coordenadas dos blocos passivos. Não foi considerado o uso de períodos tabu dinâmicos uma vez que isso normalmente exigiria a criação de uma estrutura de memória para armazenagem de informações sobre o status (tabu-ativo ou não) de todas as possíveis coordenadas dos blocos (Glover & Laguna, 1997).

Sejam (x1, y1) e (x2, y2) respectivamente os pares de coordenadas do canto superior esquerdo e do canto inferior direito do bloco ativo do movimento candidato. Duas variantes para regra de ativação foram consideradas: (1) o movimento candidato é rejeitado quando (x1, y1) e (x2, y2)do bloco ativo estiver na lista L; (2) um movimento candidato é rejeitado quando (x1, y1) ou (x2, y2)do bloco ativo estiver na lista L. Em ambos os casos, proíbe-se que blocos ativos e passivos sejam ativos nas próximas t iterações. Note que esta regra não os impede de serem passivos; uma conjectura para o bom desempenho apresentado (veja seção 4) é que ela permite "correções" da configuração resultante em movimentos subseqüentes. A proibição de que blocos ativos e passivos sejam também passivos resultou em processos de busca altamente restritivos. Os melhores resultados foram obtidos com a regra (2), mais restritiva, o que resultou em sua seleção nos experimentos posteriores.

3.4 Avaliação dos movimentos A função de avaliação dos movimentos inicialmente adotada para o cálculo do valor do movimento é: G0 = ganho real ou seja, a diferença entre o número de caixas do padrão resultante da aplicação do movimento e o padrão anterior. G0 pode assumir valores inteiros positivos, negativos ou zero, e para parte dos problemas tratados (veja seção 4), foi suficiente para obtenção da solução ótima.

Visando a resolução dos demais problemas, a análise do processo de busca sugeriu que dois movimentos com o mesmo valor de G0 possam apresentar características estruturais distintas. Estas características estariam associadas a um grau maior ou menor de "qualidade estratégica" dos movimentos, de maneira que sua identificação e quantificação poderia permitir a distinção entre eles e uma possível melhoria de desempenho da busca.

Considere que padrões com alto grau de heterogeneidade sejam aqueles formados por um grande número de blocos de diferentes orientações intercalados entre si.

Observou-se que em grande parte dos problemas considerados difíceis na literatura, a busca heurística é marcada pela geração de alguns poucos ótimos locais de grande influência (ou seja, existe uma grande recorrência a estas soluções, indicando baixa diversificação da busca). Estes ótimos locais são caracterizados por padrões com baixo grau de heterogeneidade (quase homogêneos). Foi também observado que movimentos de expansão que eliminam vários blocos passivos são aparentemente prejudiciais ao desempenho da heurística porque geralmente destroem uma estrutura do padrão corrente com alto grau de heterogeneidade. Com base nessas observações, concluiu-se que devem ser favorecidos movimentos com maior valor de G0: • que geram padrões com maior grau de heterogeneidade.

• que modifiquem minimamente a estrutura do padrão corrente.

Com este objetivo, a função de avaliação original do movimento foi alterada com a inclusão de dois termos. Em um dado movimento, seja P o conjunto de blocos passivos afetados pela realização de um movimento de expansão do bloco ativo i, areae a área total de expansão do bloco ativo, e areas(j) a porção de areae que corresponde ao bloco passivo jÎP (i.e., a área superposta do bloco passivo j).

Seja também arean a área total dos novos blocos (criados a partir dos blocos passivos), e areah a porção de arean onde os blocos têm orientação diferente do bloco ativo. As Figuras_9 e 10 ilustram estas definições.

A função de avaliação de movimentos foi então redefinida como:

O primeiro termo incluído (a ) valoriza movimentos com maior proporção da área de blocos novos com orientação diferente do bloco ativo. Note que este critério estimula mas não garante níveis maiores de heterogeneidade da solução, uma vez que a análise é local (restrita a porções do padrão) e não são consideradas intercalações das orientações dos blocos. O segundo termo incluído ((1 ' a) ) valoriza movimentos com menor proporção de área superposta dos blocos passivos sobre a área de expansão do bloco ativo. Menor proporção de área superposta significa que maior área livre do palete está sendo aproveitada na expansão, o que, por sua vez, implica que menores porções do padrão deverão ser efetivamente modificadas. Os dois critérios são ponderados por um fator a Î  [0, 1] (ou seja, uma combinação convexa entre os dois critérios), permitindo o controle da dominância de um critério sobre o outro. Note que a soma destes dois termos incluídos em G1 é um número em [0, 1], funcionando como critério de desempate entre bons movimentos com o mesmo ganho real G0.

De acordo com a função G1, movimentos admissíveis com G0 > 0 são prioritariamente selecionados. Na falta destes (mínimo locais), a busca selecionaria dentre os movimentos admissíveis com G0 = 0, aqueles movimentos que resultem na melhor combinação (dado a) dos critérios de maior heterogeneidade (1o critério) e menor alteração da estrutura do padrão (2o critério). Somente na falta de movimentos com G0 = 0 é que seriam selecionados movimentos com G0 < 0, priorizando-se aqueles que maximizem a combinação dos dois critérios.

Entretanto, em vários dos problemas tratados verificou-se a ocorrência de ótimos locais de alta influência. Estes ótimos locais são caracterizados por padrões quase homogêneos, com um grande número de movimentos com G0 = 0, que consistem de uma mera transferência de caixas entre blocos adjacentes com a mesma orientação. Estes movimentos não geram blocos novos com orientação diferente do bloco ativo e, por não alterarem na prática a estrutura da solução, são pouco efetivos. Como apresentam G0 = 0 e areah = 0, o valor de G1 destes movimentos reduz-se ao 2o critério (menores áreas superpostas).

Nestas situações parece importante conferir maior chance de seleção a movimentos com G0 < 0, uma vez que permitem que a busca escape destes ótimos locais influentes e se diversifique. Isso é feito penalizando-se movimentos que apresentem G0 = 0 e areah = 0 (a contribuição do 1o critério é nula). Para tal, retira-se a contribuição do 2o critério e soma-se um valor de penalidade pen <  0 à avaliação destes movimentos. Por exemplo, se pen = '1 e a  = 0,5, os movimentos com G0 = 0 e areah = 0 teriam valor igual à '0,5. Com isso, movimentos com G0 = '1 com vantagem do 1o e 2o critérios teriam grande chance de serem selecionados. Obteve-se assim, a seguinte função de avaliação:

Note que se G0 = 0 e areah = 0, o valor de G2reduz-se a (1 ' a)pen. Esta função apresentou um desempenho melhor que as anteriores e por esta razão, foi utilizada em todos os experimentos reportados na seção 4. A seguir são descritos os passos gerais do algoritmo.

3.5 Passos do Algoritmo 1. Gere um padrão inicial S0 através de uma heurística de blocos. Faça f (S0)=número de caixas em S0, blk=número de blocos do padrão corrente e ótimo=falso.

2. Faça it=0, S=S0, f(S)= f(S0), S*=S, f(S*)=f(S) e lista tabu L=Ø. Se f(S0) atender critérios de otimalidade, faça ótimo=verdadeiro e vá para o passo 4.

3. Repita 3.1  Para cada bloco i=1,..,blk, calcule os movimentos possíveis nas quatro direções. Faça mv=número total de movimentos de todos os blocos.

3.2  Se mv>0, selecione o movimento não tabu com a maior avaliação G2. Seja S' o padrão resultante da aplicação deste movimento. Se todos os movimentos estão proibidos, elimine o elemento mais antigo de L (t-ésimo elemento) e repita o passo. Caso contrário, efetive o movimento, gerando um novo padrão e faça S=S'. Se f(S) > f(S*), faça S*=S e f(S*)=f(S). Se S* atende critérios de otimalidade, faça ótimo=verdadeiro. Incremente o número de iterações fazendo it=it + 1.

Até que mv=0 ou it=máximo número de iterações ou ótimo=verdadeiro.

4. Se ótimo=verdadeiro, pare pois S* corresponde a um padrão ótimo. Caso contrário, se mv=0 e 0 < it < número máximo de iterações, o padrão final convergiu para um único bloco; se mv=0 e it=0, o padrão inicial S0 é homogêneo.

Caso a heurística de blocos tenha gerado um padrão homogêneo que não satisfaça o critério de otimalidade, deixa de ser possível movimentos de expansão de blocos e, conseqüentemente, a aplicação da heurística. Conforme mencionado em 3.1, uma maneira de superar esta limitação consiste em dividir o bloco em um número de sub-blocos, atualizar blk, e voltar ao passo 2.

Nos experimentos apresentados a seguir foi utilizada a heurística de blocos de Smith & De Cani (1980) no passo 1 do algoritmo, e não foram gerados padrões iniciais homogêneos (note que outras heurísticas de bloco poderiam ter sido utilizadas, por exemplo, Bischoff & Dowsland, 1992; Scheitheuer & Terno, 1996; e Morabito & Morales, 1998). No passo 2, a otimalidade da solução pode ser verificada por meio de diversos limitantes superiores encontrados na literatura, conforme Nelissen (1995), Letchford & Amaral (2001) e Morabito & Farago (2002). Nos experimentos apresentados a seguir foi utilizado o número ótimo de caixas de cada problema, fornecido pela literatura. A maior dificuldade de implementação deste algoritmo diz respeito ao passo 1 (cálculo do conjunto de movimentos a cada iteração), em especial devido à necessidade do cálculo preciso das áreas não superpostas dos blocos passivos para cada uma das quatro configurações investigadas (veja seção 3.1).

4. Experimentos e Resultados Computacionais A implementação computacional foi feita em Delphi 5, o que permitiu a elaboração de uma interface gráfica, onde os padrões gerados podiam ser observados. O uso desta interface permitiu a detecção imediata de problemas e limitações da abordagem, sendo, portanto, extremamente valiosa para o seu desenvolvimento. Os experimentos foram realizados em um microcomputador AMD Athlon 800 Mhz.

Cada execução representa uma variação paramétrica de a (peso do 1o critério em G2) e t (tamanho da lista tabu L), ambos definidos na seção 3.4. Os valores de a foram variados em incrementos de 0,1 na faixa [0,...,0,5]. A faixa foi restrita a esses valores pois experimentos preliminares indicaram que a dominância do 1o critério (maximização da heterogeneidade) é conflitante ao atendimento do 2o critério (minimização de área superposta). Por outro lado, a dominância do 2o critério afeta de igual forma movimentos mais ou menos heterogêneos. O parâmetro pen assumiu o valor '1.

Os problemas foram tratados em ordem crescente do número ótimo de caixas e a faixa de valores do parâmetro t foi definida tomando como referência os valores do problema anterior (de menor porte) resolvido otimamente, admitindo a hipótese que quanto maior o número ótimo de caixas, maior é o valor adequado de t. Um limite máximo de 6000 iterações foi utilizado nos problemas com até 60 caixas, e 8000 iterações nos problemas de maior porte.

O algoritmo foi aplicado a um conjunto de 20 problemas da literatura, os 10 primeiros com solução ótima não guilhotinada de 1a ordem (Dowsland, 1984; Nelissen, 1994; Scheithauer & Terno, 1996; Battacharya et al., 1998), e os demais 10 com solução ótima não guilhotinada de ordem superior (Morabito & Morales, 1998; Lins et al., 2003). Estes problemas envolvem um número ótimo de 23 a 100 caixas, e são considerados difíceis uma vez que heurísticas de bloco como a de Steudel (1979), Smith & De Cani (1980) e Bischoff & Dowsland (1982) não são capazes de obter seus padrões ótimos. Além disso, os últimos 10 problemas não são resolvidos nem por heurísticas de bloco mais elaboradas, como as de Scheithauer & Terno (1996) e Morabito & Morales (1998). Tais problemas são otimamente resolvidos pela abordagem de Lins et al. (2003), no entanto, os tempos computacionais requeridos são relativamente grandes (dezenas a centenas de minutos).

Dos 20 problemas tratados, 15 foram otimamente resolvidos, sendo 10 deles correspondentes a todo o conjunto de problemas de 1a ordem, e 5 deles de ordem superior. A Tabela_1 apresenta para cada problema as dimensões L,W, l e w, o número de caixas da solução inicial provida pela heurística de Smith e De Cani, o número de caixas da melhor solução provida pela heurística proposta e, nos problemas em que a heurística encontrou uma solução melhor que a inicial, os parâmetros da execução (a e t) juntamente com o tempo computacional (em segundos). Como vários dos problemas foram resolvidos otimamente com mais de um conjunto de valores de parâmetros, os resultados apresentados correspondem à execução com o valor de a que mais se aplicou a todos os problemas, ainda que em outras execuções bem-sucedidas, o tempo computacional tenha sido menor.

A Figura_11 apresenta os padrões ótimos de ordem superior obtidos para os problemas 11, 12, 13, 14 e 16 da Tabela_1. As diferentes cores distinguem as orientações das caixas. Convém observar que se no passo 3.2 do algoritmo for utilizada a função G0 ao invés de G2, apenas os problemas 1 a 7 da Tabela_1 são resolvidos otimamente, o que mostra a importância desta última função de avaliação em relação à primeira. Note também que para os problemas 11 a 20 (não guilhotinados de ordem superior), o índice de sucesso da heurística tende a decrescer com o aumento do número ótimo de caixas, o que seria esperado. Nos exemplos em que padrões ótimos não foram encontrados (problemas 15, 17, 18, 19 e 20) a heurística proposta obteve soluções a uma caixa do número ótimo (exceto pelo problema 18, a melhor solução foi gerada pela heurística de blocos de Smith e De Cani no passo 1 do algoritmo).