Wie unser Masterand Daniel Hille den Einsatz von Metaheuristiken in der Intralogistik bewertet

Der Begriff Heuristik bezeichnet ein Verfahren, durch dessen Hilfe mit begrenztem Wissen und zeitlichen Einschränkungen trotzdem eine wahrscheinliche und praktikablen Lösung für ein Problem gefunden werden kann.

Heuristische Verfahren, die oft zum Einsatz kommen, vor allem bei elektronischen Endgeräten, sind ‚trial and error‘ und das Ausschlussverfahren. Wobei letzteres auch eines der Steckenpferde von Sherlock Holmes ist:

“When you have excluded the impossible, whatever remains, however improbable, must be the truth.” – The Adventure of the Beryl Coronet / Sherlock Holmes

Das ‘Meta’ in Metaheuristik beschreibt, dass es sich dabei um eine höhere Stufe der Heuristik handelt, die – zumindest theoretisch – auf beliebige Probleme angewendet werden kann: Sei es ein Schachproblem oder die Batchbildung in einem Distributionszentrum.

In dem Beitrag ‚Metaheuristics in Combinatorial Optimization: Overview and Conceptual Comparison‘ werden die Eigenschaften von Metaheuristiken wie folgt beschrieben:

• Metaheuristiken sind Strategien, die den Suchprozess ‚lenken‘
• Das Ziel ist es, den Suchraum effizient zu erkunden, um geeignete Lösungen zu finden
• Techniken, die metaheuristische Algorithmen umfassen, reichen von einfachen lokalen Suchverfahren bis hin zu komplexen Lernprozessen
• Metaheuristische Algorithmen sind approximativ und in der Regel nicht-deterministisch
• Sie können Mechanismen enthalten, die vermeiden, dass sie in begrenzten Bereichen des Suchraums gefangen werden
• Die grundlegenden Konzepte der Metaheuristik erlauben eine Beschreibung auf abstrakter Ebene
• Metaheuristiken sind nicht problemspezifisch
• Die Metaheuristik kann Domänenwissen (beispielsweise aus dem Feld der Intralogistik) in Form von spezialisierteren Heuristiken nutzen, die von einer darüber angesiedelten Strategie gesteuert werden

Um zur Detektivarbeit zurückzukommen: Ein metaheuristischer Sherlock würde in kurzer Zeit möglichst viele Personen identifizieren, die mit relativ hoher Wahrscheinlichkeit auch Verbrecher sind, indem er spazieren geht und dabei mit seinen Analysefähigkeiten nach relevanten Datenpunkten Ausschau hält. Doch das ist keine kluge Verwendung der Zeit eines Sherlock Holmes, wenn man für das Problem auch Polizeistreifen einsetzen kann.

Das Feld der Metaheuristiken umfasst viele Methoden und Verfahren, die in diesem Beitrag nicht alle besprochen werden können. Die folgende Grafik soll aber zumindest einen ersten Überblick ermöglichen.

In der Intralogistik ist die Knappheit der Ressourcen Zeit und Rechenleistung ein Dreh- und Angelpunkt aller Optimierungsprozesse: Immer mehr kleinteilige Bestellungen müssen möglichst schnell den Pfad von Wareneingang bis -ausgang durchlaufen. Dadurch ist es oft nicht möglich, die optimale Lösung zu finden, wohl aber eine optimierte. Diese Herausforderung wird auch durch die sieben R der Logistik beschrieben:

• Das richtige Produkt
• im richtigen Zustand
• zum richtigen Zeitpunkt
• beim richtigen Empfänger
• in der richtigen Menge
• mit den richtigen Informationen
• mit den richtigen Kosten

