Need carton-fitting algorithm
Author Message
Need carton-fitting algorithm

Can anybody point me to a quick algorithm to decide how to fit
things in boxes of different sizes? What i need is a way to take
a list of items, with dimensions, compare it to a list of cartons
with dimensions, and decide what is the smallest box that will
fit all of these. Case no box fits, i need then to split and use
more than one box.

I'm sure that there must be a solution to this, but i confess i'm
stuck. The solution doesn't need to be perfect; it must be right
at least 90% of the time. It is better to choose a box that is
too large than a box that is too small.

THIS IS NOT HOMEWORK. I need help. I appreciate any pointers.
Please EMAIL if possible, and i will summarize.

Thank you very much.

Glauber

--
glauber ribeiro

-------------------------
practice random kindness and senseless acts of beauty

Wed, 25 Mar 1998 03:00:00 GMT
Need carton-fitting algorithm

Quote:

>Can anybody point me to a quick algorithm to decide how to fit
>things in boxes of different sizes? What i need is a way to take
>a list of items, with dimensions, compare it to a list of cartons
>with dimensions, and decide what is the smallest box that will
>fit all of these. Case no box fits, i need then to split and use
>more than one box.
>I'm sure that there must be a solution to this, but i confess i'm
>stuck. The solution doesn't need to be perfect; it must be right
>at least 90% of the time. It is better to choose a box that is
>too large than a box that is too small.

If I'm not mistaken, this is called the knapsack problem, and
should belong to the NP-class of problems.  That means there is
no polynomial time solution.  In English, that means getting the
optimal solution (the fewest number of boxes) is extremely slow.
Knowing this is important.

At the top of my head, I'll try a solution, but I've never tested
this, so don't blame me ;).

1.  Take all elements bigger than 1/2 of the box and allocate them
to their own boxes (because no 2 of these will fit)
2.  Sort the remaining elements in order of size
3.  Use best-fit on the list of decreasing sized elements

This is clearly not an optimal solution, but it should give you an
approximation that is not too far away.  Hope this helps.
--
Steven ?:)

Thu, 26 Mar 1998 03:00:00 GMT
Need carton-fitting algorithm

Quote:
> If I'm not mistaken, this is called the knapsack problem, and
> should belong to the NP-class of problems.  That means there is
> no polynomial time solution.

Better change that to no KNOWN polynomial time solution, for the sake of
completeness. Unless you know better than us, of course. ;-)

Henning Makholm - math and CS student - University of Copenhagen

Fri, 27 Mar 1998 03:00:00 GMT
Need carton-fitting algorithm

: >Can anybody point me to a quick algorithm to decide how to fit
: >things in boxes of different sizes? What i need is a way to take
: >a list of items, with dimensions, compare it to a list of cartons
: >with dimensions, and decide what is the smallest box that will
: >fit all of these.

: If I'm not mistaken, this is called the knapsack problem, and
: should belong to the NP-class of problems.  That means there is
: no polynomial time solution.  In English, that means getting the
: optimal solution (the fewest number of boxes) is extremely slow.
: Knowing this is important.

As far as I knew, the knapsack problem was a purely one dimensional
problem... it discusses a situation where if we have n ``boxes'' of size s_1,
s_2, ..., s_n, then the condition s_1 + .. + s_n < S   is sufficient for them
to fit in a box of size S. For 3D boxes, though, this condition is not
sufficient. As you quite rightly pointed out, the one dimensional knapsack
problem is in the set NP, which almost definitely means no polynomial time
solution exists (although proving this is still one of the ``big'' unsolved
problems in computer science).

As for the 3D case, it seems particularly intractable... has anyone seen any
work done on this?

Jason.

Sat, 28 Mar 1998 03:00:00 GMT
Need carton-fitting algorithm

: >Can anybody point me to a quick algorithm to decide how to fit
: >things in boxes of different sizes? What i need is a way to take
: >a list of items, with dimensions, compare it to a list of cartons
: >with dimensions, and decide what is the smallest box that will
: >fit all of these. Case no box fits, i need then to split and use
: >more than one box.

: If I'm not mistaken, this is called the knapsack problem, and
: should belong to the NP-class of problems.  That means there is
: no polynomial time solution.  In English, that means getting the
: optimal solution (the fewest number of boxes) is extremely slow.
: Knowing this is important.

There is a polynomial solution in the case where all sizes are integers
restricted to a (not too enormous) certain range. Some practical
implemenations can be approximated by this. The algorithm is about as
follows:

1 You know how to fill a box of size 0
2 Take an object, add its size to all known fill sizes. This gives an array
of all possible sizes which indicates the last added object.
3 Is there a known object for any of the desired box sizes? ->5 :->4
4 Select a still unused object and repeat step 2.

5 Current size becomes resulting box size
6 Add the indicated object for the current size to the list of placed
objects
7 Subtract the size of the last allocated object for the current size
from this box size.
8 repeat steps 6-8 until current size==0.

Because you need an array to hold all possible fill sizes, the maximum fill
size must be restricted to something you can allocate an array for.

The complexity of this is N x m for N objects and m possible fill sizes.

