Optimierungsmethoden bei mehrstufigen Optimierungsproblemen

Abstract

Diese Arbeit befasst sich mit einem Güter-Verteilungsproblem in Kombination mit einem Lokations-Allokationsproblem im Rahmen eines Reparaturnetzwerks. Die Aggregation von taktischen und strategischen Entscheidungen und der damit verbundenen Komplexität des Problems (NP-schwer) führt dazu, dass eine Lösung mittels mathematischer Programmierung nur für sehr kleine Referenzmodelle möglich ist. Es wird gezeigt, dass eine Teilung der Optimierungaufgabe in zwei Stufen die Komplexität des Modells ausreichend verringert, sodass auch bei praxisnahen Netzwerken moderater Größe eine Lösung in annehmbarer Zeit ermittelt werden kann; allerdings weist diese Teilung in zwei sequentielle Teilprobleme (wo das erste Teilproblem keine Informationsrückkopplung aus dem zweiten Teil hat) einen merkbaren Qualitätsverlust auf. Es werden verschiedene zweistufige Lösungsmethoden getestet und die Qualität sowie die Rechenlaufzeiten der Lösungen verglichen. Für einen Benchmark werden Ergebnisse aus einer simulierten Abkühlung Algorithmus (angewandt auf das Gesamtproblem) herangezogen.

This diploma thesis analyzes a combination of an inventory distribution problem with a location allocation problem. The reference model is a maintenance network. The combination of tactical and strategic decisions raises the complexity of the problem and causes that mathematical programming only solves small reference models (NP-hard). It will be shown that the splitting of the model into two echelons reduces the complexity so that real-world networks of moderate size can be solved. Different variations of two-echelon-models will be tested. Moreover, the quality of the solutions and the runtime will be compared. For a benchmark the results of a simulated annealing algorithm are used. The comparison of these results with the two echelon models will contribute to the conclusion that the loss of information caused by the splitting into two echelons leads to an unsatisfying loss of quality.