Packing Algorithms May Save the Planet

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.

Comments

Packing algorithms don't just apply to shipping

[Fungii]

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

[oldhack]

Pack the rubbish in the garbage dumps to allow air to flow through them. It will expedite, no, actually allow, biodegradation (sp?) by allowing the bacteria to live and do its work - biodegradable materials will actually mean something then.

This coffee tastes funny.

UPS already does this, sort of.

[R2.0]

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.

Re:UPS already does this, sort of.

[ledow]

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

Tiny packages get lost

[Mathinker]

> 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

[Joce640k]

We're getting there... search for "great pacific garbage patch": http://en.wikipedia.org/wiki/Great_Pacific_Garbage_Patch

Not just for shipping, not just in 3D

[veganboyjosh]

I work for a company that produces paper products. A large part of what we do is die cut the sheets into different shapes. We charge our customers for these shapes according to how many we get out of a sheet.

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?

[Firethorn]

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:Wall-E

[FooGoo]

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.