Simulated Annealing in der Praxis: Minimierung von Zustellkosten durch optimierte Auftragsallokation

Michael Schwarzmann | Juni 19, 2019

Ein Logistikdienstleister steht vor der Herausforderung, seine Zustellplanung so zu gestalten, dass vorgegebene Liefertermine eingehalten werden und Aufträge möglichst intelligent gebündelt werden, um Zeit und Kosten zu sparen. So trivial diese Aufgabe erscheinen mag, so komplex ist es, sie zu lösen. Bei Billionen von möglichen Varianten, die Aufträge zu kombinieren, versagt jedes Spreadsheet und auch Erfahrung und Bauchgefühl liefern meist nur suboptimale Lösungen. Mittels Simulated Annealing können derartige Optimierungsaufgaben clever gelöst werden.


Wenn die Festkörperphysik dem Komplexitätsmanagement zur Hilfe kommt

Simulated Annealing ist ein iterativer Algorithmus zur Lösung von überbordend komplexen Managementaufgaben, der seinen Ursprung in der Festkörperphysik hat: In der Metallverarbeitung wird das Verfahren des kontrollierten Erhitzens und langsamen Abkühlens vielfach eingesetzt, um das Material weicher und flexibler zu machen bzw. um Unregelmäßigkeiten in der Struktur zu vermeiden. Indem das Metall kontrolliert erhitzt wird, werden die Gitteratome mobilisiert und können Energiebarrieren überwunden werden. Während es langsam wieder abkühlt, sucht sich das Metall eine homogene Struktur, die energieeffizienter ist und weniger Spannung und damit versteckte Energie enthält als der Ausgangszustand.

Im Management-Kontext hat sich Simulated Annealing als geeignete Methode zur Lösung schwieriger Optimierungsprobleme bewährt. Ausgehend von einem zufällig gewählten Startpunkt S0 werden alternative Lösungen, wie Sn, in dessen Umgebung gesucht. Ist die Alternative Sn besser als die ursprüngliche Lösung S0, wird sie als neuer Ausgangspunkt übernommen. So weit, so logisch. Der Clou dabei ist allerdings, dass das Verfahren bis zu einem gewissen Grad auch Verschlechterungen akzeptiert. Dadurch wird sichergestellt, dass lokale Täler verlassen werden können, um in Richtung globales Optimum vorzustoßen. Mit sinkender Akzeptanzwahrscheinlichkeit – analog zur langsam sinkenden Temperatur in der Metallverarbeitung – wird die Wahrscheinlichkeit eine Verschlechterung zu akzeptieren, sukzessive reduziert, wodurch am Ende ein Optimum eruiert werden kann.

Bild1

Genauere Ausführungen zur Funktionsweise des Verfahren sowie eine Liste möglicher Anwendungsbereiche finden Sie im entsprechenden Artikel.

 

Simulated Annealing am Beispiel des Optimierungsproblems eines Logistikdienstleisters

Im Folgenden veranschaulichen wir Simulated Annealing anhand eines konkreten Business Case aus unserer Beratungspraxis, der beispielhaft für die modernen Problemstellungen in so gut wie jeder Industrie ist. Im Fall unseres Klienten, einem Logistikdienstleister, der Broschüren ausliefert, bestand die Herausforderung darin, die Auftragsallokation auf eine Minimierung der Zustellkosten hin zu optimieren – eine Herkulesaufgabe angesichts des Komplexitätsgrades der Problemstellung und der Ressourcenknappheit bei der Lösungsfindung. Konkret stellte sich die Situation zu Beginn unseres Beratungsprojekts folgendermaßen dar:

  • Die Optimierung der Wochenplanung des Zustellpersonals in 1.400 verschiedenen geografischen Teilgebieten lag in der Verantwortung von drei Vollzeitkräften.
  • Die Planung erfolgte weitgehend manuell – unterstützende technische Tools standen nur bedingt zur Verfügung.
  • Im Durchschnitt konnten die Mitarbeiter maximal fünf Minuten aufwenden, um Problemstellungen zu bearbeiten, für die es Billionen von möglichen Lösungswegen gibt.

