Personaleinsatzplanung im Flugbetrieb

In der Luftfahrt stellt der Personalkostenanteil einen erheblichen Teil der Betriebskosten dar. Optimierte Einsatzpläne können daher zu Kostenreduktionen sowie verbesserten Dienstplänen führen.

Das Planungsproblem ist gekennzeichnet von:

• • einem vorgegebenen Flugplan, der aber in der operationellen Planung laufend Änderungen unterworfen ist.
  • einem beschränkt veränderbaren Personalangebot
  • Qualifikationsrestriktionen, z.B. für Flugzeugtypen, Destinationen
  • Kollektivvertraglichen Restriktionen, z.B. Arbeits-/Ruhezeiten, Flugzeiten
  • in der operationellen Planung ist der Planungsvorgang selbst zeitkritisch, da er von vorangehenden Planungen abhängt und ein fixer Fertigstellungszeitpunkt eingehalten werden muß.

Fig. : Ablauf der Personaleinsatzplanung im Flugbetrieb

Pairing-Planning

Aus einem vorgegebenen Flugplan werden im Pairing-Planning sogenannte Pairings erstellt. Ein Pairing ist eine Kombination von einzelnen Flügen (flight legs, flight-segments) zu einer Arbeitsschicht. Ein solches Pairing könnte beispielsweise lauten: VIE-LHR-VIE-HAM-nightstop-VIE.

Restriktionen bei der Erstellung von Pairings sind maximale Dienst- und Flugzeiten. Auch müssen die Flugzeugtypen und die Besatzungskonfiguration aller Flugsegmente eines Pairings übereinstimmen.

Ziel des Pairing-Planning ist eine kostenoptimale Menge von Pairings zu produzieren, welche alle Flugsegmente beinhalten. Kosten eines Pairings sind beispielsweise Hotelkosten für Nightstops, Transferkosten (wenn der Ort des Pairingbeginns/-endes nicht die Homebase ist), Personalkosten (insbesonders für Stehzeiten), Treibstoffkosten (falls Leerflüge erforderlich sind).

Gelöst wird die Pairing-Optimierung meist mittels Set-Covering Verfahren oder lokaler Optimierung.

• Bei den Set-Covering Verfahren werden mittels eines Generators eine große Anzahl von zulässigen Pairings erzeugt und mittels Set-Covering eine Auswahl in der Weise getroffen, daß alle Flüge genau einmal enthalten sind.
• Bei den lokalen Optimierungsverfahren wird von einer zulässigen Ausgangslösung ausgegangen. Eine Untermenge aller Pairings wird nach bestimmten Kriterien herausgegriffen und die darin enthaltenen Flugsegmente in optimaler Weise zu neuen Pairings zusammengestellt.

Beispiel zum Set-Covering Ansatz:

Tab. : Set Partitioning - Pairing Optimierung

Spalten:

• alle zulässigen Pairings (= Kombinationen aus Flight-Legs)

Zeilen:

• Jeder Flight-Leg muß genau einmal geflogen werden
• Für alle p gilt: p Î {0,1}

Ziel:

• Minimiere Gesamtkosten

Pairing-Production

Monat für Monat werden die geplanten Pairing-Zylinder auf die aktuelle Planungsperiode aufgerollt und an den aktuellen Flugplan angepaßt. Die aktualisierten Pairings können nun für das eigentliche Crew-Assignment und die Planung der Flugzeugrotationen herangezogen werden. Als Pairing-Zylinder versteht man alle Pairings einer Woche. Man kann sich einen Pairing-Zylinder als Druckvorlage vorstellen, mit deren Hilfe in der Pairing-Production die Pairings auf die Periodentage abgerollt werden.

Fig. : Ausrollen des Pairingzylinders in der Pairing-Production

Analog dazu müssen auch die Ground-Pairings geplant werden. Ground-Pairings sind beispielsweise wiederkehrende Stand-by Dienste

Produktionsteilung

Im vorangegangenen Abschnitt wurde gezeigt, wie man optimale Schichten (Flight-Pairings) aus der Menge der Flugstrecken (Flight-Legs, Flight-Segments) zusammenstellt. Die Gesamtheit dieser Flight-Pairings und zusätzlicher Ground-Pairings wird als Produktion bezeichnet.

Diese Produktion wird im Crew-Assignment den einzelnen Mitarbeitern zugeordnet. Die Mitarbeiter sind bei den meisten größeren Fluglinien in Teams oder Gruppen organisiert. Aus diesem Grund muß die gesamte Produktion vor dem Assignment auf diese Teams oder Gruppen aufgeteilt werden. Dieser Vorgang wird als Produktionsteilung bezeichnet.

Beispiel LP Ansatz zur Produktionsteilung

Tab.: Set Partitioning - Produktionsteilung

Spalten:

• alle Kombinationen aus Pairings und Teams

Zeilen:

