Packing problems with mechanical equilibrium constraint

Orientador: Flávio Keidi MiyazawaTese (doutorado) - Universidade Estadual de Campinas, Instituto de ComputaçãoResumo: Neste trabalho investigamos duas variações de problemas de empacotamento com restrições de equilíbrio mecânico: O problema da mochila 0-1 bidimensional e o problema de carregamento de contêiner. Para o problema da mochila 0-1, consideramos restrições de equilíbrio estático e dinâmico aplicadas ao cenário de carregamento de paletes bidimensionais. Para tanto desenvolvemos um algoritmo "branch-and-cut", onde os cortes excluem empacotamentos inviáveis. Os empacotamentos viáveis são obtidos através de uma sub-rotina em programação por restrições e as restrições de equilíbrio estático e dinâmico são verificada através de um algoritmo baseado nas condições físicas de equilíbrio mecânico. No problema de carregamento de contêiner tridimensional com restrição de equilíbrio mecânico, desenvolvemos uma heurística utilizando a metaheurística BRKGA (Biased Random-Key Genetic Algorithms), que considera a forma geométrica e física dos itens, e utiliza um pacote de simulação física ODE, durante a fase de decodificação, para verificar se um dado empacotamento está em equilíbrio mecânico. Posteriormente desenvolvemos métodos heurísticos rápidos para testar condições de equilibrio estático e dinâmico em empacotamentos tridimencionais. A combinação de métodos heuristicos e exatos permitiu obter empacotamentos em equilíbrio estático e dinâmico para entradas maioresAbstract: In this Thesis, we investigate two variants of packing problems with mechanical equilibrium constraints: The 0-1 two-dimensional knapsack problem and the container loading problem. For the 0-1 knapsack problem, we consider static and dynamic equilibrium conditions applyed to the loading of two-dimensional pallets. We developed a branch-and-cut algorithm, using cutting planes to avoid unstable packings. Feasible packings are obtained using a constraint programming subroutine, and static and dynamic conditions are verified by an algorithm based on mechanical equilibrium theory. In the (three-dimensional) container loading problem, we developed an heuristic based on the metaheuristic BRKGA (Biased Random-Key Genetic Algorithms), that considers the geometrical configuration of the packed items and uses the ODE physical simulation package, during the chromossome decodification, to verify if a given packing satisfy mechanic equilibrium conditions. Then, we developed fast aproximate heuristics to test static and dynamic equilibrium conditions in three-dimensional packings. The combined use of heuristic and exact methods allowed to obtain an algorithm capable to obtain packings that satisfy static and dynamic equilibrium conditions for larger instancesDoutoradoCiência da ComputaçãoDoutor em Ciência da Computação03/13815-0FAPES