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

Or course we should pack things tightly...

[Ferzerp]

Who needs padding anyway? We'll just make more when it is killed in shipping...

Re:Or course we should pack things tightly...

[larpon]

T        h        i        s
c        o        m        m        e        n        t
i        s
n        o        t
s        a        v        i        n        g
t        h        e
p        l        a        n        e        t

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.

Re:Packing algorithms don't just apply to shipping

[swahebrumaf]

Something the summariser seems to have missed.. This kind of problem comes up in a lot of different places.

Another thing that is forgotten... When a process can be optimized, it normally results in price-cuts which result in heavier use of the process. In the end more resources are used than before the optimization, opposite to the original intent.

Are algorithms the issue?

[Anonymous Coward]

I find the development of new algorithms interesting in itself, and I suspect that superior packing algorithms will have a number of interesting applications; but I wonder if they'll actually have much effect on shippers in the nearish term.

A great deal of heterogenous object packing is done by humans, since the scale required to make packing assorted objects by machine is quite large(even places with automated warehouses often have a human do the packing at the end; because humans are really quite versatile object manipulators), and humans are actually pretty good at object packing. Not perfect; but quite good.

I'd suspect that inefficient packing has less to do with packing being hard, and more to do with the desire to standardize on a limited number of box sizes, to ease inventory management, which is a quite different problem.

Re:Are algorithms the issue?

[Chris Mattern]

Its not "practically impossible" to find the best solution. It is quite possible. The issue is that finding the optimal solution takes O(2^n), where n is the number of objects to be packed. So, for any large value of n, the calculation will take a prohibitively long time, but it will terminate.

So they're not practical to solve--in other words, practically impossible.

This is in contrast to undecidable problems, which really are "practically impossible" to solve.

That would be a case of *literally* impossible to solve. Which means that they're practically impossible as well, of course.

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.

Obvious

[JPLemme]

Does HP really need an algorithm to tell them not to ship fifteen single sheets of paper in fifteen 9"x12"x2" cardboard boxes?

They need an algorithm that prevents them from hiring dummies in their shipping department.

Support Amazon

[Anonymous Coward]

I know many of you despise Amazon due to the one-click fiasco (and with good reason). But packing/packaging are one area where they're trying to get things right. When possible, order items that are packed using "frustration-free" packaging.

Re:Support Amazon

[Daravon]

Online retailers offering this service only makes sense. With items sitting in a warehouse and never being viewed by the customer prior to purchase, there isn't a need for fancy packaging that shows off the product and tries to prevent theft.

I know when I bought gifts for people (or their kids), they found it a great relief that they didn't have to spend time chopping through a clamshell and cutting/unwinding wire ties in a dozen different places just to get the product out of the packaging.

The fact that it saves on the amount of trash generated by the packaging for the product is icing on the cake!

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.

ElReg:HP shatters excessive packaging world record

[D4C5CE]

Fortunately, few reach this level of "mastery": http://www.theregister.co.uk/2008/07/18/hp_packaging/

UPS is a Great Example of How Algorithms Help

[joelsherrill]

UPS has gotten itself a lot of press over the years about how it has saved fuel, time, and money with its routing algorithms. There was recently an article in Information Week about some of their technology. It is amazing how even a small improvement can save big money AND positively impact the environment. Routing improvements save time and money. Better vehicle maintenance plans. Less idling. This is the printable article. It has a session Id so I don't know if it will survive. http://www.informationweek.com/shared /printableArticle.jhtml;jsessionid=34SPUBGP0QJA2QSNDLRSKHSCJUNN2JVN?articleID=212900815 This is the link with ads. http://www.informationweek.com/story/showArticle.jhtml?articleID=212900815

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.

Re:Wall-E

[Joce640k]

Video: http://www.youtube.com/watch?v=tnUjTHB1lvM

Shipping Pillows

[RManning]

I got married last year and we registered for a lot of stuff from Crate & Barrel. Everything came packed in a ridiculous amount of packaging, but my favorite was the pillows. Each of the four pillows we got came double-wrapped in bubble paper! I guess they weren't broken when we got them, so it must have worked. ;)

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.

Save the planet

[L4t3r4lu5]

If you really want to help cut the costs of shipping, stop importing water from the other side of the planet when the stuff that comes out of your tap is perfectly drinkable.

Re:post apocolypitca romantica

[Dallas Caley]

Sad or not, i hope it happens fast because as soon as there is enough garbage that i can stand on it, i'm claiming it as my own nation. "I claim this floating island of crap in the name of Garbageland! All hail for i am the king of Garbageland!"

Re:Amazon

[PPalmgren]

Beleive it or not, overseas shipping containers are typically smaller than domestic shipping containers. Why? Cell guides on ships make it more efficient to use as few sizes as possible as to never have empty slots on the ships due to size issues. Also, the prongs on the tophandlers & cranes are positioned at set points, and making the containers longer requires costly structural improvements that outweigh the benefits. Most trucks you see on roads are 53' where ships typically carry 20's and 40's, with a few 45's. Keep in mind this may be different in areas near the coasts or denser countries (I'm in the US).

Also, overseas shipping containers are much much heavier than domestic ones because they have to be picked up from the top & withstand constant movement and stacking, where domestics are on a truck 99% of the time and are designed to never be lifted. As info, all of the grocry store & wall-mart containers you see with the big pretty advertisements on the side never go overseas, they are loaded at distribution centers near the coast that receive the shipping containers. The steel-ribbed ugly containers are the ones that go overseas.

Yes, there are inneficiencies to standardized shipping, but it removes more inefficiencies than it creates. Thats how the costs go down.