Slashdot Mirror
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.
Who needs padding anyway? We'll just make more when it is killed in shipping...
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.
Dunno about saving the planet, but I'd hate for us to end up in the situation posited by the movie...
Putting the "anal" back into "analyst"...
Do you think they will sell this onto GM? So when I take the girlfriend shopping the car can explain to me how I am supposed to get it all home.
They fitted George Orwell's coffin with rollers so he could turn over more easily years ago.
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.
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.
I heard a story once, that Amazon use a certain size/shape of box, usually oversized for the product, simply because they can pack in a van more easily and efficiently.
This coffee tastes funny.
Fuck systemd. Fuck Redhat. Fuck Soylent, too. Wait, scratch the last one.
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.
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.
Fortunately, few reach this level of "mastery": http://www.theregister.co.uk/2008/07/18/hp_packaging/
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
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.
I don't read AC A human right
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.
"As God is my witness, I thought turkeys could fly." A. Carlson
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?
Si vis pacem, para bellum! For evil to succeed good men need only do nothing!
> 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.
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.
I knew playing Tetris would pay off someday!
"pr0n": An anagram of "porn," possibly indicating the use of pornography. - www.microsoft.com
My wife recently built a series of stone walls beside our driveway. I often wondered if some program existed that would help figure out where each stone should go so that it all fit tightly together. So now one exists. The next problem is how to get the shapes of all those stones into the program for it to crunch on.
Can we now stack people more efficiently so they take up less space?
Each little widget that gets sold on eBay & sent (to USA, AU or anyplace else) from Hong Kong will still be individually wrapped, tied, labelled & shipped - at EXORBITANT postal cost - to its eBay buyer... nothing saved here.
WOW. Utterly ridiculous.
What especially ticks me off is using non-recyclable plastic or styrofoam in packaging.
Is there really any need to use stuff that _has_ to go to the land fill?
A product-specific comment: 'flash' memory cards have a crazy packaging to product ratio.
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. ;)
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. ;)
I don't read AC A human right
There's lots of tricky optimization problems where better algorithms could make a huge difference. How much fuel do you load on an airplane given that (a) any fuel you have at the end of a flight leg above the margin of safety is useless cargo and (b) fuel has different costs at different airports? It's probably a safe bet that it's always more energy efficient to transport fuel by ground though.
What about optimizing traffic flow through a city by coordinating traffic lights? If you could minimize the total time cars spend idling in traffic, you'd save vast amounts of energy. But you have to take into account how drivers will change their behavior in order to optimize their personal trips.
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.
Post may contain irony: discontinue use if experiencing mood swings, nausea or elevated blood pressure.
Applying elegant algorithms to super-densely pack articles does little to improve the total optimization situation when the articles being packed are themselves optimized for store shelf marketing.
What do you mean they cut the power? How can they cut the power, man? They're animals!
I have noticed that some companies that ship a lot of product have decided to reduce the variety of boxes that they use for shipping, as that makes it easier to buy the boxes and packing material itself. Of course that means that in some cases small objects end up shipped in boxes far, far, larger than needed, but the savings realized by the company that sold the product offsets that cost (both in terms of what they pay for boxes as well as in what they pay people on the line for managing that number of boxes).
Damn_registrars has no butt-hole. Damn_registrars has no use for a butt-hole.
When I buy something smallish, I want them mail it USPS Priority Mail for $4.80 instead of FedEx for $12-15.
Or even when do do send it USPS, I want them to charge me the $4.80 it really cost them to mail it, not $8+.
Nothing like buying $10 worth of small stuff I can't find locally and have the shipping cost more than the merchandise.
And okay, don't forget the packing.
I use to work for a small company producing about 30 machines a month. They in themselves were quite complicated bits of kit with many modular components.
Each component would come in through the door. Be Unpacked mounted and wired and the final machine was repacked and sent out.
The amount of packaging we had to dispose of was insane. As an experiment I stored up the amount of packaging for one of our units that we disposed of and compared it to the amount of packaging that we sent out.
What the end user sees land on the door step isn't half of the total packaging in production.
Save the packets, Save the world!
You can screw with the environment until the whole planet is uninhabitable and the PLANET will still be here. I think we need to concentrate on maintaining an environment that our species can survive in long before we worry about "saving the planet." It will be here long after we've died off.
I must make an aside about that "save the planet" bit: CmdrTaco thinks the title is ridiculous. The article itself uses a much better title, making no reference to "the planet" at all. So I ask, whence came the title? If the editors don't like it and the article doesn't use it then it seems pretty obvious that it should be replaced with a more descriptive one.
I work for a school that is a self maintainer of ibm/lenovo laptops. We order the parts and do the work ourselves. We joke about the massive boxes for little parts all the time. The worst I have seen is a box that was roughly 1'6"x1'6x1' that contained a single CMOS battery. I've also seen large boxes like that with bubble packing and peanuts that contain a little bag of maybe 10 screws.
superman runs linux
Without realising it! I was trying to draw a diagram similar to the one in the article (a mixture of circles of different sizes, within a larger circle).
In my case, it was to represent the sizes of subsets of an isomer space, where each subset shares the same predicted 13C-NMR spectrum.
This makes me feel slightly better about doing so badly at it (using adaptive simulated annealing)
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
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.
Finally had enough. Come see us over at https://soylentnews.org/
Although an island of floating plastic sounds romantically post-apocalyptic it could become reality. For now, the majority of the pollution floats below the surface, and the trauma is caused by tiny pellets ("raw" unprocessed plastic, the foundation of future "disposable" items) that get consumed at the bottom of the food chain and work their way up. Larger plastic items are swallowed by birds, which potentially blocks the stomach or digestive tract. Sadly, with our reliance on un-biodegradable plastics, we can expect "the island" to materialise within our lifetimes.
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."
As an interesting oddity, our local blue-bag recycle programme takes styrofoam for recycling. I have no idea what they do with it, but it's on the list of things to recycle, so we throw all of our packing styrofoam that we get from online orders and what have you in there. We were shocked to find out it was recyclable...
You might be able to combine the above 2 methodologies:
Case-Based Reasoning - Define problem parameters, e.g., number of items, sorted array of item sizes, etc. and use those parameters as indexes into a database of past solutions. You'll have to try various parameters to find which work best. Over time gather a database of successful (problem, solution) pairs.
Genetic Algorithm - Given a new problem, compare it's parameters with those of other (problem, solution) pairs stored in your database. Select one or more "closest matches" and evaluate them to see if they solve the new problem. If they are inadequate use genetic algorithms(GA) to modify the closest matches. Store any new and useful (problem, solution) pairs in the database.
This is convenient because it learns on it's own to some degree but, if the GA won't solve the problem sufficiently after some N generations then a human can intervene, define a solution and store that into the database. So it can learn from humans or from it's own exploration.
are not being used as it is.
How often have I bought a component and had it shipped, and the packaging is about 20 times larger than necessary?
It's not like I'm buying nitroglycerin, damn it.
when it comes to new ideas how to get grant money for allegedly saving humankind.
I expect a whole new era of "stop the climate catastrophe" arguments in all areas of science. The possibilities are endless.
Almost all of the packing peanuts you receive in packages these days is actually made out of corn starch. You can easily dispose of them yourself by dumping a pile in the sink, turning on the water, and watching it all dissolve away. Totally harmless. Of course, there are some companies that still use "real" styrofoam, in which case you need to either toss it (ugh!) or find a recycler that takes it.
It's big enough now that you should be able to make out the free AOL CD packaging piles on Google Earth.
Hasn't Dell also shipped a box full of boxes each containing one carefully padded sheet of paper? Weren't they going to revisit their packaging system?
It makes the packaging used for two WristStrong bracelets from Comedy Central's The Colbert Report seem conservationist by comparison.
Oh, say does that Star-Spangled Banner entwine / The myrtle of Venus with Bacchus's vine?
compact it and burn for winter heating
(no i'm not serious, although I know someone who does this)
If you can't see the value in jet powered ants you should turn in your nerd card. - Dunbal (464142)
The parent poster is referring to something called the "Rebound Effect".
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".
Funny how Jevon's paradox ends when the product/process and its place in market sinks.
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.
Not if we TAX it :)
:)
Okay, just kidding... But when optimizing a process and thus generating heavier resource usage, it'll also have a positive impact on the economy... Nevertheless, if we really want to cut CO2, you need to change your way of life... E.g. consume less, which could undoubtedly be achieved through higher energy taxes
The article describes the algorithm backtracking as some kind of novelty. But it sounds pretty close to simulated annealing.
http://en.wikipedia.org/wiki/Simulated_annealing
If this is a dupe then burn me.
Why don't we just throw all our crap in the outer space? We are already testing shuttles that go out and come back. Why not just put the "garbage bag" on it and tell it to throw the bag out in the space then come back for more? It will most certainly end on some planet in our system. Who knows .. Maybe some bacteria will survive and life may evolve where we wouldn't even think possible.
just a thought ...
mov ax,4c00h
int 21h
Stacking-optimization is one of the reasons I will never trade in my first-generation Scion xB. It dwarfs the cargo capacity to engine size (or MPG) ratio of anything else you could buy. I usually go over the cargo weight capacity before I run out of room.
I will keep rebuilding the engine on this thing until batteries become better, then I will put a 200kW motor the size of a grapefruit on it with a 100kWh battery or something. I love this car. Too bad they screwed it in 2008. The new Cube is ok, but the xB1 is still better.
KLAATU, BORADA, NIh*ahem*
http://www.west-wind.com/Weblog/images/200901/WindowsLiveWriter/NowPackagedwithLessPlastic_10811/LessPlastic_14f7e6d6-733c-43fa-8e96-b2bab474bf81.jpg
It was my impression that packing algorithms are more interesting to chemists and metallurgists than longshoremen and stevedores.
Can you be Even More Awesome?!
> but the ridiculous packaging used to ship a few tiny objects
> by some shippers is pretty shameful.
It's designed to be bulky so you can't slip small things like MP3 players into your pocket easily, and designed to be hard to open to make it hard to open it in the store and slip it into your pocket easily.
That's the rationale behind those hated hard-to-open packs.
And bigger items, like electronics for shipping, need good industrial packing to prevent damage. Yeah you could jam a bunch of radios all next to each other, then pack 'em for sale after getting here, but that's not gonna prevent them from being damaged as they sail across the ocean.
(-1: Post disagrees with my already-settled worldview) is not a valid mod option.
Buy Nothing Day
you had me at #!
Schumacher Society briefings
you had me at #!
Hewlett Packtards
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.
HP Shatters Excessive Packaging World Record
'Nuf said.
An algorithm may be useful to get the last bit of space but an even better idea is for the manufacturers and shippers to use a little more common sense.
I ordered an item that was shipped by Amazon that came in 2 ft x 1 ft x 1 ft box. The item was a box that was about 8 in x 6 in x 6 in. That second packaging contained the actual product which was the size of a double CD case.
I know that some of this "over boxing" is to reduce costs by reducing the number and types of different boxes to ship in but it get's ridiculous.
They definitely did better than my attempt. I guess I wasn't thinking outside the circle enough.
Follow me
"Schneider and colleagues' algorithm allows for occasional reverse steps that can unlock better solutions" ... "The algorithm uses backward moves often at the start of a packing process but they become less frequent as it closes in on the final solution"
That could describe just about every packing algorithm ever tried, ever. Can't we get a well-written article that actually says why it's different?
Music speeds up when you yawn, but does not change pitch.
Seems to me like a deep tetris analysis is in order.
Of course I haven't RTFA but suspect this is a knapsack type problem which is NP-hard. That is a computer actually has to try all the permutations to find the solution whereas humans can usually arrive at a solution much more quickly by some kind of intuitive process that cannot be captured in software.
I worked for a bus company which ran a number of charter like routes. My boss asked me to write a program to find the most efficient way of moving groups from A to B via C etc. I never achieved the same efficiencies as the human planner the program replaced (he had left by the way).
The basic lesson is, solve the Napsack problem and the world, including DHL, UPS, FedEx will make you a millionaire.
The military teaches you how to fit 10 pounds of crap in a 5-pound bag. You simply would NOT believe what you can fit into a duffel bag until you see a sailor/airman/marine/soldier unpack it.
For myself, I managed to pack enough clothing for 2 weeks, Christmas gifts for 5 people, snacks and goodies from Hawai'i, Japan and the Middle East, 100 linked rounds of spent .50 cal, and 50 linked rounds of spent 25mm chaingun ammo.
Needless to say, this was before 9/11.
[End Of Line]
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?
There are no karma whores, only moderation johns
Polystyrene/Styrofoam can be recycled into napalm-B.
Thank you, Edward Snowden.
"Arguments from authority are worthless." —Carl Sagan
This really is not a new idea. I work for a company that has been providing very similar algorithms and calculations to industry for 20 years. Take a look: www.topseng.com
A lot of posters are talking about packaging, as in paper, bubblewrap, cardboard. But this article is about a classic mathematics and computer science problem called the 2-D rectangle packing problem.
"The Clay Mathematics Institute million-dollars prize and a huge amount of dedicated research with no substantial results suggest that the problem is difficult."
Here's a link with some more information: P=NP
How many more years will slashdot have an off-by-one error on your Score in your profile?