Need cartonfitting algorithm
Author 
Message 
Glauber Ribei #1 / 16

Need cartonfitting 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 


SzuWen Hua #2 / 16

Need cartonfitting 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 NPclass 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 bestfit 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 


Henning Makhol #3 / 16

Need cartonfitting algorithm
Quote: > If I'm not mistaken, this is called the knapsack problem, and > should belong to the NPclass 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 


Jason Tyler  Elec3 #4 / 16

Need cartonfitting 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 NPclass 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 


Gert Jan de V #5 / 16

Need cartonfitting 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 NPclass 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 68 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 


Thad Smi #6 / 16

Need cartonfitting 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 NPclass 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 truckpacking 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 


Thad Smi #7 / 16

Need cartonfitting 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 NPclass 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 truckpacking 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 


SzuWen Hua #8 / 16

Need cartonfitting algorithm
Quote:
>I saw a presentation once on a truckpacking 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 instead of from the left. See also: "Does the stack grow up or down?" =)  Steven ?:)

Tue, 31 Mar 1998 03:00:00 GMT 


Jens M Andrease #9 / 16

Need cartonfitting 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 truckpacking 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 


Bill Whed #10 / 16

Need cartonfitting 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 start with payload capacities of 1/2 ton, and go up near 100,000 (50 ton). 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 


Stan Ryckm #11 / 16

Need cartonfitting 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. > >Thad  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 


Mark Steph #12 / 16

Need cartonfitting 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. > >Thad > 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 road. Thus, someone driving on the righthand side of the road 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 oneway streets, or have to make a sudden turn. You use old packing material, burn your equipment into the pack, pull suitablyshaped 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? Bananashaped couches, high backed chairs, spindleleg 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 viceversa. 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 


Arved Sandstr #13 / 16

Need cartonfitting 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. :> :>Thad : :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!
I have been duly chastised for my ignorance. Please stop comments. 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 


Greg Purce #14 / 16

Need cartonfitting 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. :> :>Thad : :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 issuenot 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 


Michael Shiel #15 / 16

Need cartonfitting 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 issuenot 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] 
