Beefy Boxes and Bandwidth Generously Provided by pair Networks
more useful options
 
PerlMonks  

Packaging Algorithm

by marius (Hermit)
on Nov 07, 2000 at 06:09 UTC ( #40304=perlquestion: print w/ replies, xml ) Need Help??
marius has asked for the wisdom of the Perl Monks concerning the following question:

Surrounded by christmas presents of various sizes to send to family in Norway and shot down by "Ask Slashdot", I post my question here:

I'm looking at writing a perl program that given a number of dimensions for a number of boxes will create a 3D array of what the packaging box will appear. The program would ideally calculate the optimal size of box to use, and figure out a way to effeciently put the sub-boxes into it. I'm sure that shipping companies out there have this algorithm, but I can't seem to find it anywhere. Any people out there done 3D Visualization/Representation projects with perl?

I know it would be a matter of brute forcing a number of possibilities, and since I'm a perl cloobie rather than a perl ninja, I don't know where to start. =]

Currently I have a program that reads a file (or STDIN) by way of the diamond that will basically create three hashes: width, height, and length. The keys() to these packages are the package name, which is read from the input. I also calculate what's known to be a "minimum dimension" by using the largest dimension of all the boxes included. That's about as far as I've come so far, and any help would be appreciated.

Comment on Packaging Algorithm
Re: Packaging Algorithm
by extremely (Priest) on Nov 07, 2000 at 06:57 UTC
    There isn't an answer to this one. There are some strategies for doing this with restrained box sizes but the general case you describe isn't actually solvable. At least no one has yet. (of course, there may be some genius out there that just broke NP-complete problems too but...)

    I've not heard of anyone solving this or any related 2d or 3d problem.

    The balance problem, aka tape-sides is a good simpler example. Given a set of weights (or a set of song lengths) divide them into two sets that have the least difference in weight (length)

    There are a lot of nice strategies but they all have nasty cases that don't work. Exaustively trying every case is the only hope. The best bet is to minimize the cases you have to exhaust. Force everything to inch(cm) boundries, move boxes on the same. Pack things around the largest volume item, etc.

    Really, not to discourage you too much, it might be a good idea to start on something a bit simpler, like curing cancer. =)

    --
    $you = new YOU;
    honk() if $you->love(perl)

      There isn't an answer to this one. There are some strategies for doing this with restrained box sizes but the general case you describe isn't actually solvable. At least no one has yet. (of course, there may be some genius out there that just broke NP-complete problems too but...)

      Actually, I was playing Minesweeper this morning... awww nevermind.

      ALL HAIL BRAK!!!

      Remember, just because a problem is NP, doesn't mean it's unsolvable. It just means that there's no (known) way to solve it in polynomial time. All we can do in polynomial time is verify a solution.

      There's no reason that one couldn't write an algorithm to solve this problem. The problem is that for any non-trivial number of boxes, it would take a long, long time and/or some pretty expensive hardware to run that algorithm.

      --
      Ryan Koppenhaver, Aspiring Perl Hacker
      "I ask for so little. Just fear me, love me, do as I say and I will be your slave."

Re: Packaging Algorithm
by blogan (Monk) on Nov 07, 2000 at 08:41 UTC
    I'm trying to think of an algorithm, and this is what I've gotten so far:
    foreach (@closefamilymember) { $gift = perfectgift $_; buy($gift); push @boughtengifts, $gift; } foreach (@boughtengifts) { $box->pack($_); } foreach (@notsoclosemember) { $gift = perfectgift $_; if (!box->pack($gift)) { $gift = giftthatwillfitinfreespace $_; $box->pack($gift); } } box->mail();
