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