Date of Award

8-2013

Degree Type

Thesis

Degree Name

M.A.Sc.

Department

Industrial and Manufacturing Systems Engineering

First Advisor

Abdul-Kader, Walid

Keywords

Applied sciences

Rights

CC BY-NC-ND 4.0

Abstract

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.

Included in

Engineering Commons

Share

COinS