How can I programmatically determine how to fit smaller boxes into a larger package? [closed]

Question

Does anyone know of existing software or algorithms to calculate a package size for shipping multiple items?

I have a bunch of items in our inventory database with length, width and height dimesions defined. Given these dimensions I need to calculate how many of the purchased items will fit into predefined box sizes.

Squelch

Interesting question. At first I was thinking about ways to calculate the area of each item compared to the area available for the box, but that's doesn't really work when you have things that aren't, like, perfect cubes... You could have space left in the box without it being usable space. Hrm... – Rosenquist

Thanks BTW to Rich B for improving the title of this question. Especially adding the "programatically" a la a recent SO podcast. – Squelch

Answer 1

This is a Bin Packing problem, and it's NP-hard. For small number of objects and packages, you might be able to simply use the brute force method of trying every possibility. Beyond that, you'll need to use a heuristic of some sort. The Wikipedia article has some details, along with references to papers you probably want to check out.

The alternative, of course, is to start with a really simple algorithm (such as simply 'stacking' items) and calculate a reasonable upper-bound on shipping using that, then if your human packers can do better, you make a slight profit. Or discount your calculated prices slightly on the assumption that your packing is not ideal.

Stlouis

Your definition is accurate, and I voted your answer up since it provided some useful reference info. Ideally I'd like to find a ready made solution. – Squelch

polara: did you find a solution? – Extinguish

Answer 2

The literature on "3D Bin packing" is far and wide. You can get a good overview by tracking the publications of Professor David Pisinger. He also published one of the few high quality implementations of bin packing with sourcecode: 3dbpp.c

My own logistics toolkit pyShipping comes with a 3D Bin Packing implementation for Warehousing applications. It is basically implementing 4D Bin Packing (3D size & weigth) and gets an acceptable solution for typical order sizes (a few dozens of packages) in under a second runtime. It is used in production (meaning a warehouse) for some months now to determine the upper bound of shipping crates to be used. The warehouse workers are often able to pack somewhat more efficiently but that's OK with me.

Microhenry

The source code link has died – Infect

Hi @Qwertie, I think I've found the source code here: hjemmesider.diku.dk/~pisinger/3dbpp.c – Novation

Answer 3

Pisinger is one of the few academics who posts working code. In one of his papers he mentions the "Minimum Depth" problem.

Here is a practical and efficient algorithm for 3D Rectangular Box Packing that adjusts the height of the enclosing box.

And here is an implementation in php.

Austen

Answer 4

Are you trying to see how many of a single type fits into a particular sized package, or are you trying to mix types as well?

Sounds like you're trying to solve the Knapsack Problem. You might be able to find some algorithms for that which could be adapted to your specific requirements. Just understand that it will be hard to find an efficient algorithm, as the problem is NP complete (though depending on your specific requirements you may be able to find an efficient approximation, or your inputs may be small enough that it doesn't matter).

Prithee

Your description and referenced link are accurate as well. As in the case with the Bin Packing problem that Arachnid referenced, there can be an extreme number of different possible solutions compounded by the ability to turn items sideways in the box. – Squelch

The problem as posted by the OP is not an instance of Knapsack. – Etna

Answer 5

If the boxes are to be hand packed, then you might consider writing an algorithm which would do what a reasonable human would do. The reason I suggest this is because unless you want to print out packing instructions for each order, then whoever is doing your packing is going to have to workout how they are going to fit the ordered items in however many boxes it has been allocated for the order.

This might then lead to your human packers coming to SO asking on how to programmatically workout how to pack n items into m boxes. :-P (They might also ask you to do it, ask you for instructions, etc).

As long as your algorithm does what a reasonable human being would do, I would personally accept its shipping estimate.

Sleepwalk

Answer 6

Metaheuristics are good to deal with real world bin packing problems when there are many packages and/or many constraints. One open source Java implementation is Drools Planner.

Osmond

Answer 7

Maybe this will sound obvious, but it might be worthwhile to memoize the problem, then do some of them by hand. Finding a most effecient solution for arbitrary inputs and boxes in NP-hard, but by restricting the problem space, and accepting some inefficiency, that NP size might be something reasonable, and by memoizing, you might be able to bring the "common-case" time down substantially.

It might also help to think about things in terms of hierarchical packing.

Preempt

Thanks. Yes, heuristics were suggested by Arachnid as well. The application of this was to calculate shipping charges, and I could imagine a fully automated solution coming up with all sorts of impractical arrangements. – Squelch

Answer 8

After lot of searching i have found a GitHub repository that might help someone. Function PackingService.Pack() takes list of Container and list of Item(s) to be packed as parameter and return result which contains lot of information including

"container(s) packed in percentage and list of packed and unpacked items"

Omniscient

While this link may answer the question, it is better to include the essential parts of the answer here and provide the link for reference. Link-only answers can become invalid if the linked page changes. – Cos