Flight Schedule Design Optimization, eine Methode zur besseren Saisonflugplanung?

Das klassische Vorgehen bei der Erzeugung von Saisonflugplänen sieht vor, ausgehend von kommerziellen Gesichtspunkten, Marketingaspekten aber auch aufgrund der Wettbewerbssituation feste Vorgaben bezüglich Streckenangebot, Frequenz und avisierten Ertrag zu formulieren. Solche Vorgaben beruhen auf Expertenwissen, oft unterstützt durch ein Marktmodell und historische Daten der Streckenergebnisrechnung (Revenue-Managements). Das Ergebnis ist ein kommerzieller Saisonflugplan, auf den die weiteren Planungsschritte aufbauen. Das hier vorgestellte Modell unterstützt den Prozess der kommerziellen Flugplanung und beachtet wichtige betriebliche Einschränkungen wie Flughafenslots, Flottengröße, Umläufe, usw. in Verbindung mit kommerziellen Gesichtspunkten eines Marktmodells wie Sitzplatzkapazität auf den Flugstrecken und Ertragserwartung je Flug. Die kommerzielle Flugplanung ist eines der Problemstellungen aus der Saisonplanung von Fluggesellschaften. Hier wird festgelegt, welches Angebot an Flügen in der nächsten Saison angeboten wird. Bei der Entscheidungsfindung sind in der Regel mehrere Fachabteilung einer Fluggesellschaft beteiligt. Ziel ist es einen Saisonflugplan aufzustellen der zum einen kommerziellen Erfolg verspricht und zum anderen mit vertretbaren Mitteln realisiert werden kann. Der fast dreimonatige Planungsprozess “kommerzielle Flugplanung” findet zweimal jährlich für den Sommer- und Winterflugplan statt und beginnt ca. 9 Monate vor der jeweiligen Saison. Die Planung erfolgt stets in Hinblick auf Wirtschaftlichkeit und beinhaltet folgende Vorgehensweise:

1. Bestimmung der benötigten Sitzplatzkapazität auf den Flugstrecken (O&D-Paare)
2. kommerzielle Bewertung der O&D-Paare
3. Festlegung einer groben Umlaufplanung für ein oder zwei Wochen
4. exakte Umlaufplanung für ein oder zwei Wochen

Planungsschritt 1

Basis für die Bestimmung der benötigten Sitzplatzkapazität sind Prognoserechnungen anhand historischer Daten, das Flugprogramm der Wettbewerber, die Analyseergebnisse über touristische Trends und die Informationen über die Strukturgrößen eines Zielgebietes. Ergebnis dieser Betrachtung sind Aussagen über die erwartete Verkehrsnachfrage für alle O&D-Paare der Fluggesellschaft. Diese Verkehrszahl wird anschließend noch durch die Wochenzahl der Saison und die Passagierkapazität je Flugzeug plus Sicherheitspuffer (wegen Nachfrageschwankungen) geteilt werden. Ergebnis ist eine Zahl zur benötigten Wochenfrequenz für die jeweilige O&D-Paare. In den letzten Jahren, seit 2008, ist der Trend zu beobachten, dass die Menge an Flügen stagniert und die Anzahl der gleichzeitig beförderten Passagiere zunimmt. Als Ursache für diese Entwicklung kann ein zunehmender Auslastungsgrad der Flugzeuge angeführt werden.

Planungsschritt 2

Für alle Quelle-Ziel-Relationen des Streckennetzes der Fluggesellschaft werden die erwarteten Erträge kalkuliert. Beispielhaft wird nachfolgend eine Ertragsrechnung für eine stark nachgefragte kontinentale Urlaubsflugstrecke von Deutschland nach Spanien dargestellt:

• Umsatz: +34400,- €
• Flughafen Entgelte: – 4830,- €
• Treibstoffkosten: – 9570,- €
• Flugsicherungskosten: – 2490,- €
• Sonstige Kosten: – 160,- €
• PAX-Kosten: – 5460,- €
• Wet-Leasing-Kosten (ACMI): – 10190,- €
• Ertrag: = 1700,- € (4,94 % Marge)

