volume/dimension algorithm question

  • Thread starter Thread starter sklett
  • Start date Start date
S

sklett

I realize this could be a little off-topic, but there are some great minds
on this NG and I hope you can let me slide this time ;0)

I'm designing our system to manage what products can fit in which cartons
and how many per carton. For example:
Widget A measures 10W x 10H x 10D
Carton A measures 20W x 10H x 10D
Carton B measures 50W x 10H x 10D

If I'm fulfilling an order for 2 Widget As I can choose Carton A as it will
contain 2 Widget A items.
Order for 50, Carton B, etc.

I would like to design a system that will eliminate user interaction in this
area, I would like my system to asses the item dimensions and quantity and
choose the appropriate carton.
The ideas that are floating through my head to solve this are far too basic
to be efficient and would result in a mess a spaghetti code handling
orientation combinations, etc.

Does anyone know of an algorithm that is designed to solve this problem?
I'm sure there is something out there, but my initial googling hasn't come
up with anything valid.
I hope you understand what I'm trying to achieve.

I appreciate any help!
Thanks,
Steve
 
Holy Cow!

I didn't realize how big of a question this was ;)

I've been doing some more googling and tried some didfferent key words and
found results. Everything I'm finding is very complex and that's just the
2D stuff, the 3D stuff is crazy.
I think I need to lower my hopes of finding a solution to this.

With that said, if anyone out there has done this I would still really like
to hear about it.
-Steve
 
You can seach google for "packing algorithm" and discover:
http://www.astrokettle.com/data.html
http://en.wikipedia.org/wiki/Bin_packing_problem

Your problem can be mapped to the "stock cutting problem", so you should do
a search for those algorithms too.

If you can constrain the ways in which you can fill a carton,
here is a rather naive approach that should be within 22% of optimal:
(see http://mathworld.wolfram.com/Bin-PackingProblem.html)
1. Order the cartons smallest to largest.
2. Order the items largest to smallest.
Foreach item:
select the first carton/subcarton that the item will fit in.
reduce the subcarton by dividing it into the subcartons that are left.

A "subcarton" is a cuboid (solid having 6 rectangular faces) that represents
some of the volume of the carton. The first time you add an item to a
carton you have left a set of cuboids (representing the volume left in the
carton). When you add an item to a cuboid, you dissect that cuboid into the
ones that remain, etc. So, the algorithm above looks at the subcartons
within the carton in attempting to fit the next item into the carton.

Note that when you add the first item to a carton, you can dissect the
remaining volume into 2 cuboids, in 2 different ways (and that is true for
each way you can place the item into the cuboid). If your items only fit one
way into the carton (as in your example) it will fit only one way into a
cuboid; you can see that this simplifies the problem considerably.

However, if there is more than one way to disect the remaining volume into
cuboids, you might want to do a depth-first search on the possibilities, or
some other optimization technique.
http://www.frontiernet.net/~fredm/dps/Contents.htm might be of use in that
case.
 
This is known as the bin-packing problem and is a classic problem of
computer science. The only sure way to find the best fit is to try all the
combinations, which is often an excessively large search.
 
You shouldn't have to try 'all' the combinations. Likely in a real world scenario you can find approximations first and
narrow it down to those closest to the solution from there. For instance if the cube of the widget is 1000 units and
the first 100 cartons have a cube <1000 units I wouldn't bother testing them. As for packing multiple widgets in
cartons I wouldn't bother testing cartons <2000 units.
 
Back
Top