Date of Award
Industrial and Manufacturing Systems Engineering
CC BY-NC-ND 4.0
A three-dimensional knapsack problem packs a subset of rectangular boxes inside a bin with fixed size such that the total value of packed boxes is maximized. Each box has its own value and size and can be freely rotated into any of the six positions while its edges are parallel to the bin's edges. A Mixed Integer Linear Programming is developed for the 3D knapsack problem, while some practical constraints such as vertical stability are considered. However, the given model can be applied to two dimensional problems as well. The proposed solution methodology is based on the sequence triple. Simulated annealing technique is used to model the heuristic approach. Moreover, the situation where some boxes are pre-placed in the bin is investigated. These pre-placed boxes represent potential obstacles. Numerical experiments are conducted for bins with and without obstacles. The results show that the heuristic approach is successful and can handle different kinds of instances.
Mostaghimi Ghomi, Hanan, "Three-Dimensional Knapsack Problem with Pre-Placed Boxes and Vertical Stability" (2013). Electronic Theses and Dissertations. 4987.