Mathematik-Gebäude, Seminarraum M511

Eine Schwierigkeit bei der Modellierung von praxisnahen Problemen ist die Erfassung von Daten wie Kosten oder Nebenbedingungen. Diese Daten sind meist unvollständig, variieren über die Zeit oder können nicht exakt erhoben werden. Gängige Methoden, um mit diesen Unsicherheiten umzugehen, sind die Stochastische Optimierung, bei der z.B. die erwarteten Kosten minimiert werden, und die Robuste Optimierung, die sich gegen den ungünstigsten Fall absichert. Robuste Lösungen tendieren dazu teuer zu sein und vernachlässigen die Möglichkeit, auf eingetretene Situationen mit limitierten Maßnahmen zu reagieren. Recoverable Robuste Optimierung erweitert das Konzept der Robusten Optimierung um diesen Aspekt.
In meinem Vortrag führe ich drei Recoverable Robuste Modelle für kombinatorische Optimierungsprobleme ein, die sich in der Art der Recovery und in ihren Zielfunktionen unterscheiden, um die Modellierungsmöglichkeiten dieser Methode zu verdeutlichen. Für diese Modelle stelle ich die wichtigsten Ergebnisse bzgl. des Komplexitätsstatus und der kombinatorischen Eigenschaften in Abhängigkeit des gegebenen Optimierungsproblems und der betrachteten Unsicherheiten vor. Dabei zeigt sich, dass schon kleine Veränderungen der Problemstellung, z.B. die Einschränkung der zulässigen Lösung von einfachen Wegen auf beliebige Wege, das Recoverable Robuste Problem von ``in polynomieller Zeit lösbar`` zu ``nicht approximierbar`` verändern kann.
Desweiteren betrachte ich eine Anwendung eines dieser Modelle auf das Rangieren von Zügen im Güterverkehr. Der neue Ansatz ermöglicht Rangierpläne zu erstellen, die weniger Sortierschritte als die der gängigen robusten Methoden benötigen und die gleichzeitig durch geringe Veränderungen des Originalplans an die Verspätungen der eingehenden Züge angepasst werden können. Für die Berechnung dieser Rangierpläne stelle ich einen Algorithmus vor, dessen Laufzeit von den betrachteten Unsicherheitsmengen abhängt. Basiert die Unsicherheitsmenge auf der Verspätung von einer fixen Anzahl an Zügen, ist seine Laufzeit polynomiell. Im Allgemeinen ist dies nicht der Fall, da das Recoverable Robuste Rangierplan-Problem stark NP-vollständig ist. Zum Abschluss werden die Auswirkungen dieses neuen Ansatzes im Vergleich zu rein Robusten Lösungen in mehreren auf Praxisdaten beruhenden Experimenten ausgewertet.

Dr. Christina Büsing

TU Berlin