Métodos exatos baseados em relaxações lagrangiana e surrogate para o problema de carregamento de paletes do produtor

AUTOR(ES)

Oliveira, Lilian Kátia de, Morabito, Reinaldo

FONTE

Pesquisa Operacional

DATA DE PUBLICAÇÃO

2006-08

RESUMO

Neste artigo apresentamos métodos exatos, baseados em relaxações Lagrangiana e surrogate, com bom desempenho para resolver o problema de carregamento de paletes do produtor. Este problema consiste em arranjar ortogonalmente e sem sobreposição o máximo número de retângulos de dimensões (l,w) ou (l,w) sobre um retângulo maior (L,W). Os métodos propostos são procedimentos de busca em árvore do tipo branch and bound que, em cada nó, utilizam limitantes derivados de relaxações Lagrangiana e/ou surrogate de uma formulação de programação linear 0-1. Algoritmos de otimização do subgradiente são usados para otimizar estes limitantes. São aplicados ainda testes de redução do problema e heurísticas Lagrangiana e surrogate para se obter boas soluções factíveis na otimização do subgradiente. Testes computacionais foram realizados utilizando exemplos da literatura e exemplos reais de uma transportadora. Os resultados mostram que um dos métodos propostos é competitivo com outros métodos da literatura, incluindo o software GAMS/CPLEX.

ASSUNTO(S)

problema de carregamento de paletes do produtor relaxação lagrangiana e/ou surrogate método branch and bound otimização do subgradiente

Documentos Relacionados

• Métodos exatos baseados em relaxação lagrangiana e surrogate para o problema de carregamento de paletes do produtor.
• Um método heurístico baseado em relaxação Lagrangiana para o problema de carregamento de paletes do produtor
• Uma heurística de busca tabu simples para o problema de carregamento de paletes do produtor
• Um refinamento do algoritmo tabu de Dowsland para o problema de carregamento de paletes do produtor
• Aplicação do método de decomposição de Benders para o problema de carregamento de paletes