Simulation unsicherer Optimierungsprobleme mit Anwendung in der Fahrplangestaltung und der Maschinenbelegung

Simulation unsicherer Optimierungsprobleme mit Anwendung in der Fahrplangestaltung und der Maschinenbelegung

Motivation und technischer Hintergrund

In den meisten praktisch relevanten Optimierungsproblemen treten Unsicherheiten auf: Oft sind nicht alle Parameter und benötigten Daten bekannt. In ökonomischen Problemen beispielsweise beruhen Preisentwicklungen, Absatzzahlen oder Nachfrageparameter meist auf Schätzungen, in technischen Problemen können physikalische Parameter oft nur mit gewissen Ungenauigkeiten bestimmt werden. Besonders schwierig ist es, unerwartete Störungen einzuplanen, wie sie im Verkehr oder bei der Abarbeitung von Großprojekten auftreten. Man bezeichnet eine realisierte Ausprägung der Parameter oder konkrete Störungen als ein Szenario

In diesem Projekt sollen Unsicherheiten oder Störungen schon während des Planungsprozesses mittels Simulation mit einbezogen werden. Dabei wird ausgenutzt, dass für ein festes Szenario meist effiziente Algorithmen zum Auffinden einer optimalen Lösung zur Verfügung stehen. Andererseits kann die Qualität einer festen Lösung durch Simulation unter verschiedenen Szenarien bewertet werden. Der Optimierungsprozess und die Simulation sollen in einem iterativen Prozess miteinander verbunden und zur Erzeugung robuster Lösungen oder guter Online-Strategien verwendet werden. Durch Einbeziehung gegebener Wahrscheinlichkeitsverteilungen auf der Szenariomenge können dabei die Nachteile der stark konservativen Strategien der robusten Optimierung und der Online-Optimierung abgeschwächt werden - damit entstehen neue Konzepte, die robuste und stochastische Optimierung miteinander verbinden, bzw. die in der Online-Optimierung den Gegner (Adversary) einschränken.

Das zu entwickelnde Verfahren zur Optimierung unter Unsicherheit soll für zwei konkrete Netzwerkprobleme aus dem Verkehr und der Logistik eingesetzt und an ihnen getestet werden:

  • Bei der Fahrplangestaltung im öffentlichen Verkehr soll es verwendet werden, um robuste (also wenig störanfällige) Fahrpläne zu erzeugen. Dabei soll anhand der realitätsnahen Daten aus Lin-Tim u.a. eine makroskopische Simulation der Verspätungen mit einer agentenbasierten Simulation verglichen werden.
  • Die einzelnen Produktionsstandorte des LKW Herstellers MAN und die Warenströme zwischen ihnen bilden ein ökonomisches Netzwerk, das vielen Unsicherheiten unterliegt. Das Verfahren soll eingesetzt werden, um mithilfe von Echtdaten der MAN Strategien zur besseren Synchronisation der einzelnen Stufen der zugrundeliegenden komplexen Produktionsnetzwerke zu entwickeln.

Stand der Technik

Sollen Unsicherheiten oder Störungen schon im Planungsprozess mit berücksichtigt werden, so spricht man allgemein von einem Optimierungsproblem unter Unsicherheit. Es gibt verschiedene mathematische Disziplinen, die sich mit der Optimierung unter Unsicherheit befassen: In der robusten Optimierung wird meist keine Wahrscheinlichkeitsverteilung der unsicheren Parameter vorausgesetzt. Man versucht, sich gegen den schlimmsten Fall abzusichern. Dagegen geht man in der stochastischen Optimierung von einer bekannten Wahrscheinlichkeitsverteilung aus und optimiert z.B. den erwarteten Fall. Ein anderes Ziel kann darin bestehen, die Wahrscheinlichkeit für eine unzulässige oder sehr schlechte Lösung zu minimieren. In der Online-Optimierung werden Strategien entwickelt, wie man mit Unsicherheiten zum Zeitpunkt ihres Auftretens umgehen soll. Diese drei Vorgehensweisen bei der Behandlung unsicherer Probleme werden meistens getrennt voneinander betrachtet. Einzelne neuere Arbeiten stellen solche Konzepte vergleichend einander gegenüber, so z.B. stochastische und robuste Optimierung und robuste, stochastische und Online-Optimierung.

Zu untersuchende Phänomene

Möchte man eine streng robuste Lösung finden oder eine kompetitive Online-Strategie, so muss bei der Auswertung einer Lösung bzw. Strategie jeweils der schlimmste Fall bestimmt werden: in der robusten Optimierung möchte man sich gegen den schlimmsten Fall absichern und die Kompetitivität wird in der Online-Optimierung ebenfalls im schlimmsten Fall bestimmt. Die grundlegende Idee unseres Ansatzes besteht nun darin, solche worst-case Szenarien zu nutzen, um iterativ die beiden folgenden Schritte durchzuführen: 

  • Für ein (oder mehrere) feste Szenarien wird eine robuste Lösung bzw. eine optimale Online-Strategie durch Optimierung bestimmt.
  • Für eine feste Lösung bzw. Strategie wird ihre Qualität durch Simulation ausgewertet und dabei ein worst-case Szenario für diese Lösung/Strategie bestimmt.

Das sich dabei während der Simulation ergebende worst-case Szenario kann dann als festes Szenario im Optimierungs-Schritt verwendet werden. Im Gegensatz zur simulationsbasierten Optimierung verwendet unser Verfahren die Simulation nicht einfach als Black Box sondern nutzt die aus der Simulation gewonnenen Erkenntnisse über worst-case Szenarien zur Ermittlung einer neuen Lösung bzw. Strategie.