Lösung für Packprobleme Rein, rein, rein!

Schuhe, Bücher, Kleider, Kosmetik: Alles muss mit! Aber wie quetscht man den Kram in den Koffer - und dann das ganze Gepäck in den Kofferraum? Mathematiker entdecken mit Computerhilfe erstaunliche Lösungen. Und stellen dabei einen Packrekord nach dem anderen auf.

Von


Wer kennt dieses Problem nicht? Auf dem Boden liegt ein großer Berg Sachen: Schuhe, Waschbeutel, Bücher, vieles mehr. Daneben steht ein Koffer, in den all diese Sachen hinein müssen - wie auch immer.

Sollen die Schuhe quer auf den Boden, in die Ecke oder als letztes oben drauf? Immer wieder entstehen Hohlräume, man vergeudet wertvollen Platz. Mit etwas Drücken klappt es dann irgendwie doch.

Aber könnte man die beste Packvariante nicht auch einfach ausrechnen?

Nein, in der Regel geht das nicht, lautet die wenig befriedigende Antwort der Mathematiker. Der Grund dafür ist die hohe Komplexität des Problems. Je mehr Einzelstücke zu berücksichtigen sind, umso mehr Kombinationen sind prinzipiell möglich - und umso länger dauert die Suche nach einer optimalen Lösung. Eine elegante, allgemeingültige Lösungstechnik existiert leider nicht.

Das weiß auch Elmar Schömer von der Universität Mainz, der gerade mit seinen Kollegen André Müller und Johannes Schneider eine ganze Reihe neuer Weltrekorde im Packen aufgestellt hat. Nicht für Taschen interessierte sich der Informatiker, sondern für verschieden große Kreise. Wie muss man diese zusammenlegen, so dass sie in einen möglichst kleinen Umkreis hineinpassen, ohne sich zu überlappen?

Die Packaufgabe stammt von einem Programmierwettbewerb des New Yorker Informatikers Al Zimmermann. Die N vorgegebenen Kreise haben einen Radius von 1, 2, 3, 4,… bis N. Schömers Team konnte mit einer selbstentwickelten Software alle bestehenden Packrekorde bis N=24 einstellen und für jede Zahl N von 25 bis 50 neue Bestwerte aufstellen. Die Ergebnisse sind im Fachblatt "Physical Review E" veröffentlicht, eine Übersicht über alle Lösungen von N=24 bis N=50 finden Sie hier.

Kreise rütteln sich nach und nach zurecht

Für zwei oder drei Kreise, also N=2 und N=3, ist die Aufgabe noch einfach. Wer zwei Kreise mit den Radien 1 und 2 möglichst kompakt zusammenlegen will, hat nur eine Möglichkeit: Die beiden Kreise müssen sich berühren (siehe Fotostrecke oben). Der kleinstmögliche Umkreis, der die beiden Kreise umschließt, hat deshalb einen Radius von 3. Im Fall N=3 legt man die beiden großen Kreise aneinander - und den dritten mit dem Radius 1 genau zwischen die beiden größeren. Radius des kleinstmöglichen Umkreises hier: 5.

Wesentlich anspruchsvoller wird die Aufgabe, sobald acht, zehn oder eben 50 Kreise möglichst kompakt angeordnet werden sollen. Die Mainzer Forscher haben zur Lösung ein Verfahren namens Simulierte Abkühlung (simulated annealing) genutzt. Dabei wird ein System nach und nach bis zum Nullpunkt abgekühlt. "Die Methode kommt aus der Physik", sagt Schömer im Gespräch mit SPIEGEL ONLINE. "Es ist ein klassisches Verfahren der stochastischen Optimierung."

Wie funktioniert es? Die Forscher stecken die N Kreise in einen größeren Umkreis, in den sie locker hineinpassen. Die N Kreise bewegen sich wie Moleküle bei der Brownschen Bewegung hin und her, denn die dem System zugewiesene Temperatur ist größer als null. Dann wird gleichzeitig der Umkreisradius immer mehr verkleinert und auch die Temperatur abgesenkt.

Kofferraumvolumen: Prospektangaben und die Wahrheit

"Die Kreise können sich sogar kurzzeitig leicht überlappen", sagt Schömer. Der Algorithmus tauscht immer wieder zwei zufällig ausgewählte Kreise miteinander oder ändert die Positionen von einzelnen Kreisen. "Nicht alle diese Schritte werden akzeptiert", sagt Schneider. Wenn bei ganz niedrigen Temperaturen eine Änderung zu einem größeren Umkreisradius führe oder zu einer Überlappung zwischen zwei Scheiben, sei es sehr wahrscheinlich, dass der Schritt verworfen werde. Der Algorithmus geht dann wieder einen Schritt zurück und wählt andere Kreisscheiben zum Tauschen oder Verschieben aus.

Auf diese Weise rütteln sich die Kreise nach und nach auf immer kleinerer Fläche zusammen. "Schließlich erreicht die Temperatur den Wert null, das System friert ein", sagt Schömer.

Dabei ergibt sich allerdings nicht automatisch ein neuer Packrekord. Vielmehr mussten die Forscher das Kreissystem immer wieder von Neuem starten und schauen, bei welchem Umkreisradius es am Ende zum Stillstand kam. Bei wenigen Kreisen reichten schon 1000 Durchläufe, um eine gute Packvariante zu finden. Im Fall N=50 lief die Abkühlungssimulation 30.000-mal. Auf einem Cluster bestehend aus 200 Prozessoren dauerte die Berechnung etwa einen Tag.

Styropor versus Algorithmus

Das Packen von Scheiben in einen möglichst kleinen Umkreis ist mehr als nur Spielerei. Das Team von Schneider und Schömer arbeitet auch für die Autoindustrie. Im Auftrag von Daimler füllen sie Pkw-Kofferräume mit Tetrapacks - und zwar mit so vielen wie möglich. Warum? Weil die DIN-Norm 70020 besagt, dass das Kofferraumvolumen genau auf diese Weise ermittelt werden muss. Jeder Tetrapack umfasst einen Liter - und je mehr hineinpassen, umso größer ist die Zahl, die in den Prospekten auftaucht.

Die Mainzer Forscher lösen die Aufgabe per Software. Die Zeitschrift "Auto Bild" hat die Kofferraum-Angaben der Hersteller sogar schon mit Quadern aus Styropor überprüft - siehe Fotostrecke. Fazit der Tester: Keiner der 20 Testkandidaten erreicht die Herstellerangaben. Und viele Marken übertrieben bei der Literzahl "zum Teil maßlos", wie das Blatt schreibt.

Dass die Tester die Prospektwerte nicht schaffen konnten, verwundert allerdings nicht. Gegen einen professionellen Packalgorithmus hat auch ein erfahrener TÜV-Experte kaum eine Chance.

Mehr zum Thema


© SPIEGEL ONLINE 2009
Alle Rechte vorbehalten
Vervielfältigung nur mit Genehmigung der SPIEGELnet GmbH


TOP
Die Homepage wurde aktualisiert. Jetzt aufrufen.
Hinweis nicht mehr anzeigen.