I used this algorithm to find numbers from a set which add up to a
predefined sum.
--

Dpt. of Electrical Engineering                  | for device drivers:
Digital Information Systems Group               |
Room EH11.26 Eindhoven University of Technology |      Plug and Pray

Sun, 29 Mar 1998 03:00:00 GMT
Need carton-fitting algorithm

:: >Can anybody point me to a quick algorithm to decide how to fit
:: >things in boxes of different sizes? What i need is a way to take
:: >a list of items, with dimensions, compare it to a list of cartons
:: >with dimensions, and decide what is the smallest box that will
:: >fit all of these.
:
:: If I'm not mistaken, this is called the knapsack problem, and
:: should belong to the NP-class of problems.  That means there is
:: no polynomial time solution.  In English, that means getting the
:: optimal solution (the fewest number of boxes) is extremely slow.
:: Knowing this is important.
:
:As far as I knew, the knapsack problem was a purely one dimensional
:problem... it discusses a situation where if we have n ``boxes'' of size s_1,
:s_2, ..., s_n, then the condition s_1 + .. + s_n < S   is sufficient for them
:to fit in a box of size S. For 3D boxes, though, this condition is not
:sufficient. As you quite rightly pointed out, the one dimensional knapsack
:problem is in the set NP, which almost definitely means no polynomial time
:solution exists (although proving this is still one of the ``big'' unsolved
:problems in computer science).
:
:As for the 3D case, it seems particularly intractable... has anyone seen any
:work done on this?

I saw a presentation once on a truck-packing program, used to pack
various appliances (different size boxes) into a standard truck
trailer.  I don't remember details, but it probably used several
hueristics and limited trial combinations.  One of the hueristics was
to start packing from the right side (US usage).  Do you know why?

Mon, 30 Mar 1998 03:00:00 GMT
Need carton-fitting algorithm

:: >Can anybody point me to a quick algorithm to decide how to fit
:: >things in boxes of different sizes? What i need is a way to take
:: >a list of items, with dimensions, compare it to a list of cartons
:: >with dimensions, and decide what is the smallest box that will
:: >fit all of these.
:
:: If I'm not mistaken, this is called the knapsack problem, and
:: should belong to the NP-class of problems.  That means there is
:: no polynomial time solution.  In English, that means getting the
:: optimal solution (the fewest number of boxes) is extremely slow.
:: Knowing this is important.
:
:As far as I knew, the knapsack problem was a purely one dimensional
:problem... it discusses a situation where if we have n ``boxes'' of size s_1,
:s_2, ..., s_n, then the condition s_1 + .. + s_n < S   is sufficient for them
:to fit in a box of size S. For 3D boxes, though, this condition is not
:sufficient. As you quite rightly pointed out, the one dimensional knapsack
:problem is in the set NP, which almost definitely means no polynomial time
:solution exists (although proving this is still one of the ``big'' unsolved
:problems in computer science).
:
:As for the 3D case, it seems particularly intractable... has anyone seen any
:work done on this?

I saw a presentation once on a truck-packing program, used to pack
various appliances (different size boxes) into a standard truck
trailer.  I don't remember details, but it probably used several
hueristics and limited trial combinations.  One of the hueristics was
to start packing from the right side (US usage).  Do you know why?

Mon, 30 Mar 1998 03:00:00 GMT
Need carton-fitting algorithm

Quote:

>I saw a presentation once on a truck-packing program, used to pack
>various appliances (different size boxes) into a standard truck
>trailer.  I don't remember details, but it probably used several
>hueristics and limited trial combinations.  One of the hueristics was
>to start packing from the right side (US usage).  Do you know why?

This is a guess.  Granting the motive is to leave free space
contiguous, one naturally packs along one edge so the free space
would be to the other side.  Since there are two sides, one is
selected ;).  I doubt there's any benefit starting from the right
down?"  =)
--
Steven ?:)

Tue, 31 Mar 1998 03:00:00 GMT
Need carton-fitting algorithm

Quote:

> :: >Can anybody point me to a quick algorithm to decide how to fit
> :: >things in boxes of different sizes?........

--------------------<snip>-------------------

Quote:
> I saw a presentation once on a truck-packing program, used to pack
> various appliances (different size boxes) into a standard truck
> trailer.  I don't remember details, but it probably used several
> hueristics and limited trial combinations.  One of the hueristics was
> to start packing from the right side (US usage).  Do you know why?

The algorithm must start at some place, right? The middle seems like a
bad place (IMHO) so start in one of the corners. Left or right doesn't
matter. The implementor chose right. You can mirror the algorithm and it
will work the same (may that be good or bad :-)

// Jens M Andreasen

Wed, 01 Apr 1998 03:00:00 GMT
Need carton-fitting algorithm

Quote:

>: to start packing from the right side (US usage).  Do you know why?

>The driver (in the US) sits on the left side. By starting with the
>largest object on the right you have a tendency to balance the load.

Whoa!  That must be one _BIG_ driver!  Most of the trucks I'm aware of
Can you imagine what that guy's jeans must cost?  :)  :)  :)

