Many Travel Images Collage

„Wohin die Reise geht“ oder
„Ein kurzer Ausblick zur Blogreihe Custom Heuristic vs Standard-Solver“

Zur Lösung eines Optimierungsproblems gibt es verschiedenste Strategien. Zu entscheiden, welches Lösungsverfahren das passende für welches Problem ist, erfordert sehr viel Erfahrung. Unser OR-Team stellt vor allem bei komplexen Problemen seine Expertise immer wieder unter Beweis.

Unsere Blogreihe „Custom Heuristic vs Standard-Solver” befasst sich mit den verschiedensten Aspekten, die die Wahl der richtigen Lösungsstrategie beeinflussen, um so kurz zu skizzieren, wie komplex die Entscheidung für ein Lösungsverfahren sein kann. In diesem ersten Beitrag beschäftigen wir uns mit Custom Heuristic als praktikable Alternative zum mathematisch exakten Optimierungsverfahren, bei der Optimierungsprobleme mit Hilfe der Mathematik auf analytischem Weg berechnet werden. Dieses Optimierungsverfahren bezeichnen wir synonym als Optimierungsverfahren mit Standard-Solver und wird in einem weiteren Blogbeitrag näher beschrieben. Ein dritter Beitrag thematisiert „Best of Both Worlds“ und schließt so das Thema „Custom Heuristic vs Standard-Solver“ ab.

Beginnt denn jede Reise mit Problemen?

Stellen Sie sich vor, Sie planen eine Autoreise zu den schönsten Städten Europas. Welche Städte das sind, können Sie entscheiden. Und ob Sie hierfür einen Kurztrip oder eine längere Auszeit planen, liegt auch in Ihrer Hand. Eines jedoch ist klar: Um die Reise genießen zu können und viel von den Städten zu sehen, möchten Sie so wenig Zeit wie möglich im Auto verbringen. (Manchmal ist auch der Weg das Ziel, aber das ist ein anderes Thema…) Also stellt sich die Frage: Welche Reihenfolge der Städte ermöglicht die geringste Fahrtzeit und somit die schnellste Route? Dieses Problem – bekannt als Travelling Salesman Problem – ist ein typisches Optimierungsproblem, das in vielen verschiedenen Fragestellungen in der Realität zu finden ist:

  • In der Investionsplanung: „Welcher Standortausbau ist am sinnvollsten unter Berücksichtigung logistischer Aspekte?“
  • In der Routenplanung: „Wie plane ich die Route meiner Auslieferungen optimal?“
  • In der Produktionsplanung: „Wie sieht die beste Reihenfolge für meine Maschinenbelegung aus?“

Zurück zu Ihrer Europareise: Bevor die Fahrt beginnt, stehen Sie vor einem weiteren Problem: Das Auto muss gepackt werden. Egal, ob Kleinwagen, Limousine oder Bulli – irgendwann ist der Kofferraum voll. Sie müssen nun beurteilen, was von Ihnen auf der Reise wirklich benötigt wird bzw. was Ihnen wichtiger ist: Der Regenschirm für den Stadtbummel in London? Die Daunenjacke für den Aufenthalt im winterlichen Oslo? Oder doch der Sonnenhut für den Spaziergang in Sevilla?

Dieses Problem ist bekannt als Rucksackpackproblem (Knapsack problem) und – genau wie das TSP –auf viele reale Situationen übertragbar. Mit Hilfe der Lösung dieses Optimierungsproblems lassen sich viele Herausforderungen der Realität mathematisch klären. So ist beispielsweise der Bezug zur Logistik klar vorhanden, wenn sich die Frage stellt: „Wie belade ich einen LKW unter Berücksichtigung seiner Kapazität profitmaximierend mit Gütern, die sich in Wert und Größe unterscheiden?“

Probleme lösen mit Algorithmen und Erfahrung

Um reale Probleme – wie zum Beispiel das TSP oder das Knapsack Problem – zu lösen, kommen Algorithmen zum Einsatz. Doch welche Algorithmen sind die passenden für welches Optimierungsproblem? Ist eine Custom Heuristik besser geeignet oder doch eher der Algorithmus eines Standard-Solvers?

