Skip to content

Combinatorial Optimization: The NP-Hard Nature of Crew Scheduling

To understand why the Jeppesen CARMEN system and the Rave language exist, one must first understand the sheer mathematical scale of airline crew scheduling. Crew costs represent the second major cost item for airline companies after fuel costs. This financial reality makes the optimization of crew costs incredibly attractive, but the scale of the problem is mathematically NP-Hard.

1. The Optimization Problem

To manage the massive computational load, the airline crew scheduling problem is usually solved in two consecutive steps: crew pairing and rostering.

The primary optimization problem solved in the crew pairing step is finding the least costly set of pairings that covers every flight in the given network. A pairing is defined as a sequence of consecutive flight legs that starts from and ends at the base airport of the airline company, and it is flown by a single crew.

graph TD
    A[Flight Network Timetable] --> B{Combinatorial Explosion}
    B --> C[Millions of Legal Pairings]
    C --> D[Optimization Solver]
    D --> E[Optimal Set of Pairings]

    style B fill:#e53e3e,stroke:#9b2c2c,color:#fff

2. Why is it NP-Hard?

If an airline has 1,000 flights a day, the number of mathematical ways to combine those flights into legal 3-day or 4-day trips is astronomical.

  • The Set Covering Problem: The solver must select a subset of pairings such that every flight in the timetable is covered exactly once (or at least once, if deadheading is permitted).
  • Deadheading: Transporting crew on flights as passengers (known as deadheading) has major impacts on crew costs and significantly multiplies the number of possible routing combinations.

3. The Role of Rave

Because it is impossible to evaluate every combination upfront, an optimization engine generates sequences of flights and then for each sequence generated, it checks the feasibility with respect to these rules. Rave provides the decoupled, high-level language framework required for describing the feasibility and cost calculation rules that the engine queries millions of times per second.