Gate Management für Verkehrsflughäfen

Der weltweite Passagierluftverkehr hat in den vergangenen Jahrzehnten kontinuierlich an Volumen hinzu gewonnen, und ein weiterer Anstieg der Passagier- und Flugzahlen wird allgemein erwartet. Seit 1980 hat sich das Passagier- und Frachtaufkommen ver­doppelt und es wird auch zukünftig mit einer Steigerung zwischen 5,6% beim Passagier­aufkommen und 6,7% für Frachttransporte pro Jahr gerechnet (s. International Air Transport Association - IATA Study 2000). Durch die zunehmende Liberalisierung und Privatisierung der Luftfahrtindustrie gewinnt aus Sicht der Verkehrsflughäfen daher die bestmögliche Ausnutzung der vor­handenen Ressourcen zur Abfertigung des steigenden Verkehrsaufkommens immer mehr an Bedeutung. Dies gilt sowohl für das in der Bodenabfertigung eingesetzte Personal und Gerät als auch insbesondere für bauliche Ressourcen, wie zum Beispiel Terminal-Gates oder Start- und Landebahnen, die in der Regel nur sehr schwer, lang­fristig und mit sehr hohem finanziellen Aufwand erweitert werden können.

Die zur Befriedigung der steigenden Nachfrage erforderliche hohe Ausnutzung der verfügbaren Ressourcen führt zu komplexen Planungsaufgaben, bei denen herkömm­liche manuelle Planungsmethoden an ihre Grenzen stoßen. Die Planung wird auf operationaler Ebene darüber hinaus dadurch erschwert, daß ständig kurzfristige Änderungen im Flugplan, etwa durch Verspätungen oder Flugumleitungen, berück­sichtigt werden müssen

Im Rahmen des sogenannte Gate-Managements werden ankommende und abgehende Flüge bzw. Flugzeuge zu geeigneten Terminal-Gates oder Vorfeldabfertigungs­positionen zugeordnet und die exakte Verweildauer am Gate wird bestimmt. Ein Flug kann in Abhängigkeit von Eigenschaften wie dem zugehörigen Flugzeugtyp, Herkunfts- und/oder Zielort oder Fluglinie, etc., an bestimmten Gates bearbeitet werden und erfordert zur Abfertigung eine gewisse Mindestanstelldauer am Gate.

Aus Sicht des Flughafens sind ein- und ausgehende Flüge (in erster Linie) dadurch miteinander verknüpft, daß sie von ein und demselben Flugzeug in unmittelbarer Folge bedient werden. In der Regel ist es wünschenswert, zwei miteinander verknüpfte ankommende und abgehende Flüge an dem selben Gate zu bedienen. Ist dies aus bestimmten Gründen nicht möglich oder angebracht, so muß das Flugzeug zumeist durch spezielle, knappe Flugzeugschlepper an seine neue Position gezogen werden. Während der Bodenzeit am Flughafen muß ein Flugzeug ständig einem Gate oder einer Parkposition zugeordnet sein oder sich in einem Schleppvorgang befinden. Schlepper und insbesondere Gates sind jedoch teure und damit knappe Ressourcen, und vor allem letztere können nicht kurzfristig zusätzlich bereit gestellt werden.

Zwischen der Bearbeitung zweier von unterschiedlichen Flugzeugen bedienten Flüge an ein und demselben Gate müssen vom Flugzeugtyp abhängige zeitliche Mindestabstände (Rüstzeiten) eingehalten werden. Vom Flugzeugtyp hängen darüber hinaus gewisse physikalische Ausschlußbedingungen ab, die in erster Linie durch die Flugzeugspann­weite verursacht werden: Die Bearbeitung eines Flugzeugs einer bestimmten Größe an einem Gate kann für benachbarte Gates zur Folge haben, daß dort in dieser Zeit gar keine oder nur Flugzeuge einer bestimmten Höchstgröße bedient werden können.

Die Güte eine Planes hängt von zahlreichen Kriterien ab. Vorrangiges Ziel ist die Zuordnung einer möglichst großen Zahl von Flügen zu Gates, denn häufig existiert insbesondere in Spitzenzeiten keine Lösung, bei der alle Flüge an geeignete Gates zugeordnet werden können; eine solche Situation erfordert dann manuelle Intervention, z.B. durch die Verkürzung von Mindestbearbeitungsdauern. Weitere wichtige Ziel­kriterien sind unter anderem die Maximierung der erzielten Flug-Gate-Präferenz­werte, die Minimierung der erforderlichen Schleppvorgänge und die Minimierung der Abweichungen von einem infolge von Flugplanänderungen nicht mehr länger realisierbaren Vorgabeplan. Die Gatezuordnung hat auch entscheidenden Einfluß auf den Service einer Fluggesellschaft, derart, daß sie durch blockierte Gates verursachte Warte­zeiten eines ankommenden Fluges auf dem Vorfeld minimiert.