Viele Faktoren beeinflussen die Wahl der Algorithmen. So zum Beispiel

  • die Struktur des zu lösenden Problems
  • die Menge der möglichen Lösungen
  • der Formulierungs- und Modellierungsaufwand
  • vorhandenes Domänenwissen
  • der Zeitaspekt der Planungssituation
  • und natürlich die Lösung selbst:
    Reicht eine „gute“ Lösung – mit dem Wissen, dass ggf. bessere Lösungen zu finden wären oder ist das Ziel eine bewiesene „optimale“ Lösung?

Jedes Optimierungsproblem ist hinsichtlich dieser Aspekte individuell zu betrachten: Alle genannten Faktoren werden berücksichtigt und abgewogen, um für das Optimierungsproblem die beste Lösungsstrategie zu wählen. Unser OR-Expertenteam hat die hierfür nötige Erfahrung und ist somit bestens geeignet die richtige Auswahl der Strategie zu treffen.

Das Problem wird zum Modell

Einige der genannten Faktoren beeinflussen bereits die Modellierung des Optimierungsproblems und sind deshalb schon vor Erstellung des Modells richtungsweisend. Die grundsätzliche Herausforderung der Modellierung besteht darin, eine reale Fragestellung bzw. ein reales Problem in die Sprache der Mathematik zu übersetzen, um zunächst ein mathematisches Problem zu erhalten, das mit Methoden der Mathematik gelöst werden kann (mehr hierzu im Blogbeitrag Warum OPTANO Modeling). Die Genauigkeit der Beschreibung steht jedoch der Komplexität eines Modells und der damit verbundenen Performance gegenüber.

Es zeigt sich also, dass die genannten Faktoren und deren Auswirkungen genauestens gegen- und miteinander abgewogen werden sollten, um Entscheidungen hinsichtlich der passenden Lösungsstrategie treffen zu können.

Wann kommen Custom Heuristiken zum Einsatz?

Bei jedem Optimierungsproblem ist eine Menge von möglichen Lösungen bzw. ein Lösungsraum (auch Suchraum genannt) gegeben. Custom Heuristiken werden zum Auffinden einer Näherungslösung von Optimierungsproblemen bzw. zugehörigen Optimierungsmodellen eingesetzt. Dies bedeutet, dass man unter Einsatz von Custom Heuristiken ggf. keine optimale Lösung des Problems erhält. Beziehungsweise ist es nicht bekannt, ob die Lösung die beste ist, oder ob es bessere gibt. Somit ist eine an das Optimum angenäherte Lösung akzeptabel. Zum Ermitteln eines „genügend guten“ Ergebnisses unterscheidet man in Konstruktionsheuristik und Verbesserungsheuristik.

Konstruktionsheuristiken

Konstruktionsheuristiken dienen der Bestimmung einer (ersten) zulässigen Lösung, denn mit ihnen kann ein guter zulässiger Punkt (hoher Zielfunktionswert) konstruiert werden. Dies geschieht durch das sukzessive Festlegen von Lösungselementen.

Mögliche Konstruktionsheuristiken:

  • Zufallsverfahren
  • Greedy-Verfahren / Greedy-Agorithmus
  • Vorausschauende Verfahren
Greedy-Algorithmus (Gieriger Algorithmus)

Als Beispiel für Konstruktionsheuristiken betrachten wir den Greedy-Algorithmus näher: Dieser Algorithmus bearbeitet schrittweise das Problem, indem er Teillösungen konstruiert, welche zum jeweiligen Zeitpunkt das beste Ergebnis liefern. So findet er „gierig“ in jedem Schritt (ohne zurückzusetzen) eine lokale Optimallösung. Der Vorteil des Greedy-Verfahrens ist die Laufzeit. Es führt schnell zu einer „ausreichend guten“ Lösung. Nachteilig ist die Nichtberücksichtigung früherer Lösungen, die eventuell besser waren. Somit ist das Ergebnis selten eine optimale Lösung.

Fazit: Das Greedy-Verfahren ist ein plausibler Algorithmus, der zu einer guten Lösung führt. Vor allem, wenn bei seiner Erstellung sogenanntes Domänenwissen (Kenntnisse über das Problem und Erfahrungswerte) einfließt.

Verbesserungsheuristiken

Verbesserungsheuristiken sind lokale Suchverfahren und werden verwendet, wenn bereits eine zulässige Startlösung – z. B. durch Konstruktionsheuristiken – bestimmt wurde. Die Verbesserungheuristiken führen durch sukzessive Lösungstransformationen oder „schlaues“ Ausprobieren zu verbesserten (lokal optimalen) Lösungen.

