11

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.

Mouk
  • 1,807
  • 2
  • 18
  • 26
  • 4
    You claim you are looking for an algorithm, but you then list programming languages. Are you looking for a generic algorithm or an implementation? –  Oct 13 '09 at 22:32
  • 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 Oct 13 '09 at 22:45
  • @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. –  Oct 13 '09 at 23:14
  • @Asaph: Of couse,not! Just because I mentioned "algorithm" doesn't mean it's a homework. – Mouk Oct 14 '09 at 05:17
  • @Beta, well it should be deterministic and a good solution is enough ( as I read optimal solutions are very hard to find) The cuboids are not all the same, and I guess, as Kinopiko said, any rotation other than by 90 degrees will not be helpful. – Mouk Oct 14 '09 at 06:46
  • @Mads-Elvheim: Sorry for the ambiguity. I need a concrete implementation, that I can directly call. I found a lot of papers solving this problem using integer linear programming or genetic algorithms. But I thought, for such a common problem there must be an exisitng implementation. – Mouk Oct 14 '09 at 15:55
  • 10
    @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 Oct 15 '09 at 20:16
  • @Beta Convinced. Do have such an Algorithm? 90 degrees rotations are just enough for me. – Mouk Oct 23 '09 at 16:56

3 Answers3

8

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

user320450
  • 96
  • 1
  • 2
  • 3
    Is the source or c++ app available online anywhere? – Cole W Jul 07 '11 at 19:22
  • 1
    This is good for a simple solution but really doesn't work all that well. For anyone wanting a explanation and help writing one I suggest this book: Knapsack Problems, by Martello and Toth, ISBN: 0471924202 – ars265 Mar 13 '12 at 16:26
  • 3
    I can't find results in the linked page? is this still the correct url? – Amr Elgarhy Jan 25 '20 at 18:35
  • 1
    @AmrElgarhy From the name in original url, I guess [this](https://github.com/Janet-19/3d-bin-packing-problem/blob/master/Reference/erick_dube_507-034.pdf) is the same paper. – psycho Apr 22 '21 at 15:21
4

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.

Kerem Demirer
  • 1,186
  • 2
  • 13
  • 24
1

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.

ldog
  • 11,707
  • 10
  • 54
  • 70
  • 3
    Solving an NP-complete problem in polynomial time will still not give you a polynomial-solution to NP-hard problems :) – BlueRaja - Danny Pflughoeft Feb 03 '10 at 15:42
  • Well for small packages, the required time is not that high. So brute force is a fair alternative for quite a few online shopping shipments. – ThomasRS Apr 12 '19 at 10:25
  • @ThomasRS if you are willing to go brute-force, you will most likely get the best bang for your buck by using a corresponding ILP to represent the problem and feeding it into something like gurobi. – ldog Apr 17 '19 at 07:57
  • Thanks @idog, however I've already written a custom implementation which does a few application-specific optimizations like accounting for multiple boxes of the same size and such. – ThomasRS Apr 19 '19 at 22:23