next up previous contents
Next: Parallele Packalgorithmen Up: Anwendungen der kombinatorischen Optimierung Previous: PARALOR - Parallele Algorithmen

 

Flugplanoptimierung

 
  jbquote217

Abbildung: Ausschnitt aus einem wöchentlichen Flugplan

Die Deutsche Lufthansa bietet wöchentlich knapp 10.000 Flüge an, die jeweils von einem der rund 250 Flugzeuge der Flotte bedient werden müssen. Jeder Flug wird von einer vier- bis achtköpfigen Crew begleitet, die aus dem 11.000 Menschen zählenden Flugpersonal des Unternehmens zusammengestellt wird. Die Erstellung möglichst kostengünstiger Flugpläne ist das Ziel dieses Projektes, welches von uns in Kooperation mit der Lufthansa Systems GmbH, der Gesamthochschule/Universität Paderborn und der Humboldt-Universität zu Berlin bearbeitet wird. Unser Hauptarbeitsgebiet ist dabei das Fleet Assignment, d.h. die optimale Zuordnung von Flugzeugtypen zu gegebenen Flugstrecken.

Beim Entwurf eines neuen Flugplans bestimmt die Gesellschaft zunächst, welche Verbindung zu welchem Zeitpunkt angeboten werden soll. Die Überprüfung, ob ein solcher Flugplan mit dem vorhandenen Material und den Beschäftigten realisierbar ist, erfordert einen hohen Einsatz von Erfahrung und Rechnerpotential. Dabei sind Wartungsintervalle und viele andere Restriktionen zu beachten. Bei der Kosten-Nutzen-Berechnung spielt die Analyse von Zubringerflügen eine herausragende Rolle. Es ist zu klären, wieviele Menschen, die beispielsweise die gewinnbringende Route von Köln über Frankfurt nach New York gebucht haben, überhaupt zum richtigen Zeitpunkt in Frankfurt sein können und wieviele Passagiere, die anschließend weiter nach Seattle, Miami oder San Francisco fliegen möchten, ebenfalls mitgenommen werden können. Darüber hinaus ist zu klären, ob der erstellte Flugplan eine effiziente Personaleinsatzplanung ermöglicht (Ruhepausen, Übernachtungskosten etc.). Der ungeheure Umfang des Problems ergibt sich daraus, daß jede Woche eine halbe Million solcher Reiserouten angeboten wird.

Beim Flugplandesign wird meist so vorgegangen, daß ein historisch gewachsener Flugplan an wenigen Stellen leicht modifiziert wird. So kann sich die Überprüfung der Realisierbarkeit sowie die Kostenbewertung an früheren Ergebnissen orientieren. Aufgrund des sich zunehmend verschärfenden Wettbewerbs müssen heute regelmäßig völlig neue Flugpläne entworfen werden. Rechner, wegen der Datenfülle insbesondere Parallelrechner, helfen dem Flugplandesigner dabei, ein konkurrenzfähiges Angebot der Gesellschaft für den Kunden zu erstellen.

Fleet Assignment

Nachdem geklärt wurde, zu welchem Zeitpunkt eine Flugverbindung (,,Leg``) angeboten wird, wird als nächstes festgelegt, welcher Flugzeugtyp (,,Equipment``), beziehungsweise welches konkrete Flugzeug (,,Tail``) einen Flug bedienen soll. Die Flugzeuge unterscheiden sich in der Kapazität, also der maximalen Anzahl der Passagiere, der maximalen Reichweite, sowie in den Kosten, die pro geflogenem Kilometer und befördertem Passagier verursacht werden. Durch das Fleet Assignment wird festgelegt, welcher Flugzeugtyp für die Gültigkeitsdauer des Flugplans jede Woche für eine bestimmte Flugverbindung verwendet wird. Die Kosten, die beim Fleet Assignment minimiert werden, sind vor allem Energiekosten. Diese liegen schon bei einem wöchentlichen Flugplan bei mehreren Millionen Mark.

Flußalgorithmen

Eine graphentheoretische Modellierung des Fleet-Assignment-Problems wird durch einen gerichteten Graphen D=(V,A) gegeben, wobei die Knotenmenge V der Menge der einzelnen Direktflüge entspricht. Zwei Knoten tex2html_wrap_inline3832 werden durch eine gerichtete Kante von u nach v verbunden, wenn es möglich ist, erst den Flug u und anschließend den Flug v mit demselben Flugzeug zu bedienen. Ein Fleet Assignment jbquote217 weist jedem Flug tex2html_wrap_inline3844 einen Flugzeugtyp jbquote217 zu.

Zur Lösung von Fleet-Assignment-Problemen kleinerer Fluggesellschaften wird in der Literatur häufig ganzzahlige lineare Optimierung vorgeschlagen. Die Komplexität des zugrundeliegenden Mehrgüterflußproblems (die Flugzeugtypen werden als Güter aufgefaßt, die durch den Graphen D transportiert werden müssen) läßt dieses Vorgehen jedoch bei größeren Problemen nicht zu. Bei drei oder mehr verschiedenen Flugzeugtypen ist das Problem NP-schwer.

