Crew-Pairing

Das Problem des Crew-Pairings (CPP) ist ein kombinatorisches Optimierungsproblem des Operations Research und der theoretischen Informatik. Die Aufgabe besteht – als erste Phase des Crew-Schedulings – aus der Erstellung von kostengünstigen Flugfolgen (Pairing), die von jeweils einer Crew an möglichst einem Arbeitstag bewältigt werden können. Dabei müssen tarifrechtliche und gesetzliche Restriktionen eingehalten werden. In der anschließenden Phase, dem Crew-Rostering, wird jedem Pairing eine Crew zugeordnet.

Da die Personalkosten des fliegenden Personals nach den Kerosinkosten den zweitgrößten Anteil der Gesamtkosten von Fluggesellschaften einnehmen, ist beim Crew-Pairing ein großes Einsparpotential gegeben. Lösungsverfahren werden deshalb intensiv im Bereich der Optimierung erforscht. Komplexitätstheoretisch gehört das CPP allerdings zur Klasse der NP-äquivalenten Probleme, da mit größer werdendem Flugplan die Komplexität stark ansteigt.