Im Bereich der Forschung werden häufig keine realen Daten verwendet, sondern Szenarien modelliert, die ein idealisiertes Lagerlayout verwenden – was auch der Tatsache geschuldet ist, dass Unternehmen nur selten den Zugriff auf diese Daten gewähren. Die Szenarien der Logistik-Branche sind im Vergleich zu den Versuchsanordnungen in der Forschung deutlich komplexer. So behandelt der 2015 erschienene Beitrag „An efficient hybrid algorithm for integrated order batching, sequencing and routing problem“ von Chen, T.-L. et al ein Lager mit zwölf Regalfächern, mit Platz für jeweils einen Artikel, das maximal acht Aufträge mit maximal zehn Items berücksichtigen muss. Ein modernes Distributionszentrum dagegen hat häufig Raum für mehr als 100.000 Lagerplätze, durch die Batchbildungen von 5.000 bis zu 10.000 Artikel zustande kommen können.

Eine Metaheuristik, die in kleinen Szenarien schnell zu zufriedenstellenden Lösungen kommt, kann an komplexen Szenarien scheitern. Daher ist es wichtig, mit möglichst hochwertigen und großen Datenmengen zu arbeiten.

Der Weg zum Erfolg, um eine möglichst effiziente Lösung zu finden, liegt in der möglichst individuellen und präzisen Definition der Geschäftsprozessbedingungen: Welcher Aspekt soll optimiert werden? Welche Grenzen sowie Randbedingungen der Optimierung gibt es und wieviel Ressourcen stehen zur Verfügung, bis eine Verbesserung erzielt werden muss?

In manuellen Lagern mit dynamischer Lagerhaltung, sollen beispielsweise die Laufwege minimiert werden, indem die Gangwechsel so gering wie möglich gehalten werden. Um das erfolgreich zu leisten, müssen die Nebenbedingungen genau definiert werden: Was ist die maximale Größe eines Batches? Was ist die maximale Artikelmenge eines bestimmten Typs oder die maximale Menge an Einzelbestellungen? Der Solver ist das Programm, das eine oder mehrere (Meta-)Heuristiken oder Algorithmen unter Berücksichtigung der Bedingungen anwendet, um eine Annäherung an ein definiertes Ziel zu erreichen.

Ein Algorithmus bezeichnet eine systematische, logische Regel oder Vorgehensweise, die zur Lösung eines vorliegenden Problems führt. Im Gegensatz dazu steht dabei die schnellere, aber auch fehleranfälligere Heuristik.

Stangl, W. (2020). Stichwort: ‘Algorithmus’. Online Lexikon für Psychologie und Pädagogik.

Während ein Algorithmus eine logische Kette durchläuft, die dadurch auch sehr lange und ressourcenintensiv sein kann, durchläuft eine Heuristik viele kleine Zyklen, die schneller berechnet werden können und die in folgendem Beispiel durch Wahrscheinlichkeiten am Laufen gehalten werden.

Im Fall des erwähnten ‚Simulated Annealing‘ wird eine Verbesserung immer akzeptiert und der Zyklus erneut durchlaufen. Eine Verschlechterung wird dagegen nur mit einer bestimmten Wahrscheinlichkeit angenommen. Dadurch kann ein globales Maximum oder Minimum schnell identifiziert werden, da die Startlösung immer der Endwert eines vorherigen Zyklus ist. Die Bezeichnung ‘annealing’ entlehnt sich hier dem auf Deutsch als ‘Glühen’ bezeichneten Prozess, in dem ein Werkstoff erst angewärmt, dann auf einer bestimmten Temperatur gehalten und geformt wird, um anschließend abgekühlt zu werden. Durch das kontrollierte Aufwärmen und Abkühlen wird sichergestellt, dass sich das Material möglichst nahe am gewünschten Festigkeitswert befindet. ‘Simulated annealing’ nutzt einen globalen Minimal- oder Maximalwert, um eine Lösung anzustreben. Über diesen Link zu einer archivierten Seite können Lösungen für das Handlungsreisenden-Problem sowohl mit einem Temperaturmaximum, als auch einem -minimum erreicht werden.

