# Calculate parcel size in PHP

#### Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

•  Subject
• Author
• Posted on
Hi all,

I've an internet shop and I'm facing a big problem with delivery costs. I'd
like to find a way to calculate the littlest possible box giving other
actual purchased box size.

Does somebody have an idea on how to do so ? This is not particular to PHP,
but if somebody has a PHP function, I'm interested for it !

Thanks for helping.

Bob

## Re: Calculate parcel size in PHP

Bob Bedford wrote:

Bob,

For the generic case, this is a classic advanced math problem which took
years to solve.  I would just suggest you do it do it by trial and
error; it won't be accurate all the time, but will get you close.
Otherwise, I'm afraid you'll have to bone up on your math.  It's not a
simple problem.

--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex@attglobal.net
==================

## Re: Calculate parcel size in PHP

On Tue, 16 Jun 2009 17:25:59 -0400, Jerry Stuckle

or find a carrier that calculates shipping costs by weight, not
volume. :-)

## Re: Calculate parcel size in PHP

Jerry Stuckle wrote:

If there's only a fixed set of box sizes available, that will probably
simplify things a lot.

In any case, this would better be posted to comp.programming (and
possibly sci.math, if you'd like).

--
Andrew Poelstra             <http://testing.wpsoftware.net/finex

## Re: Calculate parcel size in PHP

Thanks to all, I were quite sure it wasn't a simple problem.

I'll have a try to estimate the "best" solution

Cheers

## Re: Calculate parcel size in PHP

I love a challenge, so even though its rather off topic....

A simple solution might be to work out the minimal box volume by
iteratively adding the individual items to generate compound boxes.

So, given box A and box B

1) Place box A against box B, calculate volume as total length x total
width x total height, store orientation of A and B
2) rotate A 90 deg around X axis (i.e. swap length and breadth), if
resulting volume is less than stored, store orientation and volume
3) rotate A around Y axis (i.e. swap breadth and height), if resulting
volume is less than stored, store orientation and volume
4) rotate A around Z axis (i.e. swap length and height)
5) rotate B around X axis, repeat steps 2-4
6) totate B around Y axis, repeat steps 2-4
7) rotate B around Z axis, repeat steps 2-4
5) rotate B around Y axis
(i.e. there are 3x3 possible orientation for the 2 boxes).

Another way to think about is this - each box has dimensions width
(w),length(l),height(h) so all possible combinations are:

box a,box b,compound width,compund length,compound height,bounding box
volume
w,w,a.w+b.w,"MAX(a.l,b.l)","max(a.h,b.h)","(a.w+b.w)*MAX(a.l,b.l)*MAX
(a.h,b.h)"
w,l,a.w+b.l,"MAX(a.l,b.h)","max(a.h,b.w)","(a.w+b.l)*MAX(a.l,b.h)*MAX
(a.h,b.l)"
w,h,a.w+b.h,"MAX(a.l,b.w)","MAX(a.h,b.l)","(A.w+b.h)*MAX(a.l,b.w)*MAX
(a.h,b.l)"
l,w,a.l+b.w,"MAX(a.h,b.l)","MAX(a.w,b.h)","(a.l+b.w)*MAX(a.h,b.l)*MAX
(a.w,b.h)"
l,l,a.l+b.l,"MAX(a.h,b.h)","MAX(a.w,b.w)","(a.l+b.1)*MAX(a.h,b.h)*MAX
(a.w,b.w)"
l,h,a.l+b.h,"MAX(a.h,b.w)","MAX(a.w,b.l)","(a.l+b.h)*MAX(a.h,b.w)*MAX
(a.l,b.l)"
h,w,a.h+b.w,"MAX(a.w,b.l)","MAX(a.l,b.h)","(a.h+b.w)*MAX(a.w,b.l)*MAX
(a.l,b.h)"
h,l,a.h+b.l,"MAX(a.w,b.h)","MAX(a.l,b.w)","(a.h+b.l)*MAX(a.w,b.h)*MAX
(a.l,b.w)"
h,h,a.h+b.h,"MAX(a.w,b.w)","MAX(a.l,b.l)","(a.h+b.h)*MAX(a.w,b.w)*MAX
(a.l,b.l)"

Then you find the minimal bounding box volume.

Then repeat with subsequent boxes.

Note that to find the true optimal packing strategy you'd need to
apply the method above to all possible orientations of all possible
boxes - i.e. finding the minimum of 3^N calculations.

Without knowing what N is before hand you'd need to use a recursive
function.

So although it won't be as good a solution, it might be simpler to
calculate the box required for A and B (AB) then calculate the size
required for AB and C....that reduces the algorithm order to (N-1)*3^2

The full set of combinations above are generally referred to as a
cartesian product. You could push all the computation cost into the
database, e.g.

where 0 is width, 1 is length and 2 is height....
sku, dimension, type
PC, 90, 0
PC, 86, 1
PC, 25, 2
KeyB, 80, 0
KeyB, 25, 1
KeyB, 5, 2
Mouse, 20, 0
Mouse, 15, 0
Mouse, 7, 0
....

Then for 2 boxes...

SELECT a.dimension+b.dimension as compound_width,
GREATEST(a1.dimension, b1.dimension) as compound_length,
GREATEST(a2.dimension, b2.dimension) as compound_height,
(a.dimension+b.dimension as compound_width)
* GREATEST(a1.dimension, b1.dimension)
* GREATEST(a2.dimension, b2.dimension) AS compound_volume
FROM
prods a,
prods b
prods a1,
prods b1,
prods a2
prods b2
WHERE a.sku=3Da1.sku
AND a1.sku=3Db.sku
AND a1.dtype=3DMOD(a.dtype+1,3)
AND a2.dtype=3DMOD(a.dtype+2,3)
AND b.sku=3Db1.sku
AND b1.sku=3Db2.sku
AND b1.dtype=3DMOD(b.dtype+1,3)
AND b1.dtype=3DMOD(b.dtype+2,3)
AND a.sku=3D'\$first_product'
AND b.sku=3D'\$second_product'
ORDER BY compound_volume
LIMIT 1,1

But where this becomes even more messy is that you probably only have
a finite number of packing crates available in different sizes and
shapes - it doesn't follow that the smallest (cheapest) outer packing
crate required to accomodate the volume returned above is the smallest
one which will accomodate all the contents: if you try to minimise
volume using the algorithm above, it will tend towards a cube shape -
but if all your boxes are very long and thin, then you'll need a very
big box to accomodate the width and height calculated.

HTH

C.