Re: Calculate parcel size in PHP
- From: "Bob Bedford" <bob@xxxxxxxxxxx>
- Date: Wed, 17 Jun 2009 16:50:53 +0200
"C. (http://symcbean.blogspot.com/)" <colin.mckinnon@xxxxxxxxx> a écrit dans
le message de news:
786b29db-0b57-4c91-9ae6-baa0809e5227@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On Jun 16, 4:55 pm, "Bob Bedford" <b...@xxxxxxxxxxx> wrote:
Hi all,I love a challenge, so even though its rather off topic....
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
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:
(load as a CSV file in sa spreadsheet)
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=a1.sku
AND a1.sku=b.sku
AND a1.dtype=MOD(a.dtype+1,3)
AND a2.dtype=MOD(a.dtype+2,3)
AND b.sku=b1.sku
AND b1.sku=b2.sku
AND b1.dtype=MOD(b.dtype+1,3)
AND b1.dtype=MOD(b.dtype+2,3)
AND a.sku='$first_product'
AND b.sku='$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.
Thank you for your code, Colin. I'll have a try to those things as I've
first to understand the philosophy of what you have done.
Thank you also for the time you have spend to create such a huge answer, I
really appreciate it.
Cheers
.
- Follow-Ups:
- Re: Calculate parcel size in PHP
- From: The Natural Philosopher
- Re: Calculate parcel size in PHP
- References:
- Calculate parcel size in PHP
- From: Bob Bedford
- Re: Calculate parcel size in PHP
- From: C. (http://symcbean.blogspot.com/)
- Calculate parcel size in PHP
- Prev by Date: Re: Calculate parcel size in PHP
- Next by Date: Re: Retrieving pop mail from gmail/ssl
- Previous by thread: Re: Calculate parcel size in PHP
- Next by thread: Re: Calculate parcel size in PHP
- Index(es):
Relevant Pages
|
