Algorithm for distribute products to boxes

Question

I have Products and Boxes. I want to use minimum box count for packaging. Please ignore product and box dimensions (WxHxD). Only focus on volumes.

I need an algorithm for placing these products to boxes. Algorithm must use minimum count of boxes and the smallest boxes it can. Algorithm can use same box more than one. Each product can be used only one time.

I Tried this algorithm

Order products ascending by volume
Put smallest product to biggest box, then add next product to box. Until there is no space for next one. Repeat until products finish.

Acoording to this algorithm

E product to Z-1 Box (Free Space: 2900 cm3)
B product to Z-1 Box (Free Space: 2700 cm3)
F product to Z-1 Box (Free Space: 2300 cm3)
D product to Z-1 Box (Free Space: 1700 cm3)
A product to Z-1 Box (Free Space: 700 cm3)
B product to Z-2 Box (Free Space: 1500 cm3)

So algorithm uses 2 pieces Z Box. But human brain can fit (C+A+F+E)= 3000 cm3 (Z box) and (B+D) = 800 cm3 (X Box) Thanks for all comments and replies.

unlimited. For example product count can be 100, and box type can be only one. — sipdorus, Oct 30 '20 at 18:44
Please specify the problem better. For example, can more than one product fit in one box? How many of each product that you have that you want to package? — ldog, Oct 30 '20 at 18:45
At my examples yo can see more than one product fitted in one box. Each product can be used only once. — sipdorus, Oct 30 '20 at 18:47
Similar question - https://stackoverflow.com/questions/2192087/3-dimensional-bin-packing-algorithms — OneCricketeer, Oct 30 '20 at 18:50
If you are ignoring dimensions, then this is just a regular knapsack problem, afaict. https://en.wikipedia.org/wiki/Knapsack_problem#Solving — OneCricketeer, Oct 30 '20 at 18:52
Yes, I read similar question offer. But I am not interested in WxDxH. Only volumes. So you can think volume as weight and boxes as pochette. — sipdorus, Oct 30 '20 at 18:52
Knapsack problem is simalar but problem is we can use different size of bags, same bag more than one time. And value of all products per cm3 is same. I searched greeddy algorithm. But not suitable for this problem. — sipdorus, Oct 30 '20 at 19:10
"Algorithm must use minimum count of boxes and the smallest boxes it can" Do you mean that the number of boxes must be minimal before considering the box sizes? Because you need to specify that one of these criteria is more important than the other. If not, consider the case where you have 1 item A (1000) and 1 item E (100), these can either be fitted A into X and E into T for 2 boxes with total volume 1100, or put them both into a single box V, for 1 box with volume 2000. — ROX, Nov 02 '20 at 15:32
without going into proof, I find it very unlikely that an algorithm involving assigning the smallest products first will yield the best results. — ROX, Nov 02 '20 at 15:35
ROX algorithm must aim using minimum count of boxes. In your example algorithm must suggest V (2000 volume) for A and E. — sipdorus, Nov 02 '20 at 20:19
The problem with multiple boxes is NP hard, so you will not find an efficient algorithm that can find an optimal solution. See for instance https://stackoverflow.com/q/23689236. — Vincent van der Weele, Nov 03 '20 at 10:30
I (and ROX) noticed that you have given two different goals, which makes your request potentially ambiguous. "Algorithm must use minimum count of boxes and the smallest boxes it can." Do you mean, "The solution must use the minimum count of boxes. And while using the minimum number of boxes for a solution, the solution with the smallest boxes it can."? But even then, the second part is unclear. Is a small and a large box better or worse that using two in between size boxes? Do you intend something like, "The solution must have minimal number of boxes and with the least unused volume"? — Eric, Nov 04 '20 at 23:22
Interesting problem. If it had more points, `500+` then I might take more than a passing interest in this, but for `50` points it is just not worth my time. I know this is a real problem for many warehouses and there are commercial applications for solving this, so why give the solution away for next to nothing. I would use Prolog to solve this and start with [library(simplex): Solve linear programming problems](https://www.swi-prolog.org/pldoc/man?section=simplex) — Guy Coder, Nov 05 '20 at 12:05
This is the `bin-packing problem`. See my answer [here](https://stackoverflow.com/questions/63819538/best-way-to-loop-through-and-combine-products#63910196) — Booboo, Nov 05 '20 at 15:38
Is this abandoned? I see the critical question of weightings between min vol and min box count unanswered! — Paddy3118, Nov 07 '20 at 11:06
I will ask for clarification a different way. Suppose one has three A products of 1000 each. Is it better to put them into one Z box because this will achieve the first goal of "Algorithm must use minimum count of boxes" (but fails the second goal)? OR is it better to put them into three X boxes because it achieves the second goal "Algorithm must use ... the smallest boxes it can" (but fails the first goal)? Also, instead of "smallest boxes", do you really mean "least wasted space"? Please clarify what goal is primary and exactly what goal is secondary. — Eric, Nov 10 '20 at 11:11

score 1 · Answer 1 · answered Nov 03 '20 at 18:08

I would calculate the optimal ways to fit the boxes inside each other.

One Z equals one V and one X.
One V equals two X.
One X equals two U.
One U equals up to five T (must be able to combine at least 2 boxes into 1 for any box merge to make sense).

This step may be rather computationally expensive depending on how many boxes you have and how easily you get fit them into each other. IE: This would be much less straightforward and harder if you had box size where they are no common multiples. See the https://en.wikipedia.org/wiki/Change-making_problem for examples of what really "nice" box size combinations would look like (the example you gave is quite nice).

Move all products in one box to other boxes with the goal of get as close to 0 remaining space as you can, ideally start by looking for moves that result in exactly 0 remaining space (only by taking everything in one box and moving it to another box).

Then merge the boxes as much as you can on the above rules as long as it reduces the # of boxes by at least one. IE: CEF=> V (technically it would be E => F, then EF => C), A => X, DB => X. Then you can combine it from there. ADB = V (Combine 2X boxes into a single V box).

Another valid option is: DF => X, BCE => V, A => X. In this case, we still combine the two X into a V. There are also likely solutions where you might have 1 V and 1 Z, but that only makes sense if you had 1X and 1V, otherwise it would be better to use 2X => 1V instead.

In many cases, this may not yield optimal results, but there is something to be said about picking (or rounding) box sizes (and probably product volume sizes) such that it _can_ yield optimal results as otherwise, you probably can't get optimal results in a reasonable amount of time with 100+ products. — Nuclearman, Nov 03 '20 at 18:13

score 0 · Answer 2 · answered Nov 08 '20 at 16:36

determineBox(listOfProducts) {
  create an empty list of boxes listOfBoxes
  VS = sum_of_volume(listOfProducts)
  If there is a box which volume is bigger than VS
    add the smallest box bigger than VS to listOfBoxes
  Else
    create an empty list newListOfProducts
    consider the biggest available box B
    add B to listOfBoxes
    until the sum_of_volume(listOfProducts) become smaller than the volume of B
      drop out of listOfProducts the smallest item
      and add it to newListOfProducts
    merge listOfBoxes with the result of the function determineBox(newListOfProducts)
  returns listOfBoxes
}

The idea is to use a recursive function to find the smallest box to store the maximum of product.
For the remaining products, we use again the function.

score -2 · Answer 3 · answered Nov 07 '20 at 14:26

How much would you pay for an answer like:

==========

Found the following best packing into 2 boxes after 10 trials:
  Box z with space 200.0 cm3 left contains product(s):
    D C E B F
  Box x with space 0.0 cm3 left contains product(s):
    A

END.

The idea is to weightedly select from choices.

Algorithm for distribute products to boxes

3 Answers3

Linked