Hello,
I need an algorithm for my ecommerce application that can compute and give me the x, y & z azis dimensions of the smallest 3d rectangle that would be able to contain a unlimited set of packages. The input boxes dimensions would be specified as an array :
For example :
[0]['length'] = 2.3
[0]['width'] = 4
[0]['height'] = 6
Those dimensions will be specified for each product I have in the cart... now I want to know what is the smallest box (which the site admin entered in its admin area) that can contain all these packages.
Volume calculation does not work here, even if the overall volume of all packages would fit into a box, the physical dimensions of some packages would prevent the box from beeing used sometimes...
I would be very happy if some could come up with a near perfect solution for this problem...I tried many times but my solutions were not really precise... and I love perfection.. so im waiting for your answers !
Thank you very much in advance >what is the smallest box that can contain all these packages
This is a Packing Problem, a type of search problem as is taught in most Artificial Intelligence or algorithm courses.
Look for articles on blind search (Breadth-First Search, Depth-First Search) and heuristic search (A*).
Something with this much complexity will almost surely want to use heuristic search, and a large part of your task will be picking a good formulation AND a good heuristic.
There are very probably some open-source code or libraries for this. Sorry I don't know any names. Google should help.
But here are the keywords and concepts you want to know:
(We assume packages can't be arranged diagonally, i.e. must be orthonormal).
Anyway, you can formulate the packing problem by recursively dividing bounding volumes of free space (or adding volumes of occupied space).
Say there are N boxes, each with l,b,h parameters.
We consider configurations of each box B_i with some (xi,yi,zi) position (e.g. pick the bottom left corner, rather than the center) and each box can also be rotated to 3! =6 different configurations.
So each B_i has 4 parameters: 3 coords (integer or float) and 1 rotation (rot_i, a six-valued integer parameter).
So all points in the state space of the problem have 4N parameters.
>I would be very happy if some could come up with a near perfect solution for this problem
Well the complexity is also going to depend on the grid resolution you choose: 螖 = 0.1 ft perhaps? You can pick a coarser grid and round upwards the original l,b,h or the volumes, that may be slightly suboptimal but much-lower-complexity (especially if you have lots of irritatingly small boxes and a few large ones).
Note that since we have 3N coordinates, each of which can assume a number of values proportional to (1/螖), the number of possible states will increase with O((1/螖)^3N).
Thus if 螖=0.2 ft, we only need to consider x,y,z positions each with a granularity of 5 per foot, but if 螖=0.1 ft, we now have a granularity of 10 per foot in each of three axes, thus we increased our complexity by 2鲁 = 8.
>Volume calculation does not work here, even if the overall volume of all packages would fit into a box, the physical dimensions of some packages would prevent the box from being used sometimes...
Well at least you do know that the optimal volume must be 鈮?危 li*bi*hi , so that's a starting-point or sanity-constraint.
Also, the position and rotation of the first box are arbitrary, so you could pick the largest-volume box and place it at (0,0,0) with some arbitrary rotation. I think it has been shown that this question can only be answered definitively by trying every possibility. This can take a lot of time.
All your packages are the same shape and size.
Place one package on a table. Place another next to the first along the shortest dimension. Place two next to the first two along their combined shortest dimension. Place four more against the first four along the shortest dimension of the first four.
Continue to place a second configuration of packages identical to the present configuration of packages along their shortest dimension until all the packages are packed.
If the final lot of packages is not the same number as the previous it might be possible to arrange them in a different orientation to fit them into a smaller space. |