Generell lässt sich konstatieren, dass die Ertragsbasis für Flugdienstleistungen innerhalb Europas sehr schwach ist. Die Margen übersteigen meist nicht 5 % und defizitäre Flugstrecken überwiegen im Angebot der Fluggesellschaften. Volkswirtschaftlich kann zu nehmend von einem ruinösen Wettbewerb gesprochen werden – Meinung des Autors. Als Reaktion darauf sind die Fluggesellschaften bestrebt, ihre Kostenstruktur zu verbessern, das Sparprogramm der Deutschen Lufthansa AG “Score” ist hierfür ein Paradebeispiel. Das Problem ist nur, was die Einen können können die Anderen ebenfalls.

Planungsschritt 3

Die Festlegung der Umläufe im Flugprogramm erfolgt nach dem sogenannten Verkehrstagekonzept. Das bedeutet, dass die Flüge auf die 7 Verkehrstage einer Standardwoche (Masterweek 1) nach festgelegten Vorgaben (z.B. Bettenwechsel im Urlaubszielgebiet, Abgrenzung zum Flugprogramm der Wettbewerber, etc.) verteilt werden. Konkrete Zeiten für Abflug und Landung stehen in diesem Planungsschritt noch nicht fest. Die Masterweek 1 definiert die Netzwerkstruktur einer Fluggesellschaft und kann als strategische Vorgabe für die betreffende Saison verstanden werden.

Masterweek 1

Planungsschritt 4

Für eine exakte Umlaufplanung sind Flughafenöffnungszeiten, Flughafenslots und Blockzeiten zu beachten. Aufgrund der “Großvaterrechte” bei der Slotzuteilung ist eine manuelle Planung des Saisonflugplans (Masterweek 2) prinzipiell mit vertretbaren Aufwand möglich, da auf größere Änderungen in der Saisonflugplanung in der Praxis verzichtet wird. Den Kern bildet ein Basisplan der vergangenen Jahre, aus dem durch Ergänzungen der aktuelle Saisonflugplan, zum Teil noch manuell, konstruiert wird.

Masterweek 2

Gerade diese manuelle Konstruktion eines Saisonflugplans liefert Ansatzpunkte für eine Automatisierung. Im folgenden wird ein Modell vorgestellt, das als Ergebnis (analog der zuvor vorgestellten Planungsschritte) eine auf Grundlage der erwarteten Erträge gewinnmaximale Masterweek 2 automatisch konstruiert.

Modelltheoretischer Ansatz und Lösungsverfahren

Das Flight Schedule Design Problem lässt sich als lineares Optimierungsmodell formulieren. Zielstellung ist eine bestmögliche (gewinnmaximale) Auswahl von Flugverbindungen (Legs) und deren sinnvolle Verkettung zu virtuellen (ohne eindeutige Zuweisung eines Flugzeugs) Wochenumläufen (Rotationen) unter Beachtung betrieblich notwendiger Einschränkungen (Flughafenslots, Flughafenöffnungszeiten, Frequenz, Flottengröße und Periodizität). In der Literatur existieren verschiedene Lösungsansätze zur Erzeugung von Flugplänen. Zum Beispiel formuliert Noltemeier ihr Modell als kantenbasierendes Mehrgüternetzwerkfluss-Modell und Wieners in anderer Form als gewichtetes Netzwerkentwurfsproblem. Beide Modelle sind speziell für den Einsatz bei Charterfluggesellschaften konzipiert, als Transportproblem von Passagieren unter der Maßgabe, die Kosten zu minimieren. Im Gegensatz dazu maximiert das hier vorgestellte Modell den erwarteten Gesamtertrag des Saisonflugplans und ist auf die Bedürfnisse von Low-Cost-Fluggesellschaften zugeschnitten. Das Transportproblem von Passagieren wird nicht direkt berücksichtigt. Das Modell besitzt die zwei Entscheidungsvariablen ​

(für die Flüge nachfolgend als Legs bezeichnet) und

(für die Flugzeugumläufe nachfolgend als Rotationen bezeichnet). Beide Entscheidungsvariablen können entweder den Wert 0 oder 1 annehmen je nachdem, ob das betreffende Leg oder die Rotation Bestandteil der Lösung sind.

Die Zielfunktion (1) summiert den erwarteten Gewinn je Leg ​

​ über alle Legs, welche Bestandteil der Lösung sind. Die Summe soll maximal werden.​

(1) Maximiere: ​​$G = \sum\limits_{l \in L} g_l \cdot y_l$

Das Modell beinhaltet folgende Nebenbedingungen:

Die Nebenbedingung (2) legt fest, dass ein Leg nur einmal von einer Rotation überdeckt wird.

(2) $\sum\limits_{r \in R_l} x_r - y_l = 0$

