Packing problems with mechanical equilibrium constraint

Author(s)

Evandro Cesar Bracht

• Document type: Doctoral Thesis
• Press: Campinas, SP.
• Institution: Universidade Estadual de Campinas (UNICAMP). Instituto de Computação
• Defense date: 2016-10-31

Examining board members

Flávio Keidi Miyazawa; Reinaldo Morabito; Maria do Socorro Nogueira Rangel; Eduardo Candido Xavier; Fábio Luiz Usberti

• Advisor: Flávio Keidi Miyazawa

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 (AU)