Eine Zuweisung kann aber gefunden werden, wenn die betrachtete Flottenmenge sukzessive in jeweils zwei Untermengen unterteilt wird, und ein Fluß durch den Graphen festlegt, welcher Flug von einer der beiden Mengen bedient wird. Bestehen die einzelnen Untermengen im Verlauf dieser Heuristik nur noch aus je einem Flugzeugtyp, hat man eine Lösung des Fleet-Assignment-Problems gefunden. Unsere Untersuchungen ergaben, daß eine solche Heuristik auf einer mittleren Workstation etwa 30 Minuten benötigt, um ein Fleet Assignment zu bestimmen. Ein gegebenes Assignment kann anschließend mit Austauschheuristiken oder Simulated Annealing mit einigen Stunden Rechenzeit noch nachgebessert werden.

Simulated Annealing

Hierbei betrachtet man nun den Flugplangraphen G=(V,A) mit Flughafenmenge V und Teilflugmenge A. Die Nachbarschaft eines Flugplanes tex2html_wrap_inline3858 (mit tex2html_wrap_inline3860, E Equipmentmenge) ist durch alle Flugpläne F gegeben, die sich auf genau einem gerichteten Kreis tex2html_wrap_inline3866 (mit tex2html_wrap_inline3868 konstant in F bzw. G) in dem darauf eingesetzten Equipment unterscheiden. Die zu minimierende Zielfunktion wird dabei aus der Differenz der Kosten und Erlöse pro Passagier gebildet. Zum Auffinden eines Nachbarn, also zum Finden eines solchen ,,Equipment-Kreises`` in tex2html_wrap_inline3874, verwenden wir eine Depth-First-Search-Strategie.

 figure316
Abbildung: Die Zielfunktion mit einem exponentiellen Cooling Schedule und mit Quenching

Sowohl das Simulated-Annealing-Verfahren als auch unsere auf Flußalgorithmen basierende Heuristik sind leicht parallelisierbar. Simulated Annealing liegt bereits in einer parallelen Version vor. Realisiert wurde dies mit dem Message-Passing-Interface, was größtmögliche Portabilität gewährleistet. Sowohl die sequentiellen Algorithmen als auch das parallele Simulated Annealing liefern bereits gute Resultate. Mit Ergebnissen der weiteren Parallelisierungen rechnen wir planungsgemäß Ende 1996/Anfang 1997.

Die bisher erzielten Ergebnisse zeigen eine Gewinnsteigerung um bis zu 11 Prozent gegenüber der vorhandenen Startlösung, die einem historischen Flugplan der Lufthansa entspricht. Gleichzeitig konnten die Größen der benötigten Teilflotten reduziert werden. Verbesserungen erwarten wir vor allem in der Laufzeit, die derzeit einige Stunden beträgt.

 
 figure326

Abbildung: Ein Ausschnitt aus dem von uns berechneten wöchentlichen Einsatzplan

Tail Assignment

Ist das Fleet Assignment festgelegt, so wird der wöchentliche Einsatzplan der einzelnen Flugzeuge bestimmt. Hierbei müssen wieder neue Restriktionen, insbesondere Wartungsintervalle, beachtet werden. Für jeden Flugzeugtyp ist eine Zahl tex2html_wrap_inline3882 gegeben, die angibt, wieviele einzelne Flugzeuge des Typs t vorhanden sind.

Für ein Fleet Assignment seien tex2html_wrap_inline3886 die durch das Assignment induzierten Subgraphen von D mit tex2html_wrap_inline3890, wenn F(v)=t ist. Für jeden induzierten Subgraphen ist die minimale Anzahl von Ketten, die ihn überdecken, gleich der Anzahl der zu verwendenden Flugzeuge. Diese Zahl läßt sich mit Matchingalgorithmen in polynomieller Zeit berechnen. Ist sie kleiner als tex2html_wrap_inline3882 für alle , so ist das Fleet Assignment unter dem Gesichtspunkt der rotationellen Verknüpfung zulässig. Eine überdeckende Kette entspricht dann dem Wochenplan eines Flugzeugs. Diese Berechnungsphase braucht pro Flugzeugtyp wenige Sekunden Rechenzeit auf einer mittleren Workstation.

Marktdaten

Bereits während des Aufbaus eines Fleet Assignments werden die Erträge überprüft, die sich durch eine Zuweisung erwarten lassen. Hierbei gilt es vor allem, die Passagierzusammensetzung auf Flügen, die von verschiedenen Reiserouten benutzt werden, zu kontrollieren. Eine Reiseroute wird im graphentheoretischen Modell als Hyperkante aufgefaßt, die aus mehreren Knoten, den zugehörigen Flügen, besteht. Diese Kanten werden durch den Ertrag, den ein Passagier auf dieser Route einbringt, bewertet. Auf den Knoten gibt die Kapazität des Flugzeugtyps die Zahl der Passagiere an, die auf diesem Flug transportiert werden können.

Auf den Reiserouten werden jetzt verschiedene Güter, d.h. die Passagiere, möglichst günstig durch das Netzwerk transportiert, so daß für jedes Gut in jedem Knoten die Flußerhaltung gewährleistet bleibt. Die Lösung dieses Mehrgüterflußproblems bestimmt den Wert des Fleet Assignments. Aufgrund der Datenmenge ist vor allem in dieser Berechnungsphase der Einsatz von Höchstleistungsrechnern unerläßlich, auf denen dann parallele Flußtechniken zum Einsatz gebracht werden.


next up previous contents
Next: Parallele Packalgorithmen Up: Anwendungen der kombinatorischen Optimierung Previous: PARALOR - Parallele Algorithmen

Webmaster <www@zpr.uni-koeln.de>, 7. Apr. 1997