Nebenbedingung (3) beschränkt die Anzahl von Legs die ein bestimmte Flughafenslotkapazität ​$c_s$ nutzen.

(3) ​$\sum\limits_{l \in L_s} y_l \le c_s$

Mit Nebenbedingung (4) wird dafür gesorgt, dass die Anzahl an Rotationen, die Bestandteil der Lösung sind, auf die Menge der vorhandenen Flugzeuge ​$f$ begrenzt ist.

(4) ​$\sum\limits_{r \in R} x_r \le f$

Die Nebenbedingung (5) verhindert die Überschreitung der festgelegten Frequenz $w_c$ durch die zugehörigen Legs.

(5) ​$\sum\limits_{l \in L_c} y_l \le w_c$

Da in der Regel ein zirkulierender Flugplan notwendig ist, wird mit Nebenbedingung (6) gewährleistet, dass im Saisonflugplan die gleiche Anzahl Rotationen an einem Flughafen beginnt wie auch endet.

(6) ​$\sum\limits_{r \in R_{a_{Start}}} x_r - \sum\limits_{r \in R_{a_{End}}}x_r = 0$

Nebenbedingung (7) und (8) legen fest, dass die beiden Entscheidungsvariablen x und y nur die Werte 0 oder 1 annehmen dürfen. Es handelt sich also um ein Optimierungsproblem mit Ganzzahligkeitsbedingung.

(7) ​$x_r \in (0,1)$

(8) ​$y_l \in (0,1)$

Im Modell werden die notwendigen Nebenbedingung verknüpft, mit denen sich ein theoretisch fliegbarer Saisonflugplan berechnen lässt. In der Praxis spielen darüber hinaus weitere Vorgaben bei der Erstellung des Saisonflugplans eine Rolle. Solche Vorgaben könnten beispielsweise durch weitere Nebenbedingungen eingearbeitet werden:

• Berücksichtigung einer inhomogen Flugzeugflotte
• Festgelegte Stationierungen von Flugzeugen an Flughäfen
• Beachtung von „Goldslots“ (Flughafenslots an HUB-Flughäfen)
• Planung von Instandsetzungsereignissen
• Berücksichtigung von Kosten für die saisonale Flugzeugbenutzung
• Festlegung der Verkehrstage für die O&D

Bei der ersten Modellimplementation wird jedoch auf eine Berücksichtigung der aufgezeigten Zusatzbedingungen verzichtet, um die Implementation bewusst einfach zu halten.

Aus dem primalen Maximierungsmodell lässt sich nun das folgende Duale Minimierungsmodell (9) ableiten.

(9) Minimiere: ​$K = \sum\limits_{s \in S} c_s \cdot \beta_s + f \cdot \gamma + \sum\limits_{c \in C} w_c \cdot \delta_c$

Die Entscheidungsvariable ​​$y_l$ wird im dualen Modell zur Nebenbedingung (10) :

(10) ​$-\alpha_l + \sum\limits_{s \in S_l} \beta_s + \delta_c \ge g_l$

Die Entscheidungsvariable $x_r$ wird im dualen Modell zur Nebenbedingung (11) :

(11) ​$\sum\limits_{l \in L_r} \alpha_l + \gamma + \chi_{a_{Start}} - \chi_{a_{End}} \ge 0$

Zur Lösung des Optimierungsproblems wurde das Branch-And-Price-Verfahren (kurz BAP) gewählt. Dieses Verfahren ist geeignet, um ganzzahlige Optimierungsprobleme mit sehr vielen Variablen in akzeptabler Rechenlaufzeit zu Lösen.

Branch and Price

Das Verfahren baut auf einer guten Ausgangslösung auf, die im vorliegenden Fall der Saisonflugplan aus der vorherigen Flugplanperiode ist. Das BAP-Verfahren startet mit der Lösung des Optimierungsproblems ohne Beachtung der Ganzzahligkeitsbedingung (Nebenbedingungen (7) und (8)) mittels der Spaltengenerierungsmethode. Wesentlicher Vorteil der Spaltengenerierung ist, dass die Variablen nur nach Bedarf erzeugt werden. Das heißt, dass am Anfang nur ein kleiner Teil (z.B. aus einer Startlösung) der Variablen bekannt ist und während des Verfahrens dynamisch nur die Variablen dem Modell hinzugefügt werden, die zur Verbesserung der Lösung beitragen können. Die Erzeugung neuer Variablen wird auf das sogenannten Unterproblem (Pricing-Problem) ausgelagert. In der Implementation werden alle ​