Mögliche Verbesserungheuristiken:

  • Genetischer Algorithmus
  • Simulated Annealing
  • Ameisen-Algorithmus
Genetischer Algorithmus

Als Beispiel für Verbesserungsheuristiken betrachten wir Genetische Algorithmen (GA) näher: Diese Algorithmen eignen sich vor allem bei Problemen, deren Struktur eher unbekannt und die Menge möglicher Lösungen sehr groß ist. Genetische Algorithmen sind an die biologische Evolution und an die Genetik angelehnt (daher auch die entsprechende Terminologie): Die Anpassung an veränderte Umweltbedingungen wird als Optimierungsproblem und entsprechend die Evolution als Lösung interpretiert.
GAs übernehmen die Strategie der Evolution zur Lösung von Problemen: Neue Generationen (von Lösungsvorschlägen) werden erzeugt und solange – durch Mutation und Crossover – verändert und kombiniert bis eine „genügend gute“ Lösung gefunden wird.

Fazit: GAs liefern nicht immer die optimale Lösung des Problems. Eine suboptimale Lösung kann nicht überwunden werden, wenn die – durch Crossover und Mutation hervorgebrachten – Änderungen nicht ausreichend stark sind. Ein weiterer Kritikpunkt ist der hohe Rechenaufwand, der durch das wiederholte Erzeugen neuer Generationen verursacht wird. Ist jedoch eine Näherungslösung akzeptabel, so fällt die Laufzeit gegenüber mathematisch exakten Verfahren unter Verwendung von Standard-Solvern nicht so sehr ins Gewicht. Zudem fällt bei Genetischen Algorithmen nur ein sehr geringer Formulierungs- und Modellierungsaufwand an.

Grafik Custom Heuristic

Abbildung – Custom Heuristic

Fazit zur Custom Heuristic

Bei komplexen Optimierungsproblemen wie dem Travelling Salesman Problem und dem Knapsack Problem, ist eine optimale Lösung mit einem vertretbaren Zeitaufwand oft nicht zu erzielen. In diesen Fällen genügt meist eine suboptimale Lösung: Also ein lokales Optimum, das sich dem globalen Optimum nähert. Somit ist der Einsatz von Custom Heuristiken eine praktikable Alternative, wenn eine „genügend gute“ Lösung ausreicht. Beziehungsweise wenn berücksichtigt wird, nicht zu wissen, ob ggf. bessere Lösungen zu finden wären. Mit dem Bewusstsein, dass dieses „Trial and Error“ eine höhere Fehlerquote enthält, ergeben sich bei Custom Heuristiken aber noch Vorteile:

Als Näherungsverfahren weisen Custom Heuristiken im Allgemeinen eine kurze Laufzeit auf – auch bei einem großen Lösungsraum. Verstärkt wird dies durch vorhandenes Domänenwissen, das in die Modelle zur Abbildung der Realität mit einfließen kann. Grundsätzlich erlaubt die Modellierung mit Custom Heuristiken mehr Freiheiten (im Vergleich zum Standard-Solver, für den ein lineares Optimierungsmodell Voraussetzung ist). Dies ermöglicht eine genauere Abbildung der Realität, Unschärfe wird so reduziert. Außerdem kann die Realität oft in kleineren Modellen abgebildet werden, weil beispielsweise keine aufwändige Linearisierung nicht-linearer Zusammenhänge erforderlich ist. Dies führt wiederum zu einer Steigerung der Performance.

Abschließend sollte noch der Aspekt geringerer Lizenzkosten erwähnt werden. Im Ergebnis müssen diese Kosten jedoch dem Aufwand der individuellen Implementierung (Custom) gegenübergestellt werden.

Custom Heuristic vs Standard-Solver?

Ein Vergleich benötigt mindestens eine Alternative. Aus diesem Grund erfahren Sie mehr über mathematisch exakte Verfahren unter Einsatz von Standard-Solvern im nächsten OPTANO Blogbeitrag.

Profitieren Sie von der jahrelangen Erfahrung unserer OR-Experten: Auch bei komplexen Optimierungsproblemen wählen sie die beste Lösungsstrategie.

Auch interessant…