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

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

[twistedsymphony]

Seriously I find that poor packing of expensive items occurs far more frequently than tiny items in massive boxes.

Consider the $90 Limited Edition video game in the metal case that gets thrown in either a padded bag or a mostly empty box with a few sheet of advertising flash and a partially-inflated bag. By the time it reaches my hands it's a goddamn miracle if it doesn't have any dents or scratches.

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

[Eudial]

aaceeeghhiiilmmnnnnoopssstttttv

There, I saved the planet for you.

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.

Re:Packing algorithms don't just apply to shipping

[tixxit]

On top of this, they seem to miss the fact that there has been a great deal of research in this field, and there are several very good approximate algorithms. The problem is that packing a box is an NP-Complete problem. So, unless NP=P, we aren't going to find a fast, deterministic and exact, packing algorithm any time soon.

Re:Packing algorithms don't just apply to shipping

[Anonymous Coward]

This idea has been around since the 80s. Had a prof who had these sorts of algs done and written (smart dude).

What he found was YES you can geometrically pack everything perfectly to have the optimal load. There was a HEAVY cost and not in computing terms. The cost was getting people to pack it like that. Think crazy 3d jigsaw puzzle.

Truck dudes do not want to spend 8 hours loading a truck. They want it done in minutes. To load a truck means you either have to have a loader whos job it is to do this. Or have the driver do it. This job then needs to be done on both ends.

Many times they show up and the load is not even ready. Much less packed up.

Also many of these dudes do not run a 'full' load. They keep extra space to run extra when the need arises (which it does a lot). So do you repack when the new package shows up? Oh the one you need for stop 10 is buried bellow stop 9 and 8 and you skipped those because the schedule is screwed up again and those are not ready for you as you have been telling the dispatcher for 2 weeks now.

This works in the simplest of cases. Large FULL load from point A to point B. No extra stops.

Also keep in mind many of these companies have been doing this for YEARS. They have a 'natural' 'homegrown' idea how to do this.

Many times the extra 'time' for a package is not because of lack of containers of space to move things. It is from things like 3 of my loaders did not show up today and I just had 5 trucks all show up at the same time. Where I could normally handle it. Now 1-3 trucks will have to wait.

There is probably another thing they do not take into account is weight. Sure that cube fits PERFECTLY right there. But it needs to be as low in the load as you can get it or it will dump the trailer over.

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?

[skeeto]

This sounds a lot like the knapsack problem, which is NP-hard. It's easy to find a good solution, but practically impossible to find the best solution.

Re:Are algorithms the issue?

[quanticle]

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.

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

Re:Are algorithms the issue?

[brindleboar]

I guess it all depends on your definition of "practically"; is something that takes "a prohibitively long time" really practical?

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.

Re:Are algorithms the issue?

[bar-agent]

practically impossible...impractical...solvable...economically impractical...practically possible...theoretically possible...computationally infeasable

I'm lost in a maze of small twisting phrases, all exactly alike!

Re:Are algorithms the issue?

[ultranova]

If there is an algorithm that can describe a solution, then it's "solvable" (theoretically possible), but if it takes an infinite amount of time or an infinite amount of processing power, then it's not "practically possible".

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?

[Tarwn]

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.

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.

Re:Support Amazon

[fuzzyfuzzyfungus]

Once there is a sufficient volume of "web/warehouse" packaging floating around, retailers might consider using the model adopted by most video rental places, with a limited number of display models, in retail packaging, and a large number of generically packaged products ready on demand.

Re:Support Amazon

[drinkypoo]

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:Support Amazon

[fractalVisionz]

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.

The products come from the manufacturer in a less packed box--meaning less twistys, blister packing, plastic bags, etc. There is no unpacker involved anywhere in the scheme. The box is also optimized to be shipped individually more so than the standard box, and will actually provide better protection for the customer.

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

Dell/HP could pay attention...

[Firethorn]

Then again, some (un)common sense in their shipping divisions of various companies would help.
Dell Batteries
HP
Newegg

Still, the disc thing is probably more for packing shipping containers from China - the extra control and distance being shipped makes packing efficienty easier and more economical than discovering a way to pack random UPS trucks better.

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

Saving on delivery or pickup.

[JohnnyGTO]

Why don't we place our trash cans and mail boxes all on one side of the road rather then make the truck pickup on both side (2 trips). Of course there are roads this would not work on but really why do I need to hear the stupid trash truck twice, at 4:30 am and again at 4:53?

Re:Saving on delivery or pickup.

[Anonymous Coward]

You assume everybody has the same type of garbage pickup as you do. In some places, an actual man hangs on the back of the truck and goes from one side of the street to the other collecting the garbage and tipping it into the scoop. One trip down the street. And then some places have letter carriers deliver mail ON FOOT going from one house to another. Yes, things are done differently than what you are familiar with.

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:Not just for shipping, not just in 3D

[Anonymous Coward]

I'm working with 2D stock cutter from astrokettle (http://www.astrokettle.com/pr2dlp.html) and they have some very impressive algo to get the best out of you piece of you sheet. Give it a try.

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:Real life tetris?

[HTH NE1]

Sounds almost like a real-life game of tetris. In 3d. ;)

Who says videogames don't teach useful skills.

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.

George said it best...

[geminidomino]

