Master

Methodische Fortschritte bei der Metaheuristik (Bachelor/Master)

Metaheuristiken sind ein derzeit weit verbreitetes Optimierungsverfahren in der Industrie, im Ingenieurwesen, in der Katastrophenhilfe usw. usw. Das Ziel der Arbeit ist es, eine tutorielle Zusammenfassung darüber zu geben, wie Metaheuristiken formal analysiert werden können, welche Schlussfolgerungen aus diesen Analysen gezogen werden können usw. Sie müssen ein oder mehrere ausgewählte Ergebnisse (z.B. das relevanteste, das interessanteste...)Jansen, T. (2013). Analyzing Evolutionary Algorithms The Computer Science Perspective. Springer.DeJong, K. (2006). Evolutionary Computation: A Unified Approach. MIT Press.

Literaturübersicht über den neuartigen ng-route Relaxationsansatz für Routingprobleme (Bachelor/Master)

Baldacci, Mingozzi und Roberti (2011) schlugen die ng-Routen als Kompromiss zwischen elementaren und nicht-elementaren Routen vor. Bei einer TSP-Route ist eine elementare Route eine Route, bei der jeder Kunde auf der Tour genau einmal besucht wird. Eine nicht-elementare Route lockert dieses Kriterium, indem sie einige Kunden mehr als einmal besucht oder einige Kunden in der endgültigen Tour auslässt. Die ng-Routen legen dynamisch berechnete Beschränkungen dafür fest, welche Kunden als nächstes besucht werden können. Diese Relaxation gehört zu den modernsten Pfad-Relaxationen für Routing-Probleme und ist der Schlüssel für die Entwicklung moderner Routing-Algorithmen.

Baldacci, Roberto; Mingozzi, Aristide; Roberti, Roberto (2011): New Route Relaxation and Pricing Strategies for the Vehicle Routing Problem. In: Operations Research 59 (5), S. 1269-1283.

Roberti, Roberto; Mingozzi, Aristide (2014): Dynamic ng-Path Relaxation for the Delivery Man Problem. In: Transportation Science 48 (3), S. 413-424.

Schnelle Lösung bestimmter Terminplanungsprobleme: Umwandlung in Gilmore-Gomory TSP (Bachelor/Master)

Gilmore und Gomory (1964) entwickelten einen brillanten Algorithmus, der einen Spezialfall des Problems des reisenden Verkäufers (TSP) in polynomieller Zeit lösen kann. Seitdem wurden der Algorithmus und das Problem in verschiedenen Bereichen wie der Terminplanung eingesetzt.  Ziel dieser Arbeit ist es, die Studien zu finden, zu überprüfen und zu kategorisieren, die den Gilmore-Gomory-Algorithmus bei Terminplanungsproblemen verwendet haben, und theoretische und praktische Erkenntnisse über ihre Anwendungen zu gewinnen.

* Gilmore, P. C., & Gomory, R. E. (1964). Sequencing a one state-variable machine: A solvable case of the traveling salesman problem. Operations Research, 12, 655-679.

* Bagchi, T. P., Gupta, J. N., & Sriskandarajah, C. (2006). A review of TSP-based approaches for flowshop scheduling. European Journal of Operational Research, 169, 816-854.

Der Benders-Zerlegungsalgorithmus: Neue Anwendungsfälle, Trends und Beschleunigungsstrategien (Master)

Der Benders-Dekompositionsalgorithmus ist eine gut etablierte exakte Lösungsmethode, die ursprünglich von Benders (1962) vorgeschlagen wurde und erfolgreich zur Lösung komplizierter Probleme in vielen verschiedenen Bereichen eingesetzt wurde, z. B. in der Planung und Terminierung, im Gesundheitswesen, im Transportwesen und in der Telekommunikation, im Energie- und Ressourcenmanagement und im Design chemischer Prozesse. In den letzten Jahren ist es wieder im Trend, um komplizierte kombinatorische Optimierungsprobleme zu lösen, die als gemischt-ganzzahliges lineares Programm formuliert werden können. Neuartige Erweiterungen, Beschleunigungsmethoden und hybride Anwendungen (z.B. in Kombination mit Metaheuristiken) wurden in letzter Zeit vorgestellt. Der erste Schritt dieser Arbeit ist es, einen Überblick über die Funktionsweise des klassischen Benders-Zerlegungsalgorithmus und seiner Erweiterungen aus der Übersicht von Rhamaniani et al. 2017 zu erhalten, sowie diese Übersicht um weitere relevante Arbeiten, die seit 2017 veröffentlicht wurden, zu erweitern. Im nächsten Schritt sollte der Kandidat entweder einen neuen Anwendungsfall identifizieren, der sich für die Benders-Zerlegung eignet, und den Algorithmus auf dieses Problem anwenden, oder einen klassischen Anwendungsfall für die Benders-Zerlegung auswählen und die bestehende Implementierung durch neue Beschleunigungsstrategien oder Funktionen erweitern.

Rahmaniani, R., Crainic, T.G., Gendreau, & M. Rei, W. (2017). The Benders decomposition algorithm: A literature review. European Journal of Operational Research, 259, 801-817.