An den richtigen Stellschrauben drehen

Solver-Lösungen für Planungsprobleme

Die Optimierung erbrachte bei diesem Beispiel eine signifikante Reduzierung der Gangwechsel und damit zusammenhängend 3.908 Meter weniger Kommissionierweg. Foto: Dr. Thomas + Partner

Ein zentraler Bestandteil des Frameworks ist der so genannte Solver, mit dem mathematische Problemfälle gelöst werden können. Er verwendet dabei heuristische und metaheuristische Optimierungs-Algorithmen, während die Rahmenbedingungen – wie Zielfunktionen und Nebenbedingungen – individuell festgelegt werden, um möglichst effizient im Lösungsraum zu suchen. Entwicklungs- und Optimierungsphase verlaufen dabei stets dynamisch und auch unabhängig voneinander. So lassen sich in eine Lösung jederzeit weitere Planungs- und Optimierungsschritte einbauen, ohne dass derjenige, der die betreffende Anwendung entwickelt, sich permanent mit dem Thema Optimierung beschäftigen muss. Ein enormer Fortschritt also im Vergleich zu kostspieligen Optimierungs-Black-Boxes mit starrer Monolithen-Charakteristik, die dem gesamten TUP.WMS pauschal und quasi anonym übergestülpt werden. Zudem wird den Kunden Transparenz geboten, da jederzeit darstellbar ist, wie der Solver konfiguriert ist.

Frühzeitig analysieren und Ziele definieren

Wie der Senior-Projekt-Manager Wagner ausführt, führen die folgenden vier Schritte zu einem guten Optimierungsergebnis: Planungsprobleme modellieren, Score-Berechnung implementieren, Solver konfigurieren und die Optimierung durchführen.

Bei der Modellierung der Planungsprobleme wird zunächst die fachliche Fragestellung analysiert und das Ziel der Optimierung definiert. Wichtig ist, wie Wagner aus Erfahrung weiß, „dass die Kunden die Herausforderungen verstanden haben, bevor wir über die Lösung reden. Immer wieder allerdings verdeutlicht die frühzeitige Analysearbeit einem Kunden, dass er aktuell gar nicht so weit ist, optimieren zu lassen. Auch weil seine Prozesse derzeit gar zu fragmentiert und zu detailliert sind.“

Anschließend werden die fachlich relevanten Objekte in einem Domänenmodell aus einfachen Java-Klassen abgebildet. Es wird zwischen „problem facts“, „planning entities“ und „planning solutions“ unterschieden.

„Im Mittelwert sind nur rund zwei bis drei Wochen für den Entwurf einer Solver-Lösung erforderlich“

Eduard Wagner Senior-Projekt-Manager und Mitglied der Geschäftsleitung TUP

„Problem facts“ sind etwa unveränderlich und nicht beeinflussbar, sie „sind daher frühzeitig von den Dingen zu trennen, die man beeinflussen kann“, sagt Wagner. Die „planning entities“ beinhalten dagegen Randbedingungen der Planung, die unter Umständen veränderlich sind. Und die „planning solutions“ stehen für die eigentlichen Zielfunktionen. Beispiele:

• Der Kommissionierweg wird in Summe über sämtliche Kommissionen minimiert.
• Die Durchlaufzeit kann um maximal zehn Minuten überschritten werden.

Optimierungs-Algorithmen für jede Phase der Lösung

Die Score-Berechnung bringt alle Zielfunktionen und Nebenbedingungen in eine Normierungsform und fungiert somit als „Ein-Nordung“ einer Bewertung der Güte und Gültigkeit. Mit Hilfe des Scores wird eine Unmenge von Lösungen miteinander verglichen und bewertet. Über Regeln wird ausgedrückt, wie sich der jeweilige Score bei Verletzung von harten und weichen Restriktionen verändert.

Anschließend erfolgt die Konfiguration des Modells, des Solver und der Optimierungs-Algorithmen. Passend zu jeder Phase der Lösung eines Optimierungsproblems werden die erforderlichen Optimierungs-Algorithmen definiert. Die Lösung erfolgt iterativ und schrittweise, wobei jeder Schritt wieder zu einer neuen Lösung führt.

„Die Konfiguration des Solver ist natürlich das Kernelement“,  betont Wagner. Der Solver-Programmierer entscheidet, wie die Planungsprobleme zu modellieren sind, welche und wie Optimierungsmethoden am sinnvollsten für die Problemlösung zu verwenden sind.

Der Solver wird jeweils anwendungsbezogen konfiguriert

„Dabei wird der Solver nicht komplett neu entwickelt. Lediglich das Solver-Projekt und dessen Klassen werden neu angelegt. Zudem wird durch die Solver-Konfiguration transparent dargestellt, wie er sich verhalten wird“,  stellt Eduard Wagner klar.

