3d Packing algorithm for item's shipping

Question

I've received a task to build a shipping estimative that suggests the best accomodation of goods on as few boxes as possible:

1. There is a finite set of known retangular box sizes

2. There are many arbitrary retangular item to be packed inside boxes

3. The fewer boxes should be used the best. Because shipping two boxes 1x1x1 is way more expensive than one box 1x2x1. This should be the priority here.

4. It should also be optimized to use the smaller boxes as possible, as a second level priority. (eg.: if presented with a choice between one bigger box and two small, it should choose the bigger box)

5. Items can be rotated to fit the box, but the rotation have to be limited to increments of 45° at a minimum (in my researches it seems that some configurations allow for a 45 degrees rotation to better fit retangular boxes inside a bigger retangular box), being 90° rotations the standard to be taken.

6. Boxes have a weight limit and items have arbitrary weights (eg.: an item that is size is 1x1x1 can be havier than other 2x2x2 item)

I've researched a bit and found some abstracted algorithms on bin packing and the knapsack problem and came with the following somewhat bruteforce variation, similar to the best fit algorithm:

1. Sort the items in decrescent volume order (bigger first) on an "items to pack" list

2. For each item on this list:

   1. Choose the smaller box that is on the "used boxes" list and has enough remaining volume and weight limit to fit the item (I will use fit here to mean fitting the dimensions and weight)

   2. If there is not such box, create a new box from the know set of possible box sizes that is the smallest size that can fit the item's dimensions and weight and add it to the list of "used boxes".

   3. If a box fits the item (using the fitting function bellow), add it to the list of "this box's items" and remove it from the "items to fit" list, marking it's relative 3d position inside the box.

   4. Repeat from 2.1 until there is no item to be fitted on the "items to pack" list.

The fitting check function used on step 2 above:

1. Check if the remaining volume of the box fits the volume of the item. If not, return false.

2. Check if the sum of "box's items" weight plus the current item weight is less or equal to the box weight limit. If not, return false.

3. Check the "box's items" list to choose the first box coordinate that has the smallest Y component and that has enough space for the item's width, depth and height, considering the other items placed as unavailable space.

4. If the item doesn't fit at it's current orientation rotate it on one of the 6 possible rotations, not assuming 45° rotations for simplicity. (Rotations that result in sizes that where already tested can be skipped. Eg.: rotating a box 180° gives the same dimmensions as the original position because all boxes and items have the same size for opposite faces and so can be skipped.)

5. If the item hasn't been rotated on all the possible ways back to its original orientation, try again from step 3.

6. If all rotations where tried and no fit was found, consider the current coordinate as unavailable space.

7. If there is not avaliable space to check, return false. Else, try again from step 3.

I want to know if there can be a best solution to my problem, given the presented constraints.

This seems to work on theory but I've not tried it on code. I wish to know if I'm going in the right direction or there are better, performant ways of doing this.

References would be great.

Edit:

I've found some interesting 3rd party API that do what I want, but this will have to be disconnected, so I will not have access to these.

Some examples are:

• http://v2.3dbinpacking.com/demo/main
• http://www.packit4me.com/api

Edit 2:

A real world example of problem to solve would be:

• I have 4 box sizes WxHxD: 10x12x18, 12x16x24, 16x20x30, 24x32x40
• I have an order of 4 items, being 1 of size 6x8x10, 2x 22x14x30 and 1x 22x4x20

How do I fit this items into any amount of boxes of one or more sizes using the fewer boxes as possible, using the smallest boxes possible and leaving less free space as possible?

Answer 1

Bin packing is very computationally difficult. Think of half of the problem: you want to pack product in shipping boxes with no wastage in the box. An optimal solution for that would require going through all possible subsets and all possible 3d arrangements of the product that needs to ship in one truck. I'll give you the optimal solution for that because I have a friend who does six impossible things before breakfast.

Now you just have to get all the boxes on the truck with no wastage. My friend does his second impossible thing and gives you the solution. Unfortunately, with the box sizes you selected above, there is empty space in the truck which could be reduced if you'd chosen different (either larger or smaller) boxes in the first task. If you change the size of one box, at best you'll have to re-pack the truck; at worst, you may have to repack all of the boxes which is just as hard as the problem we started with. And, as with the first stage, you'd have to try all possible 3d arrangements.

