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.
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:
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?