Sensitivitätsanalyse kombinatorischer Optimierungsprobleme am Beispiel der Personaleinsatzplanung

Kombinatorische Optimierungsprobleme treten in einer Vielzahl praktischer Anwendungen auf und befassen sich u.a. mit der effizienten Nutzung knapper Ressourcen. In der Praxis unterliegen diese Probleme verschiedenen Restriktionen, welche das Finden einer optimalen bzw. gültigen Lösung zu einer komplexen Aufgabe machen. Fragestellungen, wie sich Änderungen von Restriktionen auf die optimale Lösung eines Optimierungsproblems auswirken, lassen sich in den Bereich der Sensitivitätsanalyse (SA) einordnen. Ein wichtiger Anwendungsfall von SAs liegt dabei in der Unterstützung von Trade- off-Entscheidungen,
z.B. im Hinblick auf eingesetzte Ressourcen und erzielten Nutzen. Im Kontext der Personaleinsatzplanung können beispielsweise Untersuchungen hinsichtlich der Mitarbeiteranzahl, deren Qualifikationen oder vertragliche Wochenarbeitszeit Gegenstände einer SA sein. Obwohl die Durchführung von SAs im Bereich der linearen Optimierung fest etabliert ist, fehlt es im Bereich der kombinatorischen Optimierung an geeigneten Ansätzen für Sensitivitätsanalysen, die universell auf praktische Probleme angewendet werden können. Ziel dieser Arbeit war es ein Vorgehensmodell zu entwickeln, welches die Durchführung von SAs für praktische kombinatorische Optimierungsprobleme ermöglicht. Dabei erfüllt es die Anforderungen, Optimierungsprobleme unabhängig vom konkreten Anwendungsfall und verwendeten Optimierungsalgorithmus zu analysieren und durch gleichzeitige Änderungen mehrerer Parameter im Bereich der Restriktionen einen umfassenden Einblick in das Modellverhalten zu erhalten. Wesentliche zugrundeliegende Konzepte des Vorgehensmodells umfassen Bilevel-Optimierung, Evolutionäre Mehrzieloptimierung, Wissensentdeckung in Datenbanken, Data Mining, Innovization sowie Visual Analytics. Das in dieser Arbeit entwickelte Vorgehensmodell wurde mit dem Titel „Bilevel-Innovization“ überschrieben, welcher die beiden zentralen Phasen des Vorgehensmodells widerspiegelt. Die erste Phase (Datengenerierung) umfasst das wiederholte Lösen der als Bilevel-Problem formulierten Problemstellung des Untersuchungsgegenstands der Sensitivitätsanalyse durch Anwendung eines Evolutionären Mehrzieloptimierungsalgorithmus. Die zweite Phase (Datenanalyse) beinhaltet die anschließende Analyse der im Rahmen der Datengenerierung evaluierten Individuen durch Anwendung von Data Mining- und Visualisierungsmethoden.

Combinatorial optimization problems occur in a variety of practical applications and deal, among other things, with the efficient use of scarce resources. In practice, these problems are subject to various restrictions, which make finding an optimal or valid solution a complex task. Questions about how changes in restrictions affect the optimal solution of an optimization problem can be categorized in the area of sensitivity analysis (SA). An important application of SA is the support of trade-off decisions, e.g. with regard to resources used and benefits achieved. In the context of personnel scheduling, for example, SA can be used to examine the number of employees, their qualifications or contractual weekly working hours. Although the implementation of SA is well established in the field of linear optimization, there is a lack of suitable approaches for sensitivity analyses in the field of combinatorial optimization that can be universally applied to practical problems. The aim of this dissertation was to develop a procedure model that enables the implementation of SA for practical combinatorial optimization problems. It fulfills the requirements of analyzing optimization problems independently of the specific application and optimization algorithm used and of gaining a comprehensive insight into the model behavior by simultaneously changing several parameters in the constraints. Key underlying concepts of the procedure model include bilevel optimization, evolutionary multi-objective optimization, knowledge discovery in databases, data mining, innovization and visual analytics. The procedure model developed in this thesis was given the title “Bilevel-Innovization”, which reflects the two central phases of the procedure model. The first phase (data generation) comprises the repeated solving of the problem formulated as a bilevel problem of the subject of the sensitivity analysis by applying an evolutionary multi-objective optimization algorithm. The second phase (data analysis) includes the subsequent analysis of the individuals evaluated during data generation by applying data mining and visualization methods.