I found Skiena's The Algorithm Design Manual to be helpful for thinking about what class of algorithms suit which sorts of problems, but I mostly learned that good solutions for even mundane problems blow up in you face with computational difficulty. Most of what you are needing fit into the class of bin-packing problems and that article is a good jumping off point. It is worth noting that some of the best algorithms for this are commercial products because this task pops up everywhere in logistics (what's the smallest number of train cars can I get my goods into? and such). There is considerable money to be made if the right heuristics can save a manufacturer 100 train cars a month.

Unfortunately, the literature on optimizing heuristics isn't nearly as large as for algorithms. If you try to go it alone, I guarantee that you'll be dreaming about moving rectangular prisms around by your second month. I had a cutting-stock problem that if I had to do again I'd probably farm out to the experts (or their propriety software).

Thanks to @JTrana for the fine expansion of my comment.

Answer 2

When creating new algorithms, and I recently just did a packing algorithm by myself (I know it still has some optimization potential), I always do the most simple approach:

How would I as a human do it, and try tro translate it into an algorithm: From my (robotics) AI teacher Rolf Pfeifer I still bear in mind, that apparent intelligence sometimes may be created with some very simple rules, so instead of overengineering I try to underengineer

1. Identify too big items (items which do not fit in any given box)
2. Try to find the best box possible (by cross comparing total volume and item dimensions)
3. Order items from big to small and boxes (spaces) from small to big
4. Fit biggest item into smallest possible space
5. If biggest item does not find jump over it and try next one until nothing more fits

6. For the remaining items, search new best box. ...

   X. always think about exceptional events (oversize items, strange forms, if a box contains only 1 item wouldn't it be better to send item without box?, etc.) but you can make a heuristic also in a form of a decision tree.

Off course there are further caveats the further you get, I just give these ideas as a starting point. From there there are lots of ways possible. One alternative would be to divide a box into little cubes (e.g. 5cmx5cmx5cm) and track them as occupied/free another approach could be called 3d tetris, etc.

With this approach you don't have to necessarily worry about combinatory explosion. At the other hand, combinatory explosion could happen if we're talking about trainloads of items, but then again: Do you really think a company will check the packing list item by item? No they'lll approach a divide and conquer solution: Divide complexity by using standardized volumes (e.g. palets, or fixed sized boxes). So even for practicitys sake, take into account that not only trains, sometimes employee's time is money too. a train can load x palets, every palet has fixed volume, so pack items into palet, but then again, perhaps a palet consists of several order, so use fixed boxes for the items, which then are loaded into palets, which then are loaded into trains.

At least that's how I as a human would deal with the task, get best box and then fit biggest item one by one in smallest space available (and add a little bit of preview).

As in my algorithm, in the end you probably won't have the best solution, but a farily good heuristic which you then can further refine.

Sometimes it's easier to start with the first step and clear out problems on your way, well off course ideally not a kind of step over the edge step, but a little bit smart... sometimes you may be forced, to explore alternatives and choose the best one or implement an "step back".

But as I learnt from my AI teacher (Rolf Pfeifer, sorry to bother with that again): Sometimes you can create apparent intelligent behaviour with some very simple and few rulesets > emergent behaviour in the example mentioned they programmed little remote cars to turn left if they detect an obstacle at the right side, turn right if there's an obstacle on the left side and go straight if there's no obstacle or if the obstacle is in front. 3 or 4 robots as that, put in a 3m x 3m square with lots of ping-pong balls lead to the amazing fact that the robots seemed to be cleaning up, pushing the ping-pong balls to the corners, even though the robots are only programmed to avoid obstacles.

PD: The only real-world deviation I found from this approach is when I was part-time working as a stagehand for big concerts as metallica, iron maiden, britney spears, paul mcCartney, U name it... The truckers working on the international tours have precise packing lists item by item. The calculations gets done once (I don't know by humans or machines), and then replicated. Sometimes when they pack the first time, they even make layer by layer pictures and stick it within the truck just so that local crews know exactly, which box has to be charged when and where. But this is also a specific packing need as for one tour they always work with the same boxes and trucks.

Answer 3

The heuristic that you mention in your post seems interesting.

I would suggest a couple of modifications in order to improve the final solution.

Given a solution with all items packed in one box, try to merge together the contents of two small boxes in one larger box (this should help in improving your criteria of using as few boxes as possible).

Alternatively, every time you start a new box, instead of using the smallest box that can accommodate the current item, you could pick the largest box that can accommodate it, and once every item is assigned to a box, try assigning all items of a box to a smaller box.

Also, in your fitting function, instead of considering the position of your other boxes as fixed, you could imagine changing the loading sequence. This should let you find better solutions at the expense of a longer running time.