In der Intralogistik ist eines der Standard-Probleme das des Handlungsreisenden, der für seine Verkaufstour die effizienteste Route wählen möchte. In diesem Beispiel wird ‚Simulated Annealing‘ eingesetzt, um eine Route zu finden, die alle 125 Punkte verknüpft, ohne einen Punkt zwei Mal anzufahren.

Dieses Beispieldiagramm zeigt den Ablauf hinter dem animierten Bild.

Bei einem neuen Problem wird zunächst durch Testläufe ein passendes Verfahren zum Finden einer guten Startlösung sowie ein geeigneter Parameter β, der beeinflusst, wie schnell in diesem Fall die Erhitzung geschieht, bestimmt. Eine zu schnelle Erhitzung verkleinert den Suchraum zu stark, eine zu langsame kann dazu führen, dass auch globale Optima wieder verlassen werden können.

Um ein solches Solver-Konstrukt anzuwenden, werden folgende Bausteine benötigt.

Dabei ist der Solver selbst zwar das zentrale, aber nicht das kritische Element. Nur, wenn die Auftragsdaten in ausreichender Menge und Qualität vorhanden sind und die Nebenbedingungen sowie Parameter individuell auf die intralogistischen Geschäftsprozesse des jeweiligen Lagers angepasst wurden, kann eine wertschöpfende Lösung gefunden werden. Sonst gilt das klassische Problem eines jeden Optimierungsprozesses: „Garbage in, garbage out“. Die korrekte Anwendung des intralogistischen Domänenwissens auf der Ebene der Strategie, der Parameter und der Daten ist die Voraussetzung für eine effiziente Solver-Konfiguration.

Die Mathematik dahinter findet sich oft in öffentlich zugänglichen Quellen, doch der Schlüssel ist die individuelle Anpassung und Parametrierung, die die Projektpartner auf Augenhöhe gemeinsam erarbeiten. Denn Distributionszentren sind komplexe Systeme, in denen für Menschen Optimierungspotentiale und aktuelle Betriebszustände oft noch nur durch maschinelle Aufbereitung zu erkennen sind.

Durch gemeinsame iterative Entwicklung wird sichergestellt, dass die Parameter Zielbedingung, Auftragsdaten und Nebenbedingungen die höchstmögliche Qualität haben. Denn je nach eingesetztem Solver, können unterschiedliche Lösungen in unterschiedlicher Geschwindigkeit zustande kommen. Standardisierte Lösungen stoßen hier auf Grund der fehlenden Anpassung schnell an ihre Grenzen.

Der Schlüssel zu schnellen und optimierten Ergebnissen sind daher Solver, die an die verschiedenen Prozesse und Situationen des Lagers angepasst sind. Je nach eingesetzter Methode können bei gleichen Rahmenbedingungen unterschiedliche Ergebnisse erreicht werden. So kann die Batchbildung durch einen Solver erfolgen, die Routenplanung des Pickers aber durch einen anderen, um sicherzustellen, dass die Ergebnisse durch individuelle Anpassung möglichst schnell und qualitativ hochwertig sind, ohne dafür viel Rechenzeit oder -leistung in Anspruch zu nehmen. Auch situationsbasierte Solverlösungen für Volllast und Teillast sind denkbar, da auch hier Sonderbedingungen herrschen, die durch eine Standardlösung nur unzureichend gelöst werden können.

Metaheuristiken sind ein hervorragendes Werkzeug, um intralogistische Prozesse zu optimieren. Sie können aber nur funktionieren, wenn die Auftragsdaten in hoher Qualität vorliegen und die Parameter individuell an die Situation sowie die Geschäftsprozesse angepasst sind. Die bestmögliche Effektivität dieser Solver kann nur dann erreicht werden, wenn zwischen den Projektpartnern auf Augenhöhe und transparent kommuniziert wird und die Testimplemtierungen mit echten, hochwertigen Daten durchlaufen werden.

Zurück zur Startseite

Zu unseren weiteren Blogbeiträgen

Zu unseren Software-Lösungen