--
*---------------------*  *--------------------------*
*  Bill Whedon, CPFT  *  *   I'm not getting older  *
*  Parkville, MO USA  *  *   I'm getting badder --  *

*---------------------*  *--------------------------*

Sun, 05 Apr 1998 03:00:00 GMT
Need carton-fitting algorithm

|[ Stuff excised ]
|>They wanted the items to be solid on the right.  There may be some
|>gaps on the left.  The difference?  Roads are crowned, causing the
|>truck bed to slightly tilt -- to the right in the US.  Thus creeping
|>refrigerators are avoided.
|>
|
|Seems to me a crowned road would also have the truck bed tilting to the
|right on the planet Mars :)

No.  On Mars, they drive on the left side of the road.  :-)

Cheers,
Stan.
--
HELP!  I'M BEING HELD PRISONER IN A .SIGNATURE FACTORY!

Thu, 09 Apr 1998 03:00:00 GMT
Need carton-fitting algorithm

Quote:

> >They wanted the items to be solid on the right.  There may be some
> >gaps on the left.  The difference?  Roads are crowned, causing the
> >truck bed to slightly tilt -- to the right in the US.  Thus creeping
> >refrigerators are avoided.

> Seems to me a crowned road would also have the truck bed tilting to the
> right on the planet Mars :)

Because of low rainfall on Mars, the roads are built with reverse
camber, so that blown sand may seep away from the center of the
would have a truck tilting left, just like a terrestrial driver in
the UK, Pakistan or Japan.

Still, it is a suit solution to the problem.  I've loaded thousands
of trucks as a mover, and the correct solution is _don't leave
spaces_.  You may be driving on one-way streets, or have to make a
sudden turn.  You use old packing material, burn your equipment into
the pack, pull suitably-shaped garbage out of a skip, whatever.

Incidentally, when you've solved the knapsack problem for
rectangular solids, would you care to try it for the typical moving
job?  Banana-shaped couches, high backed chairs, spindle-leg
furniture which /cannot/ support its own weight on its legs if you
hit a pot hole, lamps in various shapes and degree of fragility, and
marble tops which are susceptible to thermal stress.  It's OK to put
a box of books below a box of lampshades, but not vice-versa.
Bicycles must be loaded so the pedals don't experience lateral
pressure... walk around your house and you come across other
problems.

I've got several degrees and can solve these problems in real time.
I've worked with a guy who left school when he was 15, eschewed
breakfast in favor of half a bottle of vodka and an armful of
{*filter*}, and who solved them better and faster (He packed the truck,
but we wouldn't let him drive).  Obviously, there are usable
heuristics, but in my experience, the people who are best qualified
to explain them are exceptionally unforthcoming.

best wishes, mark s.

Fri, 10 Apr 1998 03:00:00 GMT
Need carton-fitting algorithm

:|[ Stuff excised ]
:|>They wanted the items to be solid on the right.  There may be some
:|>gaps on the left.  The difference?  Roads are crowned, causing the
:|>truck bed to slightly tilt -- to the right in the US.  Thus creeping
:|>refrigerators are avoided.
:|>
:|
:|Seems to me a crowned road would also have the truck bed tilting to the
:|right on the planet Mars :)
:
:No.  On Mars, they drive on the left side of the road.  :-)
:
:Cheers,
:Stan.
:--
:HELP!  I'M BEING HELD PRISONER IN A .SIGNATURE FACTORY!

Despite that, I am still somewhat pleased by the acerbity and wit of my
reply, and hope that in future I'll have a factual basis.
--
Arved H. Sandstro"m                       |     YISDER ZOMENIMOR
Physical Oceanography Group               |     ORZIZZAZIZ
Dept.of Physics, Memorial Univ. of NFLD   |     ZANZERIZ

Sat, 11 Apr 1998 03:00:00 GMT
Need carton-fitting algorithm

Quote:
Ryckman) writes:

:

:|[ Stuff excised ]
:|>They wanted the items to be solid on the right.  There may be some
:|>gaps on the left.  The difference?  Roads are crowned, causing the
:|>truck bed to slightly tilt -- to the right in the US.  Thus creeping
:|>refrigerators are avoided.
:|>
:|
:|Seems to me a crowned road would also have the truck bed tilting to
the
:|right on the planet Mars :)
:
:No.  On Mars, they drive on the left side of the road.  :-)
:
:Cheers,
:Stan.
:
Your'e incorrect. They use hovercraft on Mars (because the gravity is
so low) and they stack the oposing traffic vertically! This eliminates
the left or right issue-not to mention the road- so the reference to

--
:HELP!  I'M BEING HELD PRISONER IN A .SIGNATURE FACTORY!

Sat, 11 Apr 1998 03:00:00 GMT
Need carton-fitting algorithm

Quote:

> Your'e incorrect. They use hovercraft on Mars (because the gravity is
> so low) and they stack the oposing traffic vertically! This eliminates
> the left or right issue-not to mention the road- so the reference to

Of course, it raises the analogous problem of how to stack vehicles of
different sizes efficiently along a road.
--
Shields.

Sun, 12 Apr 1998 03:00:00 GMT

 Page 1 of 2 [ 16 post ] Go to page: [1] [2]

Relevant Pages