"Packing problem"

Wie quetsche ich möglichst viel in meinen Koffer?

11. März 2009, 18:56
  • Artikelbild
    foto: apa/epa

    Effizienz beim Anordnen oder Packen ist ein komplexes Problem.

Die optimale Anordnung von zwei- oder dreidimensionalen Objekten ist ein komplexes Problem - ein Algorithmus schafft Platz

Wie den Platz so gut wie möglich nutzen? Darüber werden sich auch heuer wieder Urlauber und Urlauberinnen vor ihren Koffern stehend die Köpfe zerbrechen. Für die optimale Nutzung von Raum kann ein Algorithmus von Nutzen sein, der unterschiedliche Formen in einem möglichst kleinen Raum anzuordnen versucht. Solche Algorithmen beschäftigen sich mit dem Problem der optimalen Anordnung bzw. mit dem "Packing-Problem".

Was zunächst nach einer komplexeren Version des Videospiels "Tetris" klingt, kann auch zur Lösung von Problemen in der realen Welt beitragen. Die Effizienz beim Anordnen oder Packen kann sowohl Kosten senken als auch den Transport diverser Güter ökologischer gestalten.

Optimale Ergebnisse

Um herauszufinden, welche Algorithmen helfen können, um verfügbaren Platz optimal zu nutzen, haben WissenschafterInnen ihre Algorithmen gegeneinander in einen Wettbewerb geschickt, bei dem spezielle "Packing-Problems" zu lösen waren. Zum Beispiel das Problem, wie eine Menge von unterschiedlich großen Scheiben in einen Kreis passt, ohne sich zu überlappen.
Das Team von Johannes Schneider an der Universität von Mainz hat alle bisherigen Rekorde zu dem Problem der Scheiben-Anordnung gebrochen, wie in "NewScientist" berichtet wird.

Anordnung von Scheiben

Die Anforderungen für den Wettbewerb wurden in früheren Wettbewerben mit 155 Gruppen aus 32 Ländern definiert. Der Algorithmus von Schneiders Team ist gleich schnell wie alle bisherigen - zumindest was die Anordnung von bis zu 23 Scheiben in einem Kreis betrifft. Schneller als alle anderen ist der Algorithmus allerdings für 26 bis 50 Scheiben.

Bisherige Algorithmen haben die Scheiben immer wieder von neuem gemischt, um eine effiziente Nutzung des Raumes zu erreichen. Das Geheimnis des Erfolges des "Rekord-Algorithmus" besteht darin, dass es auch die Möglichkeit gibt, einen Schritt zurückzugehen. Wenn eine Lösung für eine Anordnung gefunden wurde, werden somit beispielsweise Teillösungen beibehalten, andere Teile aber wieder herausgenommen und es werden wieder neue Versuche zur Anordnung gestartet.

Einfach nur bergauf?

Die oben beschriebene Vorgehensweise, ständig eine neue Zusammenstellung zu versuchen, erinnert laut Schneider eher an folgendes Szenario: Ein Alpinist versucht den höchsten Punkt auf der Erde zu finden, indem er immer bergauf geht und stehenbleibt, wenn es nicht mehr bergauf geht. Dann würde der Alpinist wahrscheinlich einfach auf dem nächstgelegenen Hügel landen und dort festsitzen - und es wäre reiner Zufall, wenn der Alpinist seinen Aufstieg gerade am Fuße des höchsten Berges der Welt beginnen würde.

Dadurch, dass die Algorithmen von Schneider und seinem Team erlauben, auch einen Schritt zurück zu gehen, können bessere Lösungen erreicht werden. Vollständig gelöst wurde das Problem der effizientesten Anordnung mit diesem Algorithmus nicht, aber es ist im Moment zumindest die beste Lösung.

3D-Szenarios

Marco Locatelli von der Universität Turin gehört zu dem Team, das die meisten bisherigen Rekorde - bevor Schneiders Team auf den Plan trat - hielt. Er sieht die Möglichkeit eines Rücksetzverfahrens als einen Hauptgrund für den erfolgreichen Ansatz, und die Herausarbeitung solcher Rückwärtsbewegungen sei bestimmt ein Verdienst. Aber die Algorithmen verbessern sich schnell und Rekorde halten sich selten lange, so Locatelli skeptisch gegenüber "NewScientist" über die aktuellen Rekordhalter. Interessant fände er 3D-Szenarios, welche Schneiders Team künftig auch untersuchen möchte.

"Wir haben jetzt einen Algorithmus, der Probleme mit 3D-Gütern von verschiedenen Größen löst", so Schneider. Somit werden derartige Probleme auch für die reale Welt relevant. Beispielsweise sehen sich Transportfirmen mit dem Anspruch konfrontiert, in Paket-Transportern oder Schiffen so viele Güter wie möglich unterzubringen.