Dies geschieht jeweils anwendungsbezogen und auf die jeweiligen Anforderungen zugeschnitten. Wagner: „Der Solver geht auf das definierte Planungsproblem ein, und dementsprechend ist jeder Solver individuell zu betrachten. Nur der Weg, wie er entwickelt wird, ist ähnlich.

Daher ist die Solver-Konfiguration auch eine Spezialaufgabe von Kollegen, die zwar im FuE-Bereich tätig sind, aber tatsächlich Bausteine verwenden, mit denen sie die Kollegen, die sich mit Prozess-Ketten beschäftigen, sofort mit Lösungen unterstützen können.“ Ein wichtiger Schritt der Konfiguration ist die Definition von Terminierungskriterien. So sind beispielsweise die Anzahl der maximal durchzuführenden Schritte ohne Verbesserung der Lösung oder eine konkret festgelegte Zeitdauer wichtige Abbruchkriterien der Optimierung.

Mut, Dinge anders anzupacken

So effizient und wirtschaftlich nützlich sich die Softwareoptimierung auch erweist, sie wird den professionellen Umgang mit IT keineswegs vereinfachen und deren operative Einsätze nicht plötzlich drastisch revolutionieren. Denn nach wie vor sind jede Menge grundlegender Tugenden und Know-how erforderlich, um die gewünschten Ergebnisse zu erzielen. „Auch in Zeiten von ‚Same Day Delivery‘, ‚Big Data‘ und Industrie 4.0 ist TUP weiterhin konservativ der Meinung, dass fundierte Basisarbeit im IT-Umfeld erforderlich ist, um die Voraussetzungen für noch bessere Lösungsansätze in der Intralogistik zu schaffen“, konstatiert Eduard Wagner bei seinem Blick in die Zukunft.

Bei Haba konnten die Laufwege und die Gangwechsel reduziert werden. Foto: Haba

Algorithmen erfolgreich angewendet: bei Haba und adidas

Die Optimierungslösung von TUP ist bereits seit mehr als einem Jahr beim Spielwaren- und Kinderartikelhersteller Haba sowie bei der Marke adidas im Einsatz.

Bei Haba wird die Kommissionsbildung optimiert. Ausgangsdaten sind komplett reservierte Aufträge, für die der Nachschub bereits abgeschlossen ist und die Kommissionierung gestartet werden kann. Zielfunktion ist, die Länge des Laufweges beziehungsweise die Anzahl der Gangwechsel über alle Kommissionen zu minimieren. Der hierzu verwendete Algorithmus ist das Optimierungsverfahren „Simulated Annealing“. Dabei werden auch die Größe der Sortiermodule und die Abwicklungsgruppen berücksichtigt.

Bei adidas werden die Batches entsprechend unterschiedlicher Kriterien gebildet. Die Optimierung beinhaltet auch eine vorgeschaltete Bildung von sogenannten Sammel-Versandeinheiten (VEs); dies sind fiktive VEs, die Versandeinheiten mit einer Position (Menge 1) zusammenfassen. Dabei soll möglichst eine Sorter-Rutsche gefüllt werden, wobei Volumen, Gewicht und Priorität berücksichtigt werden.

In einem zweiten Schritt findet die eigentliche Batchbildung statt. Ziel ist es, dass die Batches die folgenden unterschiedlichen Vorgaben möglichst gut erfüllen:

• Hoher, aber gleichmäßiger Anteil an sogenannten Golden- und Silverkartons;
• die vorgegebene Zusammensetzung bezüglich Schuh- und Textil-Lieferscheine soll über möglichst wenige Batches verteilt sein;
• Berücksichtigung der Auftragspriorität und eines Fälligkeitsdatums.

Ausgangsdaten sind Parameter, Auftragsdaten und verfügbare Mengen für Golden- und Silver-Kartons. Vom Solver werden eine vorgegebene Anzahl Batches mit einer festen maximalen Anzahl an Aufträgen gebildet. Die Parameter werden vom Benutzer mittels eines Dialogs gesetzt. Und bei Bedarf kann die Batch-Bildung auch ohne die Optimierung erfolgen.

„Das beginnt bei der grundlagenorientierten Ausbildung; geht weiter mit durchgängiger und hochverfügbarer Infrastruktur und mündet im Mut, Dinge anders anzupacken, als es bislang der Fall war – am Ende erhalten wir eine disruptive Lösung beziehungsweise Technologie.“

Wie Wagner betont, „werden anspruchsvolle analytische Modelle und Monte-Carlo-Simulation künftig unser Leben generell tiefgreifend verändern, und am Ende werden uns IT und Roboter immer mehr bei der täglichen Arbeit unterstützen; sei es im Denken, Entscheiden oder auch Handeln“.

Reinhard Irrgang