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)