I've received a task to build a shipping estimative that suggests the best accomodation of goods on as few boxes as possible:
-
There is a finite set of known retangular box sizes
-
There are many arbitrary retangular item to be packed inside boxes
-
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.
-
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)
-
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.
-
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:
Sort the items in decrescent volume order (bigger first) on an "items to pack" list
For each item on this list:
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)
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".
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.
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:
Check if the remaining volume of the box fits the volume of the item. If not, return false.
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.
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.
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.)
If the item hasn't been rotated on all the possible ways back to its original orientation, try again from step 3.
If all rotations where tried and no fit was found, consider the current coordinate as unavailable space.
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:
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?
Best Answer
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.