Packing configuration problem

[stopher]

We need to optimise the layout of boxes on a pallet such that we can get the maximum number of boxes on a layer without exceeding the perimeter of the pallet. All boxes are the same size and are laid flat but can be rotated.

There is software available to do this but I'm sure this is a problem that can be solved using VBA. An example of the problem is provided is a simple game here. If you try the game for 9 boxes then getting 8 boxes to fit is pretty easy but getting the ninth to fit requires a bit of trial and error.

So the function will have the following inputs:

• Pallet Dimensions (lxw)
• Box dimensions (lxw)

Outputs:

• Maximum number of boxes that can be placed
• Position and rotation of each box e.g. perhaps as a list of coordinates of opposite corners of each box, or maybe a graphic.

I haven't really got very far with this. I'm thinking brute force. I'm thinking of some kind of recursive algorithm but I think my biggest problem is finding some function that can determine all the possible positions/rotations that the next box can be placed.

Any ideas?

Chris

 

[MarkK]

I'd avoid thinking about it as needing a master plan for box placement. I would write a box class that given a pallet and existing boxes, places itself. So you have two essential problems,

1) next box places itself <-- and logs its placement sequence
2) assess the current configuration, <- is it the best fit found so far

And with those two steps you can run scenarios. Parameters might be how many trials to run, but I bet you'll find out fairly quickly that certain set sizes will be optimized within a certain number of trials.

 

[plog]

This seems like an interview/programming contest/senior project that I've had before. I'm not saying this is homework and to go do it yourself, I'm saying there has to be plenty of solutions to this on the internet. Most likely in another language, but with that you could translate it to VBA.

In fact, I just found a Wikipedia article on it. Looks like there are some solutions in the external links section:

http://en.wikipedia.org/wiki/Packing_problem

 

[stopher]

I'd avoid thinking about it as needing a master plan for box placement. I would write a box class that given a pallet and existing boxes, places itself. So you have two essential problems,

1) next box places itself <-- and logs its placement sequence
2) assess the current configuration, <- is it the best fit found so far

And with those two steps you can run scenarios. Parameters might be how many trials to run, but I bet you'll find out fairly quickly that certain set sizes will be optimized within a certain number of trials.

Hi Lagbolt
I think I follow your thinking. For step one are you still saying I would need some code such that the box knows to put itself in a "sensible" position? By this I mean it does not simply place itself in open space but more logically butts up against existing boxes. Is that what you mean?

My initial thinking of where to put boxes was based on already existing nodes. A node being a point where the bottom left corner of our box can snuggle up to. So for an empty pallet the only node is 0,0. But with 2x3 box placed with 3 being vertical, we then have two new nodes at 0,3 and 2,0 where the next box can be placed. Of course for each node a box can have a choice of two orientations so I have to try both. Is this where you mean with scenarios?

I agree on the box class. I was thinking of a collection to store my boxes. As I think you are saying, I don't need to store then in a representation of a pallet.

Thanks
Chris

 

[stopher]

This seems like an interview/programming contest/senior project that I've had before.

Fantastic. I hope you'll be able to share your insight to help me with this problem.

I'm not saying this is homework...

Hopefully my profile, which has remained unchanged for over 5 years, will convince you that it is not.

....I'm saying there has to be plenty of solutions to this on the internet.

I would say that statement is true of 99% of the questions posted on these forums. I just wish I could find one in this instance.

In fact, I just found a Wikipedia article on it. Looks like there are some solutions in the external links section:
http://en.wikipedia.org/wiki/Packing_problem

Googling the title of my thread and posting the link that was at the top of the result list doesn't exactly convince me that you've given this much consideration

 

[MarkK]

Did you ever check out this snap forms thread I wrote? It'll snap a rectangle to the sides and corners of other aggregations of rectangles. If you think of the pallet as a rectangle that you snap to the inside of, and other existing boxes as things you'd snap to the outside of, then you essentially have an engine that can fit boxes into existing spaces.

Say you place the first box at 0, 0 and you keep placing boxes by whatever scheme you come up with, starting at the smallest x, y on the pallet, and moving thru each x, y on a box, you will eventually run out of possibilities as the pallet fills up. One way to run a scenario is unpack the last box and see if you can place it somehow or somewhere else, and if so, do it, and see if your outcome is better. When you've exhausted the options for unpacking the last box, unpack 2 boxes and replace the last one, and proceed.

That process is essentially a brute force loop that will run until every box has been placed in every location, and each of those configurations can be assessed (like, what leaves the least free space, or what places the most boxes, or maybe multiple criteria.)