Rahmenbedingungen

Dieses Projekt wird im Rahmen des Programms Mathematische Lösungen von Aufgabenstellungen aus Industrie und Wirtschaft vom Bundesministerium für Bildung, Forschung und Technologie (BMBF) gefördert. Es ist ein Verbundprojekt, das zusammen mit der Lufthansa Systems GmbH, Frankfurt, durchgeführt wird.

Aufgabenstellung

 Die Aufgaben- undEinsatzplanung einer Fluggesellschaft besteht aus zahlreichen, zum Teil ineinandergreifenden Planungsschritten. So muß z.B. der Flugplan, wie er später dem Kunden präsentiert wird, erstellt werden, also etwa die Entscheidung ``dienstags startet um 9:15 Uhr ein Flug von Frankfurt (FRA) nach New York (JFK)'' getroffen werden. Ein solcher durch Datum, Startzeit, Landezeit, Start- und Zielflughafen bestimmter Direktflug ist ein sogenanntes Leg. Hernach muß jedem Leg ein Flugzeugtyp (z.B. Boeing 747) aus der vorhandenen Flotte zugeordnet werden, d.h., die legs müssen auf die Teilflotten aufgeteilt werden (Fleet Assignment). Ein wichtiger Aspekt ist ferner das Crew Scheduling, also das Zusammenstellen von Crews und deren Einteilung für die einzelnen Legs.

Die Rotationsplanung erfolgt nach dem Fleet Assignment. Gegeben ist also eine Menge von Legs (nämlich die Teilmenge aller Legs, die mit einem bestimmten vorgegebenen Flugzeugtyp geflogen werden sollen), und die Aufgabe ist es, nun Routen für die einzelnen konkreten Flugzeuge aus dieser Teilflotte zu bestimmen, so daß alle jene Legs bedient werden. Anders ausgedrückt muß für jeden Flughafen und für jedes dort ankommende Leg festgelegt werden, mit welchem (später) ausgehenden Leg es verknüpft werden soll.

In unserem Projekt bemühen wir uns darum, solche Rotationspläne zu berechnen, die nach vorgegebenen Gesichtspunkten möglichst gut sind. Dabei mißt man die Güte eines Rotationsplanes z.B. daran, wie lange Flugzeuge zwischen Start und Landung am Boden verbringen, weil kurze Bodenzeiten die Verspätungsgefahr erhöhen.  Kriterien von dieser Art, die nur die Verknüfung zweier Legs an einem Flughafen betreffen, sind leicht mathematisch zu modellieren und führen im wesentlichen zu einem kombinatorischen Optimierungsproblem, das als Lineares Zuordnungsproblem bekannt ist, und sehr effizient lösbar ist. Jedoch gibt es eine Reihe von weiteren Anforderungen an gute Rotationspläne, die z.B. mehrere aufeinander folgende Legs einer Flugzeugroute  betreffen. Diese zusätzlichen Anforderungen mathematisch zu modellieren und Optimierungsverfahren für die aufgestellten Modelle zu entwickeln und zu implementieren, ist die Hauptaufgabe in diesem Projekt.