Mathematische Modellierung und
Lösungsansatz

Wir verwenden zur Lösung eine Set-Partitioning-Formulierung mit Nebenbedingungen, die als Lineares Programm modelliert wird: aus der Menge aller möglichen Dienstschichten muß eine Teilmenge ausgewählt werden, so daß, unter Beachtung von globalen Nebenbedingungen wie Kapazitäten an den Heimatflughäfen, jeder Dienst (=Flug) von genau einer Crew überdeckt wird.

Die Anzahl der möglichen Dienstschichten ist schon für kleine Probleme extrem groß. So enthält z. B. eine Probleminstanz mit nur 105 Flügen und sechs Heimatflughäfen über 1.350.000 verschiedene zulässige Dienstschichten, die während der Optimierung beachtet werden müssen.

Ein direkter Lösungsansatz ist daher bei praxisrelevanten Problemgrößen nicht möglich, so daß wir uns für den Einsatz der Spaltengenerierungstechnik entschieden haben. Beginnend mit einem vereinfachten Linearen Programm, das nur eine vielversprechende Auswahl aller Dienstschichten enthält, werden in einem iterativen Prozeß abwechselnd das Lineare Programm gelöst und unter Verwendung dieser Lösung dynamisch neue Dienstschichten generiert. Dieses Teilproblem, das sogenannte Subproblem, ist ein restringiertes Kürzeste-Wege-Problem. Mit Hilfe von ,,Ressourcen`` werden in einem Multi-Label-Algorithmus interessante neue Dienstschichten erzeugt, die alle tarifrechtlichen und sicherheitsrelevanten Nebenbedingungen einhalten.

Um ganzzahlige Lösungen zu erhalten, wird dieses Verfahren in einen Branch-&-Bound-Baum eingebunden. Als Branchingregel für den linken Teilbaum erzeugen wir ,, a $\rightarrow$ b ``: die Crews müssen immer beide Flüge a und b oder keinen dieser beiden Flüge bedienen. Entsprechend gilt ,, a $\not\rightarrow$ b `` für den rechten Teilbaum, was besagt: die Crews müssen entweder a oder b, aber nicht beide oder keinen bedienen.