Auch die Reihenfolge - zuzüglich zur Anordnung - von 3D-Objekten zu berücksichtigen ist relevant für reale Probleme. Beispielsweise, wenn ein Paket-Laster so gepackt sein soll, dass Pakete der Reihe nach an Kunden und Kundinnen ausgeliefert werden können, ohne in die hinterste Ecke des LKW kriechen zu müssen. (beaha, derStandard.at, 11.3.2009)

Kommentar posten
Posting 1 bis 25 von 41
1 2
Nick Tameer
11
15.3.2009, 08:55

Die Mathematik sollte sich stattdessen einmal wirklich brennender praktischer Probleme annehmen, etwa der Frage "Wie quatsche ich möglichst viel in mein Handy?".

Psychedelic Brain
00
15.3.2009, 08:53

anstelle die sinnhaftigkeit dieser studie anzuzweifeln, sollten jene leute, die meinen das geld wäre woanders besser aufgehoben, das ergebnis der studie dafür nutzen, so viele kredite wie nur möglich unter einem hut zu bringen. dann ändert sich 'mal wir was zum positiven.

anne.sche
01
12.3.2009, 16:53
Wie quetsche ich möglichst viel in meinen Urlaubs-Koffer?

Dank der Wirtschaftskrise wird sich dieses Problem für die meisten von uns nicht mehr stellen.

Und die, die dieses Problem weiterhin haben, werden lernen, damit umzugehen....

Haben wir ein Glück!!!!

Roman Santos
01
12.3.2009, 13:22
Anstelle solche Kofferpackstudien anzustellen

sollte man lieber untersuchen, warum die lieben Mitmenschen immer einen Karton, wenn sie ihn in den Mül werfen, immer im Ganzen lassen anstelle ihn zu zerlegen oder einzuklappen um den Container nicht mit Luft zu füllen. Niemand würde auf die Idee kommen, sich in seinem Koffer mit einem aufgebauten Karton den Platz wegzunehmen wenn er den Karton auch falten und damit Platz für andere Dinge schaffen könnte.
Beim Müllcontainer kommen die Leute aber nicht auf diese Idee? Warum eigentlich? Das würde mich mehr interessieren und könnte helfen, die Anzahl an Müllabfuhren mit allen damit verbundenen Kosten zu reduzieren was uns und der Umwelt mehr nützen würde.

Daddy1951
 
00
13.3.2009, 13:22
Also das ist leicht erklärt.

Weil volle Kartons nicht zu falten sind.
Voll mit Sondermüll der sonst teuer entsorgt werden müsste.
So easy - der Mensch is a Sau.

nostra
01
12.3.2009, 18:30
Egoismus

Weil die Folgen der Faulheit und Bequemlichkeit andere bzw. die Gemeinschaft ausbaden müssen - ich bin meinen Mist los, und die anderen sollen schauen, wo sie bleiben. Ecce homo.

Erich Hofbauer
00
12.3.2009, 13:51

weil sie zu faul sind? OK, nicht jeder hat ein Messer in Griffweite, aber einmal draufsteigen würde den Karton auch plätten. Bei unserem Briefkasten steht auch ein Karton für den Werbemüll (war meine Idee, vorher lagen die Zettel meist am oder neben dem Briefkasten), weil die Leute zu faul sind, die Prospekte die 3m bis zum Müllraum zu tragen und zum Altpapier zu werfen. Die vom Geschäft in unserem Haus zerlegen die vielen bei ihnen anfallenden Kartons übrigens.

darkwing
16
12.3.2009, 13:03
Algorithmen?!?

Bledsinn.....ich lass' das meine Alte machen, die kriegt prinzipiell immer alles in den Koffer rein, und das auch noch übersichtlich angeordnet und knitterfrei zusammengelegt.....obwohl ich ihr schon zugeschaut habe, ist mir bis heute schleierhaft, WIE genau sie das herbringt.

SimplyRed
00
12.3.2009, 11:24

Man reist nach Bali mit ein, zwei Reiseführern im kleinen Rucksack und schönen Träumen im Gepäck.

Kassandra
00
12.3.2009, 10:39
Wie packt man einen Koffer

mit sämtlichen Tauchutensilien (außer Tank und Blei natürlich) UND alles andere, was man sonst noch für 2 Wochen Urlaub braucht???
Das ist eine echte Herausforderung - noch dazu beim 20 kg-Limit. Ok, ich gebs ja zu, man kann auch Tauchgepäck anmelden, dann sind 30 kg erlaubt - aber das geht leider nicht bei allen Airlines.
Was noch erschwerend hinzukommt: Früher hatte ich immer Cremes, Sonnenmittel etc. im Handgepäck - ist ja leider seit einiger Zeit auch nciht mehr möglich!

ingrid ingrid
00
12.3.2009, 12:14
Stimmt..

die Cremes hatte ich auch immer im Handgebäck.. denn im Koffer platzen sie alle..
Und auch brauch ich im Flieger feuchte Haut..
nix davon ists mehr erlaubt!

Kassandra
01
12.3.2009, 15:26
1. Feuchtigkeit für die Haut,

