Simulated Annealing – wie ein Algorithmus aus der Festkörperphysik komplexe Business Probleme lösen kann

Walter Maderner | September 4, 2018

Manche Probleme lassen sich mit Erfahrung und Standard-Tools allein nicht lösen

Im Geschäftsumfeld so gut wie jeder Industrie treten im Bereich Design und Planung komplexe Problemstellungen auf, die mit den üblichen Management-Tools und mit der Erfahrung der Mitarbeiter einfach nicht zu lösen sind. Diesen Problemstellungen ist gemeinsam, dass die potenziellen Lösungen durch eine reichhaltige Kombinatorik erzeugt werden und sie in der Gesamtheit nicht mehr zu überblicken sind.

 

Viele Wege führen nach Rom

Das klassische Beispiel dafür ist das Problem des Travelling Salesman: Ein Travelling Salesman wird aufgefordert eine vorgegebene Anzahl von Städten so zu bereisen, dass die zurückgelegte Reiseroute, und damit Zeit und Kosten minimal werden. Diese Aufgabe scheint auf den ersten Blick einfach, sie ist es aber nicht. Ein kurzes Rechenbeispiel illustriert warum. Bei drei Städten gibt es sechs mögliche Routen, und mit freiem Auge ist zu sehen welche die kürzeste ist. Bei fünf Städten sind es bereits 120, bei 10 Städten 3,6 Millionen und bei 15 Städten gar 1,3 Milliarden. Es ist unmöglich die kürzeste Route mit freiem Auge zu erkennen. Auch mit einem Spreadsheet stößt man bald an Grenzen. Was in der Praxis passiert, ist, dass mit „Erfahrung“ und „Bauchgefühl“ eine Lösung einfach erraten wird. Doch oft sind diese Lösungen weit weg vom Optimum. Zeit und Geld werden so auf dem Altar der Bauchentscheidung unnötig geopfert.

Das Problem des Travelling Salesman ist nur ein illustratives Beispiel für eine Klasse von Problemstellungen, die in vielfältiger Gestalt im Unternehmen und dessen Geschäftsumfeld auftreten können. Charakteristisch für diese Problemstellungen ist die oben schon erwähnte reichhaltige Kombinatorik von Konfigurationen, die in ihrer Gesamtheit nicht mehr sinnvoll erfasst werden können. Um aus den Konfigurationen eine Lösung zu finden, gibt es eine Bewertungsfunktion, die jeder Konfiguration einen bestimmten Wert zuordnet. Dieser Wert kann Kosten, Zeit, Energie, Länge oder eine andere problemadäquate Größe symbolisieren. Gesucht ist dann jeweils jene Konfiguration, an der die Bewertungsfunktion den geringsten Wert annimmt, also die kostengünstigste, schnellste, energetisch niedrigste oder kürzeste Lösung. Im Falle des Travelling Salesman ist die jeweils kürzeste Route gefragt. Zusätzlich können auch Randbedingungen gesetzt sein, unter denen die optimale Lösung zu suchen ist. So kann man im Beispiel des Travelling Salesman spezifische Zeitfenster festsetzen, in denen die jeweiligen Städte besucht werden müssen.  

 

Komplexe Problemstellungen trifft man häufig in Design, Planung und Disposition an

Die untenstehende Tabelle veranschaulicht an ein paar Beispielen, wo solche Problemstellungen üblicherweise auftreten können. Mittels Simulated Annealing können diese Optimierungsaufgaben gelöst werden.

 

Match-Making/Angebotsdesign

Optimierung einer Vielzahl von Angebots Parametern in Bezug auf Produktionskosten und Nutzenfunktion einer Kundenzielgruppe

Netzwerkplanung Logistik

Optimierung der Anzahl und Lage Standorte in Bezug auf die Lieferzeiten und Netzwerkkosten

Netzwerkplanung Filialen

Optimierung der Anzahl und Lage Standorte in Bezug auf Kosten, Marktpotenzial und gegenseitige Kannibalisierung

Flächenlayout Produktion

Optimierung der Flächenausnutzung Produktion bei gleichzeitiger Minimierung der innerbetrieblichen Transportwege

Chipdesign

Optimierung der Schaltkreise – Vermeidung von Überlappungen bei gleichzeitiger Minimierung der Länge der Verbindungen

