3d bin packing algorithm [closed]

11
votes

I am looking for a deterministic implementation for any 3d bin packing algorithm, i.e. for packing many small and different cuboids inside one or many bigger ones. The solution could vary from the optimal one.

It should be written in C, C++, Java, C#, IronPython, IronRuby or any other language an can bin to from .Net code.

I found this C algorithm http://www.diku.dk/hjemmesider/ansatte/pisinger/3dbpp.c , but it doesn’t rotate the cuboids to find the best fit. I am ok with not rotating them upside down, but horizontal rotation should be possible.

3
algorithmlanguage-agnosticmathbin-packing
You claim you are looking for an algorithm, but you then list programming languages. Are you looking for a generic algorithm or an implementation? – Mads Elvheim
Do you want the optimal solution, or one that's pretty good? Are the cuboids all the same? When you say rotation, do you mean 90 degrees, or any angle? – Beta
@Beta: If he is packing cuboids into a cuboid, surely anything other than integer multiples of 90 degrees will lead to a sub-optimal solution. – user181548
@Asaph: Of couse,not! Just because I mentioned "algorithm" doesn't mean it's a homework. – Mouk
@Kinopiko and Mouk, try putting 5 unit squares into a square of width 2.708, then tell me again about non-90-degree angles. – Beta

3 Answers

8
votes

I have written an approximate algorithm for the case you describe i.e. 3D rectangular boxes, with orthogonal rotation, in C++. You can find the results and algorithm in the published paper: http://www.cs.ukzn.ac.za/publications/erick_dube_507-034.pdf

4
votes

I converted wknechtel/3d-bin-pack C code to javascript. Can be easily port to C#.

https://github.com/keremdemirer/3dbinpackingjs

You can run example calculations from index.html file and review the generated report. pack1.js file contains the app and algorithm. I'm not sure how the algorithm works but the results are satisfying for packaging calculations.

1
votes

This problem is NP-hard. Your best bet is an approximation algorithm (until a genius person solves any NP problem, or a very lucky fellow stumbles across a solution.) I do not know of any well know approximation algorithms for this problem unfortunately.