Bisherige Ansätze zum Gate-Management haben zumeist vereinfachte Formen des hier beschriebenen Problems untersucht, und dabei in der Regel das Ziel der Minimierung der von den Fluggästen im Terminal zurückzulegenden Wegstrecken in den Vorder­grund gestellt. Die resultierenden Modelle ähneln daher den aus der Standort­theorie für Anordnungs­probleme bekannten Optimierungsmodellen. Das Problem wird somit im wesentlichen als quadratisches Zuordnungsproblem verstanden, das, für den Fall, daß zwei Flüge zeitlich überlappen und somit nicht derselben Ressource zugeordnet werden können, um paarweise Ausschlußbedingungen erweitert wird.

Das im Vortrag zu beschreibende komplexe Entscheidungsproblem basiert auf einer Modellierung als ressourcenbeschränktes Projektplanungsproblem. Im Gegensatz zu den Modellen der Literatur betrachten wir bis maximal drei Aktivitäten, nämlich Ankunft am Gate, ggf. Schleppen und Parken sowie Abflug von einem u.U. anderen Gate, als drei separate Ereignisse, zugewiesen zu möglicherweise verschiedenen Positionen, was u.U. Schleppzeiten für die erforderlichen Schleppvorgänge bedingt. Neben der Zuordnung der Ereignisse zu den Positionen sind darüber hinaus Anfangs- und Endzeitpunkte der an den Positionen auszuführenden Aktivitäten innerhalb der Zeitfenster zuzuweisen. Bisherige Optimierungsansätze halten Ankunft-, Park- und Abflugereignisse eines Flugzeuges stets an der gleichen Position. Planungszeitraum ist i.d.R. ein Tag und damit wesentlich größer als die bisher betrachteten, unabhängigen Zeitslots, die zu sog. Ankunfts- oder Abflugswellen korrespondieren. In den in der Literatur zu findenden Ansätzen ist die am häufigsten verwendete Zielfunktion die Minimierung der Passagier­wegezeiten, was dann auf die Lösung eines quadratischen Zuordnungsproblems führt und damit die reale Situation nicht adäquat abbildet. Unser Modell beruht auf der Idee, das Gate Management Problem als Schedulingproblem mit alternativen disjunktiven Ressourcen (Mehr­modusproblem) und variablen Bearbeitungsdauern abzubilden. Die Zielfunktion ist nicht die Minimierung der Projektdauer sondern eine Kombination mehrerer Ziele gewichtet durch vom Anwender vorgegebene Parameter. Zu den vorrangigen Zielen zählen dabei die Maximierung der gesamten Flugzeug-Gate-Zuordnungspräferenzen sowie die Minimierung der kostspieligen Schleppvorgänge. Zur Lösung wird ein mit Hilfe der Bibliotheken ILOG Solver und Scheduler implementiertes Branch-and-Bound Verfahren verwendet.

Da das exakte Verfahren, aufgrund zu langer Antwortzeiten für eine optimale Lösung zu berechnen oder Daten­änderungen online zu integrieren, nicht einsetzbar ist, wurde folgende Strategie eines unvoll­ständigen Branch-and-Bound Verfahrens gewählt: Branching wird durch die unter­­­schiedlichen Gatezuordnungen definiert; disjunktive Constraints definieren die Kapazitätsrestriktionen der Ressource Gate. Eine drastische Such­baumreduktion wird durch die Propagierung der Constraints erreicht. Zur Lösung praktischer Fragestellungen mußte eine geeignete Dekomposition in wenig über­lappende Teilprobleme gefunden werden. Die Teilprobleme werden mit dem erwähnten Branch-and-Bound Verfahren gelöst. Die so erhaltenen Lösungen werden durch eine Large-Neighbourhood Suche verbessert, bei der einige der instantiierten Variablen wieder frei gesetzt werden. Das daraus resultierende Teilproblem wird mittels des Branch-and-Bound Verfahrens für diese Variablen erneut optimiert.

Die Rechenergebnisse für zwei Wochen realer Flugdaten zeigen eine beeindruckende Überlegenheit des Verfahrens gegenüber der vorhandenen Planung.

B.Hammer