Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Packing Algorithms May Save the Planet

CmdrTaco posted more than 5 years ago | from the that-might-be-an-overstatement dept.

Math 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.

Sorry! There are no comments related to the filter you selected.

Or course we should pack things tightly... (3, Insightful)

Ferzerp (83619) | more than 5 years ago | (#27120233)

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

Re:Or course we should pack things tightly... (-1, Offtopic)

Anonymous Coward | more than 5 years ago | (#27120481)

(note: this reply was only about the summary comment complaining about wasted space in packing, not the study itself)

Re:Or course we should pack things tightly... (1)

macraig (621737) | more than 5 years ago | (#27121337)

Tell that to the Samsonite Gorillas who shipped and handled my bag of tortilla chips before I got them home! If I had wanted tortilla BITS then I'd have looked for a product labelled as tortilla bits.

Re:Or course we should pack things tightly... (5, Funny)

larpon (974081) | more than 5 years ago | (#27122001)

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... (2, Insightful)

twistedsymphony (956982) | more than 5 years ago | (#27122057)

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.

Wall-E (1)

jeffshoaf (611794) | more than 5 years ago | (#27120269)

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...

Re:Wall-E (5, Interesting)

Joce640k (829181) | more than 5 years ago | (#27120519)

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

Re:Wall-E (3, Interesting)

FooGoo (98336) | more than 5 years ago | (#27120897)

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.

post apocolypitca romantica (0)

Anonymous Coward | more than 5 years ago | (#27121207)

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.

Re:post apocolypitca romantica (5, Funny)

Dallas Caley (1262692) | more than 5 years ago | (#27121757)

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:Wall-E (2, Informative)

ColdWetDog (752185) | more than 5 years ago | (#27121321)

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.

Google Earth (1)

VShael (62735) | more than 5 years ago | (#27121885)

It's big enough now that you should be able to make out the free AOL CD packaging piles on Google Earth.

Ridiculous Titles May Save the Planet (0)

Anonymous Coward | more than 5 years ago | (#27120925)

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.

Girlfriend (0)

Ragein (901507) | more than 5 years ago | (#27120271)

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.

Re:Girlfriend (-1, Offtopic)

Anonymous Coward | more than 5 years ago | (#27120363)

boo hoo mr moneybags with his car and his girlfriend has so many problems, you tactless piece of shit i was once raped by a bag of used tins of baked beans last time i walked to the supermarket alone, i am very stoned and this is the reason for this post

Re:Girlfriend (0)

Anonymous Coward | more than 5 years ago | (#27120863)

Is this what constitutes as humour on Slashdot nowadsys

Packing algorithms don't just apply to shipping (4, Interesting)

Fungii (153063) | more than 5 years ago | (#27120275)

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 (-1, Troll)

Anonymous Coward | more than 5 years ago | (#27120461)

another use is when packing fudge. I know a lot of slashdotters like to have gay sex in airports, truck stops, bars, barney frank's house, etc. This could help optimize that.

Re:Packing algorithms don't just apply to shipping (-1, Troll)

Profane MuthaFucka (574406) | more than 5 years ago | (#27121043)

Facking Pudge what?

Re:Packing algorithms don't just apply to shipping (5, Insightful)

swahebrumaf (1452693) | more than 5 years ago | (#27120555)

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 (1, Funny)

Anonymous Coward | more than 5 years ago | (#27120635)

inb4 broken window

Re:Packing algorithms don't just apply to shipping (0)

Anonymous Coward | more than 5 years ago | (#27121057)

I'm not sure that is the original intent.

The intent is to use less resources per dollar of value produced, or per dollar of profit.

Profit and production of economic value is fine and well as long as it does not serve to push any ecological system towards an unforseen and catastrophic collapse, a risk that our current markets (and governments for that sake) cannot evaluate properly.

It seems I was trying to solve this same problem (1)

gilleain (1310105) | more than 5 years ago | (#27120997)

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)

Re:Packing algorithms don't just apply to shipping (2, Interesting)

tixxit (1107127) | more than 5 years ago | (#27121871)

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.

Are algorithms the issue? (5, Insightful)

Anonymous Coward | more than 5 years ago | (#27120277)

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? (2, Insightful)

skeeto (1138903) | more than 5 years ago | (#27120755)

This sounds a lot like the knapsack problem [wikipedia.org] , 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? (2, Informative)

quanticle (843097) | more than 5 years ago | (#27120969)

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 [wikipedia.org] , which really are "practically impossible" to solve.

Re:Are algorithms the issue? (2, Insightful)

brindleboar (1154019) | more than 5 years ago | (#27121061)

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? (5, Insightful)

Chris Mattern (191822) | more than 5 years ago | (#27121091)

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? (1)

quanticle (843097) | more than 5 years ago | (#27121651)

The issue with "practically impossible" is that the definition of such changes every year, as computers grow more and more powerful.

Re:Are algorithms the issue? (1)

skeeto (1138903) | more than 5 years ago | (#27121221)

So, for any large value of n, the calculation will take a prohibitively long time

That's exactly what I meant when I used the modifier "practically": for a large n, even if we used all the resources currently available to mankind, it would be impossible to find a solution within the amount of time that a solution would be useful.

So, it wouldn't be practical. I.e. it can't be practiced. Practically impossible. QED. ;-)

Re:Are algorithms the issue? (0)

Anonymous Coward | more than 5 years ago | (#27121753)

Don't fall into the trap that NP-hard problems are impractical to solve. In practice the knapsack problem can be easily solved in O(nW) time, where n is the number of different items and W is the weight constraint (expressed as a multiple of the greatest common divisor of the item weights). This is also noted on the wikipedia page.

Re:Are algorithms the issue? (0)

Anonymous Coward | more than 5 years ago | (#27121177)

Packing problems are one of the basic types of NP-hard problems thought in an undergrad cs curriculum. Since "the packaging problem" is not purely a CS problem, any optimal algorithm is not likely to influence the amount of garbage in the end.

Amazon (1)

celardore (844933) | more than 5 years ago | (#27120281)

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.

Re:Amazon (1)

Phasma Felis (582975) | more than 5 years ago | (#27120341)

Just about everyone does this, yeah. You have to if you want your business to be competitive. That's what this research is aimed at addressing.

Re:Amazon (1)

gbjbaanb (229885) | more than 5 years ago | (#27120875)

Yes, a lot of suppliers use standard shipping containers (including the big shipping containers that slot onto ships, that revolutionised shipping from the old 'anything in a bag' that dock workers used to load by hand to allowing fully automated systems to be used instead)

However, whilst its great for the common case, it falls over on the edge cases [thedailywtf.com] !

Oxymoron of the day: conservative conservationist (1)

HTH NE1 (675604) | more than 5 years ago | (#27122063)

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.

Pack the rubbish too (4, Interesting)

oldhack (1037484) | more than 5 years ago | (#27120299)

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.

Re:Pack the rubbish too (0)

Anonymous Coward | more than 5 years ago | (#27120411)

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

Obvious (4, Insightful)

JPLemme (106723) | more than 5 years ago | (#27120333)

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.

Re:Obvious (1)

whyloginwhysubscribe (993688) | more than 5 years ago | (#27120531)

I guess it could help to even further shrink the size of electronic components - but I would be impressed to see them fit more into my mobile phone which is tiny!

Re:Obvious (1)

morgan_greywolf (835522) | more than 5 years ago | (#27120739)

Bought some HP photo paper later, huh? ;)

No, seriously, far too many things already use egregious amounts of packaging material, much of it ostensibly used for 'security' purposes.

Go buy a USB thumb drive and see what kind of package it comes in.

Re:Obvious (0)

Anonymous Coward | more than 5 years ago | (#27121327)

Bought some HP photo paper later, huh? ;)

I think the grandparent posters statement:

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

may be a case in which HP did something like separately package EULA or Site Licenses individually for shipping in boxes with padding when common sense would dictate to stack them, put a paperclip on them and shove them in a manilla envelope like a sensible person would. I don't recall if it was actually HP but I do recall seeing this incident on slashdot some time ago, whether as an article in its own right or as someone's post.

No, seriously, far too many things already use egregious amounts of packaging material, much of it ostensibly used for 'security' purposes.

Go buy a USB thumb drive and see what kind of package it comes in.

A lot of the stuff for security purposes actually is for security purposes when items are sold retail. Amazing what shoplifters will take when it isn't securely packed. I imagine that if you had thumb drives in flimsy packaging within reach of the public by the end of a couple of days you'd have nothing left but flimsy packaging and no thumb rives left.

Re:Obvious (1)

Captain Spam (66120) | more than 5 years ago | (#27121385)

Go buy a USB thumb drive and see what kind of package it comes in.

Not to lessen the impact of that statement (which, for almost all cases, is true), but the last time I was at a Micro Center, they had bulk thumb drives and SD cards stocked at the cash registers the same way grocery stores would stock impulse buys. No packing*, no fuss; just a small box of media. Ah, the bliss of Micro Center...

Shame, of course, that's only one case.

*: Well, okay, grocery stores usually stock impulse buys with packaging, yes...

Re:Obvious (1)

drinkypoo (153816) | more than 5 years ago | (#27121133)

HP is running on pure incompetence these days [slashdot.org] . It's like running a diesel on water - sure, it works for a little while, but it damages your rings and cylinders, and it removes the heat needed for combustion quite quickly. When HP sent me a little baggie of trackpoint covers, they sent it to me in a cardboard box big enough to send DIMMs or a small expansion card. I've had HP send me two boxes to ship back one laptop... HP's problem isn't needing computer software to pack more efficiently, it's hiring employees who care enough to pack efficiently. I think they also have some completely retarded process in place, explaining why they send you essentially undamageable parts in padded cardboard boxes.

Support Amazon (5, Informative)

Anonymous Coward | more than 5 years ago | (#27120337)

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. [amazon.com]

Re:Support Amazon (3, Insightful)

Daravon (848487) | more than 5 years ago | (#27120941)

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 (2, Interesting)

fuzzyfuzzyfungus (1223518) | more than 5 years ago | (#27121051)

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 (2, Interesting)

drinkypoo (153816) | more than 5 years ago | (#27121755)

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 (2, Insightful)

fractalVisionz (989785) | more than 5 years ago | (#27122039)

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.

Re:Support Amazon (1)

HTH NE1 (675604) | more than 5 years ago | (#27122173)

and cutting/unwinding wire ties in a dozen different places

Well, one thing you can do with those plastic-coated wire-ties is bend them into an oversized paper-clip shape. Add a pair of small googly eyes and you have your very own Clippy Action Figure (whom you can then torture in so many ways).

ElReg:HP shatters excessive packaging world record (4, Funny)

D4C5CE (578304) | more than 5 years ago | (#27120349)

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

Re:ElReg:HP shatters excessive packaging world rec (1)

whereiswaldo (459052) | more than 5 years ago | (#27120647)

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.

Re:ElReg:HP shatters excessive packaging world rec (1)

Tanktalus (794810) | more than 5 years ago | (#27121377)

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...

Re:ElReg:HP shatters excessive packaging world rec (0)

Anonymous Coward | more than 5 years ago | (#27121855)

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.

UPS is a Great Example of How Algorithms Help (5, Informative)

joelsherrill (132624) | more than 5 years ago | (#27120377)

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 [informationweek.com] /printableArticle.jhtml;jsessionid=34SPUBGP0QJA2QSNDLRSKHSCJUNN2JVN?articleID=212900815 This is the link with ads. http://www.informationweek.com/story/showArticle.jhtml?articleID=212900815 [informationweek.com]

Re:UPS is a Great Example of How Algorithms Help (0, Flamebait)

russotto (537200) | more than 5 years ago | (#27120653)

UPS's packing algorithms, on the other hand, leave a lot to be desired. Mostly they are optimized to provide the most opportunity for damage. For instance, cheap, heavy items will always be loaded on top of expensive, fragile, light items. Also UPS does its box burst testing in production, giving new meaning to the phrase "drop ship".

Dell/HP could pay attention... (2, Funny)

Firethorn (177587) | more than 5 years ago | (#27120393)

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

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. (4, Interesting)

R2.0 (532027) | more than 5 years ago | (#27120439)

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. (0)

Anonymous Coward | more than 5 years ago | (#27120629)

It seems that it would be beneficial to pack them not only based on size/shape but by weight as well. This would minimize stress on the vehicle, thereby reducing wear and tear. Probably would also increase fuel efficiency.

Real life tetris? (3, Interesting)

Firethorn (177587) | more than 5 years ago | (#27120657)

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? (1)

Deltaspectre (796409) | more than 5 years ago | (#27121185)

No!!! Don't put that box there!

Great, now we'll have to start over

Re:UPS already does this, sort of. (3, Interesting)

ledow (319597) | more than 5 years ago | (#27120889)

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 should fit."), taking into account things like being able to remove a parcel without killing yourself under a pile of heavier parcels, packing fragile items more loosely and with softer items around them (the most efficient packing might well have that fragile parcel inserted between two slabs of lead in other parcels... first bump = squish!), etc.

Can mathematics design a nice, slightly more efficient box for a certain combination of items? Certainly. Is it worth doing that over some bog-standard, mass-produced square crates holding the same? Probably not. If the maths *could* be that much more efficient, could it take account of the million and one factors required? Almost certainly not, because a lot of them take so long to describe mathematically that it could take you longer than the product lasts in order to arrive to describe the problem, let alone find a solution.

Re:UPS already does this, sort of. (0)

Anonymous Coward | more than 5 years ago | (#27121153)

In a warehouse, though, humans learn some solutions that are more close to perfect than you would have (maybe than is possible) moving. I worked a few summers in a warehouse in college, and you pretty quickly get a feel for which boxes fit evenly 5 or 7 or 10 to a layer on a shipping pallet, so some parts of the packing do have a simple and perfect solution. Others are, as you said, best guess stacking. I don't know if the good people are much better at saving space, but the guys who were really fast were 2-3x as fast as the slow guys, even with everyone paid by productivity rate.

Re:UPS already does this, sort of. (1)

drinkypoo (153816) | more than 5 years ago | (#27121617)

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.

When my friend Adam Croston (well, he was my friend until he stole some of my shit and moved away) worked for UPS they used to build a small wall of packages in the back of the truck, then throw boxes over it until the truck was full.

Saving on delivery or pickup. (2, Insightful)

JohnnyGTO (102952) | more than 5 years ago | (#27120453)

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. (0)

Anonymous Coward | more than 5 years ago | (#27120489)

Worse than just that... Have you seen garbage pickup on a multi-lane one-way street? Not only do you need two trucks (one of them left-hand drive, one of them right-hand drive) but they have to go down the street the same way twice.

Crazy...

Re:Saving on delivery or pickup. (2, Insightful)

Anonymous Coward | more than 5 years ago | (#27120661)

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.

Re:Saving on delivery or pickup. (1)

lazyforker (957705) | more than 5 years ago | (#27121847)

Maybe they drive down one side on the way out; and on the other on the way back. Maybe it's quicker than idling their truck while people try to run across the street dragging cans with them.

It's possible that the operators have already arrived at the most efficient method to service their route. Why don't you ask them one morning?

Re:Saving on delivery or pickup. (1)

entgod (998805) | more than 5 years ago | (#27121873)

That's how the mailboxes in Finland are positioned. Would be cool if they did it for garbage too.

Tiny packages get lost (3, Interesting)

Mathinker (909784) | more than 5 years ago | (#27120515)

> 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:Tiny packages get lost (1)

westlake (615356) | more than 5 years ago | (#27121135)

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.

You'd feel worse if it was a microscopic sample of the Ebola virus that went astray.

A package can't be so small that it will - quite literally - slip through the cracks. It can't be smaller than the human and machine readable labels it must carry.

Not just for shipping, not just in 3D (4, Interesting)

veganboyjosh (896761) | more than 5 years ago | (#27120523)

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 (2, Informative)

Anonymous Coward | more than 5 years ago | (#27120759)

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

Anonymous Coward | more than 5 years ago | (#27121453)

Look into clothing manufacture. They solve this problem for cutting cloth into unusual shapes. The big manufacturers most definitely use computer-controlled cutting tools and have put serious money into algorithm research.

Case-Based Reasoning + Genetic Algorithm (1)

littlewink (996298) | more than 5 years ago | (#27121629)

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.

I've been working on this for years! (1)

imadoofus (233751) | more than 5 years ago | (#27120535)

I knew playing Tetris would pay off someday!

Building Stone Walls (1)

methano (519830) | more than 5 years ago | (#27120553)

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.

Stacking (1)

nicklott (533496) | more than 5 years ago | (#27120581)

Can we now stack people more efficiently so they take up less space?

Re:Stacking (0)

Anonymous Coward | more than 5 years ago | (#27121117)

Thats why cubicles exist!

Won't help bring in the eBay stuff from China & (0)

Anonymous Coward | more than 5 years ago | (#27120607)

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.

Shipping Pillows (5, Funny)

RManning (544016) | more than 5 years ago | (#27120655)

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. ;)

Oh, sure. (1)

hey! (33014) | more than 5 years ago | (#27120663)

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.

Re:Oh, sure. (1)

PMuse (320639) | more than 5 years ago | (#27120835)

. . . and (c) that landing delays, diversions, unexpected headwinds, and the occasional airport-sacking terrorist [wikipedia.org] suggest a certain safety reserve be maintained.

Re:Oh, sure. (0)

Anonymous Coward | more than 5 years ago | (#27120939)

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.

There are extreme cases where you would lose that safe bet. For example, moving kerosene into Afghanistan currently probably is cheapest by air. I do not know the numbers, but it might even be cheaper for flights out of Kuwait to load fuel for the retour flight.

you Fail It?! (-1, Troll)

Anonymous Coward | more than 5 years ago | (#27120677)

Marketing (1)

devnullkac (223246) | more than 5 years ago | (#27120679)

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.

Shameful but thrifty in its own way (1)

damn_registrars (1103043) | more than 5 years ago | (#27120711)

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).

Forget the packing (0)

Anonymous Coward | more than 5 years ago | (#27120729)

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.

Packaging in Electronics Industry (1)

sce7mjm (558058) | more than 5 years ago | (#27120761)

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.

Obligatory but... (0)

Anonymous Coward | more than 5 years ago | (#27120773)

Save the packets, Save the world!

Save what? (1)

Akita24 (1080779) | more than 5 years ago | (#27120867)

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.

IBM is terrible (1)

L0stm4n (322418) | more than 5 years ago | (#27120985)

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.

George said it best... (2, Insightful)

geminidomino (614729) | more than 5 years ago | (#27121123)

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 (3, Insightful)

L4t3r4lu5 (1216702) | more than 5 years ago | (#27121139)

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? (2, Insightful)

Vryl (31994) | more than 5 years ago | (#27121209)

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

"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."

The algorithms we already have (1)

VShael (62735) | more than 5 years ago | (#27121809)

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.

Re:The algorithms we already have (1)

Registered Coward v2 (447531) | more than 5 years ago | (#27122081)

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.

Part of the problem is a company generally doesn't know what size boxes it would need in advance, so it's often cheaper to have a few standard sizes to handle all of the boxed shipping requirements. The can by a few sizes in bulk for a lot less than a lot of random sizes. In addition, it speeds the packing process because you don't have to decide what size box you need from a large set of sizes and repack if you run out of space. I'd guess, even if you had a variety of sizes some 80% of the shipments would go out in one of two or three box sizes; so standardizing makes sense from a cost perspective.

Companies that ship the same item over and over, especially via airfreight, find it useful to have a special box for those items; and work with box engineers at the shipper to design the best possible box. Shippers like dense packing - so they don't run out of space before the run out of payload weight; especially since they tend to charge by the pound rather than cubic meter.

Love the creativity of researchers ... (1)

jopet (538074) | more than 5 years ago | (#27121823)

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.

Load More Comments
Slashdot Login

Need an Account?

Forgot your password?