Sabre machte die Crew-Verstärkung zu einer expliziten Variable in der Pairing-Optimierung von Fluggesellschaften

Die Crew-Planung von Fluggesellschaften läuft in zwei Schritten ab: Zunächst erzeugt das Crew-Pairing anonyme Arbeitspläne, die den Flugplan abdecken, dann werden diese Pairings einzelnen Crewmitgliedern zugewiesen. Langstreckenflüge benötigen aus Sicherheitsgründen verstärkte Crews, und hier liegt der Haken: Wie viele zusätzliche Kapitäne oder Offiziere ein Flug erfordert, hängt von den Eigenschaften des Pairings ab, das ihn abdeckt. Der Bedarf und die Wahl des Plans sind miteinander gekoppelt. Die meisten Werkzeuge lösen diese Kopplung auf, indem sie die Verstärkungsanforderungen im Voraus festlegen oder einschränken, wie sie erfüllt werden können, weil das allgemeine Problem sehr schwierig ist.

Sabre entwickelte seinen Pairing-Optimierer für Langstrecken Mitte der 1990er-Jahre und schlug den entgegengesetzten Weg ein: Der Optimierer modelliert explizit viele Arten von Crew-Verstärkungsprozessen und berücksichtigt gleichzeitig die relevanten Ränge aller Cockpit-Crewmitglieder. Das daraus resultierende große Modell wird mit Branch and Price gelöst. In einem Interfaces-Artikel aus dem Jahr 2015 zeichneten die Autoren zwei Jahrzehnte der Modell- und Algorithmusentwicklung nach und verglichen ihren Ansatz mit vier konventionellen Methoden; dabei zeigte sich, dass er das allgemeine Crew-Verstärkungsproblem löst und Fluggesellschaften erhebliche Einsparungen bei den Crew-Kosten bringt.

Warum es funktioniert: Verstärkung kostet echtes Geld. Wird derselbe Flug mit Pairing A abgedeckt, können drei zusätzliche Crewpositionen anfallen, während Pairing B nur eine erfordert; wer den Bedarf vor der Optimierung festlegt, friert die Kosten in den Plan ein. Legt man den Bedarf in die Zielfunktion, kauft der Solver über das gesamte Netzwerk hinweg auf einmal die günstigste zulässige Kombination. Die Einsparungen summieren sich über jedes Pairing in einer Bid Line, weshalb Fluggesellschaften für das Produkt zahlten und nicht für eine Regelanpassung.

Die Crew-Verstärkung zu einer Optimierungsvariable machen

Verstärkungsanforderungen sind an die Wahl des Pairings gekoppelt; legt man sie a priori fest, werden die Crew-Kosten eingefroren, bevor der Solver überhaupt läuft.

Branch and Price hält das vergrößerte Modell handhabbar, sodass Millionen von Kandidaten-Pairings einschließlich Verstärkungszuständen lösbar bleiben.

Sabre verkaufte Crew-Pairing-Systeme an viele Langstrecken-Fluggesellschaften, sodass sich die Verbesserung über die Flotten der Kunden vervielfachte statt nur einmal zu wirken.

Zwei Jahrzehnte inkrementeller Modell- und Algorithmusarbeit (1995–2015) machten die explizite Formulierung produktionsreif.

Wenn eine Nebenbedingung tatsächlich mit der Lösung variiert, sollte man sie im Modell belassen. Die vorherige Festlegung „bekannter“ Parameter vereinfacht die Mathematik, friert aber Kosten ein, die der Solver beseitigt hätte.

Der Optimierer blieb bis Mitte der 2010er-Jahre in Sabres Produktlinie für Langstrecken-Pairings; der Interfaces-Artikel von 2015 dokumentiert die Entwicklung seiner Modelle und Algorithmen und vergleicht ihn mit vier konventionellen Ansätzen. Der Artikel stellt die Formulierung mit expliziter Verstärkung als etablierte Produktfunktion und nicht als Forschung dar und merkt an, dass das allgemeine Problem in der Praxis gerade wegen seiner Komplexität lange übergangen worden war.