2-dimensional bin-packing in Excel

Question

I’m trying to find a solution for the 2-dimensional packing problem using Excel (Formulas, Solver, VBA).

But apart from finding said solution, I would like to bring back this topic as base for discussion, because I realized during my extended web-searches that this problem (or variations of it) creates headaches for many people – novice and professional users.

The explanation for my problem:

I am trying to fit rectangular packages in rectangular containers. Usually there is one larger box and 2-5 smaller boxes to ship. On average, there is still capacity of 30-50% left in the containers, so I want to calculate how many additional standardized boxes would fit in this free space to fill up the container.

There are no constraints, as long as the boxes fit into the container.
Height and weight are irrelevant.
The Boxes can be rotated by 90°.
One 40’ container is 1203cm long and 233cm wide.
The standardized boxes are 85cm x 70cm
The other boxes have different sizes.

I checked bin-packing algorithms but as of now I was not able to implement any solution in excel. I’d prefer a way to calculate this using Excel Solver or VBA, but my VBA-programming knowledge is limited.

The knapsack problem does not apply here in my opinion, although it is mentioned many times in this context.

In my case, I would be happy with a solution giving me something like: “You can fit at least x additional Boxes in the container”. Some inaccuracy does not matter – meaning up to 25% less boxes than possible. Too much boxes, on the other hand, are a no-go.

Now, do you guys have any idea how to get started here or even accomplish this? Maybe there is even a super-simple approximation I don’t know of?

Thanks!

UPDATE

After quite some time, I finally found some hours to get into this problem again.

I read Erwin Kalvelagen ‘s Blogposts and some papers on bin packing algorithms. Also, the solver option is off the table. I decided to go for a Bottom-Left-Algorithm (BLT) with some restraints (not just greedy).

Quick explanation of the BLT-Algorithm: Each box is placed in the bottom-most and left-most possible position in a given area (container). When a box is placed, it creates two new “corners” where the remaining boxes can be placed. Initially, the boxes are sorted by length (to start with the longest box) and place them in a 2-dimensional array. Then the starting point will be set in an Array (x, y coordinates) – the first coordinates are obviously 0, 0 as we start in an empty container. Then the algorithm would try to place the first box in the bottom-left corner with coordinates 0, 0 – which of course works perfectly. Then the starting cords would be replaced by the coords of one of the new corners and the coords of the other corner will be added to C. this would loop until all non-standard boxes are loaded. Then the algorithm would add standardized boxes if possible (and count them). The loop would end, if adding more boxes is not possible anymore due to constraints.

The dimension of the non-standard boxes will be entered in a worksheet - one box per row. The dimensions of the container and the standardized boxes will be written there as well.

Constraints would be, that no box can overlap another and all boxes would have to inside the container. Although rotation is practically possible, it is not necessary to implement it in the code as I am trying to orient the packages along the container.

Here is some pseudo code of the BLT-Algorithm I found:

**Procedure BLF(width, height,maxWidth)**
begin
initialize the arrays x and y
initialize the list and add the null point
for all rectangles
 initialize choosePoint as impossible
 while choosePoint is impossible and j < length of list
  if the rectangle could be placed in a specific point
   choose the point
  endif
 endwhile
 if choosePoint is possible
  update the arrays x and y
  remove the point from the position choosePoint
  from list
  add the points (xi+width,yi),(xi,yi+height) to the points list
 else
  if (width > maxWidth) the problem has no solution
  else xi = 0 and yi = max(heightk + yk)
  where k 2 {1, . . . , i − 1}
  endif
 endif
endfor
solutions: the arrays x and y with (xi, yi)
the coordinates of rectangle i
end

Now, although I know a lot (like really A LOT) more about packing algorithms I am still not very experienced with VBA. Especially not with implementing algorithms. So again I would be happy for any help you can give me to get started with the implementation.

So I started off with this (I know it’s really nothing, but I find it quite difficult):

Sub BLT1()

Dim Boxes As Variant, i As Integer, j As Integer ‘’Boxes dimensions
Dim Cntnr As Variant, a As Integer, b As Integer ‘’Container dimensions
Dim BLPoints As Variant ‘’Array with coordinates of bottom-left corners

Boxes = Range("B11:C15")
Cntnr = Range("D2:E2")

‘’Now I would like to add the first coordinates (0, 0) to the BLPoints
‘’Then I want to pick the first box and fit it in the container at the (0, 0) coordinates
‘’Then I want to update the BLPoints array with the new coordinates
…

End Sub

I’m looking forward to any constructive feedback and advice!

2-dimensional bin-packing in Excel

Answers (1)

Related Questions