3D bin packing can help Santa

It’s a little late to help Santa this year, but as this Kaggle competition (essentially a 3D bin packing problem) does not close until the 26th January 2014, you can contribute towards the planning that will no doubt start as soon as he touches down at the North Pole after delivering all the presents this year.

In the competition you are asked to pack Santa’a sleigh in the most efficient way possible, so that he can carry as many presents as possible.

3D bin packing

The problem is actually an abstraction of the 3D bin packing problem, which has many practical uses, such as loading lorries, packing containers and loading pallets.

I admit to having a liking for this problem as my PhD was in a related area; 2D bin packing. Some of my papers in this area can be seen here,  and since finishing my PhD I have published on the 3D bin packing problem. Most of this work has been to do with meta- and hyper- heuristic approaches, rather than exact methods, which tend to be too computationally expensive for reasonably sized problems.

The competition

In this festive version of the 3D bin packing problem you are asked to help Santa load up his sleigh with as many presents as possible. You should be warned that this is a very difficult problem to solve, especially if you want to find the optimal solution but, If you think that you are good enough, give it a go. At least the problem is very easy to understand and, unlike, other versions of the problems (e.g. 2D packing where the shapes can contain holes), the geometry is fairly easy to get to grips with.

Good luck!

Note: I also posted a similar post at the University of Nottingham blog (the post will not appear until the 27th Dec 2013).