Wie betreibt man einen Flughafen während des Spitzenverkehrs unter extremen Unsicherheiten, ständigen Ausnahmen, eingeschränkten Ressourcen und unvorhersehbarem Wetter?
Durch die Berechnung eines Plans zur Optimierung des Flughafens und seiner Ressourcen. Hört sich einfach an, erfordert aber einiges an höherer Mathematik, damit es funktioniert.
Die Herausforderung
Wenn Weihnachten vor der Tür steht, verändert sich Lappland.
Auf dem Flughafen Kittilä stieg das Fluggastaufkommen im Jahr 2018 um 12 %. Dieses Wachstum setzte die Infrastruktur und Ressourcen in der Region enorm unter Druck.
Obwohl Kittilä ein kleiner Flughafen mit gerade einmal zwölf Flugzeugstellplätzen ist, starten und landen an den verkehrsreichsten Tagen 58 Flüge. Die Anzahl der möglichen Parkalternativen am Flughafen zu berechnen, wird für einen Menschen schnell unmöglich.
Bei 58 Flügen gibt es 10^31 verschiedene Parkmöglichkeiten — eine harte Nuss, selbst für einen Supercomputer. Da 70 bis 80 % dieser Flüge innerhalb eines Zeitfensters von vier Stunden landen, wäre es noch untertrieben, dies als Spitzenzeiten zu bezeichnen.
Die Stellplätze sind nicht die einzige Ressource, die begrenzt ist. Der Flughafen kämpft ständig darum, genügend Busse, Mitarbeitende und Check-in-Schalter zur Verfügung zu stellen, um dem zunehmenden Flugverkehr gerecht zu werden. Einfach nur mehr Ressourcen bereitzustellen, wäre nicht effektiv, da der Flughafen außerhalb dieser Hochsaison gerade einmal einen oder zwei Flüge pro Tag abzufertigen hat. Wie betreibt man also einen Flughafen mit begrenzten Ressourcen?
Die Lösung
Wir haben in Zusammenarbeit mit den Parkexpert:innen und dem Management des Flughafens Kittilä ein Optimierungsmodell entwickelt, das optimale Parkpläne generiert.
Zuvor wurden die täglichen Stellplatzpläne in Kittilä eine Nacht vorher mit Stift und Papier erstellt. Da die Herausforderungen am Flughafen Kittilä mit Flugplanänderungen und fehlenden Ressourcen zusammenhängen, wurden die Kriterien für den perfekten Stellplatzplan wie folgt definiert:
- die Fähigkeit des Plans, Änderungen im Zeitplan standzuhalten (Robustheit)
- die Bus-Ressourcen, die für die Umsetzung des Plans erforderlich sind
Das Modell ermöglicht es den Nutzern, die Kriterien bei der Erstellung des perfekten Plans frei anzupassen.
Anhand der festgelegten Kriterien generiert das Optimierungsmodell dann unter Verwendung der Flugdaten einen mathematisch perfekten Stellplatzplan, der auf allen verfügbaren Daten basiert. Der Plan berücksichtigt alle für die Stellplätze geltenden Regeln (z.B. nicht alle Flugzeugtypen dürfen auf allen Stellplätzen parken) und Präferenzen (z.B. Nicht-Schengen-Flüge parken in der Nähe der Passkontrolle). Die Lösung nutzt außerdem Machine Learning, um Ankunftszeiten und Passagierzahlen vorherzusagen, die anschließend in den Optimierungsprozess einfließen.
Gemeinsam mit Finavia, dem Flughafenbetreiber, und Reaktor, einem finnischen Technologieunternehmen, entwickelten wir ein ERP-System für den Flughafen, dessen Kernstück das Optimierungsmodell bildet. Anstatt mühselig von Hand eine Tabelle zu erstellen, können die Verantwortlichen für die Flughafenstellplätze nun über dieselbe einfache Benutzeroberfläche einen Stellplatzplan generieren und die erforderlichen Busse reservieren. Falls sich die Bedingungen im Laufe des Tages ändern, kann innerhalb von Sekunden eine neuer optimaler Plan erstellt werden.
Kaum zu glauben – ein mathematisch perfekter Stellplatzplan auf Knopfdruck.
Die Lösung wird täglich eingesetzt, um den Stellplatzplan zu erstellen und die Busrouten und -ressourcen zu optimieren. Sie wird auch dazu genutzt, den Plan zu aktualisieren, wenn Verspätungen auftreten, und ermöglicht eine langfristige Ressourcenplanung, was zuvor undenkbar gewesen wäre.
Wie funktioniert die Optimierung?
Eine Erzwingung einer Lösung, indem wir Parkpläne generieren und prüfen, ob sie die Anforderungen erfüllen, wäre viel zu zeitaufwendig und daher nicht realisierbar. Stattdessen haben wir das Problem als ein lineares gemischt-ganzzahliges Optimierungsproblem dargestellt, mit dem Ziel, die Robustheit zu maximieren und gleichzeitig die geschäftlichen, rechtlichen und logistischen Anforderungen als lineare Einschränkungen einzufügen. Damit engen wir den möglichen Bereich, in dem eine Lösung gefunden werden kann, ein. Die Lösung wird dann mit dem Simplex-Algorithmus nach Dantzig in einem iterativen Eliminierungsprozess gefunden. Für Einschränkungen, für die keine harten Daten verfügbar sind, schätzen wir deren Werte mithilfe des Gaußschen Prozesses als Vorhersagemodell.
Die Ergebnisse
Von drei Stunden auf 30 Sekunden.
Die Lösung wurde im Dezember 2018 umgesetzt, und die Ergebnisse sind äußerst beeindruckend.
Ein Vergleich zwischen Dezember 2018 und Dezember 2017:
Die Anzahl der Flüge stieg um 12 %
Der Anteil der flughafenbedingten Flugverspätungen sank um 61 %
Die Dauer der durchschnittlichen flughafenbedingten Verspätungen sank um 66 %
Der Rückgang bei den Verspätungen führte zu einer geschätzten Kosteneinsparung von 500.000 €
Die NPS-Bewertung des Flughafens stieg um 20 Punkte
Robuster gegenüber Zeitplanänderungen
Der von dem Modell generierte Stellplatzplan ist in dem Sinne optimal, als dass die Leerzeit zwischen aufeinanderfolgenden Flügen am selben Standplatz so lang wie möglich ist. Daher fällt — falls Verspätungen oder Ausnahmen auftreten, was unvermeidlich ist — die Wahrscheinlichkeit, dass sich Verspätungen auf andere Flüge auswirken, deutlich geringer aus. Da der Plan robuster ist, gibt es keinen „Schneeballeffekt“ auf andere Flüge.
Transparenz
Mit dem neuen System ist es nun möglich, sofort eine Helikopteransicht über den gesamten Flughafen zu erhalten. Die Parkplätze, Flugzeuge und Busse werden jetzt auf einem einzigen Bildschirm angezeigt, sodass das Geschehen am Flughafen leicht zu verstehen ist. Und wenn sich Probleme abzeichnen, genügt ein einziger Klick, um einen neuen Plan zu generieren.
Verbesserte Kollaboration
Der Betrieb eines Flughafens ist eine kollektive Angelegenheit. Da der Stellplatzplan nun allen Mitarbeitenden auf dem Flughafen leicht zugänglich und vertraut ist, werden die Kollaboration und Koordination zwischen den einzelnen Parteien auf dem Flughafen vereinfacht.
Weniger CO2-Emissionen
Die Wahrscheinlichkeit, dass ein Flugzeug über Kittilä kreisen muss, bevor ein Stellplatz zur Verfügung steht, hat sich verringert. Das spart Tonnen von Treibstoff ein.
Seit wir diese Software für die Zuweisung von Stellplätzen in die Hände bekommen haben, ist unsere Arbeit sehr viel einfacher geworden. Wir können nicht nur die Stellplatzpläne, sondern auch die Betankung von Flugzeugen, die Pushback-Vorgänge und die Vorfeldbusse besser koordinieren. Es gibt kein Zurück mehr – ohne dieses Tool ist die Betriebsplanung ein komplettes Chaos.