Hinzu kommt eine Reihe an Bedingungen, die in jedem möglichen Lösungsszenario zwingend erfüllt werden müssen. Diese betreffen:

  • Das Höchstgewicht einer einzelnen Lieferung
  • Die maximale Anzahl an pro Lieferung zustellbaren Broschüren
  • Eine Reihe von Ausnahmeregelungen für bestimmte Arten von Broschüren

 

Charakteristika eines Anwendungsfalls für Simulated Annealing

Dass sich eine derart komplexe Aufgabe mit standardmäßigen Management-Tools und Erfahrung allein nicht lösen lässt, liegt auf der Hand. Dass Simulated Annealing eine Methode ist, die sich besonders gut zur Lösungsfindung dieses Problems eignet, ergibt sich aus folgenden Charakteristika der Aufgabenstellung:

  • Eine reichhaltige Kombinatorik, aus der sich eine Vielzahl an potenziellen Lösungen ergibt
  • Eine Vielzahl von einschränkenden Bedingungen, die jedenfalls erfüllt werden müssen
  • Zeit als limitierenden Faktor für die Berechnung
  • Den Anspruch, eine bessere und nicht zwangsläufig die optimale Lösung zu finden
  • Die Unmöglichkeit, dass herkömmliche Ansätze in vernünftiger Zeit eine brauchbare Lösung zu liefern

 

Modifizierter Simulated Annealing Algorithmus führte zu verbesserter Planung

Um konkret auf die Problemstellung unseres Klienten eingehen zu können, haben wir die Parameter der Kalkulation entsprechend den Rahmenbedingungen angepasst und den Algorithmus so modifiziert, dass unter Einhaltung aller Einschränkungen auch die notwendige Rechenzeit möglichst gering gehalten wird. Das Ergebnis: Die mittels Simulated Annealing errechnete Planung deckte im Vergleich zu den manuell geplanten Zustellungen ein Einsparungspotential von bis zu 9% der Gesamtkosten auf.

 

Key Takeaways einer optimierten Auftragsallokation

1. Signifikante und nachhaltige EBIT-Verbesserung erzielbar
  • In den getesteten Regionen konnten erhebliche Ergebnisverbesserungen erzielt werden.
  • Der Optimierungsalgorithmus wurde dokumentiert und der IT-Abteilung zur Implementierung in die operativen Betriebssysteme übergeben.

2. Aufgabenverlagerung innerhalb der Planungsabteilung
  • Die Automatisierung der Planungsaufgaben ermöglicht es dem Planungsteam, sich auf wertschöpfendere Aufgaben zu konzentrieren:
    • Trouble Shooting, z.B. Neuplanung bei Krankheitsfällen
    • Überarbeitung von automatisiert erzeugten Vorschlägen im Fall von kurzfristigen (Zusatz-)Auftragseingängen
  • Abweichungsanalyse und verursachungsgerechte Quantifizierung der verursachten Mehrkosten
    • Gemeldetes vs. tatsächliches Gewicht
    • Angekündigtes Lieferdatum vs. tatsächliches Lieferdatum
  • Szenarioanalysen zur gesamthaften Ressourcenplanung über einzelne Gebiete und Zustellwochen hinweg

Fazit: Durch die Verbesserungen, die mithilfe des maßgeschneiderten Simulated Annealing Algorithmus erzielt werden konnten, hat sich der konzeptive Aufwand allemal rentiert. Das zeigt: Komplexe Probleme erfordern sophistizierte Lösungsansätze. Mit Standard-Tools und fertigen Softwarepaketen kommt man gegen die Herausforderungen moderner Problemstellungen heute nicht mehr an. Wo herkömmliche Managementmethoden versagen, braucht es oft die Inspiration aus anderen Disziplinen, um innovative Lösungen zu entwickeln und in jedem Fall: Den Mut, neue Wege zu gehen.

 

New Call-to-action

 

 

 

Über den Autor

Michael Schwarzmann

Manager bei GCI Management

Kommentare

Wie Big Data und KI Ihrem Unternehmen nutzen