How many bottles will fit in a box?
-
nimmi.smith (5/20/2009)
Thanks for the advise. I will find a math forum and post there. Any know of math forums?I will say it again - the problem you are trying to solve is known as the bin packing problem (or knapsack). It is known as an np-complete or np-hard problem.
Hugo has several methods in his blog to solve the problem in SQL. The best solution he came up with (so far) uses a cursor and the link I provided will get you started. Look for the second or third article in the series that outline the different methods.
Jeffrey Williams
“We are all faced with a series of great opportunities brilliantly disguised as impossible situations.”― Charles R. Swindoll
How to post questions to get better answers faster
Managing Transaction Logs -
Perhaps using a CAD package with the 3D size of the boxes and then you can put the bottles in there.
-
Jeffrey Williams (5/20/2009)
nimmi.smith (5/20/2009)
Thanks for the advise. I will find a math forum and post there. Any know of math forums?I will say it again - the problem you are trying to solve is known as the bin packing problem (or knapsack). It is known as an np-complete or np-hard problem.
Hugo has several methods in his blog to solve the problem in SQL. The best solution he came up with (so far) uses a cursor and the link I provided will get you started. Look for the second or third article in the series that outline the different methods.
Actually, this is more of a geometric packing problem. The bin-packing problems tend to be volumetric in nature. And usually the treatments of it that you will see (like Hugo's, IIFC) are one-dimensional in nature. Even the multi-dimensional treatments are based on rectangular shapes (rectangles, boxes, cuboids, hyper-cuboids, etc.).
Anytime you start talking about curves or irregular shapes (and bottle qualify on both counts) you're really into a completely different class of problem. I think that the OP would do best to look for "circle packing" or "disk packing" papers and discussions. The Bin-packing articles are not likely to help much.
[font="Times New Roman"]-- RBarryYoung[/font], [font="Times New Roman"] (302)375-0451[/font] blog: MovingSQL.com, Twitter: @RBarryYoung[font="Arial Black"]
Proactive Performance Solutions, Inc. [/font][font="Verdana"] "Performance is our middle name."[/font] -
Here's a recent article about a significant improvement in geometric packing algorithims, that includes a nice introduction as well.
[font="Times New Roman"]-- RBarryYoung[/font], [font="Times New Roman"] (302)375-0451[/font] blog: MovingSQL.com, Twitter: @RBarryYoung[font="Arial Black"]
Proactive Performance Solutions, Inc. [/font][font="Verdana"] "Performance is our middle name."[/font] -
Based on the link Barry's previous post an additional question needs to be answered:
Are you looking for the number of equally shaped bottles per box (meaning all bottles have the same diameter, for instance)?
How accurate this maximum needs to be? Are you looking for a local max or the global max (which would run into a totally different level of complexity)?
Adding another issue to be considered:
Since this is a "real world problem" and you're running a small job as you stated before I assume that the packing is done manually.
Referring to the link in Barry's prev. post again: Do you think one of your folks in the Shipping Dptmt. would actually be able to pack the given number of bottles in the given shape like it's shown? I wouldn't be able to do it in an acceptable amount of time...
Assuming, you'd give them an empty barrel and the number of bottles of each diameter as described in the link together with the "hint", that it will -theoretically- fit in there, how long do you think they will need? (even if you hand over a nice printout of the target pattern)
The point I'm trying to make is that the time for packing will increase with the complexity of the packing pattern.
Considering the increasing time for packing there probably will be a break-even-point where it starts to cost more to do the packing than the shipment will save.
Off T-SQL topic:
You should consider defining some practical packing rules first (if not happened already), e.g.
- packing will be done in (overlapping) rows of bottles with identical diameter (easy-to-remember-pattern)
- not more than two different diameter per layer (reduced complexity for manual handling)
- packing pattern will be repeatable within an box and across different boxes (standardization of packing)
With rules like above it should be feasible to come up with a function to calculate how many bottles per type (or types) will fit into a given box or what box you'd need for a given number of bottles.
-
RBarryYoung (5/21/2009)
... usually the treatments of it that you will see (like Hugo's, IIFC) are one-dimensional in nature. Even the multi-dimensional treatments are based on rectangular shapes (rectangles, boxes, cuboids, hyper-cuboids, etc.).Anytime you start talking about curves or irregular shapes (and bottle qualify on both counts) you're really into a completely different class of problem. I think that the OP would do best to look for "circle packing" or "disk packing" papers and discussions. The Bin-packing articles are not likely to help much.
While lmu92's comments should be a start, wondered what the real difference is here between bottles and rectangular shapes? I realize that the object itself is not shaped as a rectangle/box/whatever, but are they really going to fill the scant empty space with anything? If you treat it as a box, you should be able to come up with the same answer as treating it with curves. They'll all be (presumably) pointing up and stacked in layers within the boxes.
---------------------------------------------------------
How best to post your question[/url]
How to post performance problems[/url]
Tally Table:What it is and how it replaces a loop[/url]"stewsterl 80804 (10/16/2009)I guess when you stop and try to understand the solution provided you not only learn, but save yourself some headaches when you need to make any slight changes."
-
jcrawf02 (5/22/2009)
RBarryYoung (5/21/2009)
... usually the treatments of it that you will see (like Hugo's, IIFC) are one-dimensional in nature. Even the multi-dimensional treatments are based on rectangular shapes (rectangles, boxes, cuboids, hyper-cuboids, etc.).Anytime you start talking about curves or irregular shapes (and bottle qualify on both counts) you're really into a completely different class of problem. I think that the OP would do best to look for "circle packing" or "disk packing" papers and discussions. The Bin-packing articles are not likely to help much.
While lmu92's comments should be a start, wondered what the real difference is here between bottles and rectangular shapes? I realize that the object itself is not shaped as a rectangle/box/whatever, but are they really going to fill the scant empty space with anything? If you treat it as a box, you should be able to come up with the same answer as treating it with curves. They'll all be (presumably) pointing up and stacked in layers within the boxes.
Pointing all of the bottles up reduces it from a 3D to a 2D problem, but the difference between rectangular shapes and curved and more irregular shapes persists. I think that it can be explained by two reasons, first rectangular shapes can be oriented in a presumed rectangular grid making them much more amenable to array/loop computational solutions.
And secondly, although people often assume that something close to a rectilinear arrangement is optimal or a least near-optimal for shapes like circles, it in fact is generally poor compared to less structured solutions or even solutions structured on hexagonal or triangular approaches. Here is an image from the article that I mentioned previously that demonstrates the problem pretty well:
I think that it's easy to see that no rectilinear approach could compare to this. And even though it's circular shapes within a circular container, the same thing happens with circular shapes within a rectangular container (except that it is slightly easier because it is a well-known strategy to pack the smallest circles into the corners).
[font="Times New Roman"]-- RBarryYoung[/font], [font="Times New Roman"] (302)375-0451[/font] blog: MovingSQL.com, Twitter: @RBarryYoung[font="Arial Black"]
Proactive Performance Solutions, Inc. [/font][font="Verdana"] "Performance is our middle name."[/font] -
Hi Barry,
focussing on the question of the OP you're right that a rectilinear arrangement or any other structured solution won't be an optimum (even for boxes).
What I had in mind when I posted my reply was trying to apply the business case considering packing time as well. Something like:
SELECT MIN(((packing_time_per_box * packers_hourly_rate) + (shipment_cost_per_box )) / number_of_bottles_packed_per_box)
I assumed, a person who'd be packing boxes would be faster in packing a given amount of bottles when using a (repetitive) structured solution (including triangular and hexagonal) compared to a less structured ("visually random") solution.
I'm sure we both look at the same coin, just from different perspectives... 😉
Viewing 8 posts - 16 through 22 (of 22 total)
You must be logged in to reply to this topic. Login to reply