Math question

April 14, 2009 3:33 AM

Math problem with shipping rates. Can a maths whiz point me in the right direction?

Let's say a post office charges two rates, depending on the dimensions of the box you are sending. If your box is smaller than 350mm x 200mm x 30mm, it's calculated at rate X, if it's bigger, it's rate Y.

Now let's say we know the exact dimensions of all the individual products that will go in a box, and we just want to know if the total volume of the order is bigger than the cutoff or not. How can I work this out?

Answers in English, computer language, or just a general pointer would be appreciated. Also: is this an insanely difficult math problem? (it is for me, but I'm kind of a maths neophyte). Cheers

posted by dydecker to computers & internet (11 comments total)

Just a clarification: it's not about "total volume of the order", it's about whether the objects will fit into a box smaller than the cutoff, which is a much more difficult to work out IMO.
posted by dydecker at 3:37 AM on April 14

This is basically a packing problem. I don't have any insights to offer myself, except that knowing what it's called will help you find more resources on it.
posted by knave at 3:47 AM on April 14

Yep this is actually quite a bit more difficult than it first appears (iirc DHL saved millions recently by solving this problem more efficiently). As an alternative to thinking, you could use brute force :)
posted by devnull at 3:55 AM on April 14

Yes, it's hard.
posted by flabdablet at 3:59 AM on April 14

I see you are using mm, so are you perhaps in Canada? If so, then Canada Post has online tools that can make those calculations for you, and interface with many popular commerce packages. Information is here.
posted by woodblock100 at 4:03 AM on April 14

You can't do this absolutely, since you have no record of the SHAPE of the objects, or how they have to be packed. You can't just add volume together without data on the shapes, and that's crazy hard to calculate, to the point that it's not worth trying.

Some combinations of 100cc's will fit into a 120cc... but some will not. Depending on shape, in fact, 100cc's "worth" of items might not even fit into a 200cc box.

That is, the only way you could be sure that two 50cc's fit into a single 100cc box is if you are willing to accept that the two items can be crushed or destroyed into 50cc's of malleable powder. That'll work.
posted by rokusan at 6:36 AM on April 14

(PS: If this is only about ONE item per box, it becomes possible with just L x W x H. Maybe that is what you are asking, but your original question says "total volume of the order" which I read as "multiple items".)
posted by rokusan at 6:37 AM on April 14

While this is certainly a computational challenge for arbitrary sizes, you probably actually only have a few types of packages making this just slightly less hard.

What are the dimensions of all of your smaller packages? How many of those get packed together in groups? Are there subsets of things that you will always package together?
posted by odinsdream at 6:47 AM on April 14

You really want a full box-packing algorithm, but that's what they call an "NP-hard" problem, i.e., really really hard to teach a computer to do well. So, instead, some basic heuristics, which will do most of what you want, and reduce the number of times the guys in the warehouse tell you, "Well, we could have fit all the items into the flat-rate box if we ran them through the shredder first."

First, check overall dimensions for each item. Sort your box dimensions, largest to smallest (length, width, depth). For each item, sort its dimensions, largest to smallest (length, width, depth). Compare each sorted dimension against its box counterpart (length v. length, width, v. width, etc.). If the item's dimension is larger than the box dimension, the order won't fit.

Next, check total volume. Box volume is length x width x depth. Add up all the item volumes: item1length x item1width x item1depth + item2length x item2width x item2 depth.... If the total item volume exceeds the box volume, then the order won't fit. If the item volume is less than the box volume, then it will probably fit.

You could stop there, but you'll probably end up running into the aforementioned shredder problem, and you'll have told the customer you can ship the order for $20 but really it'll cost you $40 in postage because you'll have to use the higher rate, and that's no good at all. If your items are all small compared to the box dimensions then you have a greater likelihood of the box packers being able to find nooks and crannies in which to fit stuff. If not, you'll want one more simple check.

So, a naive box-packing heuristic. Stuff gets packed by layers, and you want to find out if the overall height of stuff that has to be stacked on top of one another will exceed the height of the box.

Examine each item in turn. If its length and width are more than half the length and width of the box, then it's going to have to be stacked. Start with an overall stack height of zero. Add the height of the item. Move on to the next item. If its length and width are less than half the length and width of the box, then chances are good it can fit into the remaining volume of the box somewhere, so skip it. Otherwise, add its height to the overall stack height. If the stack height exceeds the box height, the order won't fit. If you've examined all the items and the stack height is less than the box height, it'll probably fit.

Remember, this is a naive approach, but it's better than just calculating overall item volume.
posted by bigbigdog at 7:16 AM on April 14

Yes, this is a packing problem, and it is hard in general.

Please don't use the term 'maths whiz.' I don't call people who are good at writing 'English whiz'. It's demeaning, like it's a trick or something.
posted by number9dream at 9:27 AM on April 14

number9dream, can you solve this problem or are you just going to snark? I will use whatever expression i please, thank you very much.
posted by dydecker at 12:04 PM on April 14