Bachelor’s thesis: Algorithms for 3D Bin Packing


August 14, 2012

Bachelor’s thesis: Algorithms for 3D Bin Packing

Thesis in operational research with professor Marco Trubian.

Study and implementation in C of a recent heuristic algorithm solving the 3D bin packing problem.

The algorithm needs the lower bound of Boschetti. It starts from an initial solution built with a first-fit heuristic, depending on 6 different types of orderings.

The heuristic is made of two different procedures: the first one optimizing the disposition of objects inside a single bin, the second moving objects from different bins trying to reduce the number of bins used (2 layered approach). The search is a tabu-search algorithm.
The search space is reduced by using a graph representation of the object disposition.

The testing phase involved the comparison of the result of the 6 different ordering algorithms and the lower bound given by Boschetti.

Algoritmi per il bin packing 3D (italian)