​-Variablen global erzeugt, da deren Menge im Vergleich zu den ​​-Variablen wesentlich geringer ist. Ausgehend von der dualen Nebenbedingung der ​

​-Variable (11) kann das Pricing-Problem (12) und (13) wie folgt formuliert werden:

(12) Minimiere: ​$P_r = \sum\limits_{l \in L_r} \alpha_l + \gamma + \chi_{a_{Start}} - \chi_{a_{End}}$

(13) ​$P_r < 0$

Das Pricing-Problem lässt sich als Kürzestes-Wege-Problem formulieren, bei dem nach Rotationen gesucht wird, die die duale Restriktion der

-Variable (11) maximal verletzen.

Kürzeste Wege Algorithmus

Die reduzierten Kosten ​​$\hat P_r $ für die duale Nebenbedingung der Entscheidungsvariable ​​$x_r$ lassen sich wie folgt bestimmen:

(14) ​$\hat P_r = \sum\limits_{l \in L_r} \alpha_l + \gamma + \chi_{a_{Start}} - \chi_{a_{End}}$

Wird durch die kürzeste Wegesuche eine neue Rotation gefunden bei der negativ ist, wird diese Variable zum Optimierungsmodell hinzugefügt. Lassen sich keine neuen Rotationen mehr finden, bei denen ​

​ negativ ist kann das Verfahren abgebrochen werden. Die optimale Lösung ohne Ganzzahligkeitsbedingung ist gefunden und kann als globale obere Schranke (UB) für das BAP-Verfahren verwendet werden, dass nun die Ganzzahligkeitsbedingung realisiert. Die Berechnung der unteren Schranke (LB) ist als Branch-And-Bound-Verfahren (kurz BAB) über die Rotationsvariablen xr implementiert. Alternativ würden sich aus Laufzeitgründen auch Heuristiken anbieten um schnell eine gute untere Schranke (ganzzahlige Lösung) zu bestimmen. Zur Berechnung der oberen lokalen Schranke (UB) innerhalb der BAP-Knoten hat sich in der vorliegenden Problemstellung die Lagrange-Multiplikator-Methode bewährt. Weiteres Verbesserungspotential im Laufzeitverhalten der aktuellen BAP-Implementation wird gesehen und zukünftig stärker untersucht.

Fallstudie und erste Ergebnisse

Als Fallstudien dienen Szenarien kleiner virtueller Fluggesellschaften die im Low-Cost Segment operieren. Vorhanden sind jeweils die Saisonflugpläne aus der vorherigen Flugplanperiode. Die Eingangsdaten für das Modell sind geschätzt und basieren auf Erfahrungswerten zur Saisonflugplanung, welche aus der Zusammenarbeit mit verschiedenen Fluggesellschaften stammen sowie aus allgemein zugänglichen Datenquellen. Alternativ bietet sich an, bestehende Verkehrsnachfrage-Modelle für die Berechnung der erwarteten Gewinne ​

​ je Leg zu nutzen. Die Prognosegüte des Parameters ​

​ hat alles entscheidenden Einfluss auf die Qualität der Optimierungslösung und sollte möglichst realitätsnah sein.

Zur Optimierung der Fallstudien stand ein Rechner mit Intel i3 2,67 GHz Prozessor und 8 GB Ram zur Verfügung. Die Implementation des BAP-Verfahrens ist eine Eigenentwicklung unter Verwendung der C++ Standard Library auf Linux-Basis.

Für zwei kleine Optimierungsszenarien mit leerer Startlösung (stand nicht zur Verfügung) konnten folgende Ergebnisse erzielt werden:

Szenario 1 (kleine Fluggesellschaft mit 12 O&D-Paaren)

• Dualitätslücke: 0,6654%
• Erzeugte ​-Variablen: 90
• Modell-Variablen: 3174
• Modell-Nebenbedingungen: 4653
• Laufzeit bis Optimum: 8 min 35 s

Szenario 2 (kleine Low-Cost-Fluggesellschaft mit 45 O&D-Paaren)

• Dualitätslücke: 2,1264%
• Erzeugte ​-Variablen: 1002
• Modell-Variablen: 1085
• Modell-Nebenbedingungen: 271
• Laufzeit bis Optimum: 9 min 15 s

Die Laufzeiten sich durch weitere Verbesserung des Programmcodes und bessere Hardware extrem verkürzen.