next up previous contents
Next: Tourenplanung Up: Anwendungen der kombinatorischen Optimierung Previous: Flugplanoptimierung

Parallele Packalgorithmen

Das Vehicle-Routing-Problem - die Bestimmung kostenoptimaler Touren, auf denen Kunden ausgehend von einem Depot beliefert werden - wird wie zahlreiche Scheduling- und Packungsprobleme schon seit längerem in der kombinatorischen Optimierung untersucht. Sowohl im Bereich der internen Logistik (Lagerorganisation) als auch im Bereich der externen Logistik (Transport) treten aber häufig komplexe Optimierungsaufgaben auf, in denen diese Probleme kombiniert sind. So muß beispielsweise bei der Auftragszusammenstellung ein Kommissionierungswagen auf kürzestem Weg durch das Fertigungslager gesteuert und mit unterschiedlichen Paketen beladen werden. Bei Just-in-time-Produktion werden Produkte nach ihrer Fertigstellung - ohne Zwischenlagerung - direkt in LKW verpackt und an die Kunden ausgeliefert. Hier besteht ein enger Zusammenhang zwischen Vehicle-Routing-Problem (in welcher Reihenfolge werden die Kunden beliefert), Stauraumoptimierung und Scheduling (in welcher Reihenfolge werden die Produkte hergestellt).

  figure345
Abbildung: Visualisierung eines dreidimensionalen Packmusters

Zusammen mit der Forschungsgruppe um Professor Monien an der Universität Paderborn und der Remscheider Unternehmensberatung Profi.L, deren Schwerpunkt im Bereich Transport und Logistik liegt, wird in unserer Arbeitsgruppe das PARALOR-Teilprojekt ,, Integrierte Steuerung von Fertigungslagern`` bearbeitet. In diesem Rahmen untersuchen wir sequentielle und parallele Verfahren zum Packen gleicher oder verschiedenartiger zwei- oder dreidimensionaler Objekte in einen oder mehrere Behälter (z.B. Container, Euro-Paletten) und ihre Visualisierung (Bild gif). Diese Verfahren sollen zusammen mit Algorithmen zur Wegeminimierung und Plazierung im Lager sowie mit Tourenplanungsalgorithmen in einer integrierten Lageroptimierung vereinigt werden.

In einer industriellen Fallstudie wurde das dreidimensionale Packen von Artikeln mit komplexer Geometrie behandelt. Das dabei entwickelte Verfahren befindet sich seit April 1995 bei einem Hersteller von Sanitärartikeln im Einsatz. Als Kernproblem identifizierten wir die homogene Kommissionierung von Wannen, ein Packungsproblem, das wir sowohl als Bin-Packing-Problem mit nachfolgerabhängigen Gewichten als auch als Vehicle-Routing-Problem mit Kapazitätsbeschränkung formuliert haben. Letzteres ist bemerkenswert, da die ursprüngliche Interpretation des Vehicle-Routing-Problems aus einem völlig anderen Anwendungsbereich stammt, nämlich der Planung einer optimalen Auslieferungstour z.B. für LKW. Eine eingehendere Darstellung sowie eine Beschreibung der angewandten sequentiellen Algorithmen findet sich im Jahresbericht 1993/1994.

Aufbauend auf diesen Ergebnissen haben wir im Jahre 1995 drei Möglichkeiten untersucht, Parallelrechner zur Lösung dieses Problems einzusetzen: eine kundenweise Aufspaltung (d.h. die Auftragsbestände verschiedener Kunden werden gleichzeitig auf verschiedenen Rechnerknoten bearbeitet), eine funktionale Dekomposition (also die Zerlegung des Programms in unabhängige Funktionseinheiten, die gleichzeitig abgearbeitet werden können) und das am ZPR ursprünglich zur Tourenplanung entwickelte parallele ,,Simulated Trading``.

Mit einer Implementierung der kundenweisen Aufspaltung wurden auf dem Parsytec GCel-3/1024 des ZPR, einem massiv-parallelen System mit 1024 Prozessoren, Real-World-Probleme mit bis zu 8300 Posten effizient bearbeitet. Diese Art der Parallelisierung lieferte schon bei kleinen Problemen gute Ergebnisse, so daß man sie in der Praxis auf jeden Fall einsetzen sollte, falls Performanceprobleme auftreten und insbesondere, wenn die Probleminstanzen größer werden sollten.
Die funktionale Dekomposition erwies sich erst bei Kunden mit sehr großer Postenanzahl als sinnvoll einsetzbar. Sie sollte dann zusätzlich zur kundenweisen Aufteilung verwendet werden.
Im parallelen Simulated Trading werden mehrere Simulated-Trading-Prozesse parallel auf mehrere Palettencluster angewendet. Die Tauglichkeit dieses Algorithmus für das Packproblem konnte experimentell bestätigt werden.

Für die Fallstudie ,,Packen von Sanitärartikeln`` kann insgesamt festgehalten werden, daß für die momentan aktuellen Praxisprobleme eine Parallelisierung nicht notwendig ist, was sich aber bei der sich abzeichnenden Vergrößerung der Produktpalette in den nächsten Jahren ändern kann.


next up previous contents
Next: Tourenplanung Up: Anwendungen der kombinatorischen Optimierung Previous: Flugplanoptimierung

Webmaster <www@zpr.uni-koeln.de>, 7. Apr. 1997