We're so self-important. So self-important. Everybody's going to save something now. "Save the trees, save the bees, save the whales, save those snails." And the greatest arrogance of all: save the planet. What? Are these fucking people kidding me? Save the planet, we don't even know how to take care of ourselves yet. We haven't learned how to care for one another, we're gonna save the fucking planet?

I'm getting tired of that shit. Tired of that shit. I'm tired of fucking Earth Day, I'm tired of these self-righteous environmentalists, these white, bourgeois liberals who think the only thing wrong with this country is there aren't enough bicycle paths. People trying to make the world safe for their Volvos. Besides, environmentalists don't give a shit about the planet. They don't care about the planet. Not in the abstract they don't. Not in the abstract they don't. You know what they're interested in? A clean place to live. Their own habitat. They're worried that some day in the future, they might be personally inconvenienced. Narrow, unenlightened self-interest doesn't impress me.

Besides, there is nothing wrong with the planet. Nothing wrong with the planet. The planet is fine. The PEOPLE are fucked. Difference. Difference. The planet is fine. Compared to the people, the planet is doing great. Been here four and a half billion years. Did you ever think about the arithmetic? The planet has been here four and a half billion years. We've been here, what, a hundred thousand? Maybe two hundred thousand? And we've only been engaged in heavy industry for a little over two hundred years. Two hundred years versus four and a half billion. And we have the CONCEIT to think that somehow we're a threat? That somehow we're gonna put in jeopardy this beautiful little blue-green ball that's just a-floatin' around the sun?

The planet has been through a lot worse than us. Been through all kinds of things worse than us. Been through earthquakes, volcanoes, plate tectonics, continental drift, solar flares, sun spots, magnetic storms, the magnetic reversal of the poles...hundreds of thousands of years of bombardment by comets and asteroids and meteors, worlwide floods, tidal waves, worldwide fires, erosion, cosmic rays, recurring ice ages...And we think some plastic bags, and some aluminum cans are going to make a difference? The planet...the planet...the planet isn't going anywhere. WE ARE!

We're going away. Pack your shit, folks. We're going away. And we won't leave much of a trace, either. Thank God for that. Maybe a little styrofoam. Maybe. A little styrofoam. The planet'll be here and we'll be long gone. Just another failed mutation. Just another closed-end biological mistake. An evolutionary cul-de-sac. The planet'll shake us off like a bad case of fleas. A surface nuisance. --George Carlin

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.

Jevons Paradox, anyone?

[Vryl]

http://en.wikipedia.org/wiki/Jevons_paradox

"In economics, the Jevons Paradox (sometimes called the Jevons effect) is the proposition that technological progress that increases the efficiency with which a resource is used, tends to increase (rather than decrease) the rate of consumption of that resource."

Re:Wall-E

[ColdWetDog]

From the Wikipedia article:

Despite Charles Moore's description, the eastern garbage patch cannot be characterised as a continuous visible field of densely floating marine debris. The process of disintegration means that the plastic particulate in much of the affected region may be too small to be seen. Researchers must estimate the overall extent and density of plastic pollution in the EGP by taking samples. In a 2001 study, researchers (including Moore) found that in certain areas of the patch, concentrations of plastic reached one million particles per square mile.[8] The study found concentrations of plastics at 3.34 pieces with a mean mass of 5.1 milligrams per square meter. In many areas of the affected region, the overall concentration of plastics was greater than the concentration of zooplankton by a factor of seven. Samples collected at deeper points in the water column found much lower levels of plastic debris (primarily monofilament fishing line), confirming earlier observations that most plastic waste concentrates in the upper parts of the water column.

So you won't see it on an aerial photo of the area, but you will definitely notice it if you sail through it.

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:post apocolypitca romantica

[fuzzyfuzzyfungus]

Who runs bartertown?

Re:Wall-E

[sFurbo]

Brian Dunning from Skeptoid says no... He is usually well researched. And funny.

Re:Not necessarily...

[Brandybuck]

E.g. consume less, which could undoubtedly be achieved through higher energy taxes :)

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:post apocolypitca romantica

[cerberusss]

as soon as there is enough garbage that i can stand on it, i'm claiming it as my own nation.

As soon as you claim it, I'd like to start a datacenter on there. I'd rent out dedicated boxes and install my custom Linux distribution on it, calling it Garbix.

(Please don't mod me troll, I'm actually a Linux fan! Really!)

Re:Oh, sure.

[exi1ed0ne]

The idea that energy prices should be kept high, through a carbon tax, is intended to harness the market's ability to provide approximations of optimal solutions to resource distribution problems by internalizing the environmental costs of energy use.

Bah, you don't need a tax for that. All that need to happen is to stop subsidizing security in the Middle East.

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.

Re:Amazon

[gbjbaanb]

You might be interested in "the box", a continuing BBC report of the life of a shipping container.

How does this save the planet?

[The Clockwork Troll]

Even naive packing algorithms such as "first-fit" have been shown to be relatively close to optimal.

If naive packing algorithms waste at most 30% of space (i.e. a constant coefficient), but the population (and our associated resource consumption) is growing at least geometrically if not exponentially, then one must show that more efficient packing is at least a catalyst for some other kind of supralinear reduction in resource consumption (or other benefit) for the premise of "saving the planet" to be plausible.

By all means, someone can correct my simplistic thinking?