John is correct... I have been thinking about this problem for 19 years.
(FWIW my background is math and physics, not programming).
You cannot simply "cube" the dimensions - that doesn't work (we tried long ago). It would work if we were dealing with a liquid in a container.
We have a PC software that creates stacking patterns for same-sized cartons on a pallet.
But this would be different sized boxes within a box.
So you would almost need to take the longest dimension, find the boxes you have that it would fit into. Then start adding (stacking) the remaining items around it, keeping the other two dimensions as small as possible.
I would love to see UPS or FedEx create a web service that did this for their customers. Just think how much efficiency THEY could gain in their delivery system if they were shipping less "air".
We all pay for "dimensional weight" now because of a certain company... (Hint: they have a smile on their boxes).
Greg
-----Original Message-----
From: MIDRANGE-L <midrange-l-bounces@xxxxxxxxxxxxxxxxxx> On Behalf Of John Yeung
Sent: Thursday, September 8, 2022 10:29 AM
To: Midrange Systems Technical Discussion <midrange-l@xxxxxxxxxxxxxxxxxx>
Subject: Re: SQL Question
On Thu, Sep 8, 2022 at 9:17 AM Greg Wilburn
<gwilburn@xxxxxxxxxxxxxxxxxxxxxxx> wrote:
Thank you all for the responses... Charles hit the nail on the head. This is certainly non-trivial.
It's not "merely" nontrivial. It is a well-known hard problem in
mathematics and computer science. The optimization version (i.e.
what's the most efficient possible packing?) has been proven to be
NP-hard. The decision version (i.e. given a particular container, is
there a way to pack all the widgets into it?) is NP-complete. This
puts it in the same computational class of problem as the perhaps more
famous Traveling Salesperson Problem.
No one has found an efficient perfect solution. Not even Amazon, with
all its resources. There are efficient heuristic algorithms that can
provide "good enough" solutions. (In general, these kinds of
algorithms are not very well suited to programming in SQL.)
Rather than trying to figure out what box the items will fit into (based on their dimensions), I was considering finding an order that matched the contents.
That's an excellent idea. Looking up a past calculation is almost
always easier and faster than doing the calculation from scratch.
So for right now, we're going to rely on the "human" computer (i.e. the picker) to know what box to use.
Humans have *extremely* efficient heuristic algorithms.
John Y.
midrange.com
