Dichte Packungen von Kreisen in ein Rechteck

Prof. Dr. Uwe Schöning
Prof. Dr. Jacobo Toran
PD Dr. Thomas Thierauf
Dr. Jochen Messner
Uwe Bubeck

Abteilung Theoretische Informatik
Universität Ulm

Das Projekt wurde mit dem

Kooperationspreis Wissenschaft-Wirtschaft 2001/02

der Universität Ulm ausgezeichnet.

Wie packt man möglichst viele Garnrollen platzsparend auf eine Palette? Für dieses Problem der Firma Autefa Automation Gmbh galt es ein Steuerprogramm für einen Roboterarm zu entwickeln, der diese Garnrollen dann entprechend auf Paletten stellt.

Die seitherige Vorgehensweise war, dass die Garnrollen gemäß einer Gitterstruktur gleichmäßig auf die Paletten gestellt wurden. Die Paletten sind Rechtecke mit den Seitenlängen 1 m und 1,2 m. Die Garnrollen haben alle die gleiche Höhe, und verschiedene Durchmesser im Bereich von 9 bis 29 cm. Je nach Durchmesser der Garnrollen konnte es dann passieren, dass an den Rändern viel Platz frei blieb. Dadurch waren dann die Platzkapazitäten nicht optimal ausgenutzt, was erhöhte Kosten zur Folge hat. Wir haben im Auftrag von Autefa einen Algorithmus zur Platzierung der Garnrollen entwickelt, der in solchen Fällen deutlich mehr Rollen auf eine Palette bringt.

Ein Beispiel

Haben die Garnrollen einen Durchmesser von 20 cm, so passen gemäß der Gitterstruktur gerade 5 mal 6 = 30 Garnrollen auf eine Palette und dies ist auch die optimale Packung.
Haben die Garnrollen einen Durchmesser von 21 cm, so passen gemäß der Gitterstruktur nur 4 mal 5 = 20 Garnrollen auf eine Palette und es bleibt ein Randstreifen von 16 bzw. 15 cm Breite. Die Palettenfläche ist dann nur zu knapp 58% abgedeckt.
Das von uns entwickelte Verfahren platziert in einer unregelmäßigen Anordung 26 Garnrollen mit einem Durchmesser von 21 cm auf einer Palette, also 6 mehr als bei der Gitterstruktur. Die Palettenfläche ist dann zu ca. 75% abgedeckt.

Dies bedeutet also eine Steigerung der Platzauslastung um fast 30%. Die Paletten werden mit Lastwagen ausgefahren. In der Folge sinken also die LKW-Transporte entprechend um 30%.

Eine abstrakte Formulierung der Problemstellung

Eine einfache mathematische Beschreibung des Problems erhält man, wenn man eine Palette als Rechteck und die Garnrollen als Kreise auffasst. Die Aufgabenstellung lautet dann folgendermaßen:

Gegeben sind ein Rechteck einer festen Größe und Kreise von verschiedenen Durchmessern.
Gesucht ist eine nicht-überlappende Anordnung von einigen dieser Kreise innerhalb des Rechtecks, so dass die abgedeckte Fläche maximal ist.

Historie und Referenzen

Ein Spezialfall des Problems wird bereits seit einigen Jahren von Mathematikern studiert: packe möglichst viele Kreise mit gleichem Durchmesser in ein Quadrat. Die besten Lösungen bis zu 25 Kreisen findet man übersichtlich in Erich's Packing Center. Lösungen bis zu 100 Kreisen findet man auf der home page von Peter Gabor Szabo. Ein individuelles Berechnungsformular wird auf der Packomania Seite von Eckard Specht bereitgestellt. Ein guter Algorithmus ist in einer Arbeit von David W. Boll, Jerry Donovan , Ronald L. Graham and Boris D. Lubachevsky im Electronic Journal of Combinatorics 7(1), 2000 veröffentlicht (ps | pdf). Uwe Schöning hat die Problemstellung in eine Aufgabe beim Bundeswettbewerb Informatik gepackt.

Die Grundidee des Algorithmus

Wir starten (virtuell) mit einem Rechteck, das um einiges größer ist als die Palette, so dass die zu packenden Kreise regelmäßig und in gewissen Abständen zueinander in dieses Rechteck platziert werden können.

Dann startet gewissermaßen ein Schüttelvorgang: die Kreise werden in eine zufällig gewählte Richtung verschoben, wobei die Richtung zum Rechteckszentrum bevorzugt wird. Falls es nach einer solchen Schüttelbewegung am Rand etwas Platz gibt, wird das virtuelle Rechteck entsprechend verkleinert. Dieser Vorgang wird dann sehr oft wiederholt. Die Stärke der Schüttelbewegung nimmt dabei ständig ab, je enger die Kreise bereits liegen.

Im erfolgreichen Fall ist das virtuelle Rechteck nach einiger Zeit auf die Größe der Palette geschrumpft und alle Kreise sind gepackt. Ansonsten konstatiert der Algorithmus, dass diese Kreise nicht auf die Palette passen, und man wiederholt das ganze mit weniger Kreisen.

Eine ausführlichere Beschreibung findet man in einem Auszug aus dem Bericht zum Projekt (ps | pdf).

Warum funktioniert das so gut? Vermutlich haben die Meisten dieses Verfahren in anderen Zusammenhängen schon angewendet: füllt man eine Dose beispielsweise mit Kaffeebohnen voll und schüttelt die Dose dann etwas, so sinken die Bohnen ein wenig in sich zusammen. Der Schüttelvorgang, gewissermaßen ein Zufallsprozess, führt zu einer dichteren Lagerung der Bohnen.

Intuitiv kann man sich vorstellen, dass eine Bohne durch das Schütteln zunächst angehoben wird und dann durch die Schwerkraft wieder nach unten fällt. Dabei kann sie dann in Lücken fallen, die vorher durch andere Bohnen versperrt waren. Die Schwerkraft wird in unserem Algorithmus simuliert durch eine gewichtete Wahrscheinlichkeitsverteilung der Bewegungsrichtung der Kreise, die mit höherer Wahrscheinlichkeit zum Rechteckszentrum führt.