Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/331435
Type: TESE DIGITAL
Degree Level: Doutorado
Title: Problemas de empacotamento com restrições de equilíbrio mecânico
Title Alternative: Packing problems with mechanical equilibrium constraint
Author: Bracht, Evandro Cesar, 1977-
Advisor: Miyazawa, Flávio Keidi, 1970-
Abstract: Resumo: 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 maiores

Abstract: 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 instances
Subject: Problemas de empacotamento
Otimização combinatória
Algoritmos de computador
Algoritmos branch-and-cut
Equilíbrio mecânico
Editor: [s.n.]
Date Issue: 2016
Appears in Collections:IC - Tese e Dissertação

Files in This Item:
File SizeFormat 
Bracht_EvandroCesar_D.pdf830.49 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.