weil sonst ist die Urlaubsräune gleich futsch und diese Mini-Spender (so überhaupt vorhanden) in den Toiletten sind immer gleich leer. Und ein 100ml Cremchen nützt für all die Haut, die nicht unter Textilien ist reichlich wenig!
2. Flussigkeit! Gerade bei einem Flug sollte man sehr viel trinken. Ich hatte immer ein 1,5 L Mineral mit. Wenn man z.b. bei einem 4stündigen Flug mit der AUA 3-4 x so ein Mini-Gläschen bekommt, ist das eindeutig viiiieeel zu wenig!!!

fibiundchillie
00
12.3.2009, 12:32

in kleine döschen bzw.Flascherl abfüllen, kann man kaufen: immer in apotheken, manchmal bei butler´s (auch kl. Flascherl), in Wien afaik im "Plastikhaus" gleich beim Stephansplatz.
kürzlich ließ man mich mit einer fast volle pet-flasche mineralwass. in dubai in den flieger. hm?

duke box
00
12.3.2009, 19:40
kürzlich ließ man mich mit einer fast volle pet-flasche mineralwass. in dubai in den flieger. hm?

die flüssigkeitsparanoia ist auch eine europäische erfindung, die verdanken wir den engländern.

Kassandra
00
12.3.2009, 15:28
Hmm - ich würde sagen:

Glück gehabt!
Andererseits ersticken sie auf den Flughäfen ja eh im Müll, wenn man alles abgeben muss. Ich finds hirnrissig! Eine Wasserflasche kann net viel mit Sicherheit zu tun haben

's koite Sopherl
01
12.3.2009, 08:59

Ist dann die Minimierung des Platzbedarfs gleichzusetzen mit der Maximierung des Knitterlooks?

Kamine glühen leise
00
12.3.2009, 08:40

oh - ein gaaaanz neuer ansatz, lokale minima zu ignorieren...

ob die algorithmen für die transportfirmen dann auch max. zulässiges gewicht und balance (zb schwere sachen unten) berücksichtigen werden?

Frau Techne
15
12.3.2009, 05:56

Fräulein Redakteurin, seien Sie versichert: Auch Sie besitzen mit Sicherheit KEIN "zweidimensionales Objekt".

Nick Tameer
01
15.3.2009, 16:53

Tu felix Austria besitzt noch die in Deuschland die in Deutschland völlig augestorbenen Fräuleins? Falls diese dann zweidimensionale Objekte besäßen, würde das mich dann auch schon nicht mehr wundern.

Frau Techne
01
21.3.2009, 20:19

Ich pflege "Fräulein" ausschließlich als Schimpfwort zu verwenden.

NickNameless
00
14.3.2009, 10:31

ein blatt papier kommt aber schon verdammt nah ran

Susi Stattnam
11
11.3.2009, 22:01
Uebung macht die Meisterin ...

es ist nicht nur wichtig, wie man moeglichst viel hinein bekommt, sondern auch vorher bereits die richtige Auswahl der Sachen und danach das Einhalten der genauen Gepaeckangaben der Fluglinien. Wenn das Personal gut drauf ist, geht fast alles durch, wenn sie schlecht drauf sind, lassen sie sogar einen leeren Rollie in exakter Groesse des Handgepaeckes ins Gepaeck geben, nur um danach es einzuziehen, zwei Tage spaeter dann der Anruf mit der Frage: was war denn drin???? weil sie dachten, es waere was raus gestohlen worden. Und selbstverstaendlich ist der Rollie komplett zerquetscht... ;0) Aber ich hoere, ich bin nicht die Einzige, die manchmal weniger Glueck hat.
Ryanair ist mittlerweile sehr streng mit dem Handgepaeck....

Hugh G Rection
02
12.3.2009, 12:23
Was müssen Männer machen

um zum Meister zu avancieren?

Susi Stattnam
30
12.3.2009, 14:38
ich brauch von mir nicht in der maennlichen Form sprechen.

Wenn das Sie persoenlich als Mann beleidigt, gehn Sie sich bitte beim Salzamt beschweren.

StrgAltEntf
 
04
11.3.2009, 20:29
Die Wurstkatastrophe

Mit Kugeln wirds richtig interessant
http://de.wikipedia.org/wiki/Theo... lpackungen

Kommentar posten
Posting 1 bis 25 von 41
1 2

Die Kommentare von Usern und Userinnen geben nicht notwendigerweise die Meinung der Redaktion wieder. Die Redaktion behält sich vor, Kommentare, welche straf- oder zivilrechtliche Normen verletzen, den guten Sitten widersprechen oder sonst dem Ansehen des Mediums zuwiderlaufen (siehe ausführliche Forenregeln), zu entfernen. Der/Die Benutzer/in kann diesfalls keine Ansprüche stellen. Weiters behält sich die derStandard.at GmbH vor, Schadenersatzansprüche geltend zu machen und strafrechtlich relevante Tatbestände zur Anzeige zu bringen.