Packing Algorithms May Save the Planet 195
An anonymous reader writes "New Scientist reports on how competitions to devise better packing algorithms could help cut the environmental impact of deliveries and shipping. A new record setter at packing differently-sized discs into the smallest space without overlapping them has potential to be applied to real world 3D problems, researchers claim." Ok the title might be a little ridiculous, but the ridiculous packaging used to ship a few tiny objects by some shippers is pretty shameful.
Packing algorithms don't just apply to shipping (Score:5, Interesting)
Something the summariser seems to have missed.. This kind of problem comes up in a lot of different places.
One example would be brain tumor treatment using lasers.
Pack the rubbish too (Score:4, Interesting)
This coffee tastes funny.
UPS already does this, sort of. (Score:4, Interesting)
When I worked for UPS in school, they used manual labor to load the trailers they used to send packages to the next facility. Loaders used their eyes, brains, and some basic tips to pack the trailer as tight as possible while using totally random sized packages. If you did well, you were rewarded; if you didn't, you were...not.
These guys would be well advised to watch how those trailers are loaded to figure out what algorithm the loader is using internally - we could get those trailers packed pretty damned tight.
Tiny packages get lost (Score:3, Interesting)
> Ok the title might be a little ridiculous, but the ridiculous packaging
> used to ship a few tiny objects by some shippers is pretty shameful.
In my experience, the smaller an item is that I carry around, the more likely it is for me to lose it. I think the same thing goes for the USPS. I don't think I'd feel all that great if Amazon tried to ship my new microSD card to me in a package the size of a postage stamp.
Re:Wall-E (Score:5, Interesting)
We're getting there... search for "great pacific garbage patch": http://en.wikipedia.org/wiki/Great_Pacific_Garbage_Patch [wikipedia.org]
Not just for shipping, not just in 3D (Score:5, Interesting)
Sometimes the shapes are square/rectangular, which nest next to each other very well. Generally, they do not. Among other things, I am tasked with figuring out how many shapes we can get out of a sheet of paper. With the irregular shapes, the best method I've found is just to brute force the problem, trying various layouts to see if orienting the shapes one way will get us one or two more shapes out of a sheet. It's not a simple area problem, since some shapes nest very well, and some don't. I do have tricks I've learned to help speed the process, but I'd love to have something like this software, which would take the one-up shape, and tell me how many I can get out of a sheet of paper.
Real life tetris? (Score:4, Interesting)
If you did well, you were rewarded; if you didn't, you were...not.
Sounds almost like a real-life game of tetris. In 3d. ;)
Re:UPS already does this, sort of. (Score:4, Interesting)
You'll find that this is relatively easy and, technically speaking, still quite inefficient.
Packing problems are inherently complex because there's very little you can do but try every arrangement in clever ways. However, basic human packing is nothing more than throwing the stuff in the truck in the order it arrives. A "good" human can fit more because they do things like "biggest objects first", which in comparison is orders of magnitude more efficient. An skilled human packer goes even better and plans for odd-shapes, uses the flexibility/squashiness of various items in order to pack even better (e.g. put your socks in your luggage last because you can pretty much jam them in anywhere, into all the unusual, difficult-to-fill gaps - or put them inside your shoes and wrap your delicate watch in them first!).
However, the skilled human, although MUCH better than the basic human, is nowhere near the most efficient. They're pretty damn good, however, and for 99.999% of cases, I see no reason to spend the extra to work out the "perfect" arrangement, especially given the inaccuracies and other factors involved (is the parcel squishy, where does the algorithm want me to put it, damn I left something out, now I have to repack the computer's way, etc.). You can give any packing solution as a percentage - "there is only 5% wasted space," etc. with the "optimum" settings usually being a percentage too (i.e. the BEST way to do it is with only 2% space given these parcels). You'll never really fill anything *perfectly*, i.e. 0% wastage, without thousands of years waiting around for a parcel of *just* the right shape.
It took us until very recently to prove that the best way to pack 3D spherical objects into a 3D square container is to use a hexagonal configuration - ever looked at the boxes that fruit are packed in? We've been using it for years, and mathematics *knew* it was the right answer but we've only just *proven* it's the best possible solution. In fact, most animal shells and millions of biological, botanical and other natural processes provide similar answers to the packing problems which were developed by trial-and-error and getting close enough to an answer to be useful.
I would estimate, after years of looking into the mathematics of packing problems and similar years of packing rucksacks for Scout troops, Scout troops and equipment into Scout vans, moving house by myself several times in limited amounts of trips (I did a complete three bedroom house full of years of crap into another, smaller, three bedroom house with *more* crap via three ordinary (Mk5 Ford Transit) van loads and two car journeys of miscellaneous stuff like a cat), jamming two months worth of food into a freezer etc. that your "naive" human packer has anywhere between 10-15% wastage. The "good" human would probably bring that to 5-10% and the perfect human between 2-5%. The computer/algorithm running some of the most complex algorithms in the world, in a cut-down model (no squishy parcels!), in a perfect universe probably can get 1-4% depending on the load. Is it worth the extra hassle to get a solution that (potentially, in ideal situations) gets 1% more parcels into every van versus the amount of time it takes to FIND, COMMUNICATE and IMPLEMENT that solution? Almost certainly not. In fact, I wouldn't be surprised that, if Amazon did their own deliveries, they'd load the vans as quick as possible to send them out as quick as possible and get them back just as quick. The costs don't balance.
Also, packing problems with real-world uses have a lot more problems - you might well want to pack the items in a certain order (because then you can get at the items you want without having to drive around town randomly according to what parcels you can get to!), the afore-mentioned "squishiness" issues, knowing what size the parcels are in the first place, awkward internal shapes to vans, getting humans to implement anything approaching a perfect solution ("Look, John, the computer say it goes in that hole and sho
Re:Wall-E (Score:4, Interesting)
I keep hearing about this but has anyone actually seen in? All the videos I see are just generic pollution shots. If there is really a giant island of plastic floating out there lets see some pictures. I am not saying it's not there I just want to see it if it is.
Re:Support Amazon (Score:3, Interesting)
Re:Support Amazon (Score:3, Interesting)
It is just unfortunate that this kind of idea is next to impossible to have done in physical stores. While the idea of a display item doing the advertising and the real product being sold in plain boxes sounds like it would work, it becomes very hard to embellish on your product without outside packing.
I would almost never buy an unpacked product because I would be afraid it would interfere with my warranty, and because otherwise there is literally no way to tell who fucked up a product; the manufacturer, or the unpacker. If the Unpacker were already highly trusted and gave me some kind of fantastic warranty I might consider it for inexpensive items.
Re:Packing algorithms don't just apply to shipping (Score:3, Interesting)
Overhyped False Buzzkill (Score:1, Interesting)
The parent poster is referring to something called the "Rebound Effect" [wikipedia.org].
The occurrence of consumption rebound that is greater than the efficiency gain is extremely rare for any fully used resource.
For a rebound to bounce higher than the efficiency gain, there must be an increase in the market size, which is no longer possible with oil.
In the end more resources are used than before the optimization,
Jevon's Paradox" [wikipedia.org].
Funny how Jevon's paradox ends when the product/process and its place in market sinks.
Re:Wall-E (Score:2, Interesting)
Re:Not necessarily... (Score:3, Interesting)
That just leads to more bureaucracy, filling up D.C. buildings with corpulent bureaucrats stuffing their faces with vending machine hot dogs and farting dangerous greenhouse gases. This will hasten the demise of the planet much faster than an extra UPS trip over other odd week.
Seriously, his is why shipping methodologies need to be left to the market. Shipping companies want to make a profit, and fewer trips at using less fuel adds to their profits. Taxes may also perform the same function, but bureaucrats are incapable of making the economic calculations necessary to target taxes with sufficient precision, because markets are constantly shifting and changing. Go read up on Hayek and economic calculation.
Re:Are algorithms the issue? (Score:3, Interesting)
If it takes an infinite amount of time or processing power (same thing, really) to solve a given problem instance by a given algorithm, then that problem instance is not solvable by said algorithm even in theory, since the algorithm will never return the solution (by definition of infinite).
When we say that a problem is "solvable" (theoretically possible), we mean that there is an algorithm that will return a solution after a finite number of operations for any finite problem instance. If we don't put this constraint on the word "solvable", then for example the Halting Problem becomes trivially solvable: simply run the algorithm to be tested in a "simulation" and return "it halted" if it halts.
Re:Are algorithms the issue? (Score:3, Interesting)
Many companies are taking advantage of better packing (euither by changing their packaging, tweaking their loading method, etc) as a method to cut down on costs. The ability to cram two extra boxes on a truck can often mean selling two extra boxes that you originally couldn't or reducing the shipping costs per order by reducing the amount of leftover head space in a shipping container by stacking more efficiently.
Re:Are algorithms the issue? (Score:1, Interesting)