Robotik Linie Produktion

Optimierung der Roboterbewegungen – maximale Taktung bei Minimierung von Richtungswechseln und Wegen

Just-in Sequence-Produktionsplanung (Automotive)

Planung der Produktionsaufträge bei maximaler Ausnutzung der Schicht Kapazitäten unter Beibehaltung größtmöglicher Flexibilität

Routenplanung

Planung der Zustellroute – Minimierung der Wegstrecke unter Berücksichtigung der ZustellZeitfenster

Terminplanung Servicetechniker

Zuordnung der Servicetechniker zu den Service Jobs (Qualifikation) unter Berücksichtigung minimaler Wegzeiten

Disposition Zusteller

Zuordnung von Kundenaufträgen zu Zustellern im Hinblick auf die Optimierung von Zustellkosten

Airline Crew Pairing

Zuordnung der Crew zu Flügen unter Berücksichtigung des Crew Standortes und der maximalen Einsatzzeit

 

Diese Liste ließe sich beliebig fortsetzen. Was man aber gut erkennen kann, ist dass in den Bereichen Design und Disposition/Planung solche Problemstellungen mannigfach auftreten.

Wenn es aber so viele Konfigurationen gibt, dass man nicht alle gesamthaft erfassen kann, wie lassen sich diese Problemstellungen dann lösen?

 

Simulated Annealing – wenn die Physik dem Management zur Hilfe kommt

Problemstellungen dieser Art nennt man in der Informatik NP-Probleme. NP-Probleme lassen sich nicht mit Computeralgorithmen in polynomialer Rechenzeit berechnen. Anders gesagt: Kein Algorithmus kann in vernünftiger Zeit eine exakte Lösung liefern. Doch wenn man keine exakte Lösung berechnen kann, kann man eine sehr gute Lösung berechnen?

Der Ausweg aus dem Dilemma ist ein iterativer Algorithmus, der auf heuristischem Weg eine möglichst gute, oft auch die exakte Lösung liefert. Eine Anleihe hat die numerische Mathematik dabei bei der Festkörperphysik genommen. Der Algorithmus heißt Simulated Annealing und ist mittlerweile zu einem der stärksten Algorithmen in der numerischen Mathematik geworden. Von der Idee her modelliert der Algorithmus das in der Metallverarbeitung seit jahrhunderten bewährte Verfahren der kontrollierten Erwärmung und des graduellen Abkühlens. Bei dieser Art von Wärmebehandlung wird das Metall auf Temperatur gebracht. Das Erwärmen führt zu einer Mobilisierung der atomaren Strukturen. Langsames Abkühlen ermöglicht den so mobilisierten Atomen besser, einen Zustand niedrigster freier Energie zu erreichen. Als Resultat davon wird das Metall homogener und spannungsfreier und ist im Allgemeinen deutlich besser zu verarbeiten.

Umgelegt auf das Traveling Salesman Problem geht man nach der Simulated Annealing Methode folgendermaßen vor: Die zu optimierende Konfiguration wird „geschmolzen“, also formal auf Temperatur gebracht um den größtmöglichen Spielraum bei der Tourenbildung zu erlauben. Ausgehend von einer beliebigen Anfangskonfiguration der Tour simuliert man in Analogie zur Physik die thermische Bewegung der Atome durch schrittweise kleine Änderungen an der Route. Dies geschieht etwa durch Vertauschung der Reihenfolge von zwei zu bereisenden Städten. Eine Akzeptanzregel bewertet dann, ob die neue Tour für die Iteration zulässig ist: Sie ist es dann, wenn die neue Tour kürzer oder nur ein wenig länger als die vorhergehende ist. Dabei wird die Akzeptanz einer längeren Route durch die formale Temperatur bestimmt und geht mit fallender Temperatur gegen null. Die Analogie zur Physik besteht darin, durch thermische Bewegung Energiebarrieren zu überwinden und so das energetische Minimum zu erreichen. Dadurch stellt man sicher, dass das System nicht in einem Nebenoptimum hängen bleibt. Was es bedeutet in einem Nebenoptimum hängen zu bleiben sieht man am Schicksal des  müden Wanderers, der ins Tal will und nur bergab gehen kann: Er wird in den Bergen hängen bleiben, weil er am Weg ins Tal die kleine Kuppe nicht mehr überwinden kann.