RE: Packaging Algorithm
by marius (Hermit) on Nov 07, 2000 at 08:50 UTC
    Incidentally, after much googling, I have found this which will almost cover what I'd like to do. After the suggestion of an IRC-"pal" I decided to limit myself to boxes readily available at U-Haul. The concept of limiting myself to purely integer units had already come to mind, and to come the number of "solutions" from being infinite, it's definitely needed. I'm not really looking for the definitive answer, just a good "guess" and close approximation. =]
      I've found a similar algorithm, written in C. This is giving me an excuse to play with the Inline module, but I won't have anything tonight. :)

      But yah the algorithm calls for a known container size, and it attempts to pack everything into that container. What I'd like to do is extend this C version using Perl to give us the needed "given these sizes, what's the smallest that successfully packs everything" behavior, which would just iterate from the smallest to the largest (or whatever order, since I guess some boxes of the same size might be cheaper than others, etc.), and return the first one that gets them all in.

      I thought about re-writing this totally in Perl, but the algorithm is rather complex.

        Well, I've got the perl part down to picking the box that has the next highest capacity volume as the total volume of sub-boxes. (I'm using box information available at U-Haul) Mind passing along the C algorithm?
Re: Packaging Algorithm
by mitd (Curate) on Nov 07, 2000 at 09:07 UTC
    With all do respect to our esteemed monk extremely is this not closer to the 'Knapsack' and 'bin packing' class of problems which can be solved using several non-brute force techniques therefore do not fall into the general class of NP-Complete problems.

    There are several books that cover detailed solutions to these kinds of problems. My personal favourite is 'ALGORITHMS', Robert Sedgewick, Addison-Wesley, 1983.

    Sedgewick describes some excellent approaches to your problem.

    Computer Algorithms, Inroduction to Design and Analyssis, Sara Base, Addison-Wesley 1988 is also a good source.

    mitd-Made in the Dark
    'My favourite colour appears to be grey.'

      Actually, no it isn't like a bin-packing problem. It's like the sphere-packing problem. It is unbounded since he specifically asked for the smallest container. I'm pretty sure that is a rather bit nastier than bin-packing, since the only way to find the answer is to run the bin-packing work on a huge series of various container sizes. As I recall, that was what made this such a nasty problem, there isn't a specific strategy for finding the "best" answer, just a good strategy for finding a "fair" answer for a single facet of the problem.

      OTOH, mentioning Sedgewick's book is good enough for a ++ in my book, anyday =) And you are correct in that refactoring the problem can surely help make it solvable.

      --
      $you = new YOU;
      honk() if $you->love(perl)

        Why a sphere? He has a bunch of boxes. This seems perfect for a bin-packing problem. He just needs to try the algorithm against successively larger containers until he's able to fit everything. He's followed up with a comment indicating that he's already planned to limit himself to a pre-determined discrete set of box sizes.

        BTW, I used to work for a guy who had several good solutions for packing spheres. He used them for designing composites (for example, what mixes of sizes of gravel to use for certain types of concrete). One involved selecting spheres from the chosen mix at random and dropping them into a virtual cylinder and letting them settle. Sure, he wasn't proving the maximally tightest possible packing. But he was able to make good predictions about how certain mixes of sizes of spheres would pack in practice.

        He also sometimes repeated the experiment of make a bunch of spheres, put them in a bag, squeeze the bag for a few days, poor wax in, let it cool, remove bag, analyze positions of spheres.

        Don't let someone's proof that some problem is impossible to solve prevent you from solving the problem well enough to get your work done!

                - tye (but my friends call me "Tye")
RE: Packaging Algorithm
by Albannach (Prior) on Nov 07, 2000 at 19:07 UTC
    I just wanted to mention that this just screams to me for an adaptation of the Breeding Perls solution. If it weren't for this darn job I'd probably obsess about it for days, but since I haven't got the time now I'm throwing it in the ring here in hopes that some enterprising and terminally (ha!) bored student will have a go. C'mon, this is doctorate material!
Re: Packaging Algorithm
by Anonymous Monk on Feb 19, 2011 at 22:40 UTC
    This is not a perl solution and doesn't offer source code but if you're keen on saving time and not re-inventing the wheel, you can check out:

    SolvingMaze

    They have an e-Commerce shipping calculator that packages items into multiple boxes of different sizes and returns the postage. It also supports items with multiple packaging dimensions or "this-side-up" restriction, and boxes with postage varied by weight. There is an online API for integration with any application. As long your app has Internet connectivity, you can add to it.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://40304]
Approved by root
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (13)
As of 2014-08-27 18:04 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The best computer themed movie is:











    Results (248 votes), past polls