• Jedes Pairing muß genau einem Team zugeordnet werden
• Für jedes Team, an jedem Tag, für jeden Flugzeugtyp muß gelten: Mitarbeiter-Bedarf <= Supply
• Für alle Variablen gilt: PxT Î {0,1}

Ziel:

• Suche zulässige Lösung

Crew-Assignment

Nachdem die Arbeitsschichten (Pairings) erstellt wurden, kann nun die Zuteilung des Personals auf die Pairings beginnen. Dabei müssen auch Urlaube, Schulungen und notwendige Emergency-Training’s berücksichtigt werden. Ziel des Crew-Assignment ist, daß neben den kollektivvertraglichen Bedingungen auch die Präferenzen der Mitarbeiter berücksichtigt werden.

Im Amerikanischen Raum ist eine modifizierte Variante des Crew-Assignment verbreitet: Ohne Berücksichtigung der Mitarbeiter werden Monatsdienstpläne erstellt (LoW “Line of Work”). Die Mitarbeiter können nun, in Reihenfolge ihres Dienstalters, aus den fertigen Monatsdienstplänen einen gewünschten Dienstplan auswählen (Bidline System).

Beispiel LP-Ansatz zum Crew-Assignment

Tab. : Set Partitioning - Crew Assignment

Spalten:

• Für jeden Mitarbeiter (i) alle zulässigen LineOfWork’s (j)

Zeilen:

• Jeder Mitarbeiter muß genau eine LineOfWork erhalten
• Jedes Pairing muß genau die benötigte Anzahl an Mitarbeitern erhalten
• Für alle x(i,j) gilt: x Î {0,1}

Ziel:

• Suche zulässige Lösung, maximiere Bewertung der LoW’s

Die Literatur zum Crew-Assignment Problem ist zur Zeit noch sehr spärlich. Dies liegt einerseits am Problemumfang, welcher es erst seit kurzer Zeit lösbar machte. Andererseits an den vielschichtigen formalen und informellen Regelungen zur Dienstplanerstellung.

In meiner Dissertation wurde diesem Bereich breiten Raum gewidmet und dabei folgende Fragestellungen bearbeitet:

• Wie kann man Mitarbeiterwünsche formalisieren, um sie beim Assignment berücksichtigen zu können (Preassignments, Präferenzprofile, etc.)
• Welche Lösungsverfahren können angewandt werden. (Set-Partitioning, implizite Enumeration, Graphentheoretische Verfahren, Heuristiken, etc.)
• Wie können Erweiterungen des Standardmodells modelliert werden. (Team-Assignment)

Literatur (Auswahl)

[Cir93] Ciriani, Tito A.; Leachman, Robert, “Optimization in Industry: Mathematical Programming and Modelling Techniques in Practice”,
1. Auflage, 1993, John Wiley & Sons Ltd, ISBN 0-471-93492-5

[Hil95] Hillier, Frederick S.; Lieberman, Gerald J.
“Introduction to Operations Research”, 6. Auflage, 1995
McGraw-Hill, ISBN 0-07-113989-3

[Law87] Lawrence, David
“Genetic algorithms and simulated annealing”, 1987, ISBN 0.273-08771-1

[Neu93] Neumann; Morlock, “Operation Research”, 1993
Verlag Hanser, München, ISBN 2-446-15771-9

[Bix92] Bixby, Robert E.; Gregory, John W.; Lustig, Irvin J.; Marsten, Roy E.; Shanno, David F.
“Very large-scale linear programming: a case study in combining interior point and simplex methods”, Operations Research, Vol. 40, September-Oktober 1992, Seite 885ff

[Gra93] Graves, Glenn W.; McBride, Richard D.; Gershkoff, Ira; Anderson, Diane; Mahidhara, Deepa, “Flight Crew Scheduling”
Management Science, Vol. 39, No. 6, Juni 1993, Seite 736ff

[Hof93] Hoffman, Karla L.; Padberg Manfred, “Solving Airline Crew Scheduling Problems by Branch-and-Cut”, Management Science, Vol. 39, No. 6, Juni 1993, Seite 657ff

[Lau96] Lau, Hoong Chuin, “On the complexity of manpower shift scheduling”
Computers and Operations Research, 1996, Vol 23, No. 1, Seite 93-102

[Rya92] Ryan, D. M., “The Solution of Massive Generalized Set Partitioning Problems in Aircrew Rostering”, Journal of the Operations Research Society, Vol. 43, No. 5, 1992, Seite 459ff

[Wre95] Wren, Anthony; Wren, David O., “A genetic algorithm for public transport driver scheduling”, Computers and Operations Research, 1995, Vol 22, No. 1, Seite 101-110

[Koe95] Johannes König, “Flexible Personaleinsatzplanung: Methoden des Personalscheduling am Beispiel der Personaleinsatzplanung bei British-Airways Wien”
Diplomarbeit, Institut für Operations Research, TU-Wien, 1995