Über die Anwendung der Akzeptanzregel werden iterativ in der oben beschriebenen Art und Weise immer bessere Lösungen gefunden, und mit fallender Temperatur werden schlussendlich nur Lösungen für die Tour akzeptiert die kürzer als die vorangegangene Tour sind -- das System erstarrt und das Minimum (oder zumindest: eine sehr sehr gute Lösung) ist gefunden. Wie sich der Algorithmus in einem Praxisbeispiel bewährt, lesen Sie am Besten im Premium Artikel nach.

 

Auf welche Problemstellungen ist Simulated Annealing anwendbar?

Die oben angeführten Beispiele geben einen Überblick über die Vielzahl von Problemstellungen, die mit Simulated Annealing gelöst werden können. Doch was haben diese Beispiele gemeinsam? Hier die bestimmenden Kriterien für die Anwendbarkeit:

  • Umfangreicher diskreter Konfigurationsraum. Die Anzahl der Konfigurationen, die als potenzielle Lösungen in Frage kommen, muss hinreichend reichhaltig sein (sonst wäre das Problem ja trivial). Ein Indiz dafür ist, dass sich die Konfigurationen nicht mehr sinnvoll in einer Datenbank erfassen lassen. Die Kombinatorik ist so reichhaltig, dass sich die Lösungen nicht mittels Brute-Force errechnen lassen, ohne unverhältnismäßig hohen Zeitaufwand zu betreiben. Umgekehrt muss man aber jede der Konfigurationen über ein Verfahren aus jeder anderen Konfiguration erzeugen können. Im Falle des Travelling Salesman kann man bei 30 Städten alle Konfigurationen nicht mehr gesamthaft erfassen. Jede Route lässt sich aber durch Vertauschung von Städten aus jeder anderen beliebigen Route erzeugen.
  • Bewertungsfunktion. Es muss eine Größe geben, in Bezug auf welche die Konfigurationen bewertet werden können. Wie oben erläutert, können dies Kosten, Zeit, Länge, Energie oder jeder problemadäquate Parameter sein.
  • Randbedingungen. Typischerweise gibt es bei den meisten Problemstellungen Randbedingungen, welche die möglichen Konfigurationen einschränken. So kann man beim Beispiel des Travelling Salesman Zeitfenster vorgeben innerhalb derer einzelne Städte besucht werden müssen. Im Falle des Airline Crew Pairing wäre die Randbedingung diese, dass der erste Flug auf der Home Base der Crew startet und der letzte Flug dort landet.

Sind diese Voraussetzungen gegeben, dann lässt sich das Problem mit Simulated Annealing lösen, und man darf bei hinreichender Komplexität erwarten, signifikant bessere Lösungen als die über Bauchentscheidungen getroffenen zu erhalten.

 

One size fits none

Wenn Sie ein Business Problem dieser Art in Ihrem Unternehmen identifiziert haben, das aktuell „manuell“ gelöst wird, also z.B. durch einen Disponenten im Falle der Tourenplanung oder der Einteilung der Servicetechniker, dann können Sie davon ausgehen, dass eine unterstützte Optimierung über Simulated Annealing zu deutlichen Verbesserungen führen wird.

Aktuell gibt es im Bereich der Routenplanung fertige Softwarelösungen am Markt. Diese Routenplaner haben aber oft den Nachteil, dass spezifische Randbedingungen oft nicht so wie gewünscht abgebildet werden können. Bei anderen Anwendungsbereichen gibt es Off the Shelf nichts wirklich Brauchbares. Der Grund liegt auf der Hand: Der Algorithmus muss maßgeschneidert an das Problem angepasst werden, und der Customizing Aufwand einer Standard-Lösung wäre so hoch, dass man den Algorithmus gleich neu programmieren kann. Dieser Aufwand ist aber beherrschbar.

Fazit: Unserer Erfahrung nach zahlt sich der Aufwand einer individuellen Lösung mit Sicherheit aus. Die maßgeschneiderten Lösungen führen oft zu Verbesserungen im zweistelligen Prozentbereich.

 

New Call-to-action

Über den Autor

Walter Maderner

Dr. - Partner, Wien

Kommentare